On multiprocessor scheduling of preemptive periodic real-time tasks with error recovery

A real-time system must execute functionally correct computations in a timely manner. Among these real-time systems, multiprocessor systems are increasingly being used because of their capability for high performance, reliability and extensibility. Since many real-time systems process tasks of a periodic nature, a large body of literature has been developed to guarantee the timely execution of periodic preemptive real-time tasks. However, this timeliness is usually only guaranteed in the absence of faults, which may be unacceptable for some critical systems. When a fault causes an error in a computation, some recovery action must take place, but this recovery action impacts the timeliness guarantees of the system. Therefore, this dissertation addresses the problem of guaranteeing timely error recovery when scheduling periodic preemptive real-time tasks on multiprocessor systems.; The first contribution of this thesis is RBound, a new admission control for rate-monotonic scheduling. RBound uses information about the tasks periods to obtain a high processor utilization and performs particularly well when used in multiprocessor environments. RBound can easily be adapted to problems related to RMS, such as aperiodic task servicing. The second contribution of this thesis is given in the form of negative results, where global scheduling for RMS and EDF are shown to achieve a lower processor utilization than their partitioned counterparts, in the average case for global RMS and when tasks have bounded utilization for global EDE The third contribution of this thesis is a general framework for error recovery that encompasses several types of faults, different error recovery techniques and shows what error recovery technique is appropriate for which type of fault. The last contribution of this thesis is algorithm MultiRec that guarantees the execution of periodic preemptive real-time tasks within their deadlines even in the presence of multiple types of faults. Experimental results indicate that MultiRec scales well to large systems, in particular because task or instance migration across processors is not necessary. Furthermore, MultiRec is a generic algorithm where tasks can recover from different types of faults and use various recovery actions. The proposed solution can be used online or off-line, with homogeneous or heterogeneous processors. Finally, reliability analysis shows that MultiRec provides a very good fault coverage without sacrificing system utilization and that MultiRec provides a tradeoff between the fault coverage it offers and the system utilization it achieves.