Rate monotonic scheduling algorithm: Exact characterization and average case behavior

John Lehoczky, Lui Sha, Ye Ding

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


An exact characterization of the ability of the rate monotonic scheduling algorithm to meet the deadlines of a periodic task set is represented. In addition, a stochastic analysis which gives the probability distribution of the breakdown utilization of randomly generated task sets is presented. It is shown that as the task set size increases, the task computation times become of little importance, and the breakdown utilization converges to a constant determined by the task periods. For uniformly distributed tasks, a breakdown utilization of 88% is a reasonable characterization. A case is shown in which the average-case breakdown utilization reaches the worst-case lower bound of C. L. Liu and J. W. Layland (1973).

Original languageEnglish (US)
Title of host publicationProceedings - Real-Time Systems Symposium
Editors Anon
PublisherPubl by IEEE
Number of pages6
ISBN (Print)0818620048
StatePublished - 1989
Externally publishedYes
EventProceedings - Real-Time Systems Symposium - Santa Monica, CA, USA
Duration: Dec 5 1989Dec 7 1989

Publication series

NameProceedings - Real-Time Systems Symposium


OtherProceedings - Real-Time Systems Symposium
CitySanta Monica, CA, USA

ASJC Scopus subject areas

  • Software
  • Hardware and Architecture
  • Computer Networks and Communications


Dive into the research topics of 'Rate monotonic scheduling algorithm: Exact characterization and average case behavior'. Together they form a unique fingerprint.

Cite this