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

D. Towsley, S. S. Panwar

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProc EUROMICRO 90 Workshop Real Time
PublisherPubl by IEEE
Pages17-24
Number of pages8
ISBN (Print)0818620765
StatePublished - 1990
EventProceedings - EUROMICRO '90 Workshop on Real Time - Horsholm, Den
Duration: Jun 6 1990Jun 8 1990

Publication series

NameProc EUROMICRO 90 Workshop Real Time

Other

OtherProceedings - EUROMICRO '90 Workshop on Real Time
CityHorsholm, Den
Period6/6/906/8/90

ASJC Scopus subject areas

  • Engineering(all)

Fingerprint Dive into the research topics of 'On the optimality of minimum laxity and earliest deadline scheduling for real-time multiprocessors'. Together they form a unique fingerprint.

Cite this