The rate monotonic scheduling algorithm: exact characterization and average case behavior Export

@proceedings{citeulike:4463465, abstract = {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)}, author = {Lehoczky, J. and Sha, L. and Ding, Y.}, booktitle = {Real Time Systems Symposium, 1989., Proceedings.}, citeulike-article-id = {4463465}, citeulike-linkout-0 = {http://dx.doi.org/10.1109/REAL.1989.63567}, citeulike-linkout-1 = {http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=63567}, doi = {10.1109/REAL.1989.63567}, journal = {Real Time Systems Symposium, 1989., Proceedings.}, keywords = {qual, real-time, scheduling}, pages = {166--171}, posted-at = {2009-08-14 15:10:31}, priority = {2}, title = {The rate monotonic scheduling algorithm: exact characterization and average case behavior}, url = {http://dx.doi.org/10.1109/REAL.1989.63567}, year = {1989} }

TY - CONF ID - citeulike:4463465 L3 - citeulike-article-id:4463465 N2 - 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) JF - Real Time Systems Symposium, 1989., Proceedings. EP - 171 TI - The rate monotonic scheduling algorithm: exact characterization and average case behavior T2 - Real Time Systems Symposium, 1989., Proceedings. SP - 166 KW - qual KW - real-time KW - scheduling AU - Lehoczky, J AU - Sha, L AU - Ding, Y PY - 1989/// UR - http://dx.doi.org/10.1109/REAL.1989.63567 ER -