×

Schedulability and sensitivity analysis of multiple criticality tasks with fixed-priorities. (English) Zbl 1213.68145

Summary: Safety-critical real-time standards define several criticality levels for the tasks. In this paper we consider the real-time systems designed under the DO-178B safety assessment process (i.e., Software Considerations in Airborne Systems and Equipment Certification). Vestal introduced a new multiple criticality task model to efficiently take into account criticality levels in the schedulability analysis of such systems. Such a task model represents a potentially very significant advance in the modeling of safety-critical real-time softwares. Baruah and Vestal continue this investigation, with a new scheduling algorithm combining fixed and dynamic priority policies. Another major design issue is to allow a system developer to determine how sensitive is the schedulability analysis to changes in execution time of various software components.
In this paper, we first prove that the well-known Audsley’s algorithm is optimal for assigning priorities to tasks with multiple criticality levels. We then provide a proof on the optimality of Vestal’s algorithm for optimizing the resource requirements to schedule tasks with multiple criticality levels. We then present a sensitivity analysis for multiple criticality tasks that is based on Bini et al. results on sporadic tasks.

MSC:

68M20 Performance evaluation, queueing, and scheduling in the context of computer systems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] ARINC: Avionics application software standard interface. ARINC Spec 653 (1997)
[2] Audsley N (1991) Optimal priority assignment and feasibility of static priority tasks with arbitrary start times. Technical report YCS 164, Dept. Computer Science, University of York, UK
[3] Audsley N, Burns A, Richardson M, Tindell K, Wellings AJ (1993) Applying new scheduling theory to static priority pre-emptive scheduling. Softw Eng J 8:284–292 · doi:10.1049/sej.1993.0034
[4] Authority F (1992) Software considerations in airborne systems and equipment certification. RTCA Inc: EUROCAE
[5] Balbastre P, Ripoll I, Crespo A (2009) Period sensitivity analysis and d-p domain feasibility region in dynamic priority systems. J Syst Softw 82:1098–1111 · doi:10.1016/j.jss.2009.01.040
[6] Baruah S, Li H, Stougie L (2010) Scheduling for certifiability in mixed criticality systems. In: The real-time technology and applications symposium. Pre-publication
[7] Baruah S, Vestal S (2008) Schedulability analysis of sporadic tasks with multiple criticality specifications. In: ECRTS ’08: Proceedings of the 2008 Euromicro conference on real-time systems. IEEE Comput Soc, Washington, pp 147–155
[8] Bini E, Buttazzo G (2004) Schedulability analysis of periodic fixed priority systems. Comput IEEE Trans 53(11):1462–1473 · doi:10.1109/TC.2004.103
[9] Bini E, Buttazzo G (2009) The space of EDF deadlines: the exact region and a convex approximation. Real-Time Syst 41:27–51 · Zbl 1170.93358 · doi:10.1007/s11241-008-9060-7
[10] Bini E, Di Natale M, Buttazzo G (2008) Sensitivity analysis for fixed-priority real-time systems. Real-Time Syst 39(1–3):5–30 · Zbl 1141.68020 · doi:10.1007/s11241-006-9010-1
[11] Bougueroua L, George L, Midonnet S (2007) Dealing with execution-overruns to improve the temporal robustness of real-time systems scheduled fp and edf. In: The second international conference on systems (ICONS’07)
[12] Joseph M, Pandya P (1986) Finding response times in a real-time system. Comput J 29(5):390–395 · doi:10.1093/comjnl/29.5.390
[13] Katcher D, Arakawa H, Strosnider J (1993) Engineering and analysis of fixed priority scheduler. IEEE Trans Softw Eng 19(9):920–934 · Zbl 05114404 · doi:10.1109/32.241774
[14] Klein M, Ralaya T, Pollak B, Obebza R, Harbour M (1993) Guide to rate monotonic analysis for real-time systems. Kluwer Academic, Norwell
[15] Lehoczky J (1990) Fixed priority scheduling of periodic task sets with arbitrary deadlines. In: Proceedings of the 11th real-time systems symposium, pp 201–209
[16] Lehoczky JP, Sha L, Ding Y The rate monotonic scheduling algorithm-exact characterization and average case behavior. In: Real-time system symposium (1989)
[17] Liu CL, Layland JW (1973) Scheduling algorithms for multiprogramming in a hard-real-time environment. J ACM 20(1):46–61 · Zbl 0265.68013 · doi:10.1145/321738.321743
[18] Punnekkat S, Davis R, Burns A (1997) Sensitivity analysis of real-time task sets. In: Advances in computing science, LNCS, vol 1345, Springer, Berlin, pp 72–82
[19] Racu R, Hamann A, Ernst R (2008) Sensitivity analysis of complex embedded real-time systems. Real-Time Syst 39:31–72 · Zbl 1140.68346 · doi:10.1007/s11241-007-9039-9
[20] Sha L, Lehoczky JP, Rajkumar R (1986) Solutions for some practical problems in prioritized preemptive scheduling. In: Proceedings IEEE real-time systems symposium. IEEE Comput Soc, Los Alamitos, pp 181–191.
[21] Vestal S (1994) Fixed-priority sensitivity analysis for linear compute time models. IEEE Trans Softw Eng 20(4):308–317 · Zbl 05113668 · doi:10.1109/32.277577
[22] Vestal S (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: RTSS ’07: proceedings of the 28th IEEE international real-time systems symposium. IEEE Comput Soc, Washington, pp 239–243
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.