An analysis of EDF schedulability on a multiprocessor

Abstract

A new schedulability test is derived for preemptive deadline scheduling of periodic or sporadic real-time tasks on a single-queue m-server system. The new test allows the task deadline to be more or less than the task period, and is based on a new analysis concept, called a /spl mu/-busy interval. This generalizes a result of Goossens et al. [2003] that a system of periodic tasks with maximum individual task utilization u/sub max/ is EDF-schedulable on m processors if the total utilization does not exceed m(1 /sup max/)+u/sub max/. The new test allows the analysis of hybrid EDF-US [x] scheduling, and the conclusion that EDF-US[1/2] is optimal, with a guaranteed worst-case schedulable utilization of (m +1)/2.