| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Enhanced Utilization Bounds for QoS Management
February 2004 (vol. 53 no. 2)
pp. 187-200
Abstract—In many practical real-time applications, there is a given set of task frequencies (i.e., inverse of task periods) corresponding to predetermined QoS options that the applications can choose. For example, in audio applications, the typical choices of playback frequencies are for CD quality, radio quality, and phone quality. Similar configurations can be found in streaming video and in control applications. In such systems, applications dynamically arrive requesting one of the periods provided by the QoS manager. Thus, the accurate and efficient online schedulability test is essential for any task set whose periods are chosen from the QoS period set. For this purpose, this paper proposes new utilization bounds as a function of given QoS periods. As long as there is a set of given periods that can be chosen by applications, the bounds developed in this paper can be used by the QoS manager to quickly determine the schedulability of dynamic applications.
[1] 187 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, Jan. 1973.[2] M. Joseph and P. Pandya, Finding Response Times in a Real-Time System BCS Computer J., vol. 29, no. 5, pp. 390-395, Oct. 1986.[3] H. Chetto and M. Chetto, “Some Results of the Earliest Deadline Scheduling Algorithm,” IEEE Trans. Software Eng., vol. 15, no. 10, pp. 1,261-1,269, Oct. 1989.[4] 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.[5] K. Schwan and H. Zhou, “Dynamic Scheduling of Hard Real-Time Tasks and Real-Time Threads,” IEEE Trans. Software Eng., vol. 18, no. 8, pp. 736–748, Aug. 1992.[6] K. Tindell, A. Burns, and A. Wellings, An Extendible Approach for Analyzing Fixed Priority Hard Real-Time Tasks J. Real-Time Systems, vol. 6, no. 2, pp. 133-151, 1994.[7] L. Sha, R. Rajkumar, and S.S. Sathaye, "Generalized Rate-Monotonic Scheduling Theory: A Framework for Developing Real-Time Systems," Proc. IEEE, vol. 82, no. 1, Jan. 1994.[8] T.-W. Kuo and A.K. Mok, “Load Adjustment in Adaptive Real-Time Systems,” Proc. IEEE Real-Time Systems Symp., Dec. 1991.[9] T.W. Kuo and A.K. Mok, Load Adjustment in Adaptive Real-Time Systems Proc. IEEE Trans. Computers, vol. 16, no. 12, Dec. 1997.[10] Y. Oh and S.H. Son, Allocating Fixed-Priority Periodic Tasks on Multiprocessor Systems J. Real-Time Systems, vol. 9, no. 3, pp. 207-239, 1995.[11] A. Burchard, J. Liebeherr, Y. Oh, and S.H. Son, “Assigning Real-Time Tasks to Homogeneous Multiprocessor Systems,” IEEE Trans. Computers, vol. 44, no. 12, pp. 1429-1442, Dec. 1995.[12] 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.[13] T.-W. Kuo, Y.-H. Liu, and K.-J. Lin, Efficient On-Line Schedulability Tests for Priority Driven Real-Time Systems Proc. IEEE Real-Time Technology and Applications Symp., June 2000.[14] 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.[15] D.R. Billetter, Multifunction Array Radar, chapters 2, 7. Artech House, 1989.[16] A.K. Mok and D. Chen, "A Multiframe Model for Real-Time Tasks," Proc. IEEE Real-Time System Symp., pp. 22-29,Washington DC, Dec. 1996.[17] 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.[18] J.W.S. Liu, Real-Time Systems. Prentice Hall, 2000.[19] C.-G. Lee and L. Sha, Utilization Bounds for Online QoS Management technical report, Univ. of Illinois,http://www. eleceng.ohio-state.edu/~cglee/ paperscgleeUtilBound_Tech Report.ps, Dec. 2001.[20] 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.[21] L. Sha, R. Rajkumar, and J.P. Lehoczky, Real-Time Synchronization Protocol for Multi-Processors Proc. IEEE Real-Time Systems Symp., Dec. 1988.[22] B. Sprunt, L. Sha, and J.P. Lehoczky, Aperiodic Task Scheduling for Hard Real-Time Systems Real-Time Systems J., vol. 1, no. 1, pp. 27-60, 1989.
Index Terms:
Real-time system, scheduling, utilization bound, QoS (Quality of Service), online admission control, multiframe task model.
Citation:
Chang-Gun Lee, Lui Sha, Avinash Peddi, "Enhanced Utilization Bounds for QoS Management," IEEE Transactions on Computers, vol. 53, no. 2, pp. 187-200, Feb. 2004, doi:10.1109/TC.2004.1261828
