On the optimality of minimum laxity and earliest deadline scheduling for real-time multiprocessors

The problem of scheduling jobs with real-time constraints on a multiprocessor is considered. If a job does not complete within a certain time interval of its arrival to such a system, it is considered useless and need not be served. It is therefore desirable to schedule jobs so that the fraction of jobs served within their respective deadlines is maximized. Such a system is modeled as a multiple server queue. It is shown, for a variety of systems, that the minimum laxity (ML) policy maximizes the fraction of jobs that successfully complete service when jobs must begin service by their deadline, and that the earliest deadline policy does the same for wide class of systems when jobs must complete service by their deadlines. Results are given for unreliable multiprocessors and multiprocessors that serve several priority classes of jobs