Worst-case utilization bound for EDF scheduling on real-time multiprocessor systems

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 /spl alpha/, the previous bound is raised, and the new utilization bound considering /spl alpha/ 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.