GR3: O(1) Proportional Share Resource Management

Network Computing Laboratory, Columbia University

GR3: O(1) PROPORTIONAL SHARE RESOURCE MANAGEMENT

Proportional share resource management provides a flexible and useful abstraction for multiplexing time-shared resources. We introduce a family of round-robin proportional share schedulers that combine accurate proportional fairness scheduling behavior with O(1) scheduling overhead. Group Ratio Round-Robin (GR3) is one such scheduler we have developed that uses a novel client grouping strategy to organize clients into groups of similar processor allocations which can be more easily scheduled. Using this grouping strategy, GR3 combines the benefits of low overhead round-robin execution with a novel ratio-based scheduling algorithm. We have analyzed the behavior of GR3 ane measured its performance against other schedulers commonly used in research and practice, including the standard Linux scheduler, Weighted Fair Queueing, and Smoothed Round-Robin. Our experimental results demonstrate that GR3 can provide much lower scheduling overhead and much better scheduling accuracy in practice than these other approaches.

More Information:

Bogdan Caprita, Jason Nieh, and Clifford Stein, "Grouped Distributed Queues: Distributed Queue, Proportional Share Multiprocessor Scheduling", Proceedings of the Twenty-fifth Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2006), Denver, CO, July 23-26, 2006, pp. 72-81.
Bogdan Caprita, Jason Nieh, and Clifford Stein, "Grouped Distributed Queues: Distributed Queue, Proportional Share Multiprocessor Scheduling", Technical Report CUCS-004-06, Department of Computer Science, Columbia University, February 2006.
Bogdan Caprita, Jason Nieh, and Wong Chun Chan, "Group Round Robin: Improving the Fairness and Complexity of Packet Scheduling", Proceedings of the First ACM/IEEE Symposium on Architectures for Networking and Communications Systems (ANCS 2005), Princeton, NJ, October 26-28, 2005, pp. 29-40.
Bogdan Caprita, "Grouped Distributed Queues: Distributed Queue, Proportional Share Multiprocessor Scheduling", M.S. Thesis, Department of Computer Science, Columbia University, May 2005.
Bogdan Caprita, Wong Chun Chan, Jason Nieh, Clifford Stein, and Haoqiang Zheng, "Group Ratio Round-Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems", Proceedings of the 2005 USENIX Annual Technical Conference, Anaheim, CA, April 10-15, 2005, pp. 337-352.
Shailabh Nagar, Rik Van Riel, Hubertus Franke, Chandra Seetharaman, Vivek Kashyap, and Haoqiang Zheng, "Improve Linux Resource Control Using CKRM", Ottawa Linux Symposium 2004 (OLS 04), Ottawa, Canada, July 21-24, 2004.
Bogdan Caprita, Wong Chun Chan, Jason Nieh, Clifford Stein, and Haoqiang Zheng, "Group Ratio Round-Robin: O(1) Proportional Share Scheduling for Uniprocessor and Multiprocessor Systems", Technical Report CUCS-028-04, Department of Computer Science, Columbia University, July 2004.
Wong Chun Chan, "Group Ratio Round-Robin: An O(1) Proportional Share Scheduler", M.S. Thesis, Department of Computer Science, Columbia University, June 2004.
Hubertus Franke, Shailabh Nagar, Chandra Seetharaman, Vivek Kashyap, Haoqiang Zheng, and Jiantao Kong, "Enabling Autonomic Workload Management in Linux", Proceedings of the First International Conference on Autonomic Computing (ICAC 2004), New York, NY, May 17-19, 2004, pp. 314-315.
Haoqiang Zheng and Jason Nieh, "SWAP: A Scheduler With Automatic Process Dependency Detection", Proceedings of the First USENIX/ACM Symposium on Networked Systems Design and Implementation (NSDI 2004), San Francisco, CA, March 29-31, 2004, pp. 183-196.
Bogdan Caprita, Wong Chun Chan, and Jason Nieh, "Group Round Robin: Improving the Fairness and Complexity of Packet Scheduling", Technical Report CUCS-018-03, Department of Computer Science, Columbia University, June 2003.
Wong Chun Chan and Jason Nieh, "Group Ratio Round-Robin: An O(1) Proportional Share Scheduler", Technical Report CUCS-012-03, Department of Computer Science, Columbia University, April 2003.
Haoqiang Zheng and Jason Nieh, "SWAP: A Scheduler With Automatic Process Dependency Detection", Technical Report CUCS-005-03, Department of Computer Science, Columbia University, April 2003.
Jason Nieh, Chris Vaill, and Hua Zhong, "Virtual-Time Round-Robin: An O(1) Proportional Share Scheduler", Proceedings of the 2001 USENIX Annual Technical Conference, Boston, MA, June 25-30, 2001, pp. 245-259.
Jason Nieh, Chris Vaill, and Hua Zhong, "Virtual-Time Round-Robin: An O(1) Proportional Share Scheduler", NMADS-3: NYC Metro Area Distributed Systems, New York, NY, April 13, 2001.