Abstract
In this paper we present a novel admission control scheme for a mixed set of periodic and aperiodic tasks with hard deadlines under EDF, which can achieve near optimal performance with practical utility. The proposed admission control scheme is based on a novel schedulability measure for a deadline-constrained task, called utilization demand, which can be viewed as a combination of the processor time demand and the utilization factor. We first show that this new schedulability measure provides a necessary and sufficient schedulability condition for aperiodic tasks. We then present an efficient schedulability test for a mixed set of periodic and aperiodic tasks under EDF. The resulting schedulability test can be implemented as an on-line admission control algorithm of O(n) complexity, which in practice incurs sufficiently low overhead. Our experimental results show that the proposed admission control scheme outperforms existing approaches with respect to achievable processor utilization.
The work reported in this paper was supported in part by the Korea Research Foundation Grant KRF-2003-003-D00340, in part by IT Leading R&D Support Project funded by Ministry of Information and Communication, and in part by the research fund of Hanyang University HY-2003.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdelzaher, T., Sharma, V., Lu, C.: A utilization bound for aperiodic tasks and priority driven scheduling. IEEE Transactions on Computers 53, 334–350 (2004)
Audsley, N., Burns, A., Richardson, M., Wellings, A.: Hard real-time scheduling: The deadline-monotonic approach. In: Proceedings of IEEE Workshop on Real-Time Operating Systems and Software, pp. 133–137 (1991)
Buttazzo, G., Sensini, F.: Optimal deadline assignment for scheduling soft aperiodic tasks in hard real-time environments. IEEE Transactions on Computers 48, 1035–1052 (1999)
Chetto, H., Chetto, M.: Some results of the earliest deadline first scheduling algorithm. IEEE Transactions on Software Engineering 15, 1261–1268 (1989)
Lehoczky, J., Ramos-Thuel, S.: An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems. In: Proceedings of IEEE Real-Time Systems Symposium, pp. 110–123 (1992)
Liu, C., Layland, J.: Scheduling algorithm for multiprogramming in a hard real-time environment. Journal of the ACM 20, 46–61 (1973)
Parekh, A., Gallagher, R.: A generalized processor sharing approach to flow control in integrated services networks: the single-node case. IEEE/ACM Transactions on Networking 1, 344–357 (1993)
Ripoll, I., Crespo, A., Garcia-Fornes, A.: An optimal algorithm for scheduling soft aperiodic tasks in dynamic-priority preemptive systems. IEEE Transactions on Software Engineering 23, 388–400 (1996)
Sprunt, B., Sha, L., Lehoczky, J.: Aperiodic task scheduling for hard-real-time systems. The Journal of Real-Time Systems 1, 27–60 (1989)
Spuri, M., Buttazzo, G.: Scheduling aperiodic tasks in dynamic priority systems. Journal of Real-Time Systems 10, 1979–2012 (1996)
Strosnider, J., Lehoczky, J., Sha, L.: The deferrable server algorithm for enhanced aperiodic responsiveness in hard real-time environments. IEEE Transactions on Computers 44, 73–91 (1995)
Zhang, L.: VirtualClock: A new traffic control algorithm for packet switching networks. In: Proceedings of SIGCOMM (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Park, J., Ryu, M., Hong, S. (2005). An Efficient On-line Job Admission Control Scheme to Guarantee Deadlines for QoS-Demanding Applications. In: Yolum, p., Güngör, T., Gürgen, F., Özturan, C. (eds) Computer and Information Sciences - ISCIS 2005. ISCIS 2005. Lecture Notes in Computer Science, vol 3733. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11569596_8
Download citation
DOI: https://doi.org/10.1007/11569596_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29414-6
Online ISBN: 978-3-540-32085-2
eBook Packages: Computer ScienceComputer Science (R0)