This project was supported in part by DARPA contracts/grants N66001-97-C-8522, N66001-97-C-8523, and F19628-95-C-0193, and by Tektronix, Inc. and Intel Corporation.
Operating systems (Computers) -- Resource allocation, Adaptive computing systems, Linux
In this paper we propose changing the decades-old practice of allocating CPU to threads based on priority to a scheme based on proportion and period. Our scheme allocates to each thread a percentage of CPU cycles over a period of time, and uses a feedback-based adaptive scheduler to assign automatically both proportion and period. Applications with known requirements, such as isochronous software devices, can bypass the adaptive scheduler by specifying their desired proportion and/or period. As a result, our scheme provides reservations to applications that need them, and the benefits of proportion and period to those that do not. Adaptive scheduling using proportion and period has several distinct benefits over either fixed or adaptive priority based schemes: finer grain control of allocation, lower variance in the amount of cycles allocated to a thread, and avoidance of accidental priority inversion and starvation, including defense against denial-of-service attacks. This paper describes our design of an adaptive controller and proportion-period scheduler, its implementation in Linux, and presents experimental validation of our approach.
"A Feedback-driven Proportion Allocator for Real-Rate Scheduling" David C. Steere, Ashvin Goel, Joshua Gruenberg, Dylan McNamee, Calton Pu, and Jonathan Walpole, Oregon Graduate Institute CSE Technical Report 98-014, September 1998.
Oregon Graduate Institute CSE Technical Report 98-014, September 1998.
Subsequently published in the Proceedings of the 3rd Symposium on Operating Systems Design and Implementation, New Orleans, Louisiana, February, 1999 (OSDI. Vol. 99, pp. 145-158).