INCREASING PROCESSOR UTILIZATION IN HARD-REAL-TIME SYSTEMS WITH CHECKPOINTS

Often hard real-time systems require results that are produced on time despite the occurrence of processor failures. This paper considers a distributed system where tasks are periodic and each task occurs in mu ltiple copies which are periodically synchronized in order to handle f ailures. The problem of preemptively scheduling a set of such tasks is discussed where every occurrence of a task has to be completely execu ted before the next occurrence of the same task. First, a static sched uling algorithm is proposed which uses periodic checkpoints to tolerat e processor failures. Then, the performance of the algorithm is substa ncially improved employing a mixed strategy which constructs a schedul e where high frequency tasks are duplicated, and low frequency tasks a re periodically checkpointed. The performance of the solution proposed is evaluated in terms of the minimum achievable processor utilization due to the useful computation of the tasks. Moreover, analytical and simulation studies are used to reveal interesting trade-offs associate d with the scheduling algorithm. In particular, if high frequency task s are less than 70 percent of the total number of tasks then the mixed strategy yields a higher processor utilization than the task duplicat ion scheme.