Schedulability and optimal checkpoint placement for real-time multi-tasks

An optimal checkpoint strategy for fault-tolerance in real-time systems is addressed in this paper. We consider multiple real-time tasks with arbitrary periods that are scheduled by Rate Monotonic (RM) algorithm. Equidistant checkpointing is maintained for each kind of task, while the width of checkpoint intervals is different with respect to the task. We propose a method to determine the optimal checkpoint interval for each task so that the probability of completing all the tasks is maximized. Whenever a fault occurs to a checkpoint interval of a task, the execution time of the task would be prolonged by rollback and re-execution of checkpoints. Our scheme includes the schedulability test to examine whether a task can be completed with an extended execution time. A numerical experiment demonstrates the applicability of the proposed scheme.