Scheduling Algorithms For Real-time Multiprocessor Systems

Scheduling Algorithms for Real-Time Multiprocessor Systems A real-time system is typically composed of several tasks with timing constraints. This timing constraint of an operation is usually specified using a deadline, which corresponds to the time by which that operation must complete. Thus a proper method is essential to ensure that all activities are able to meet their timing constraints. Selecting appropriate methods for scheduling activities is one of the important considerations in the design of a real-time system.

Scheduling of real-time systems has always assumed that the underlying hardware is a single processor system. But current trends indicate that sophisticated real-time applications with high computational demands are emerging. Examples of such systems include automatic tracking systems and telepresence systems. These applications have timing constraints that are used to ensure high system fidelity and responsiveness, and may also be crucial for correctness in certain applications such as telesurgery. Also, the processing requirements of these systems exceed the capacity of a single processor, and a multiprocessor may be necessary to achieve an effective implementation. These observations underscore the growing importance of multiprocessors in real-time systems. The priority of the task to be scheduled may be fixed or dynamic. The rate-monotonic scheduling (RMS) algorithm is an optimal fixed-priority scheduling algorithm. An optimal dynamic-priority algorithm is the earliest-deadline first (EDF) algorithm. These scheduling algorithms which are optimal in single processor systems will result in arbitrarily low processor utilization in multiprocessor systems.

There are two approaches for scheduling on multiprocessors: partitioning and global scheduling. In partitioning, each task is assigned to a single processor. Each of these processors will execute the jobs assigned to it. These processors are then scheduled independently. This reduces the multiprocessor scheduling problem to a set of uniprocessor ones. We can then implement an algorithm like the EDF or the RMS on the tasks. Unfortunately, finding an optimal assignment of 1

tasks to processors is an NP-hard problem. Thus, tasks are usually partitioned using non-optimal methods. Moreover, there exist task systems that are schedulable if and only if tasks are not partitioned.

In global scheduling, all eligible tasks are stored in a single priority-ordered queue. The scheduler selects the highest-priority tasks from this queue for execution. Thus a task is not fixed to a processor and is allowed to migrate between processors. The issue with global scheduling is that it can result in low processor utilization if used with the EDF or RMS algorithms.

The algorithm that I discuss is called proportionate fair (Pfair) scheduling. The work of Baruah et al. proved that periodic task systems could be optimally scheduled using global scheduling algorithms based on Pfairness. Under Pfair scheduling, each task is required to execute at a uniform rate by breaking it into a series of subtasks. Each task with weight w would receive w.L units of processor time over interval L.

𝒘𝒊 =

𝒆𝒊 𝒑𝒊

Each task allocated resource for x.e time units in each interval. By breaking tasks into uniformsized subtasks, Pfair scheduling avoids the bin-packing issues of multiprocessor scheduling. Indeed, Pfair scheduling is presently the only known approach for optimally scheduling periodic tasks on multiprocessors. The advantages of Pfair scheduling are that it is able to schedule periodic, sporadic or ratebased task systems. Also it can handle dynamic events, such as tasks leaving and joining a system. However, the use of such a global scheduling algorithm results in degraded processor affinity. Pfair scheduling algorithms can result in frequent preemptions and migrations resulting in excessive overhead.

2

In spite of these disadvantages, the Pfair scheduling is presently the only known approach for optimally scheduling periodic tasks on multiprocessors.

References: [1] K. Ramamritham, J.A. Stankovic, and P.F. Shiah, "Efficient Scheduling Algorithms for Real-Time Multiprocessor Systems," IEEE Trans. Parallel and Distributed Systems, vol. 1, no. 2, pp. 184- 194, Apr. 1990. [2] J. Carpenter, S. Funk, et al. “A categorization of real-time multiprocessor scheduling problems and algorithms," In J. Y. Leung, editor, Handbook on Scheduling Algorithms, Methods, and Models, pp 30.130.19. Chapman Hall/CRC, Boca Raton, Florida, 2004. [3] S. Baruah, N. Cohen, C. Plaxton and D. Varvel, "Proportionate Progress: A Notion of Fairness in Resource Allocation", Algorithmica 15(6), pp. 600-625, 1996. [4] M. Adler, P. Berenbrink, T. Friedetzy, L.A. Goldberg, P. Goldberg and M. Paterson, “A proportionate fair scheduling rule with good worst-case performance,” Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, pp 101104, June 2003. [5] O.U.P. Zapata and P. Meija-Alvarez, "Analysis of Real-Time Multiprocessors Scheduling Algorithms, " Proceedings of the Real-Time Systems Symposium, Dec. 2003

3