Abstract
At early stages in the design of real-time embedded applications, the timing attributes of the computational activities are often incompletely specified or subject to changes. Later in the development cycle, schedulability analysis can be used to check the feasibility of the task set. However, the knowledge of the worst-case response times of tasks is often not sufficient to precisely determine the actions that would correct a non-schedulable design. In these situations, sensitivity analysis provides useful information for changing the implementation, by giving a measure of those computation times that must be reduced to achieve feasibility, or those that can be increased in case of a product extension, or providing the range of feasible periods for selecting the proper task activation rates.
In this work, we exploit the concept of feasibility region to propose a faster and more concise solution to the sensitivity analysis problem with respect to existing techniques based on binary search. Furthermore, we show how the formalization of other problems in the feasibility domain, such as managing overloads through elastic scheduling, can be extended to the exact analysis.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Abbreviations
- RM:
-
Rate Monotonic
- EDF:
-
Earliest Deadline First
- FP:
-
Fixed Priorities
References
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
Baruah SK (2003) Dynamic- and static-priority scheduling of recurring real-time tasks. Real-Time Syst 24(1):93–128
Baruah SK, Chen D, Gorinsky S, Mok AK (1999) Generalized multiframe tasks. Real-Time Syst 17(1):5–22
Bini E, Buttazzo GC (2004) Schedulability analysis of periodic fixed priority systems. IEEE Trans Comput 53(11):1462–1473
Bini E, Buttazzo GC (2005) Measuring the performance of schedulability tests. Real-Time Syst 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, pp 399–409
Burns A, Bernat G, Broster I (2003) A probabilistic framework for schedulability analysis. In: proceedings of the EMSOFT, Philadelphia, PA, pp 1–15
Buttazzo GC, Lipari G, Caccamo M, Abeni L (2002) Elastic scheduling for flexible workload management. IEEE Trans Comput 51(3):289–302
Buttazzo GC, Velasco M, Martí P, Fohler G (2004) Managing quality-of-control performance under overload conditions. In: Proceedings of the 16th euromicro conference on real-time systems, Catania, Italy, pp 53–60
Evidence SRL (2004) RT-druid. Available at http://www.evidence.eu.com/RT-Druid.asp
Hamann A, Henia R, Jerzak M, Racu R, Richter K, Ernst R (2004) SymTA/S symbolic timing analysis for systems. Available at http://www.symta.org
Joseph M, Pandya PK (1986) Finding response times in a real-time system. Comput J 29(5):390–395
Kuo TW, Mok AK (1991) Load adjustment in adaptive real-time systems. In: Proceedings of the 12th IEEE real-time systems symposium, San Antonio, TX, pp 160–170
Lehoczky JP (1990) Fixed priority scheduling of periodic task sets with arbitrary deadline. In: Proceedings of the 11th IEEE real-time systems symposium, Lake Buena Vista, FL, pp 201–209
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, pp 166–171
Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard real-time environment. J Assoc Comput Mach 20(1):46–61
Manolache S, Eles P, Peng Z (2001) Memory and time-efficient schedulability analysis of task sets with stochastic execution time. In: Proceedings of the 13th euromicro conference on real-time systems, Delft, The Nederlands, pp 19–26
Medina Pasaje JL, González Harbour M, Drake JM (2001) MAST real-time view: a graphic UML tool for modeling object-oriented real-time systems. In: Proceedings of the 22nd IEEE real-time systems symposium, London, UK, pp 245–256
Mok AK, Chen D (1997) A multiframe model for real-time tasks. IEEE Trans Softw Eng 23(10):635–645
Palencia JC, González Harbour M (1998) Schedulability analysis for tasks with static and dynamic offsets. In: Proceedings of the 19th IEEE real-time systems symposium, Madrid, Spain, pp 26–37
Punnekkat S, Davis R, Burns A (1997) Sensitivity analysis of real-time task sets. In: Proceedings of the 3rd Asian computing science conference on advances in computing science, Kathmandu, Nepal, pp 72–82
Racu R, Jersak M, Ernst R (2005) Applying sensitivity analysis in real-time distributed systems. In: Proceedings of the 11th real time and embedded technology and applications symposium, San Francisco, CA, pp 160–169
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, pp 188–198
Sjödin M, Hansson H (1998) Improved response-time analysis calculations. In: Proceedings of the 19th IEEE real-time systems symposium, Madrid, Spain, pp 399–408
Stankovic JA, Zhu R, Poornalingam R, Lu C, Yu Z, Humphrey M, Ellis B (2003) VEST: an aspect-based composition tool for real-time systems. In: Proceedings of the 9th real-time and embedded technology and applications symposium, Washington, DC, pp 58–69
Tindell KW, Burns A, Wellings A (1994) An extendible approach for analysing fixed priority hard real-time tasks. J Real Time Syst 6(2):133–152
Vestal S (1994) Fixed-priority sensitivity analysis for linear compute time models. IEEE Trans Softw Eng 20(4):308–317
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bini, E., Di Natale, M. & Buttazzo, G. Sensitivity analysis for fixed-priority real-time systems. Real-Time Syst 39, 5–30 (2008). https://doi.org/10.1007/s11241-006-9010-1
Received:
Accepted:
Published:
Issue date:
DOI: https://doi.org/10.1007/s11241-006-9010-1