|
USENIX 2005 Annual Technical Conference, General Track — Abstract
Pp. 337–352 of the Proceedings
Group Ratio Round-Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems
Bogdan Caprita, Wong Chun Chan, Jason Nieh, Clifford Stein, and Haoqiang Zheng, Columbia University
Abstract
We present Group Ratio Round-Robin (GR3), the first proportional
share scheduler that combines accurate proportional
fairness scheduling behavior with O(1) scheduling
overhead on both uniprocessor and multiprocessor systems.
GR3 uses a simple grouping strategy to organize clients
into groups of similar processor allocations which can be
more easily scheduled. Using this strategy, GR3 combines
the benefits of low overhead round-robin execution with a
novel ratio-based scheduling algorithm. GR3 introduces a
novel frontlog mechanism and weight readjustment algorithm
to operate effectively on multiprocessors. GR3 provides
fairness within a constant factor of the ideal generalized
processor sharing model for client weights with a fixed
upper bound and preserves its fairness properties on multiprocessor
systems. We have implemented GR3 in Linux
and measured its performance. Our experimental results
show that GR3 provides much lower scheduling overhead
and much better scheduling accuracy than other schedulers
commonly used in research and practice.
- View the full text of this paper in HTML and PDF.
Until April 2006, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2005 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.
|
Need help? Use our Contacts page.
