Abstract
It is well known that the performance of computer controlled systems is heavily affected by delays and jitter occurring in the control loops, which are mainly caused by the interference introduced by other concurrent activities. A common approach adopted to reduce delay and jitter in periodic task systems is to decrease relative deadlines as much as possible, but without jeopardizing the schedulability of the task set.
In this paper, we formally characterize the region of admissible deadlines so that the system designer can appropriately select the desired values to maximize a given performance index defined over the task set. Finally we also provide a sufficient region of feasible deadlines which is proved to be convex.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Balbastre P, Ripoll I, Crespo A (2006) Optimal deadline assignment for periodic real-time tasks in dynamic priority systems. In: Proceedings of the 18th Euromicro conference on real-time systems, Dresden, Germany, July 2006, pp 65–74
Baruah SK, Burns A (2006) Sustainable schedulability analysis. In: Proceedings of the 27th IEEE real-time systems symposium, Rio de Janeiro, Brazil, December 2006, pp 159–168
Baruah SK, Howell R, Rosier L (1990) Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Systems 2:301–324
Baruah SK, Buttazzo G, Gorinsky S, Lipari G (1999) Scheduling periodic task systems to minimize output jitter. In: Proceedings of the 6th international conference on real-time computing systems and applications, Hong Kong, December 1999, pp 62–69
Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real-Time Systems 30(1–2):129–154
Bini E, Di Natale M (2005) Optimal task rate selection in fixed priority systems. In: Proceedings of the 26th IEEE real-time systems symposium, Miami, FL, USA, December 2005, pp 399–409
Bini E, Di Natale M, Buttazzo GC (2006) Sensitivity analysis for fixed-priority real-time systems. In: Proceedings of the 18th Euromicro conference on real-time systems, Dresden, Germany, July 2006, pp 13–22
Buttazzo G, Cervin A (2006) Analysis and evaluation of jitter control methods. Technical report RETIS-TR06-01, Scuola Superiore Sant’Anna, Pisa, Italy
Buttazzo G, Sensini F (1999) Optimal deadline assignment for scheduling soft aperiodic task in hard real-time environments. IEEE Trans Comput 48(10):1035–1052
Cervin A (1999) Improved scheduling of control tasks. In: Proceedings of the 11th Euromicro conference on real-time systems, York, UK, June 1999, pp 4–10
Cervin A, Lincoln B, Eker J, Årzén K-E, Buttazzo G (2004) The jitter margin and its application in the design of real-time control systems. In: Proceedings of the 10th international conference on real-time and embedded computing systems and applications, Göteborg, Sweden, August 2004
Chantem T, Sharon Hu X, Lemmon MD (2006) Generalized elastic scheduling. In: Proceedings of the 27th IEEE real-time systems symposium, Rio de Janeiro, Brazil, December 2006, pp 236–245
Crespo A, Ripoll I, Albertos P (1999) Reducing delays in RT control: the control action interval. In: Proceedings of the 14th IFAC World Congress, Beijing, China, July 1999, pp 257–262
Davidson C (1973) Random sampling and random delays in optimal control. PhD thesis, Department of Optimization and Systems Theory, Royal Institute of Technology, Sweden
Di Natale M, Stankovic JA (2000) Scheduling distributed real-time tasks with minimum jitter. IEEE Trans Comput 49(4):303–316
Hoang H, Buttazzo G, Jonsson M, Karlsson S (2006) Computing the minimum EDF feasible deadline in periodic systems. In: Proceedings of the 12th IEEE international conference on embedded and real-time computing systems and applications, Sydney, Australia, August 2006, pp 125–134
Kalman RE, Bertram JE (1959) A unified approach to the theory of sampling systems. J Franklin Inst 267:405–436
Kushner HJ, Tobias L (1969) On the stability of randomly sampled systems. IEEE Trans Autom Control 14(4):319–324
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J Assoc Comput Mach 20(1):46–61
Lluesma M, Cervin A, Balbastre P, Ripoll I, Crespo A (2006) Jitter evaluation of real-time control systems. In: Proceedings of the 12th IEEE international conference on embedded and real-time computing systems and applications, Sydney, Australia, August 2006, pp 257–260
Martí P, Fuertes JM, Ramamritham K, Fohler G (2001) Jitter compensation for real-time control systems. In: Proceedings of the 22nd IEEE real-time system symposium, London, UK, December 2001, pp 39–48
Nilsson J, Bernhardsson B, Wittenmark B (1998) Stochastic analysis and control of real-time systems with random time delays. Automatica 34(1):57–64
Racu R, Hamann A, Ernst R (2006) A formal approach to multidimensional sensitivity analysis of embedded real-time systems. In: Proceedings of the 18th Euromicro conference on real-time systems, Dresden, Germany, July 2006, pp 3–12
Seto D, Lehoczky JP, Sha L, Shin KG (1996) On task schedulability in real-time control systems. In: Proceedings of the 17th IEEE real-time systems symposium, Washington, DC, USA, December 1996, pp 13–21
Seto D, Lehoczky JP, Sha L (1998) Task period selection and schedulability in real-time systems. In: Proceedings of the 19th IEEE real-time systems symposium, Madrid, Spain, December 1998, pp 188–198
Zheng Q, Shin KG (1994) On the ability of establishing real-time channels in point-to-point packet-switched networks. IEEE Trans Commun 42(2–4):1096–1105
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bini, E., Buttazzo, G. The space of EDF deadlines: the exact region and a convex approximation. Real-Time Syst 41, 27–51 (2009). https://doi.org/10.1007/s11241-008-9060-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11241-008-9060-7