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≤2.33 N₀+κ, where N is the number of processors required to feasibly schedule a set of tasks by the heuristic, N₀ is the minimum number of processors required to feasibly schedule the same set of tasks, and κ 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.