Enhancing fault-tolerance in rate-monotonic scheduling

Yingfeng Oh, Sang H. Son

Research output: Contribution to journalArticlepeer-review

14 Scopus citations

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 languageEnglish
Pages (from-to)315-329
Number of pages15
JournalReal-Time Systems
Volume7
Issue number3
DOIs
StatePublished - Nov 1994

Fingerprint

Dive into the research topics of 'Enhancing fault-tolerance in rate-monotonic scheduling'. Together they form a unique fingerprint.

Cite this