An Optimal Boundary-Fair Scheduling Algorithm for Multiprocessor Real-Time Systems




Zhu, Dakai
Qi, Xuan
Mossé, Daniel
Melhem, Rami

Journal Title

Journal ISSN

Volume Title


UTSA Department of Computer Science


Although the scheduling problem for multiprocessor real-time systems has been studied for decades, it is still an evolving research field with many open problems. In this work, focusing on periodic real-time tasks, we propose a novel optimal scheduling algorithm, namely boundary fair (Bfair), which follows the same line of research as the well-known Pfair scheduling algorithms and can also achieve full system utilization. However, different from the Pfair algorithms that make scheduling decisions at every time unit to enforce proportional progress (i.e., fairness) for each task, Bfair makes scheduling decisions and enforces fairness to tasks only at tasks’ period boundaries. The correctness of the Bfair algorithm to meet the deadlines of all tasks’ instances is formally proved. The performance of Bfair is evaluated through extensive simulations. The results show that, compared to that of the Pfair algorithms, Bfair can significantly reduces the number of scheduling points (by upto 94%) and the time overhead of Bfair is comparable to that of the most efficient Pfair algorithm (i.e., P D^2). Moreover, by aggregating the time allocation of tasks for the time interval between consecutive period boundaries, the resulting Bfair schedule needs dramatically reduced number of context switches and task migrations, as low as 18% and 15%, respectively, when compared to those of Pfair schedules.


A preliminary version of this paper appeared in IEEE RTSS 2003.




Computer Science