|
Published Articles >> Table of Contents >> Abstract
July 2003 (Vol. 52, No. 7)
pp. 933-942
Rate Monotonic Analysis: The Hyperbolic Bound
Enrico Bini
Giorgio C. Buttazzo, IEEE
Giuseppe M. Buttazzo
Full Article Text:
   
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/TC.2003.1214341
Send link to a friend
| Abstract |
|
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, 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.
|
 References
|
[1] J. Locke, Designing Real-Time Systems invited talk at IEEE Int'l Conf. Real-Time Computing Systems and Applications, Dec. 1997.
[2] C.L. Liu and J.W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,” J. ACM, vol. 20, no. 1, pp. 40-61, 1973.
[3] J. Lehoczky, L. Sha, and Y. Ding, The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior Proc. IEEE Real-Time Systems Symp., pp. 166-171, 1989.
[4] M. Joseph and P. Pandya, Finding Response Times in a Real-Time System The Computer J., vol. 29, no. 5, pp. 390-395, 1986.
[5] N.C. Audsley, A. Burns, M. Richardson, K. Tindell, and A. Wellings, "Applying New Scheduling Theory to Static Priority Preemptive Scheduling," Software Eng. J. vol. 8, no. 5, pp. 284-292, Sept. 1993.
[6] M. Sjodin and H. Hansson, “Improved Response-Time Analysis Calculations,” Proc. IEEE Real-Time Systems Symp., pp. 36-45, Dec. 1998.
[7] L. Sha, R. Rajkuma, and J.P. Lehoczky, "Priority Inheritance Protocols: An Approach to Real-Time Synchronization," IEEE Trans. Computers, vol. 39, no. 9, pp. 1,175-1,185, Sept. 1990.
[8] Y. Oh and S.H. Son, Allocating Fixed-Priority Periodic Tasks on Multiprocessor Systems Real-Time Systems, vol. 9, pp. 207-239, 1995.
[9] J.W.S. Liu, Real-Time Systems. Upper Saddle River N.J.: Prentice Hall, 2000.
[10] E. Bini, G.C. Buttazzo, and G.M. Buttazzo, A Hyperbolic Bound for the Rate Monotonic Algorithm IEEE Proc. 13th Euromicro Conf. Real-Time Systems, June 2001.
[11] R. Devillers and J. Goossens, Liu and Layland's Schedulability Test Revisited Information Processing Letters, vol. 73, no. 5, pp. 157-161, Mar. 2000.
[12] J.P. Lehoczky, L. Sha, and J.K. Strosnider, Enhanced Aperiodic Responsiveness in Hard Real-Time Environments Proc. IEEE Real-Time Systems Symp., pp. 261-270, 1987.
[13] J.K. Strosnider, J.P. Lehoczky, and L. Sha, “The Deferrable Server Algorithm for Enhanced Aperiodic Responsiveness in Hard Real-Time Environments,” IEEE Trans. Computers, vol. 44, no. 1, Jan. 1995.
[14] T.-W. Kuo and A.K. Mok, “Load Adjustment in Adaptive Real-Time Systems,” Proc. IEEE Real-Time Systems Symp., Dec. 1991.
|
 Additional Information
|
Index Terms- Rate-monotonic analysis, periodic scheduling, schedulability test.
Citation:
Enrico Bini, Giorgio C. Buttazzo, Giuseppe M. Buttazzo,
"Rate Monotonic Analysis: The Hyperbolic Bound,"
IEEE Transactions on Computers,
vol. 52,
no. 7,
pp. 933-942,
Jul.,
2003
|
|
RSS Feed