Synthesis of Flexible Fault-Tolerant Schedules for Embedded Systems with Soft and Hard Timing Constraints

Introduction

Fault-tolerant embedded real-time systems have to meet their deadlines and function correctly in the worst-case and with the presence of faults. Such systems are usually designed for the worst-case, which often leads to overly pessimistic solutions. Design of fault-tolerant embedded real-time systems for the average case, addressed in this chapter, is a promising alternative to the purely worst-case-driven design. It is important to emphasize that the generated designs have to be safe, i.e. all hard deadlines are met, even in the worst-case execution scenarios and when affected by faults.

Faults can be permanent (i.e. damaged microcontrollers or communication links), transient, or intermittent. Transient and intermittent faults (also known as “soft errors”) appear for a short time and can be caused by electromagnetic interference, radiation, temperature variations, software “bugs”, etc. Transient and intermittent faults, which we will deal with in this chapter, are the most common and their number is increasing due to greater complexity, higher frequency and smaller transistor sizes (Izosimov, 2009). We will refer to both transient and intermittent faults as “transient” faults since they manifest themselves similar from fault tolerance point of view.

Real-time systems have been classified as hard real-time and soft real-time systems. For hard real-time processes, failing to meet a deadline can potentially have catastrophic consequences, whereas a soft real-time process retains some diminishing value after its deadline. Traditionally, hard and soft real-time systems have been scheduled using very different techniques (Kopetz, 1997). However, many applications have both hard and soft timing constraints (Buttazzo, & Sensini, 1999), and therefore researchers have proposed techniques for addressing mixed hard/soft real-time systems (Buttazzo, & Sensini, 1999; Davis, Tindell, & Burns, 1993; Cortes, Eles, & Peng, 2004). Particularly, Cortes et al. (2004) have developed a design approach for multiprocessor embedded systems composed of soft and hard processes. A number of quasi-static scheduling heuristics has been proposed such that the overall utility of soft processes is maximized while deadlines of hard processes are satisfied. However, neither Cortes et al. (2004) nor any other of the above mentioned work on mixed soft and hard real-time systems has addressed fault tolerance aspects. In this chapter, thus, we present a novel approach to design fault-tolerant mixed soft/hard real-time systems. The approach is generic and can be applied on a variety of embedded systems, in particular, on systems-on-chip (SoC) used in factory automation, telecommunication and medical equipment and, last but not least, automotive electronics.