{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T22:52:05Z","timestamp":1790808725547,"version":"4.1.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,2,21]],"date-time":"2021-02-21T00:00:00Z","timestamp":1613865600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,21]],"date-time":"2021-02-21T00:00:00Z","timestamp":1613865600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003006","name":"ETH Zurich","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100003006","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Real-Time Syst"],"published-print":{"date-parts":[[2021,10]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Mixed-criticality systems often need to fulfill safety standards that dictate different requirements for each criticality level, for example given in the \u2018probability of failure per hour\u2019 format. A recent trend suggests designing this kind of systems by jointly scheduling tasks of different criticality levels on a shared platform. When this is done, the usual assumption is that tasks of lower criticality are degraded when a higher criticality task needs more resources, for example when it overruns a bound on its execution time. However, a way to quantify the impact this degradation has on the overall system is not well understood. Meanwhile, to improve schedulability and to avoid over-provisioning of resources due to overly pessimistic worst-case execution time estimates of higher criticality tasks, a new paradigm emerged where task\u2019s execution times are modeled with random variables. In this paper, we analyze a system with probabilistic execution times, and propose metrics that are inspired by safety standards. Among these metrics are the probability of deadline miss per hour, the expected time before degradation happens, and the duration of the degradation. We argue that these quantities provide a holistic view of the system\u2019s operation and schedulability.<\/jats:p>","DOI":"10.1007\/s11241-021-09365-4","type":"journal-article","created":{"date-parts":[[2021,2,21]],"date-time":"2021-02-21T16:02:26Z","timestamp":1613923346000},"page":"397-442","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Schedulability of probabilistic mixed-criticality systems"],"prefix":"10.1007","volume":"57","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0450-6116","authenticated-orcid":false,"given":"Stefan","family":"Draskovic","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rehan","family":"Ahmed","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pengcheng","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lothar","family":"Thiele","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,2,21]]},"reference":[{"key":"9365_CR1","unstructured":"Rtca\/do-178c software considerations in airborne systems and equipment certification (2012)"},{"key":"9365_CR2","doi-asserted-by":"crossref","unstructured":"Abdedda\u00efm Y, Maxim D (2017) Probabilistic schedulability analysis for fixed priority mixed criticality real-time systems. In: Design, automation and test in Europe conference and exhibition (DATE), 2017. IEEE, pp 596\u2013601","DOI":"10.23919\/DATE.2017.7927056"},{"key":"9365_CR3","unstructured":"Alahmad B, Gopalakrishnan S (2016) A risk-constrained Markov decision process approach to scheduling mixed-criticality job sets. In: Workshop on mixed criticality systems (WMC 2016)"},{"issue":"1","key":"9365_CR4","first-page":"01","volume":"5","author":"BN Alahmad","year":"2018","unstructured":"Alahmad BN, Gopalakrishnan S (2018) Risk-aware scheduling of dual criticality job systems using demand distributions. Leibniz Trans Embed Syst 5(1);01-1","journal-title":"Leibniz Trans Embed Syst"},{"issue":"2","key":"9365_CR5","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/S1474-6670(17)51283-5","volume":"24","author":"NC Audsley","year":"1991","unstructured":"Audsley NC, Burns A, Richardson MF, Wellings AJ (1991) Hard real-time scheduling: the deadline-monotonic approach. IFAC Proc Vol 24(2):127\u2013132","journal-title":"IFAC Proc Vol"},{"key":"9365_CR6","doi-asserted-by":"crossref","unstructured":"Baruah S, Fohler G (2011) Certification-cognizant time-triggered scheduling of mixed-criticality systems. In: 2011 IEEE 32nd real-time systems symposium (RTSS). IEEE, pp 3\u201312","DOI":"10.1109\/RTSS.2011.9"},{"key":"9365_CR7","doi-asserted-by":"crossref","unstructured":"Baruah SK, Bonifaci V, D\u2019Angelo G, Marchetti-Spaccamela A, Van Der Ster S, Stougie L (2011) Mixed-criticality scheduling of sporadic task systems. In: ESA. Springer, pp 555\u2013566","DOI":"10.1007\/978-3-642-23719-5_47"},{"key":"9365_CR8","doi-asserted-by":"crossref","unstructured":"Baruah SK, Burns A, Davis RI (2011) Response-time analysis for mixed criticality systems. In: 2011 IEEE 32nd real-time systems symposium (RTSS). IEEE, pp 34\u201343","DOI":"10.1109\/RTSS.2011.12"},{"issue":"6","key":"9365_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3131347","volume":"50","author":"A Burns","year":"2017","unstructured":"Burns A, Davis RI (2017) A survey of research into mixed criticality systems. ACM Comput Surv (CSUR) 50(6):1\u201337","journal-title":"ACM Comput Surv (CSUR)"},{"key":"9365_CR10","doi-asserted-by":"crossref","unstructured":"Cucu-Grosjean L, Santinelli L, Houston M, Lo C, Vardanega T, Kosmidis L, Abella J, Mezzetti E, Quinones E, Cazorla FJ (2012) Measurement-based probabilistic timing analysis for multi-path programs. In: 2012 24th Euromicro conference on real-time systems (ECRTS). IEEE, pp 91\u2013101","DOI":"10.1109\/ECRTS.2012.31"},{"issue":"1","key":"9365_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s11241-010-9106-5","volume":"47","author":"RI Davis","year":"2011","unstructured":"Davis RI, Burns A (2011) Improved priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. Real Time Syst 47(1):1\u201340","journal-title":"Real Time Syst"},{"key":"9365_CR12","unstructured":"Davis RI, Burns A, Griffin D (2017) On the meaning of pWCET distributions and their use in schedulability analysis. In: Real-time scheduling open problems seminar at ECRTS"},{"issue":"1","key":"9365_CR13","first-page":"1","volume":"6","author":"RI Davis","year":"2019","unstructured":"Davis RI, Cucu-Grosjean L (2019) A survey of probabilistic schedulability analysis techniques for real-time systems. Leibniz Trans Embed Syst 6(1):1\u201353","journal-title":"Leibniz Trans Embed Syst"},{"issue":"1","key":"9365_CR14","first-page":"03-1","volume":"6","author":"RI Davis","year":"2019","unstructured":"Davis RI, Cucu-Grosjean L (2019) A survey of probabilistic timing analysis techniques for real-time systems. Leibniz Trans Embed Syst 6(1):03-1","journal-title":"Leibniz Trans Embed Syst"},{"key":"9365_CR15","doi-asserted-by":"crossref","unstructured":"Devgan A, Kashyap C (2003) Block-based static timing analysis with uncertainty. In: Proceedings of the 2003 IEEE\/ACM international conference on computer-aided design. IEEE Computer Society, p 607","DOI":"10.1109\/ICCAD.2003.159744"},{"key":"9365_CR16","doi-asserted-by":"crossref","unstructured":"D\u00edaz JL, Garc\u00eda DF, Kim K, Lee CG, Bello LL, L\u00f3pez JM, Min SL, Mirabella O (2002) Stochastic analysis of periodic real-time systems. In: 23rd IEEE real-time systems symposium, 2002. RTSS 2002. IEEE, pp 289\u2013300","DOI":"10.1109\/REAL.2002.1181583"},{"key":"9365_CR17","unstructured":"D\u00edaz JL, L\u00f3pez JM (2004) Safe extensions to the stochastic analysis of real-time systems. Technical report. Departamento de Informatica, University of Oviedo. http:\/\/www.atc.uniovi.es\/research\/SESARTS04.pdf. Accessed 1 Oct 2019"},{"key":"9365_CR18","doi-asserted-by":"crossref","unstructured":"D\u00edaz JL, L\u00f3pez JM, Garcia M, Campos AM, Kim K, Bello LL (2004) Pessimism in the stochastic analysis of real-time systems: concept and applications. In: 25th IEEE international real-time systems Symposium, 2004. Proceedings. IEEE, pp 197\u2013207","DOI":"10.1109\/REAL.2004.41"},{"key":"9365_CR19","unstructured":"Draskovic S, Huang P, Thiele L (2016) On the safety of mixed-criticality scheduling. In: Workshop on mixed criticality systems (WMC 2016)"},{"key":"9365_CR20","unstructured":"Durrieu G, Faugere M, Girbal S, P\u00e9rez DG, Pagetti C, Puffitsch W (2014) Predictable flight management system implementation on a multicore processor. In: Embedded real time software (ERTS\u201914)"},{"key":"9365_CR21","doi-asserted-by":"crossref","unstructured":"Ekberg P, Yi W (2012) Outstanding paper award: bounding and shaping the demand of mixed-criticality sporadic tasks. In: 2012 24th Euromicro conference on real-time systems (ECRTS). IEEE, pp 135\u2013144","DOI":"10.1109\/ECRTS.2012.24"},{"issue":"5","key":"9365_CR22","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1109\/MDAT.2016.2594790","volume":"33","author":"R Ernst","year":"2016","unstructured":"Ernst R, Di Natale M (2016) Mixed criticality systems\u2014a history of misconceptions? IEEE Des Test 33(5):65\u201374","journal-title":"IEEE Des Test"},{"key":"9365_CR23","doi-asserted-by":"crossref","unstructured":"Guo Z, Santinelli L, Yang K (2015) EDF schedulability analysis on mixed-criticality systems with permitted failure probability. In: 2015 IEEE 21st international conference on embedded and real-time computing systems and applications (RTCSA). IEEE, pp 187\u2013196","DOI":"10.1109\/RTCSA.2015.8"},{"key":"9365_CR24","doi-asserted-by":"crossref","unstructured":"Huang P, Giannopoulou G, Stoimenov N, Thiele L (2014) Service adaptions for mixed-criticality systems. In: 2014 19th Asia and South Pacific design automation conference (ASP-DAC). IEEE, pp 125\u2013130","DOI":"10.1109\/ASPDAC.2014.6742877"},{"key":"9365_CR25","unstructured":"K\u00fcttler M, Roitzsch M, Hamann CJ, Volp M (2017) Probabilistic analysis of low-criticality execution. In: Workshop on mixed criticality systems (WMC 2017)"},{"issue":"2","key":"9365_CR26","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1007\/s11241-008-9053-6","volume":"40","author":"JM L\u00f3pez","year":"2008","unstructured":"L\u00f3pez JM, D\u00edaz JL, Entrialgo J, Garc\u00eda D (2008) Stochastic analysis of real-time systems under preemptive priority-driven scheduling. Real Time Syst 40(2):180","journal-title":"Real Time Syst"},{"key":"9365_CR27","doi-asserted-by":"crossref","unstructured":"Masrur A (2016) A probabilistic scheduling framework for mixed-criticality systems. In: Proceedings of the 53rd annual design automation conference. ACM, p 132","DOI":"10.1145\/2897937.2897971"},{"key":"9365_CR28","doi-asserted-by":"crossref","unstructured":"Maxim D, Buffet O, Santinelli L, Cucu-Grosjean L, Davis RI (2011) Optimal priority assignment algorithms for probabilistic real-time systems. In: RTNS, pp 129\u2013138","DOI":"10.1109\/WFCS.2010.5548602"},{"key":"9365_CR29","doi-asserted-by":"crossref","unstructured":"Maxim D, Davis RI, Cucu-Grosjean L, Easwaran A (2017) Probabilistic analysis for mixed criticality systems using fixed priority preemptive scheduling. In: Proceedings of the 25th international conference on real-time networks and systems. ACM, pp 237\u2013246","DOI":"10.1145\/3139258.3139276"},{"key":"9365_CR30","doi-asserted-by":"crossref","unstructured":"Pagetti C, Saussi\u00e9 D, Gratia R, Noulard E, Siron P (2014) The ROSACE case study: from simulink specification to multi\/many-core execution. In: 2014 IEEE 20th real-time and embedded technology and applications symposium (RTAS). IEEE, pp 309\u2013318","DOI":"10.1109\/RTAS.2014.6926012"},{"key":"9365_CR31","doi-asserted-by":"crossref","unstructured":"Park T, Kim S (2011) Dynamic scheduling algorithm and its schedulability analysis for certifiable dual-criticality systems. In: Proceedings of the ninth ACM international conference on Embedded software. ACM, pp 253\u2013262","DOI":"10.1145\/2038642.2038681"},{"key":"9365_CR32","unstructured":"Santinelli L, George L (2015) Probabilities and mixed-criticalities: the probabilistic c-space. In: Proceedings of the workshop on mixed criticality systems (WMC 2015)"},{"key":"9365_CR33","doi-asserted-by":"crossref","unstructured":"Santinelli L, Guo Z (2018) A sensitivity analysis for mixed criticality: trading criticality with computational resource. In: 2018 IEEE 23rd international conference on emerging technologies and factory automation (ETFA), vol 1. IEEE, pp 313\u2013320","DOI":"10.1109\/ETFA.2018.8502493"},{"key":"9365_CR34","doi-asserted-by":"crossref","unstructured":"Santinelli L, Guo Z, George L (2016) Fault-aware sensitivity analysis for probabilistic real-time systems. In: 2016 IEEE international symposium on defect and fault tolerance in VLSI and nanotechnology systems (DFT), pp 69\u201374","DOI":"10.1109\/DFT.2016.7684072"},{"issue":"3","key":"9365_CR35","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1145\/2700103","volume":"14","author":"D T\u0103ma\u015f-Selicean","year":"2015","unstructured":"T\u0103ma\u015f-Selicean D, Pop P (2015) Design optimization of mixed-criticality real-time embedded systems. ACM Trans Embed Comput Syst 14(3):50","journal-title":"ACM Trans Embed Comput Syst"},{"key":"9365_CR36","doi-asserted-by":"crossref","unstructured":"Vestal S (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: 28th IEEE international real-time systems symposium, 2007. RTSS 2007. IEEE, pp 239\u2013243","DOI":"10.1109\/RTSS.2007.47"}],"container-title":["Real-Time Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-021-09365-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11241-021-09365-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11241-021-09365-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,23]],"date-time":"2021-08-23T20:27:52Z","timestamp":1629750472000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11241-021-09365-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,21]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,10]]}},"alternative-id":["9365"],"URL":"https:\/\/doi.org\/10.1007\/s11241-021-09365-4","relation":{},"ISSN":["0922-6443","1573-1383"],"issn-type":[{"value":"0922-6443","type":"print"},{"value":"1573-1383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,21]]},"assertion":[{"value":"16 January 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 February 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}