|
USENIX 2001 Abstract
Virtual-Time Round-Robin: An O(1) Proportional Share Scheduler
Jason Nieh, Chris Vaill, and Hua Zhong, Columbia University
Abstract
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.
