A fault-tolerant time-triggered scheduling algorithm of mixed-criticality systems. (English) Zbl 1494.68030
Summary: 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.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68M15 | Reliability, testing and fault tolerance of networks and computer systems |
Keywords:
real-time systems; mixed-criticality systems; fault-tolerance; time-triggered schedule; TT-merge algorithmReferences:
| [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.; Stougie, L., Scheduling real-time mixed-criticality jobs, IEEE Trans Comput, 61, 8, 1140-1152 (2012) · Zbl 1365.90132 · doi:10.1109/TC.2011.142 |
| [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.; Bhaduri, P., Time-triggered scheduling of mixed-criticality systems, ACM Trans Des Autom Electron Syst (TODAES), 22, 4, 74 (2017) |
| [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.; Buttazzo, G., Measuring the performance of schedulability tests, Real-Time Syst, 30, 1-2, 129-154 (2005) · Zbl 1083.68008 · doi:10.1007/s11241-005-0507-9 |
| [9] | Burns, A.; Baruah, S., Timing faults and mixed criticality systems (2011), Berlin, Heidelberg: Springer, Berlin, Heidelberg |
| [10] | Burns, A.; Davis, RI, A survey of research into mixed criticality systems, ACM Comput. Surv. (2017) · doi:10.1145/3131347 |
| [11] | Buttazzo, GC, Hard real-time computing systems: predictable scheduling algorithms and applications (2011), Berlin: Springer, Berlin · Zbl 1246.68001 · doi:10.1007/978-1-4614-0676-1 |
| [12] | Davis, RI; Zabos, A.; Burns, A., Efficient exact schedulability tests for fixed priority real-time systems, IEEE Trans, 57, 9, 1261-1276 (2008) · Zbl 1390.68122 |
| [13] | Deng, S.; Zhang, C.; Li, C.; Yin, J.; Dustdar, S.; Zomaya, AY, Burst load evacuation based on dispatching and scheduling in distributed edge networks, IEEE Trans Parallel Distrib Syst, 32, 8, 1918-1932 (2021) · doi:10.1109/TPDS.2021.3052236 |
| [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, Berlin · Zbl 1226.68001 · doi:10.1007/978-1-4419-8237-7 |
| [16] | Kopetz, H.; Damm, A.; Koza, C.; Mulazzani, M.; Schwabl, W.; Senft, C.; Zainlinger, R., Distributed fault-tolerant real-time systems: the mars approach, IEEE Micro, 9, 1, 25-40 (1989) · doi:10.1109/40.16792 |
| [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; Layland, JW, Scheduling algorithms for multiprogramming in a hard-real-time environment, J ACM (JACM), 20, 1, 46-61 (1973) · Zbl 0265.68013 · doi:10.1145/321738.321743 |
| [20] | Liu, JWSW, Real-Time Systems (2000), Upper Saddle River, NJ, USA: Prentice Hall PTR, Upper Saddle River, NJ, USA |
| [21] | Pathan, RM, Fault-tolerant and real-time scheduling for mixed-criticality systems, Real-Time Syst, 50, 4, 509-547 (2014) · Zbl 1291.68091 · doi:10.1007/s11241-014-9202-z |
| [22] | Poledna, S., Fault-tolerant real-time systems: the problem of replica determinism (2007), Berlin: Springer, Berlin · Zbl 0864.68007 |
| [23] | Ranjbar, B.; Safaei, B.; Ejlali, A.; Kumar, A., Fantom: fault tolerant task-drop aware scheduling for mixed-criticality systems, IEEE Access, 8, 187232-187248 (2020) · doi:10.1109/ACCESS.2020.3031039 |
| [24] | Safari, S.; Hessabi, S.; Ershadi, G., Less-mics: a low energy standby-sparing scheme for mixed-criticality systems, IEEE Trans Comput-Aided Des Integr Circuits Syst, 39, 12, 4601-4610 (2020) · doi:10.1109/TCAD.2020.2977063 |
| [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.; Punnekkat, S., Fault tolerant scheduling of mixed criticality real-time tasks under error bursts, Procedia Comput Sci, 46, 1148-1155 (2015) · doi:10.1016/j.procs.2015.01.027 |
| [29] | Valavanis, KP; Vachtsevanos, GJ, Handbook of unmanned aerial vehicles (2015), Berlin: Springer, Berlin · doi:10.1007/978-90-481-9707-1 |
| [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.; Fu, X., Fault-tolerant task scheduling for mixed-criticality real-time systems, J Circuits Syst Comput, 26, 1, 1750016 (2017) · doi:10.1142/S0218126617500165 |
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.
