Synthesis of fault-tolerant schedules with transparency/performance trade-offs for distributed embedded systems

ABSTRACT

In this paper we present an approach to the scheduling of fault-tolerant embedded systems for safety-critical applications. Processes and messages are statically scheduled, and we use process re-execution for recovering from multiple transient faults. If process recovery is performed such that the operation of other processes is not affected, we call it transparent recovery. Although transparent recovery has the advantages of fault containment, improved debugability and less memory needed to store the fault-tolerant schedules, it will introduce delays that can violate the timing constraints of the application. We propose a novel algorithm for the synthesis of fault-tolerant schedules that can handle the transparency/performance trade-offs imposed by the designer, and makes use of the fault-occurrence information to reduce the overhead due to fault tolerance. We model the application as a conditional process graph, where the fault occurrence information is represented as conditional edges and the transparent recovery is captured using synchronization nodes.

REFERENCES

• 1: Alan A. Bertossi , Luigi V. Mancini, Scheduling algorithms for fault-tolerance in hard-real-time systems, Real-Time Systems, v.7 n.3, p.229-245, Nov. 1994 [doi>10.1007/BF01088520]
• 2: A. Burns et al., "Feasibility Analysis for Fault-Tolerant Real-Time Task Sets", Euromicro Workshop on Real-Time Systems, 29--33, 1996.
• 3: J. Söderberg, The XBW Model for Dependable Real-Time Systems, Proceedings of the 1998 International Conference on Parallel and Distributed Systems, p.130, December 14-16, 1998
• 4: C. Dima et al, "Off-line Real-Time Fault-Tolerant Scheduling", Euromicro Parallel and Distributed Processing Workshop, 410--417, 2001.
• 5: G. Fohler, Joint scheduling of distributed complex periodic and hard aperiodic tasks in statically scheduled systems, Proceedings of the 16th IEEE Real-Time Systems Symposium (RTSS '95), p.152, December 05-07, 1995
• 6: G. Fohler, "Adaptive Fault-Tolerance with Statically Scheduled Real-Time Systems", Euromicro Real-Time Systems Workshop, 161--167, 1997.
• 7: Petru Eles , Zebo Peng , Paul Pop , Alex Doboli, Scheduling with bus access optimization for distributed embedded systems, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.8 n.5, p.472-491, Oct., 2000 [doi>10.1109/92.894152 ]
• 8: Ching-Chih Han , Kang G. Shin , Jian Wu, A Fault-Tolerant Scheduling Algorithm for Real-Time Periodic Tasks with Possible Software Faults, IEEE Transactions on Computers, v.52 n.3, p.362-372, March 2003 [doi>10.1109/TC.2003.1183950 ]
• 9: Viacheslav Izosimov , Paul Pop , Petru Eles , Zebo Peng, Design Optimization of Time-and Cost-Constrained Fault-Tolerant Distributed Embedded Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.864-869, March 07-11, 2005 [doi>10.1109/DATE.2005.116]
• 10: N. Kandasamy, J. P. Hayes, B. T. Murray, "Transparent Recovery from Intermittent Faults in Time-Triggered Distributed Systems", IEEE Trans. on Computers, 52(2), 113--125, 2003.
• 11: N. Kandasamy, J. P. Hayes B. T. Murray "Dependable Communication Synthesis for Distributed Embedded Systems," Computer Safety, Reliability and Security Conf., 275--288, 2003.
• 12: Hermann Kopetz, Real-Time Systems: Design Principles for Distributed Embedded Applications, Kluwer Academic Publishers, Norwell, MA, 1997
• 13: Hermann Kopetz , Andreas Damm , Christian Koza , Marco Mulazzani , Wolfgang Schwabl , Christoph Senft , Ralph Zainlinger, Distributed Fault-Tolerant Real-Time Systems: The Mars Approach, IEEE Micro, v.9 n.1, p.25-40, January 1989 [doi>10.1109/40.16792 ]
• 14: H. Kopetz, Günter Bauer, "The Time-Triggered Architecture", Proc. of the IEEE, 91(1), 112--126, 2003.
• 15: Claudio Pinello , Luca P. Carloni , Alberto L. Sangiovanni-Vincentelli, Fault-Tolerant Deployment of Embedded Software for Cost-Sensitive Real-Time Feedback-Control Applications, Proceedings of the conference on Design, automation and test in Europe, p.21164, February 16-20, 2004
• 16: P. Pop, "Analysis and Synthesis of Communication-Intensive Heterogeneous Real-Time Systems", Ph. D. Thesis No. 833, Dept. of Computer and Information Science, Linköping University, 2003.
• 17: D. Ullman, "NP-Complete Scheduling Problems," in J. of Computer Systems Science, vol. 10, 384--393, 1975.
• 18: Ying Zhang , Krishnendu Chakrabarty, Energy-Aware Adaptive Checkpointing in Embedded Real-Time Systems, Proceedings of the conference on Design, Automation and Test in Europe, p.10918, March 03-07, 2003