Calculus of Variations and Geometric Measure Theory

E. Bini - G. Buttazzo - G. Buttazzo

Rate monotonic analysis: the hyperbolic bound

created by buttazzo on 12 Oct 2017


Published Paper

Inserted: 12 oct 2017

Journal: IEEE Transactions on Computers
Volume: 52
Number: 7
Pages: 933-942
Year: 2003
Doi: 10.1109/TC.2003.1214341
Links: paper at the journal web site


We propose a novel schedulability analysis for verifying the feasibility of large periodic task sets under the rate monotonic algorithm when the exact test cannot be applied on line due to prohibitively long execution times. The proposed test has the same complexity as the original Liu and Layland (1973) bound, but it is less pessimistic, thus allowing it to accept task sets that would be rejected using the original approach. The performance of the proposed approach is evaluated with respect to the classical Liu and Layland method and theoretical bounds are derived as a function of n (the number of tasks) and for the limit case of n tending to infinity. The analysis is also extended to include aperiodic servers and blocking times due to concurrency control protocols. Extensive simulations on synthetic tasks sets are presented to compare the effectiveness of the proposed test with respect to the Liu and Layland method and the exact response time analysis.

Keywords: Rate-monotonic analysis, periodic scheduling, schedulability test