Colloquium Details
Resource Allocation Using Controls: A Feedback-Driven Proportion Allocator for Real-Rate Scheduling
| Authors: | David Steere Dept. of Computer Science and Engineering, Oregon Graduate Institute Molly Shor Dept. of Electrical and Computer Engineering, Oregon State University |
|---|---|
| Date: | January 27, 2000 |
| Time: | 16:00 |
| Location: | 220 Deschutes |
Abstract
A standard problem in OS resource management is the scheduling of resources to individual program threads. The standard scheme, based on "priority", may result in high variance in the amount of cycles allocated to a thread and accidental priority inversion and starvation. High variance in allocation can result in unacceptable performance in video and other real-rate applications. Priority inversion and starvation may result in denial-of-service attacks.
Steere and Shor will present an alternative to priority-based scheduling - "real-rate scheduling" - which has been developed and demonstrated at Oregon Graduate Institute. Real-rate scheduling allocates to each thread a percentage of CPU cycles over a period of time. Feedback controllers for real-rate applications adaptively assign the proportion and period allocations based on application progress. Applications with known requirements, such as isochronous software devices, can bypass the adaptive scheduler by specifying their desired proportion and/or period. This approach 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.
Steere, et al., have implemented real-rate scheduling in a Linux environment and used it to schedule a mixed workload including gcc, an adaptive multimedia player, and the X server. They are working to implement it in NT.
Molly Shor is working with Steere and Walpole on controller design and analysis.
Biography
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 DISC systems research center at the Oregon Graduate Institute. He received his Ph.D. from Carnegie Mellon University under Professor M. Satyanarayanan.
Molly Shor received her A.B. from Harvard University in 1984, and her M.S. and Ph.D. degrees from University of Illinois at Urbana-Champaign in 1987 and 1992. She joined Oregon State University in 1992. Her research specialty is control systems. She also has interests in other applications of dynamical system modeling and analysis.