loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
A Utilization Bound for Aperiodic Tasks and Priority Driven Scheduling
March 2004 (vol. 53 no. 3)
pp. 334-350
ASCII Text
x 
 
Tarek F. Abdelzaher, Vivek Sharma, Chenyang Lu, "A Utilization Bound for Aperiodic Tasks and Priority Driven Scheduling," IEEE Transactions on Computers, vol. 53, no. 3, pp. 334-350, March, 2004.
 
 
BibTex
x
 
@article{ 10.1109/TC.2004.1261839,
author = {Tarek F. Abdelzaher and Vivek Sharma and Chenyang Lu},
title = {A Utilization Bound for Aperiodic Tasks and Priority Driven Scheduling},
journal ={IEEE Transactions on Computers},
volume = {53},
number = {3},
issn = {0018-9340},
year = {2004},
pages = {334-350},
doi = {http://doi.ieeecomputersociety.org/10.1109/TC.2004.1261839},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - JOUR
JO - IEEE Transactions on Computers
TI - A Utilization Bound for Aperiodic Tasks and Priority Driven Scheduling
IS - 3
SN - 0018-9340
SP334
EP350
EPD - 334-350
A1 - Tarek F. Abdelzaher,
A1 - Vivek Sharma,
A1 - Chenyang Lu,
PY - 2004
KW - Real-time scheduling
KW - schedulability analysis
KW - utilization bounds
KW - aperiodic tasks.
VL - 53
JA - IEEE Transactions on Computers
ER -
 

Abstract—Real-time scheduling theory offers constant-time schedulability tests for periodic and sporadic tasks based on utilization bounds. Unfortunately, the periodicity or the minimal interarrival-time assumptions underlying these bounds make them inapplicable to a vast range of aperiodic workloads such as those seen by network routers, Web servers, and event-driven systems. This paper makes several important contributions toward real-time scheduling theory and schedulability analysis. We derive the first known bound for schedulability of aperiodic tasks. The bound is based on a utilization-like metric we call synthetic utilization, which allows implementing constant-time schedulability tests at admission control time. We prove that the synthetic utilization bound for deadline-monotonic scheduling of aperiodic tasks is {\frac 1 {1 + \sqrt {1/2}}}. We also show that no other time-independent scheduling policy can have a higher schedulability bound. Similarly, we show that EDF has a bound of 1 and that no dynamic-priority policy has a higher bound. We assess the performance of the derived bound and conclude that it is very efficient in hit-ratio maximization.

[1] T. Abdelzaher and C. Lu, Schedulability Analysis and Utilization Bounds for Highly Scalable Real-Time Services Proc. IEEE Real-Time Technology and Applications Symp., June 2001.[2] T.F. Abdelzaher, K.G. Shin, and N. Bhatti, Performance Guarantees for Web Server End-Systems: A Control-Theoretical Approach IEEE Trans. Parallel and Distributed Systems, 2001.[3] K.G. Shin and Y.-C. Chang, “A Reservation-Based Algorithm for Scheduling Both Periodic and Aperiodic Real-Time Tasks,” IEEE Trans. Computers, vol. 44, no. 12, pp. 1,405-1,419, Dec. 1995.[4] D. Chen, A.K. Mok, and T.-W. Kuo, “Utilization Bound Re-Visited,” Proc. Sixth Int'l Conf. Real-Time Computing Systems and Applications, 1999.[5] R. Davis and A. Burns, Optimal Priority Assignment for Aperiodic Tasks with Firm Deadlines in Fixed Priority Pre-Emptive Systems Information Processing Letters, vol. 53, no. 5, pp. 249-254, Mar. 1995.[6] R. Devillers and J. Goossens, Liu and Layland's Schedulability Test Revisited Information Processing Letters, vol. 73, no. 5, pp. 157-161, Mar. 2000.[7] N. Gandhi, S. Parekh, J. Hellerstein, and D. Tilbury, Feedback Control of a Lotus Notes Server: Modeling and Control Design Proc. Am. Control Conf., 2001.[8] C.-C. Han, “A Better Polynomial-Time Scheduleability Test for Real-Time Multiframe Tasks,” Proc. IEEE Real-Time Systems Symp., Dec. 1998.[9] C.-C. Han, H.y. Tyan, “A Better Polynomial-Time Schedulability Test for Real-Time Fixed-Priority Scheduling Algorithms,” Proc. IEEE Real-Time Systems Symp., pp. 36-45, Dec. 1997.[10] G. Koren and D. Shasha, “D-Over: An Optimal On-Line Scheduling Algorithm for Overloaded Real-Time Systems,” Proc. IEEE Real-Time Systems Symp., pp. 290-299, Dec. 1992.[11] T.-W. Kuo and A.K. Mok, “Load Adjustment in Adaptive Real-Time Systems,” Proc. IEEE Real-Time Systems Symp., Dec. 1991.[12] S. Lauzac, R. Melhem, and D. Mosse, “An Efficient RMS Admission Control and Its Application to Multiprocessor Scheduling,” Proc. Int'l Parallel Processing Symp., pp. 511-518, 1998.[13] 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.[14] J.P. Lehoczky and S. Ramos-Thuel, “An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems,” Proc. Real-Time Systems Symp., pp. 110-123, 1992.[15] J.P. Lehoczky, Real-Time Queueing Theory Proc. 17th IEEE Real-Time Systems Symp. (RSS '96), pp. 186-195, Dec. 1996.[16] J.P. Lehoczky, Using Real-Time Queueing Theory to Control Lateness in Real-Time Systems Proc. 1997 ACM SIGMETRICS Int'l Conf. Measurement and Modeling of Computer Systems, Performance Evaluation Rev., vol. 25, no. 1, pp. 158-168, June 1997.[17] T.-H. Lin and W. Tarng, Scheduling Periodic and Aperiodic Tasks in Hard Real-Time Computing Systems Performance Evaluation Rev., vol. 19, no. 1, May 1991.[18] C.L. Liu and J.W. Layland, Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment J. ACM, vol. 20, no. 1, pp. 46-61, 1973.[19] J.M. López, J.L. Díaz, M. García, and D.F. García, Worst-Case Utilization Bound for EDF Scheduling on Real-Time Multiprocessor Systems Proc. Euromicro Conf. Real-Time Systems, pp. 25-33, 2000.[20] C. Lu, T. Abdelzaher, J. Stankovic, and S. Son, A Feedback Control Approach for Guaranteeing Relative Delays in Web Servers Proc. IEEE Real-Time Technology and Applications Symp., June 2001.[21] Y. Lu, A. Saxena, and T.F. Abdelzaher, Differentiated Caching Services; a Control-Theoretical Approach Proc. Int'l Conf. Distributed Computing System, Apr. 2001.[22] A.K. Mok and D. Chen, “A Multiframe Model for Real-Time Tasks,” IEEE Trans. Software Eng., vol. 23, no. 10, pp. 635-645, Oct. 1997.[23] M. DiNatale and J. Stankovic, Dynamic End-to-End Guarantees in Distributed Real-Time Systems Proc. Real-Time Systems Symp., pp. 216-227, Dec. 1994.[24] D.-I. Oh and T.P.B. TP, Utilization Bounds for n-Processor Rate Monotone Scheduling with Static Processor Assignment Real-Time Systems, vol. 15, no. 2, 1998.[25] M. Pandya and M. Malek, “Minimum Achievable Utilization for Fault-Tolerant Processing of Periodic Tasks,” IEEE Trans. Computers, vol. 47, no. 10, pp. 1102-1112, Oct. 1998.[26] D.-W. Park, S. Natarajan, and A. Kanevsky, Fixed-Priority Scheduling of Real-Time Systems Using Utilization Bounds J. Systems and Software, vol. 33, no. 1, pp. 57-63, Apr. 1996.[27] K. Ramamritham, J.A. Stankovic, and W. Zhao, “Distributed Scheduling of Tasks with Deadlines and Resource Requirements,” Trans. Computers, vol. 38, no. 8, Aug. 1989.[28] I. Bhandari, M. Halliday, E. Tarver, D. Brown, J. Chaar, and R. Chillarege, "A Case Study of Software Process Improvement During Development," IEEE Trans. Software Eng., vol. 19, no. 12, pp. 1,157-1,170, Dec. 1993.[29] B. Sprunt, L. Sha, and J. Lehoczky, Aperiodic Task Scheduling for Hard-Real-Time Systems Real-Time Systems, vol. 1, no. 1, pp. 27-60, June 1989.[30] J.A. Stankovic, “Decentralized Decision Making for Tasks Reallocation in a Hard Real-Time System,” IEEE Trans. Computers, vol. 38, no. 3, pp. 341-355, Mar. 1989.[31] J. Stankovic and K. Ramamritham, Hard Real-Time Systems. IEEE Press, 1988.[32] J.A. Stankovic and K. Ramamritham, The Design of the Spring Kernel Proc. Real-Time Systems Symp., pp. 146-157, Dec. 1987.[33] J.A. Stankovic and K. Ramamritham, “The Spring Kernel: A New Paradigm for Real-Time Systems,” IEEE Software, pp. 62-72, May 1991.[34] J.A. Stankovic, K. Ramamritham, and S. Cheng, Evaluation of a Flexible Task Scheduling Algorithm for Distributed Hard Real-Time Systems IEEE Trans. Computers, vol. 34, no. 12, pp. 1130-1143, Dec. 1985.[35] D.C. Steere, A. Goel, J. Gruenberg, D. McNamee, C. Pu, and J. Walpole, A Feedback-Driven Proportion Allocator for Real-Rate Scheduling Operating Systems Design and Implementation, 1999.[36] 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.[37] S.R. Thuel and J.P. Lehoczky, Algorithms for Scheduling Hard Aperiodic Tasks in Fixed-Priority Systems Using Slack Stealing Proc. Real-Time Systems Symp., pp. 22-33, Dec. 1994.[38] O. Yingfeng and S.H. Son, Allocating Fixed-Priority Periodic Tasks on Multiprocessor Systems Real-Time Systems, vol. 9, no. 3, pp. 207-239, Nov. 1995.[39] W. Zhao, K. Ramamritham, and J. Stankovic, Preemptive Scheduling under Time and Resource Constraints IEEE Trans. Computers, vol. 36, no. 8, pp. 949-960, Aug. 1987.[40] W. Zhao, K. Ramamritham, and J. Stankovic, Scheduling Tasks with Resource Requirements in Hard Real-Time Systems IEEE Trans. Software Eng., vol. 13, no. 5, pp. 564-577, May 1987.

Index Terms:
Real-time scheduling, schedulability analysis, utilization bounds, aperiodic tasks.
Citation:
Tarek F. Abdelzaher, Vivek Sharma, Chenyang Lu, "A Utilization Bound for Aperiodic Tasks and Priority Driven Scheduling," IEEE Transactions on Computers, vol. 53, no. 3, pp. 334-350, Mar. 2004, doi:10.1109/TC.2004.1261839
Usage of this product signifies your acceptance of the Terms of Use.