Optimal Scheduling Algorithms for Parallel Real-Time Systems

Problem Description: The real-time system consists m resources and n periodic tasks, G = {T1, , Tn }, in which each task Ti = (ci, pi) is characterized by its execution requirement ci and its period pi. The deadline for each task instance is the task's next period. ci and pi are integer multiples of a system unit time. The weight (or utilization) for task Ti is defined as wi = ci/pi, and the system utilization is the summation of all tasks' utilizations U = Swi (U m). The problem is to design a scheduling algorithm with the following constraints: (C1). A resource can only be allocated to one task at any time, that is, resources can not be shared concurrently; (C2) A task can only be allocated at most one resource at any time, that is, tasks are not parallel and thus cannot occupy more than one resource at any time.

Current Solutions: An optimal scheduling algorithm (Pfair) [1] has been proposed. But, the Pfair algorithm incurs a very high scheduling overhead by making scheduling decision for every time unit to enforce strict proportional progress for each task at any time unit, which prevents it from being employed in practice, as many of its variants. To reduce the scheduling overhead, notice that deadline misses happen only at the end of tasks periods, we proposed a novel idea of boundary-fair (Bfair) scheduling [2], which makes scheduling decision at a period boundary to ensure that all tasks with deadline as next period boundary will finish on time, and to properly allocate resources to the rest tasks such that they can meet their deadlines in the future. A schedule Bfair iff any task Ti is either allocated wi*tb or wi*tb units at any period boundary time tb.

Bfair algorithm is also optimal in the sense that it can achieve full system utilization. And by making scheduling decisions at periodic boundaries, it effectively reduces the number of scheduling points as well as context switches. We showed that Bfair algorithm has the same complexity as that of Pfair algorithm for each scheduling point, but with fewer scheduling points. Thus, it will reduce the overall scheduling overhead compared to Pfair algorithm, which is especially important when they are used on-line. We believe it will attract researchers' attention from Pfair to boundary-fairness.

Consider an example task set that has 6 tasks T1=(2, 5), T2=(3, 15), T3=(3, 15), T4=(2, 6), T5=(20, 30), T6=(6, 30). Here, LCM = 30, Swi = 2. The proportional-fair schedule generated by Pfair scheduling algorithm in [1] is shown in Fig. 1 (the dotted bold lines are period boundaries) with 30 scheduling points and 60 context switches. The boundary-fair schedule generated by Bfair scheduling algorithm in [2] is shown in Fig. 2 with only 11 scheduling points and 46 context switches.

Can we do better than the schedule above? Yes. If tasks are in the order of T1, T2, T3, T6, T4, T5, the first four tasks could be scheduled on one resource while the last two task were scheduled on another resource. We can get the BETTER scheduling as shown in Fig. 3 where there are only 29 context switches (considering scheduling points effect). However the ordering of tasks is NP-hard.

Future work: Exploring ideas to further reduce the scheduling overhead and incorporating other issues in parallel scheduling (such as synchronization and migration) would be the next step in this direction. Also, a real implementation of the algorithm and the performance comparison with previous efficient Pfair variants will also be pursued. A comprehensive list of publication on the fairness scheduling algorithms can be found from the website of Prof. James H. Anderson (University of North Carolina at Chapel Hill).

[1]   S. K. Baruah, N. K. Cohen, C. G. Plaxton, and D. A. Varel. Proportionate progress: A notion of fairness in  resource allocation. Algorithmica, 15(6):600625, 1996

[2]   D. Zhu, D. Mosse and R. Melhem, Periodic Scheduling Problem for Multi-Processor Real-Time Systems: how much fairness is necessary? IEEE Real-Time System Symposium 2003

Last Updated: 2006-09-10 11:54:47 PM