nach oben

Real-Time Systems

Erschienen in:

01.07.2014

Fault-tolerant and real-time scheduling for mixed-criticality systems

verfasst von: Risat Mahmud Pathan

Erschienen in: Real-Time Systems | Ausgabe 4/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

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 interrelated design constraints: (i) meeting the hard deadlines of application tasks, (ii) providing fault tolerance by executing backups, and (iii) respecting the criticality of each task to facilitate system’s certification. First, a new approach to model mixed-criticality systems from the perspective of fault tolerance is proposed. Second, a uniprocessor fixed-priority scheduling algorithm, called fault-tolerant mixed-criticality (FTMC) scheduling, is designed for the proposed model. The FTMC algorithm executes backups to recover from task errors caused by hardware or software faults. Third, a sufficient schedulability test is derived, when satisfied for a (mixed-criticality) task set, guarantees that all deadlines are met even if backups are executed to recover from errors. Finally, evaluations illustrate the effectiveness of the proposed test.

Vorheriger Artikel An optimal boundary fair scheduling

Nächster Artikel Precautious-RM: a predictable non-preemptive scheduling algorithm for harmonic tasks

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

An interval is called level-i busy period if task \(\tau _i\) and its higher priority jobs continuously execute in that interval. A more formal definition of busy period will be provided later.

A task is runnable if it has been released but has not completed its execution.

The term “task errors” here refers to errors in the primary and backups of one job of task \(\tau _{i} \), i.e., errors are considered to be detected at the job level; not at task level.

If the relative deadline of each task in a task set is less than or equal to its period, then the task set is called a constrained-deadline task system. If the relative deadline of each task is exactly equal to its period, then the task set is called an implicit-deadline task system.

The \(h{th}\) job of task \(\tau _{k} \) is denoted by \(J_k^h\).

Aidemark J, Folkesson P, Karlsson J (2005) A framework for node-level Ffault tolerance in distributed real-time systems. In: Proceedings of the international conference on dependable systems and networks, pp 656–665

Al-Asaad H, Murray BT, Hayes JP (1998) Online BIST for embedded systems. IEEE Des Test 15(4):17–24. doi:10.1109/54.735923 CrossRef

Audsley NC (2001) On priority assignment in fixed priority scheduling. Inf Proc Lett 79(1):39–44CrossRefMATH

Audsley NC, Burns A, Richardson MF, Wellings AJ (1991) Hard real-time scheduling: the deadline-monotonic approach. In: Proc. IEEE workshop on real-time operating systems and software, pp 133–137

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(5):284–292 ISSN 0268–6961CrossRef

Avižienis A, Laprie J-C, Randell B, Landwehr C (2004) Basic concepts and taxonomy of dependable and secure computing. IEEE Trans Depend Sec Compt 1(1):11–33. doi:10.1109/TDSC.2004.2 ISSN 1545–5971CrossRef

Aydin H (2007) Exact fault-sensitive feasibility analysis of real-time tasks. IEEE Trans Compt 56(10):1372–1386. doi:10.1109/TC.2007.70739 ISSN 0018–9340CrossRefMathSciNet

Barhorst J, Belote T, Binns P, Hoffman J, Paunicka J, Sarathy P, Stanfill JSP, Stuart D, Urzi R (2009) In white paper: a research agenda for mixed-criticality systems. https://www.cs.unc.edu/~mollison/pubs/icess10.pdf. Accessed 5 Mar 2010

Baruah S, Fohler G (2011) Certification-cognizant time-triggered scheduling of mixed-criticality systems. In: Proc. of RTSS, pp 3–12

Baruah S, Vestal S (2008) Schedulability analysis of sporadic tasks with multiple criticality specifications. In: Proc. of ECRTS, pp 147–155

Baruah S, Rosier LE, Howell RR (1990a) Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor. Real-Time Syst 2(4):301–324. doi:10.1007/BF01995675 ISSN 0922–6443CrossRef

Baruah SK, Mok AK, Rosier LE (1990b) Preemptively scheduling hard-real-time sporadic tasks on one processor. In: Proc. of the RTSS, pp 182–190

Baruah S, Li H, Stougie L (2010) Towards the design of certifiable mixed-criticality systems. In: Proc. of RTAS

Baruah S, Bonifaci V, D’Angelo G, Marchetti-Spaccamela A, Van Der Ster S, Stougie L (2011a) Mixed-criticality scheduling of sporadic task systems. In: Proc. of the European conf. on algorithms, pp 555–566

Baruah S, Burns A, Davis R (2011b) Response-time analysis for mixed criticality systems. In: Proc. of RTSS

Baruah S, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, Megow N, Stougie L (2012a) Scheduling real-time mixed-criticality jobs. IEEE Trans Comput 61(8):1140–1152

Baruah S, Bonifaci V, D’Angelo G, Li H, Marchetti-Spaccamela A, van der Ster S, Stougie L (2012b) The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems, In: Proc of ECRTS

Baumann R (2005) Soft errors in advanced computer systems. IEEE Des Test Comput 22(3):258–266CrossRef

Bini E, Buttazzo G (2005) Measuring the performance of schedulability tests. Real-Time Syst 30:129–154CrossRefMATH

Burns A, Davis R, Punnekkat S (1996) Feasibility analysis of fault-tolerant real-time task sets. In: Proc. of the ECRTS, pp 522–527

Campbell A, McDonald P, Ray K (1992) Single event upset rates in space. IEEE Trans Nuclear Sci 39(6):1828–1835. doi:10.1109/23.211373 ISSN 0018–9499CrossRef

Castillo X, McConnel R, Siewiorek DP (1982) Derivation and calibration of a transient error reliability model. IEEE Trans Comput 37(7):658–671. doi:10.1109/TC.1982.1676063 ISSN 0018–9340CrossRef

Chattopadhyay S, Kee CL, Roychoudhury A, Kelter T, Marwedel P, Falk H (2012) A unified WCET analysis framework for multi-core platforms. In: Proc. of the RTAS, pp 99–108

Chetto H, Chetto M (1989) Some results of the earliest deadline scheduling algorithm. IEEE Trans Softw Eng 15(10):1261–1269. doi:10.1109/TSE.1989.559777 ISSN 0098–5589CrossRefMathSciNet

Davis R, Burns A (2009) Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. In: Proc. of RTSS, pp 398–409

de Lima GM, Burns A (2003) An optimal fixed-priority assignment algorithm for supporting fault-tolerant hard real-time systems. IEEE Trans Comput 52(10):1332–1346CrossRef

de Niz D, Lakshmanan K, Rajkumar R (2009) On the scheduling of mixed-criticality real-time task sets. In: Proc. of the RTSS, pp 291–300

Dorin F, Richard P, Richard M, Goossens J (2010) Schedulability and sensitivity analysis of multiple criticality tasks with fixed-priorities. Real-Time Syst 46:305–331CrossRefMATH

Ekberg P, Yi W (2012) Bounding and shaping the demand of mixed-criticality sporadic tasks. In: Proc. of the ECRTS

Ghosh S, Melhem R, Mossé D (1995) Enhancing real-time schedules to tolerate transient faults. In: Proc. of the RTSS, pp 120–129

Guan N, Ekberg P, Stigge M, Yi W (2011) Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems. In: Proc. of RTSS, pp 13–23

Guan N, Lv M, Yi W, Yu G (2012) WCET analysis with MRU caches: challenging LRU for predictability. In: Proc. of RTAS, pp 55–64

Han C-C, Shin KG, Wu J (2003) A fault-tolerant scheduling algorithm for real-time periodic tasks with possible software faults. IEEE Trans Compt 52(3):362–372. doi:10.1109/TC.2003.1183950 ISSN 0018–9340CrossRef

Hiller M (2000) Executable assertions for detecting data errors in embedded control systems. In: Proc. of the DSN

Huynh BK, Ju L, Roychoudhury A (2011) Scope-aware data cache analysis for WCET estimation. In: Proc. of the RTAS, pp 203–212

Iyer RK, Rossetti DJ, Hsueh MC (1986) Measurement and modeling of computer reliability as affected by system activity. ACM Trans Compt Syst 4(3):214–237 ISSN 0734–2071CrossRef

Jhumka A, Hiller M, Claesson V, Suri N (2002) On systematic design of globally consistent executable assertions in embedded software. In: Proceedings of the joint conference on Languages, compilers and tools for embedded systems, pp 75–84

Kalla R, Sinharoy B, Starke WJ, Floyd M (2010) Power 7: ibm’s next-generation server processor. Micro IEEE 30(2):7–15CrossRef

Koren I, Krishna CM (2007) Fault-tolerant systems. Morgan Kaufmann

Lakshmanan K, de Niz D, Rajkumar R, Moreno G (2010) Resource allocation in distributed mixed-criticality cyber-physical systems. In: Proc. of the ICDCS, pp 169–178

Lakshmanan K, de Niz D, Rajkumar R (2011) Mixed-criticality task synchronization in zero-slack scheduling. In: Proc. of RTAS, pp 47–56

Leung JYT, Whitehead J (1982) On the complexity of fixed-priority scheduling of periodic real-time tasks. Perform Eval 2:237–250CrossRefMATHMathSciNet

Li H, Baruah S (2010a) Load-based schedulability analysis of certifiable mixed-criticality systems. In: Proc. of EMSOFT, pp 99–108

Li H, Baruah S (2010b) An algorithm for scheduling certifiable mixed-criticality sporadic task systems. In: Proc. of RTSS, pp 183–192

Liberato F, Melhem R, Mossé D (2000) Tolerance to multiple transient faults for aperiodic tasks in hard real-time systems. IEEE Trans Compt 49(9):906–914CrossRef

Madeira H, Camoes J, Silva JG (1991) A watchdog processor for concurrent error detection in multiple processor systems. Microprocess Microsyst 15(3):123–130CrossRef

Many F, Doose D (2011) Scheduling Analysis under Fault Bursts. In: Proc. of the RTAS, pp 113–122

Meixner A, Bauer ME, Sorin DJ (2007) Argus: low-cost, comprehensive error detection in simple cores. In: Proc. of the annual IEEE/ACM int. symp. on Microarchitecture, pp 210–222

Mok AK, Feng X, Chen D (2001) Resource partition for real-time systems. In: Proc. of the RTAS, p 75

Mollison MS, Erickson JP, Anderson JH, Baruah SK, Scoredos JA (2010) Mixed-criticality real-time scheduling for multicore systems. In: Proc. of ICESS, pp 1864–1871

Pandya M, Malek M (1998) Minimum achievable utilization for fault-tolerant processing of periodic tasks. IEEE Trans Compt 47(10):1102–1112. doi:10.1109/12.729793 ISSN 0018–9340CrossRef

Pathan RM (2012) Schedulability analysis of mixed-criticality systems on multiprocessors. In: Proc. of ECRTS, pp 309–320

Pellizzoni R, Meredith P, Caccamo M, Rosu G (2008) Hardware runtime monitoring for dependable COTS-based real-time embedded systems, In: Proc of the RTSS

Pellizzoni R, Meredith P, Nam M, Sun M, Caccamo M, Sha L (2009) Handling mixed-criticality in soc-based real-time embedded systems. In: Proc. of EMSOFT

Petters SM, Heffernan M, Elphinstone K (2009) Towards real multi-criticality scheduling. In: Proc. of RTCSA, pp 155–164

Punnekkat S, Burns A, Davis R (2001) Analysis of checkpointing for real-time systems. Real-Time Syst 20(1):83–102. doi:10.1023/A:1026589200419 ISSN 0922–6443CrossRefMATH

Raju SCV, Rajkumar R, Jahanian F (1992) Monitoring timing constraints in distributed real-time systems. In: Proc. of the RTSS, pp 57–67

Santy F, George L, Thierry P, Goossens J (2012) Relaxing mixed-criticality scheduling strictness for task sets scheduled with FP. In: Proc. pf the ECRTS, pp 155–165

Shivakumar P, Kistler M, Keckler SW, Burger D, Alvisi L (2002) Modeling the effect of technology trends on the soft error rate of combinational logic. In: Proc. of the DSN, pp 389–398

Short M, Proenza J (2013) Towards efficient probabilistic scheduling guarantees for real-time systems subject to random errors and random bursts of errors. InL Proc. of the ECRTS, pp 259–268. doi:10.1109/ECRTS.2013.35

Siewiorek DP, Kini V, Mashburn H, McConnel S, Tsao M (1978) Experiences with fault tolerance in multiprocessor systems. Proc IEEE 66(10):1199 ISSN 0018–9219

Srinivasan J, Adve SV, Bose P, Rivers JA (2004) The impact of technology scaling on lifetime reliability. In: Proceedings of the international conference on dependable systems and networks, pp 177–186

Tamas-Selicean D, Pop P (2011) Design optimization of mixed-criticality real-time applications on cost-constrained partitioned architectures. In: Proc. of RTSS, pp 24–33

Vestal (2007) Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: Proc. of RTSS, pp 239–243

Yoon M, Kim J, Sha L (2011) Optimizing tunable wcet with shared resource allocation and arbitration in hard real-time multicore systems. In: Proc. of the RTSS, pp 227–238

Titel: Fault-tolerant and real-time scheduling for mixed-criticality systems
verfasst von: Risat Mahmud Pathan
Publikationsdatum: 01.07.2014
Verlag: Springer US
Erschienen in: Real-Time Systems / Ausgabe 4/2014
Print ISSN: 0922-6443
Elektronische ISSN: 1573-1383
DOI: https://doi.org/10.1007/s11241-014-9202-z

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"