Seventh International Conference on Real-Time Computing Systems and Applications (RTCSA'00)
Fixed-priority preemptive multiprocessor scheduling: to partition or not to partition
Cheju Island, South Korea
December 12-December 14
ISBN: 0-7695-0930-4
B. Andersson, Dept. of Comput. Eng., Chalmers Univ. of Technol., Goteborg, Sweden
J. Jonsson, Dept. of Comput. Eng., Chalmers Univ. of Technol., Goteborg, Sweden
Traditional multiprocessor real-time scheduling partitions a task set and applies uniprocessor scheduling on each processor. By allowing a task to resume on another processor than the task was preempted on, some task sets can be scheduled where the partitioned method fails. We address fixed-priority preemptive scheduling of periodically arriving tasks on m equally powerful processors. We compare the performance of the best algorithms of the partitioned and non-partitioned method, from two different aspects. First, an average-case comparison, using an idealized architecture, shows that, if a system has a small number of processors, then the non-partitioned method offers higher performance than the partitioned method. Second, an average-case comparison, using a realistic architecture, shows that, for several combinations of preemption and migration costs, the non-partitioned method offers higher performance.
Index Terms:
processor scheduling; real-time systems; software performance evaluation; fixed-priority preemptive multiprocessor scheduling; multiprocessor real-time scheduling; task set partitioning; uniprocessor scheduling; periodically arriving tasks; algorithm performance; preemption costs; migration costs
Citation:
B. Andersson, J. Jonsson, "Fixed-priority preemptive multiprocessor scheduling: to partition or not to partition," rtcsa, pp.337, Seventh International Conference on Real-Time Computing Systems and Applications (RTCSA'00), 2000