Title :
Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems
Author :
López, J.M. ; Garcia, M. ; Díaz, J.L. ; García, D.F.
Author_Institution :
Dept. of Comput. Sci., Oviedo Univ., Spain
Abstract :
Presents the utilization bound for earliest deadline first (EDF) scheduling on homogeneous multiprocessor systems with partitioning strategies. Assuming that tasks are pre-emptively scheduled on each processor according to the EDF algorithm, and allocated according to the first-fit (FF) heuristic, we prove that the worst-case achievable utilization is 0.5(n+1), where n is the number of processors. This bound is valid for arbitrary utilization factors. Moreover, if all the tasks have utilization factors under a value α, the previous bound is raised, and the new utilization bound considering α is calculated. In addition, we prove that no uniprocessor scheduling algorithm/allocation algorithm pair can provide a higher worst-case achievable utilization than that of EDF-FF. Finally, simulation provides the average-case achievable utilization for EDF-FF
Keywords :
multiprocessing systems; processor scheduling; real-time systems; resource allocation; average-case achievable utilization; earliest deadline first scheduling; first-fit heuristic; homogeneous multiprocessor systems; partitioning strategies; preemptively scheduled tasks; processor number; real-time multiprocessor systems; simulation; task allocation; uniprocessor allocation algorithm; uniprocessor scheduling algorithm; utilization factors; worst-case utilization bound; Computer science; Heuristic algorithms; Multiprocessing systems; Optimal scheduling; Optimized production technology; Partitioning algorithms; Performance evaluation; Processor scheduling; Real time systems; Scheduling algorithm;
Conference_Titel :
Real-Time Systems, 2000. Euromicro RTS 2000. 12th Euromicro Conference on
Conference_Location :
Stockholm
Print_ISBN :
0-7695-0734-4
DOI :
10.1109/EMRTS.2000.853989