Virtual-Time Round-Robin: An O(1) Proportional Share Scheduler

Jason Nieh, Chris Vaill, Hua Zhong

Proceedings of the 2001 USENIX Annual Technical Conference, Boston, MA, June 25-30, 2001, pp. 245-259


Proportional share resource management provides a flexible and useful abstraction for multiplexing time- shared resources. However, previous proportional share mechanisms have either weak proportional sharing ac- curacy or high scheduling overhead. We present Virtual- Time Round-Robin (VTRR), a proportional share sched- uler that can provide good proportional sharing accuracy with O(1) scheduling overhead. VTRR achieves this by combining the benefits of fair queueing algorithms with a round-robin scheduling mechanism. Unlike many other schedulers, VTRR is simple to implement. We have implemented a VTRR CPU scheduler in Linux in less than 100 lines of code. Our performance re- sults demonstrate that VTRR provides accurate propor- tional share allocation with constant, sub-microsecond scheduling overhead. The scheduling overhead using VTRR is two orders of magnitude less than the standard Linux scheduler for large numbers of clients.



Columbia University Department of Computer Science