Published Articles >> Table of Contents >> Abstract

24th IEEE International Real-Time Systems Symposium (RTSS'03)   p. 142
Multiple-Resource Periodic Scheduling Problem: how much fairness is necessary?
Dakai Zhu, University of Pittsburgh, PA
Daniel Mosse, University of Pittsburgh, PA
Rami Melhem, University of Pittsburgh, PA

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/REAL.2003.1253262
Send link to a friend

Abstract
The Pfair algorithms are optimal for independent periodic real-time tasks executing on a multiple-resource system, however, they incur a high scheduling overhead by making scheduling decisions in every time unit to enforce proportional progress for each task. In this paper, we will propose a novel scheduling algorithm, boundary fair (), which makes scheduling decisions and enforces fairness to tasks only at period boundaries. The BF algorithm is also optimal in the sense that it achieves 100% system utilization. Moreover, by making scheduling decisions at period boundaries, BF effectively reduces the number of scheduling points. Theoretically, the BF algorithm has the same complexity as that of the Pfair algorithms. But, in practice, it could reduce the number of scheduling points dramatically (e.g., upto 75% in our experiments) and thus reduce the overall scheduling overhead, which is especially important for on-line scheduling.
Back to Top Additional Information
Citation:  Dakai Zhu, Daniel Mosse, Rami Melhem, "Multiple-Resource Periodic Scheduling Problem: how much fairness is necessary?," rtss, p. 142,  24th IEEE International Real-Time Systems Symposium (RTSS'03),  2003