Check out the new USENIX Web site.

Home About USENIX Events Membership Publications Students
USENIX 2001 Abstract

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

Jason Nieh, Chris Vaill, and Hua Zhong, Columbia University


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 accuracy or high scheduling overhead. We present Virtual-Time Round-Robin (VTRR), a proportional share scheduler 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 results demonstrate that VTRR provides accurate proportional 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.
  • View the full text of this paper in HTML and PDF.
    The Proceedings are published as a collective work, © 2001 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.

  • If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.

  • To become a USENIX Member, please see our Membership Information.
?Need help? Use our Contacts page.

Last changed: 3 Jan. 2002 ml
Technical Program
USENIX 2001 Home