Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems
- 7 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In this paper we present 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 pair of uniprocessor scheduling algorithm-allocation algorithm 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
This publication has 6 references indexed in Scilit:
- Using exact feasibility tests for allocating real-time tasks in multiprocessor systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Allocating fixed-priority periodic tasks on multiprocessor systemsReal-Time Systems, 1995
- New strategies for assigning real-time tasks to multiprocessor systemsIEEE Transactions on Computers, 1995
- Multiprocessor online scheduling of hard-real-time tasksIEEE Transactions on Software Engineering, 1989
- On a Real-Time Scheduling ProblemOperations Research, 1978
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973