Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Real-Time Systems
Published in: Real-Time Systems 5/2012

01-09-2012

On-line schedulability tests for adaptive reservations in fixed priority scheduling

Authors: Rodrigo Santos, Giuseppe Lipari, Enrico Bini, Tommaso Cucinotta

Published in: Real-Time Systems | Issue 5/2012

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Adaptive reservation is a real-time scheduling technique in which each application is associated a fraction of the computational resource (a reservation) that can be dynamically adapted to the varying requirements of the application by using appropriate feedback control algorithms. An adaptive reservation is typically implemented by using an aperiodic server (e.g. sporadic server) algorithm with fixed period and variable budget. When the feedback law demands an increase of the reservation budget, the system must run a schedulability test to check if there is enough spare bandwidth to accommodate such increase. The schedulability test must be very fast, as it may be performed at each budget update, i.e. potentially at each instance of a task; yet, it must be as efficient as possible, to maximize resource usage.
In this paper, we tackle the problem of performing an efficient on-line schedulability test for adaptive resource reservations in fixed priority schedulers. In the literature, a number of algorithms have been proposed for on-line admission control in fixed priority systems. We describe four of these tests, with increasing complexity and performance. In addition, we propose a novel on-line test, called Spare-Pot algorithm, which has been specifically designed for the problem at hand, and which shows a good cost/performance ratio compared to the other tests.
previous article Performance debugging of Esterel specifications

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
2
See the FRESCOR API implementation at http://​www.​frescor.​org.
 
Literature
Abeni L, Buttazzo G (1998) Integrating multimedia applications in hard real-time systems. In: Proc 19th IEEE real time systems symposium
Abeni L, Buttazzo G (1998) Integrating multimedia applications in hard real-time systems. In: Proceedings of the 19th IEEE real-time systems symposium, Madrid, Spain, December 1998, pp 4–13
Abeni L, Palopoli L, Buttazzo G (2000) On adaptive control techniques in real-time resource allocation. In: Proceedings of the 12th Euromicro conference on real-time systems, Stockholm, Sweden, June 2000, pp 129–136
Abeni L, Palopoli L, Lipari G, Walpole J (2002) Analysis of a reservation feedback scheduler. In: Proc 23rd IEEE real time systems symposium
Abeni L, Cucinotta T, Lipari G, Marzario L, Palopoli L (2005) Qos management through adaptive reservations. Real-Time Syst, 29(2–3):131–155 MATHCrossRef
Almeida L, Anand M, Fischmeister S, Lee I (2007) A dynamic scheduling approach to designing flexible safety-critical systems categories and subject descriptors. In: Proc of the 7th annual ACM conference on embedded software EMSOFT
Audsley NC, Burns A, Richardson M, Tindell KW, Wellings AJ (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8(5):284–292 CrossRef
Bini E, Buttazzo GC (2004) Schedulability analysis of periodic fixed priority systems. IEEE Trans Comput 53(11):1462–1473 CrossRef
Bini E, Buttazzo GC, Buttazzo GM (2003) Rate monotonic scheduling: the hyperbolic bound. IEEE Trans Comput 52(7):933–942 CrossRef
Bini E, Di Natale M, Buttazzo GC (2007) Sensitivity analysis for fixed-priority real-time systems. Real-Time Syst 39(1–3):5–30
Bini E, Huyen T, Nguyen C, Richard P, Baruah SK (2009) A response-time bound in fixed-priority scheduling with arbitrary deadlines. IEEE Trans Comput 58(2):279–286 MathSciNetCrossRef
Block A, Brandenburg B, Anderson JH, Quint S (2008) An adaptive framework for multiprocessor real-time system. In: Euromicro conference on real-time systems. ECRTS’08, July 2008, pp 23–33 CrossRef
Burchard A, Liebeherr J, Oh Y, Son SH (1995) New strategies for assigning real-time tasks to multiprocessor systems. IEEE Trans Comput 44(12):1429–1442 MathSciNetMATHCrossRef
Buttazzo G, Lipari G, Caccamo M, Abeni L (2002) Elastic scheduling for flexible workload management. IEEE Trans Comput 51(3):289–302 CrossRef
Buttazzo G, Lipari G, Abeni L, Caccamo M (2005) Soft real-time systems: predictability vs. efficiency. Springer, Berlin MATH
Caccamo M, Buttazzo G, Sha L (2000a) Elastic feedback control. In: IEEE proceedings of the 12th Euromicro conference on real-time systems, pp 121–128 CrossRef
Caccamo M, Buttazzo G, Sha L (2000b) Capacity sharing for overrun control. In: Proceedings of the 21st IEEE real-time systems symposium, Orlando (FL), USA, December 2000, pp 295–304 CrossRef
Caccamo M, Buttazzo GC, Thomas DC (2005) Efficient reclaiming in reservation-based real-time systems with variable execution times. IEEE Trans Comput 54(2):198–213 CrossRef
Chen D, Mok AK, Kuo T-W (2003) Utilization bound revisited. IEEE Trans Comput 52(3):351–361 CrossRef
Cucinotta T, Palopoli L (2007) Feedback scheduling for pipelines of tasks. In: Proceedings of the 10th international conference on hybrid systems: computation and control, HSCC’07. Springer, Berlin, pp 131–144
Cucinotta T, Palopoli L, Marzario L (2004a) Stochastic feedback-based control of qos in soft real-time systems. In: 43rd IEEE conference on decision and control, 2004. CDC, vol 4, pp 3533–3538
Cucinotta T, Palopoli L, Marzario L, Lipari G, Abeni L (2004b) Adaptive reservations in a Linux environment. In: Proc of 10th IEEE real-time and embedded technology and applications symposium
Cucinotta T, Abeni L, Palopoli L, Lipari G (2011) A robust mechanism for adaptive scheduling of multimedia applications. ACM Trans Embed Comput Syst 10(4):1–24 CrossRef
Han C-C, Tyan H-y (1997) A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithm. In: Proceedings of the 18th IEEE real-time systems symposium, San Francisco (CA), USA, December 1997, pp 36–45
Lauzac S, Melhem R, Mossé D (2003) An improved rate-monotonic admission control and its applications. IEEE Trans Comput 52(3):337–350 CrossRef
Lee C-G, Sha L, Peddi A (2004) Enhanced utilization bounds for QoS management. IEEE Trans Comput 53(2):187–200 CrossRef
Lehoczky JP, Sha L, Ding Y (1989) The rate-monotonic scheduling algorithm: exact characterization and average case behavior. In: Proceedings of the 10th IEEE real-time systems symposium, Santa Monica (CA), USA, December 1989, pp 166–171
Lipari G, Baruah SK (2000) Greedy reclamation of unused bandwidth in constant bandwidth servers. In: Proceedings of the 12th Euromicro conference on real-time systems, Stockholm, Sweden, June 2000
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J Assoc Comput Mach 20(1):46–61 MathSciNetMATHCrossRef
Lu C, Stankovic J, Tao G, Son S (2002) Feedback control real-time scheduling: framework, modeling and algorithms. Real-Time Syst 23:85–126 MATHCrossRef
Manabe Y, Aoyagi S (1998) A feasibility decision algorithm for rate monotonic and deadline monotonic scheduling. Real-Time Syst 14(2):171–181 CrossRef
Marzario L, Lipari G, Balbastre P, Crespo A (2004) Iris: A new reclaiming algorithm for server-based real-time systems. In: IEEE real-time and embedded technology and applications symposium, pp 211–218
Masrur A, Chakraborty S (2011) Near-optimal constant-time admission control for DM tasks via non-uniform approximations. In: Proceedings of the 17th IEEE real-time and embedded technology and applications symposium (RTAS), Chicago, IL, USA, pp 57–67 CrossRef
Palopoli L, Abeni L, Lipari G (2003a) On the applications of hybrid control to CPU reservations. In: Proc of hybrid systems computation and control HSCC03. LNCS
Palopoli L, Cucinotta T, Bicchi A (2003b) Quality of service control in soft real-time application. In: Proc 42nd IEEE conference on decision and control, December 2003 pp 664–669
Palopoli L, Abeni L, Cucinotta T, Lipari G, Baruah SK (2008) Weighted feedback reclaiming for multimedia applications. In: IEEE/ACM/IFIP workshop on embedded systems for real-time multimedia. ESTImedia 2008, October 2008 pp 121–126 CrossRef
Park D-W, Natarajan S, Kanevsky A, Kim MJ (1995) A generalized utilization bound test for fixed-priority real-time scheduling. In: Proceedings of the 2nd international workshop on real-time systems and applications, Tokyo, Japan, October 1995, pp 73–77
Rajkumar R, Juvva K, Molano A, Oikawa S (1998) Resource kernels: A resource-centric approach to real-time and multimedia systems. In: Proc of the SPIE/ACM conference on multimedia computing and networking, January 1998
Sprunt B, Sha L, Lehoczky JP (1989) Aperiodic task scheduling for hard-real-time systems. Real-Time Syst 1:27–60 CrossRef
Stankovic JA, Lu C, Son SH (1998) The case for feedback control in real-time scheduling. In: Proceedings of the IEEE Euromicro conference on real-time, York, England, June 1998
Zabos A, Davis R, Burns A, Gonzalez Harbour M (2009) Spare capacity distribution using exact response-time analysis. In: 17th international conference on real-time and network systems, Paris, France, October 2009
Metadata
Title
On-line schedulability tests for adaptive reservations in fixed priority scheduling
Authors
Rodrigo Santos
Giuseppe Lipari
Enrico Bini
Tommaso Cucinotta
Publication date
01-09-2012
Publisher
Springer US
Published in
Real-Time Systems / Issue 5/2012
Print ISSN: 0922-6443
Electronic ISSN: 1573-1383
DOI
https://doi.org/10.1007/s11241-012-9156-y

Premium Partner

    Image Credits