Fair scheduling of real-time tasks on multiprocessors

Abstract

There has been much recent interest in fair scheduling algorithms for real-time multiprocessor systems. The roots of much of the research on this topic can be traced back to the seminal work of Baruah et al. on Proportionate fairness (Pfairness) [6]. This work proved that the problem of optimally scheduling periodic tasks on multiprocessors could be solved on-line in polynomial time by using Pfair scheduling algorithms. Pfair scheduling differs from more conventional real-time scheduling approaches in that tasks are explicitly required to execute at steady rates. In most realtime scheduling disciplines, the notion of a rate is implicit. For example, in a periodic schedule, a task T executes at a rate defined by its required utilization (T.e/T.p) over large intervals. However, T's execution rate over short intervals, e.g., individual periods, may vary significantly. Hence, the notion of a rate under the periodic task model is a bit inexact. Under Pfair scheduling, each task is executed...