Title :
Multiprocessor Scheduling with Few Preemptions
Author :
Andersson, Björn ; Tovar, Eduardo
Author_Institution :
IPP Hurray Res. Group, Polytech. Inst. of Porto
Abstract :
Consider the problem of scheduling a set of periodically arriving tasks on a multiprocessor with the goal of meeting deadlines. Processors are identical and have the same speed. Tasks can be preempted and they can migrate between processors. We propose an algorithm with a utilization bound of 66% and with few preemptions. It can trade a higher utilization bound for more preemptions and in doing so it has a utilization bound of 100%
Keywords :
processor scheduling; multiprocessor scheduling; preemption scheduling; Algorithm design and analysis; Costs; Partitioning algorithms; Processor scheduling; Scheduling algorithm; Upper bound;
Conference_Titel :
Embedded and Real-Time Computing Systems and Applications, 2006. Proceedings. 12th IEEE International Conference on
Conference_Location :
Sydney, Qld.
Print_ISBN :
0-7695-2676-4
DOI :
10.1109/RTCSA.2006.45
