Deadline Fair Scheduling: Bridging the theory and practice of proportionate fair scheduling in multiprocessor systems

A. Chandra, M. Adler, P. Shenoy

Research output: Contribution to journalConference articlepeer-review

45 Scopus citations


In this paper, we present Deadline Fair Scheduling (DFS), a proportionate-fair CPU scheduling algorithm for multiprocessor servers. A particular focus of our work is to investigate practical issues in instantiating proportionate-fair (p-fair) schedulers into conventional operating systems. We show via a simulation study that characteristics of conventional operating systems such as the asynchrony in scheduling multiple processors, frequent arrivals and departures of tasks, and variable quantum durations can cause proportionate-fair schedulers to become non-work-conserving. To overcome this drawback, we combine DFS with an auxiliary work-conserving scheduler to ensure work-conserving behavior at all times. We then propose techniques to account for processor affinities while scheduling tasks in multiprocessor environments. We implement the resulting scheduler in the Linux kernel and evaluate its performance using various applications and benchmarks. Our experimental results show that DFS can achieve proportionate allocation, performance isolation and work-conserving behavior at the expense of a small increase in the scheduling overhead. We conclude that practical considerations such as work-conserving behavior and processor affinities when incorporated into a P-fair scheduler such as DFS can result in a practical approach for scheduling tasks in a multiprocessor operating system.

Original languageEnglish (US)
Pages (from-to)3-14
Number of pages12
JournalReal-Time Technology and Applications - Proceedings
StatePublished - 2001
Event7th Real-Time Technology and Applications Symposium (RTAS 2001) - Taipei, Taiwan, Province of China
Duration: May 30 2001Jun 1 2001


Dive into the research topics of 'Deadline Fair Scheduling: Bridging the theory and practice of proportionate fair scheduling in multiprocessor systems'. Together they form a unique fingerprint.

Cite this