Abstract
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 N0+κ, 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 κ 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.
Original language | English |
---|---|
Pages (from-to) | 315-329 |
Number of pages | 15 |
Journal | Real-Time Systems |
Volume | 7 |
Issue number | 3 |
DOIs | |
State | Published - Nov 1994 |