IEEE Real-Time Systems Symposium (RTSS) Influential Paper Award

1989

1. Rate monotonic scheduling algorithm: Exact characterization and average case behavior

   John Lehoczky, Lui Sha, and Ye Ding

   Proceedings - Real-Time Systems Symposium, 1989

   Abs Bib

   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).

   @article{Lehoczky1989166,
     author = {Lehoczky, John and Sha, Lui and Ding, Ye},
     title = {Rate monotonic scheduling algorithm: Exact characterization and average case behavior},
     journal = {Proceedings - Real-Time Systems Symposium},
     year = {1989},
     pages = {166-171},
     url = {https://www.scopus.com/inward/record.uri?eid=2-s2.0-0024915921&partnerID=40&md5=756dc0fe3e25215eb898b889851e7975},
     keywords = {Computer Programming--Algorithms;  Probability--Random Processes, Rate Monotonic Scheduling;  Real Time Systems;  Scheduling Algorithms, Computer Systems, Digital},
     document_type = {Conference Paper},
     source = {Scopus},
   }