Speaker: David Steere, Oregon Graduate Institute
Date: February 22, 1999
A Feedback-driven Proportion Allocator for Real-Rate Scheduling
In this talk I 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 applications that do not need reservations. 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. We have implemented this scheduler in Linux, and used it to schedule a mixed workload including gcc, an adaptive multimedia player, and the X server. We hope to port it to NT to experiment with more common work environments.
David Steere has been working in operating systems and distributed systems for over 10 years, and is or has been a member of the Quasar, Coda, Recoverable Virtual Memory (rvm), and Odyssey projects. His current interests lie in adaptive system software: systems that adjust their behaviors or policies in response to changes in environment, resource availability, and load. He is currently working on adaptive operating systems for mobile computers and multimedia applications, and on advancing the state of the art of software controllers of physical systems. Dr. Steere is an assistant research professor in the System Software Laboratory at the Oregon Graduate Institute. He received his Ph.D. from Carnegie Mellon University under Professor M. Satyanarayanan.