Assigning Real-Time Tasks to Homogeneous Multiprocessor Systems

Abstract

Optimal scheduling of real-time tasks on multiprocessor systems is known to be computationally intractable for large task sets. Any practical scheduling algorithm for assigning real-time tasks to a multiprocessor system presents a trade-off between its computational complexity and its performance. The performance of a scheduling algorithm is measured in terms of the additional number of processors required to arrive at a schedule without deadline violations as compared to an optimal algorithm. In this study, new schedulability conditions are presented for homogeneous multiprocessor systems where individual processors execute the rate-monotonic scheduling algorithm. The conditions are used to develop new strategies for assigning real-time tasks to processors. The performance of the new strategies is shown to be significantly better than suggested by the existing literature. Under the (realistic) assumption that the load of each real-time task is small compared to the processing speed of each processor, it is shown that all processors can be almost fully utilized. Task assignment strategies are proposed for scenarios where the task set is known a priori (off-line schemes), and where the real-time task set can change dynamically (on-line schemes).