Abstract: We consider Pfair scheduling in real-time multiprocessor systems. Under Pfair scheduling, tasks are required to execute at steady rates. The most efficient Pfair scheduling algorithm proposed to date is an algorithm called PD developed by Baruah and colleagues. PD schedules periodic tasks by breaking them into quantum-length subtasks that are subject to intermediate deadlines. Ties among subtasks with the same intermediate deadline are broken by inspecting four tie-break parameters. PD improved upon a previous algorithm called PF, which relies on a less-efficient procedure for resolving ties.
In this paper, we show that the priority definition used in PD can be simplified to consist of one intermediate deadline and only two tie-break parameters. We also show that further simplifications are, in general, unlikely. In particular, we show if either tie-break parameter is eliminated, then there exists a feasible task set that is not correctly scheduled. Although both tie-breaks are needed in general, for the important special case of a two-processor system, we show that no tie-breaking information is required. In proving that our simplified version of PD is correct, we use an inductive "swapping" argument in which aschedule produced by an optimal scheduler is converted into one allowed by our priority definition by systematically interchanging pairs of subtasks. This proof reveals many fundamental properties inherent to Pfair scheduling.