A performance analysis of minimum laxity and earliest deadline scheduling in a real-time system

A study is made of the performance of a real-time system in which jobs all have deadlines for either the beginning or the end of service. In the first case the authors analyze the minimum laxity (ML) scheduling policy when there are c processors, and in the latter case they analyze the preemptive-resume earliest deadline (ED) scheduling policy when there is one server. In both cases, the analysis assumes a Poisson arrival process, exponential service times that are not known to the scheduler, and exponential laxities or deadlines, and families of upper and lower bounds on the fraction of jobs that miss their deadlines are developed. The pessimistic bounds are of special interest because they correspond to a family of implementable policies, ML(n) and ED( n), n a positive integer 1, for which the performance approaches that of ML and ED as n increases, but at the cost of increasing overhead