Multiple-resource periodic scheduling problem: how much fairness is necessary

The Pfair algorithms are optimal for independent peri-odic real-time tasks executing on a multiple-resource sys-tem, 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 (BF), 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 utiliza-tion. Moreover, by making scheduling decisions at period boundaries, BF effectively reduces the number of schedul-ing 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 dramati-cally (e.g., upto 75 % in our experiments) and thus reduce the overall scheduling overhead, which is especially impor-tant for on-line scheduling. 1