More Web Proxy on the site http://driver.im/

article

Exact admission-control for integrated aperiodic and periodic tasks

Authors:

Björn Andersson,

Cecilia EkelinAuthors Info & Claims

Journal of Computer and System Sciences, Volume 73, Issue 2

Pages 225 - 241

https://doi.org/10.1016/j.jcss.2006.04.001

Published: 01 March 2007 Publication History

Abstract

Admission-controllers are used to prevent overload in systems with dynamically arriving tasks. Typically, these admission-controllers are based on sufficient (but not necessary) capacity bounds in order to maintain a low computational complexity. In this paper we present how exact admission-control for aperiodic tasks can be efficiently obtained. Our first result is an admission-controller for purely aperiodic task sets where the test has the same runtime complexity as utilization-based tests. Our second result is an extension of the previous controller for a baseload of periodic tasks. The runtime complexity of this test is lower than for any known exact admission-controller. In addition to presenting our main algorithm and evaluating its performance, we also discuss some general issues concerning admission-controllers and their implementation.

References

[1]

Liu, C.L. and Layland, J.W., Scheduling algorithms for multiprogramming in a hard-real-time environment. J. Assoc. Comput. Mach. v20 i1. 46-61.

[2]

B. Andersson, Static-priority scheduling on multiprocessors, PhD thesis, Department of Computer Engineering, Chalmers University of Technology, Göteborg, Sweden, September 2003

[3]

T. Abdelzaher, C. Lu, Schedulability analysis and utilization bounds for highly scalable real-time services, in: Proc. of the IEEE Real-Time Technology and Applications Symposium, Taipei, Taiwan, May 30--June 21, 2001, pp. 15--25

[4]

B. Andersson, T. Abdelzaher, J. Jonsson, Partitioned aperiodic scheduling on multiprocessors, in: Proc. of the IEEE International Parallel and Distributed Processing Symposium, Nice, France, April 22--26, 2001

[5]

Knuth, D.E., The Art of Computer Programming, vol. 3. Sorting and Searching. Addison--Wesley, Reading, MA.

[6]

Abdelzaher, T.A. and Lu, C., A utilization bound for aperiodic tasks and priority driven scheduling. IEEE Trans. Comput. v53 i3. 334-350.

[7]

Stankovic, J.A., Spuri, M., Ramamritham, K. and Buttazzo, G.C., Fundamentals of EDF scheduling. In: Deadline Scheduling for Real-Time Systems, Kluwer Academic, Boston. pp. 27-65.

[8]

Wirth, N., Algorithms + Data Structures = Programs. Prentice Hall, Englewood Cliffs, NJ.

[9]

S. Baruah, G. Koren, B. Mishra, A. Raghunathan, L. Rosier, D. Shasha, On-line scheduling in the presence of overload, in: Proc. of the IEEE Symposium on Foundations of Computer Science, San Juan, Puerto Rico, October 1991, pp. 100--110

[10]

L. Abeni, G. Buttazzo, Integrating multimedia applications in hard real-time systems, in: Proc. of the IEEE Real-Time Systems Symposium, Madrid, Spain, December 2--4, 1998, pp. 4--13

[11]

T.F. Abdelzaher, B. Andersson, J. Jonsson, V. Sharma, M. Nguyen, The aperiodic multiprocessor utilization bound for liquid tasks, in: Proc. of the IEEE Real-Time Technology and Applications Symposium, San José, California, September 25--27 2002, pp. 173--186

[12]

Chetto, H. and Chetto, M., Some results of the earliest deadline scheduling algorithm. IEEE Trans. Softw. Engrg. v15 i10. 1261-1269.

[13]

G. Fohler, Joint scheduling of distributed complex periodic and hard aperiodic tasks in statically scheduled systems, in: Proc. of the IEEE Real-Time Systems Symposium, Pisa, Italy, December 5--7, 1995, pp. 152--161

[14]

Tia, T.-S., Liu, J.W.-S., Sun, J. and Ha, R., A linear-time optimal acceptance test for scheduling of hard real-time tasks.

[15]

L. Abeni, L. Palopoli, G. Lipari, J. Walpole, Analysis of a reservation-based feedback scheduler, in: Proc. of the IEEE Real-Time Systems Symposium, Austin, Texas, December 3--5 2002, pp. 71--80

[16]

G. Lipari, S. Baruah, Efficient scheduling of real-time multi-task applications in dynamic systems, Proc. of the IEEE Real-Time Technology and Applications Symposium, Washington, DC, USA, May 31--June 2, 2000, pp. 166--175

[17]

D.S. Johnson, Near-optimal bin-packing algorithms, PhD thesis, Massachusetts Institute of Technology, 1974

[18]

B. Andersson, S. Baruah, J. Jonsson, Static-priority scheduling on multiprocessors, in: Proc. of the IEEE Real-Time Systems Symposium, London, UK, December 3--6, 2001, pp. 193--202

[19]

Martello, S. and Toth, P., Knapsack Problems: Algorithms and Computer Implementations. Wiley, Chichester.

Cited By

Piva MColetta AMaselli GStankovic J(2021)Environment-driven Communication in Battery-free Smart BuildingsACM Transactions on Internet of Things10.1145/34487392:2(1-30)Online publication date: 22-Apr-2021
https://dl.acm.org/doi/10.1145/3448739
Leng CQiao YHu XWang H(2015)Utilization-based admission control for aperiodic tasks under EDF schedulingReal-Time Systems10.1007/s11241-014-9216-651:1(36-76)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1007/s11241-014-9216-6

Index Terms

Recommendations

Global EDF-based scheduling with laxity-driven priority promotion

This paper presents an algorithm, called Earliest Deadline Critical Laxity (EDCL), for scheduling sporadic task systems on multiprocessors. EDCL is a derivative of the Earliest Deadline Zero Laxity (EDZL) algorithm. Each job is assigned a priority based ...
DC/sup 2/ scheduling for aperiodic tasks in strongly partitioned real-time systems
RTCSA '00: Proceedings of the Seventh International Conference on Real-Time Systems and Applications

The strongly partitioned real time system (SP-RTS) provides temporal and spatial partitioning for its integrated real time applications. The SP-RTS architecture adopts a two-level hierarchical scheduling mechanism. In the lower level, multiple ...
Preference-oriented fixed-priority scheduling for periodic real-time tasks

A preference priority assignment (PPA) scheme that explicitly incorporates the ASAP and ALAP execution preferences of periodic real-time tasks is proposed.An online dual-queue based preference-oriented fixed- priority (POFP) scheduler is proposed 4, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Computer and System Sciences

Journal of Computer and System Sciences Volume 73, Issue 2

March, 2007

90 pages

ISSN:0022-0000

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2006.

Publisher

Academic Press, Inc.

United States

Publication History

Published: 01 March 2007

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Piva MColetta AMaselli GStankovic J(2021)Environment-driven Communication in Battery-free Smart BuildingsACM Transactions on Internet of Things10.1145/34487392:2(1-30)Online publication date: 22-Apr-2021
https://dl.acm.org/doi/10.1145/3448739
Leng CQiao YHu XWang H(2015)Utilization-based admission control for aperiodic tasks under EDF schedulingReal-Time Systems10.1007/s11241-014-9216-651:1(36-76)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1007/s11241-014-9216-6

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents