Hierarchical scheduling for symmetric multiprocessors

Abhishek Chandra, Prashant Shenoy

Research output: Contribution to journalArticlepeer-review

23 Scopus citations

Abstract

Hierarchical scheduling has been proposed as a scheduling technique to achieve aggregate resource partitioning among related groups of threads and applications in uniprocessor and packet scheduling environments. Existing hierarchical schedulers are not easily extensible to multiprocessor environments because (i) they do not incorporate the inherent parallelism of a multiprocessor system while resource partitioning, and (ii) they can result in unbounded unfairness or starvation if applied to a multiprocessor system in a naive manner. In this paper, we present a novel hierarchical scheduling algorithm designed specifically for multiprocessor environments that overcomes the limitations of existing algorithms in several ways. We present a generalized weight feasibility constraint that specifies the limit on the achievable CPU bandwidth partitioning in a multiprocessor hierarchical framework, and propose a hierarchical weight readjustment algorithm designed to transparently satisfy this feasibility constraint. We then present hierarchical multiprocessor scheduling (H-SMP), a hierarchical CPU scheduling algorithm designed for a symmetric multiprocessor (SMP) platform. The novelty of this algorithm lies in its combination of space- and time-multiplexing to achieve desired bandwidth partition among the nodes of the hierarchical scheduling tree. This algorithm is also characterized by its ability to incorporate existing proportional-share algorithms as auxiliary schedulers to achieve efficient hierarchical CPU partitioning. We evaluate the properties of this algorithm using hierarchical surplus fair scheduling (H-SFS), an instantiation of H-SMP that employs surplus fair scheduling (SFS) as an auxiliary algorithm. This evaluation is carried out through a simulation study that shows that H-SFS provides better fairness properties in multiprocessor environments as compared to existing algorithms and their naive extensions.

Original languageEnglish (US)
Pages (from-to)418-431
Number of pages14
JournalIEEE Transactions on Parallel and Distributed Systems
Volume19
Issue number3
DOIs
StatePublished - Mar 2008

Keywords

  • Hierarchical design
  • Multiprocessor Systems
  • Scheduling

Fingerprint

Dive into the research topics of 'Hierarchical scheduling for symmetric multiprocessors'. Together they form a unique fingerprint.

Cite this