Calculus of Variations and Geometric Measure Theory

E. Bini - G. Buttazzo - G. Buttazzo

A hyperbolic bound for the rate monotonic algorithm

created by buttazzo on 12 Oct 2017


Published Paper

Inserted: 12 oct 2017

Journal: IEEE Proceedings of the 13th Euromicro Conference on Real-Time Systems
Pages: 59-66
Year: 2001
Doi: 10.1109/EMRTS.2001.934000
Links: paper at the IEEE web site


In this paper 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 bound but it is less pessimistic, so allowing 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: hyperbolic bound, rate monotonic algorithm, schedulability analysis