A fault-tolerant time-triggered scheduling algorithm of mixed-criticality systems
Abstract
Real-time and safety-critical systems are an integration of multiple functionalities onto a single computing platform. Some of the functionalities are safety-critical and subject to certification while the rest of the functionalities are nonsafety-critical and do not need the certification. Various researches have been done for the scheduling theory of mixed-criticality systems. But the time-triggered scheduling of mixed-criticality systems is very popular and used in industry. Since the schedule is prepared offline in a time-triggered mixed-criticality system, we need to prepare the schedule in such a way that the schedule must tolerate fault online. Hence the problem of fault-tolerance in the time-triggered system is important. This work proposes a new and novel time-triggered fault-tolerant algorithm for mixed-criticality systems. Then we show that the proposed algorithm is correct and tolerate at most one fault over the hyperperiod. Finally, we compare the proposed algorithm with the existing time-triggered scheduling algorithms for mixed-criticality systems.
References
[1]
Al-bayati Z, Caplan J, Meyerand B.H, Zeng H (2016) A four-mode model for efficient fault-tolerant mixed-criticality systems. In: 2016 Design, automation & test in Europe conference & exhibition (DATE), pp. 97–102. IEEE
[2]
Al-bayati Z, Meyer BH, Zeng H (2016) Fault-tolerant scheduling of multicore mixed-criticality systems under permanent failures. In: 2016 IEEE international symposium on defect and fault tolerance in VLSI and nanotechnology systems (DFT), pp. 57–62. IEEE
[3]
Baruah S, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, Megow N, and Stougie L Scheduling real-time mixed-criticality jobs IEEE Trans Comput 2012 61 8 1140-1152
[4]
Baruah S, Fohler G (2011) Certification-cognizant time-triggered scheduling of mixed-criticality systems. In: 32nd IEEE real-time systems symposium (RTSS), pp. 3–12. IEEE
[5]
Behera L and Bhaduri P Time-triggered scheduling of mixed-criticality systems ACM Trans Des Autom Electron Syst (TODAES) 2017 22 4 74
[6]
Behera L, Bhaduri P (2018) Time-triggered scheduling for multiprocessor mixed-criticality systems. In: International conference on distributed computing and internet technology, pp. 135–151. Springer
[7]
Behera L, Bhaduri P (2019) An energy-efficient time-triggered scheduling algorithm for mixed-criticality systems. Des Autom Embed Syst 24:79–109
[8]
Bini E and Buttazzo G Measuring the performance of schedulability tests Real-Time Syst 2005 30 1–2 129-154
[9]
Burns A and Baruah S Timing faults and mixed criticality systems 2011 6875 Berlin, Heidelberg Springer
[10]
Burns A and Davis RI A survey of research into mixed criticality systems ACM Comput. Surv. 2017
[11]
Buttazzo GC Hard real-time computing systems: predictable scheduling algorithms and applications 2011 Berlin Springer
[12]
Davis RI, Zabos A, and Burns A Efficient exact schedulability tests for fixed priority real-time systems IEEE Trans 2008 57 9 1261-1276
[13]
Deng S, Zhang C, Li C, Yin J, Dustdar S, and Zomaya AY Burst load evacuation based on dispatching and scheduling in distributed edge networks IEEE Trans Parallel Distrib Syst 2021 32 8 1918-1932
[14]
Huang P, Yang H, Thiele L (2014) On the scheduling of fault-tolerant mixed-criticality systems. In: 2014 51st ACM/EDAC/IEEE design automation conference (DAC), pp. 1–6. IEEE
[15]
Kopetz H Real-time systems: design principles for distributed embedded applications 2011 Berlin Springer
[16]
Kopetz H, Damm A, Koza C, Mulazzani M, Schwabl W, Senft C, and Zainlinger R Distributed fault-tolerant real-time systems: the mars approach IEEE Micro 1989 9 1 25-40
[17]
Kopetz H, Grunsteidl G (1993) TTP-a time-triggered protocol for fault-tolerant real-time systems. In: FTCS-23 The twenty-third international symposium on fault-tolerant computing, pp. 524–533. IEEE
[18]
Lin J, Cheng AM, Steel D, Wu MYC (2014) Scheduling mixed-criticality real-time tasks with fault tolerance. In: Workshop on mixed criticality systems
[19]
Liu CL and Layland JW Scheduling algorithms for multiprogramming in a hard-real-time environment J ACM (JACM) 1973 20 1 46-61
[20]
Liu JWSW Real-Time Systems 2000 1 Upper Saddle River, NJ, USA Prentice Hall PTR
[21]
Pathan RM Fault-tolerant and real-time scheduling for mixed-criticality systems Real-Time Syst 2014 50 4 509-547
[22]
Poledna S Fault-tolerant real-time systems: the problem of replica determinism 2007 Berlin Springer
[23]
Ranjbar B, Safaei B, Ejlali A, and Kumar A Fantom: fault tolerant task-drop aware scheduling for mixed-criticality systems IEEE Access 2020 8 187232-187248
[24]
Safari S, Hessabi S, and Ershadi G Less-mics: a low energy standby-sparing scheme for mixed-criticality systems IEEE Trans Comput-Aided Des Integr Circuits Syst 2020 39 12 4601-4610
[25]
Socci D, Poplavko P, Bensalem S, Bozga M (2013) Mixed critical earliest deadline first. In: 2013 25th Euromicro conference on real-time systems, pp 93–102
[26]
Thekkilakattil A, Burns A, Dobrin R, Punnekkat S (2015) Mixed criticality systems: beyond transient faults. In: Proc. 3rd workshop on mixed criticality systems (WMC), RTSS, pp 18–23
[27]
Thekkilakattil A, Dobrin R, Punnekkat S (2014) Mixed criticality scheduling in fault-tolerant distributed real-time systems. In: 2014 International conference on embedded systems (ICES), pp. 92–97. IEEE
[28]
Thekkilakattil A, Dobrin R, and Punnekkat S Fault tolerant scheduling of mixed criticality real-time tasks under error bursts Procedia Comput Sci 2015 46 1148-1155
[29]
Valavanis KP and Vachtsevanos GJ Handbook of unmanned aerial vehicles 2015 Berlin Springer
[30]
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, pp 239–243
[31]
Xiang Z, Deng S, Jiang F, Gao H, Tehari J, Yin J (2020) Computing power allocation and traffic scheduling for edge service provisioning. In: 2020 IEEE international conference on web services (ICWS), pp 394–403. IEEE
[32]
Xu X, Karney B (2017) An overview of transient fault detection techniques. Model Monit Pipelines Netw 7:13–37
[33]
Zeng L, Huang P, Thiele L (2016) Towards the design of fault-tolerant mixed-criticality systems on multicores. In: Proceedings of the international conference on compilers, architectures and synthesis for embedded systems, pp 1–10
[34]
Zhao H, Deng S, Liu Z, Yin J, Dustdar S (2020) Distributed redundancy scheduling for microservice-based applications at the edge. IEEE Trans Serv Comput 1–14
[35]
Zhou J, Yin M, Li Z, Cao K, Yan J, Wei T, Chen M, and Fu X Fault-tolerant task scheduling for mixed-criticality real-time systems J Circuits Syst Comput 2017 26 01 1750016
Index Terms
- A fault-tolerant time-triggered scheduling algorithm of mixed-criticality systems
Index terms have been assigned to the content through auto-classification.
Recommendations
Time-Triggered Scheduling of Mixed-Criticality Systems
Real-time and embedded systems are moving from the traditional design paradigm to integration of multiple functionalities onto a single computing platform. Some of the functionalities are safety critical and subject to certification. The rest of the ...
An energy-efficient time-triggered scheduling algorithm for mixed-criticality systems
AbstractReal-time safety-critical systems are getting more complicated due to the introduction of mixed-criticality systems. The increasing use of mixed-criticality systems has motivated the real-time systems research community to investigate various non-...
Fault-tolerant and real-time scheduling for mixed-criticality systems
The design and analysis of real-time scheduling algorithms for safety-critical systems is a challenging problem due to the temporal dependencies among different design constraints. This paper considers scheduling sporadic tasks with three ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
© The Author(s), under exclusive licence to Springer-Verlag GmbH Austria, part of Springer Nature 2021.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 March 2022
Accepted: 22 October 2021
Received: 30 October 2020
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Mar 2025