Generalized Multiprocessor Sharing (GMS) based Scheduling Algorithms

Table of Contents

Generalized Multiprocessor Sharing (GMS) is an idealized proportional-share scheduling algorithm for symmetric multiprocessor systems.

Surplus Fair Scheduling (SFS) [1] is a practical instantiation of GMS which provides proportionate allocation and performance isolation to applications.

Deadline Fair Scheduling (DFS) [2] is a proportional-share multiprocessor scheduler based on the notion of P-fairness, which is a stricter form of proportional-share fairness.

Start-time Fair Queuing (SFQ) [3] is a uniprocessor proportional-share scheduling algorithm based on GPS (Generalized Processor Sharing). It has been implemented as a multiprocessor algorithm for comparison purposes.

These algorithms have been implemented in the Linux kernel version 2.2.14.

People

GMS-based algorithms have been designed and implemented in the Laboratory for Advanced System Software at the University of Massachusetts. The following people are involved in this development:

References

[1] Surplus Fair Scheduling: A Proportional-Share CPU Scheduling Algorithm for Symmetric Multiprocessors,
Abhishek Chandra, Micah Adler, Pawan Goyal and Prashant Shenoy.
Proceedings of the Fourth Symposium on Operating System Design and Implementation (OSDI 2000), San Diego, CA, October 2000.

[2] Deadline Fair Scheduling: Bridging the Theory and Practice of Proportionate-Fair Scheduling in Multiprocessor Servers,
Abhishek Chandra, Micah Adler and Prashant Shenoy.
Proceedings of the 21st IEEE Real-Time Technology and Applications Symposium (RTAS 2001), Taipei, Taiwan ROC, May 2001.

[3] A Hierarchical CPU Scheduler for Multimedia Operating Systems
P. Goyal and X. Guo and H.M. Vin
Proceedings of 2nd Symposium on Operating System Design and Implementation (OSDI'96), Seattle, WA, pages 107-122, October 1996.


Download Software

We have implemented Surplus Fair Scheduling (SFS) [1] and Deadline Fair Scheduling (DFS) [2] scheduling algorithm in the 2.2.14 Linux kernel. In addition, we have also implemented a non-hierarchical version of Start-time Fair Queueing (SFQ) [3] in the same kernel for comparison purposes. The schedulers were developed and tested on RedHat Linux 6.0. While we believe the code should work on othere versions of Linux, we haven't verified it due to resource constraints.

Our implementation is open-source and is freely downloadable under Gnu General Public License.

The latest version is 2.2.14 (based on the 2.2.14 kernel). You can download the entire source code from here (16MB gzip'd). Alternatively, a patch for the 2.2.14 kernel is available here (79KB).

Release notes are available here.


Abhishek Chandra
Last modified: Wed Aug 21 11:44:42 EDT 2002