ENHANCING FAULT-TOLERANCE IN RATE-MONOTONIC SCHEDULING

In this paper, we address the problem of supporting timeliness and dependability at the level of task scheduling. We consider the problem of scheduling a set of tasks, each of which, for fault-tolerance purposes, has multiple versions, onto the minimum number of processors. On each individual processor, the tasks are guaranteed their deadlines by the Rate-Monotonic algorithm. A simple online allocation heuristic is proposed. It is proven that N less-than-or-equal-to 2.33N0 + kappa, where N is the number of processors required to feasibly schedule a set of tasks by the heuristic, N0 is the minimum number of processors required to feasibly schedule the same set of tasks, and kappa is the maximum redundancy degree a task can have. The bound is also shown to be a tight upper bound. The average-case performance of the heuristic is studied through simulation. It is shown that the heuristic performs surprisingly well on the average.