Item Details

Scheduling Real-Time Tasks for Dependability

Oh, Yingfeng; Son, Sang
Format
Report
Author
Oh, Yingfeng
Son, Sang
Abstract
Real-time systems are increasingly used in applications whose failure may result in large economic and human costs. Since many of the systems operate in environments that are non-deterministic, and even hazardous, it is extremely important that the systems must be dependable, i.e., the deadlines of tasks must be met even in the presence of certain failures. In order to enhance the dependability of a real-time system, we study the problem of scheduling a set of real-time tasks to meet their deadlines even in the presence of processor failures. We first prove that the problem of scheduling a set of non-preemptive tasks on more than two processors to tolerate one arbitrary processor failure is NP-complete even when the tasks share a common deadline. A heuristic algorithm is then proposed to solve the problem. The schedule generated by the heuristic algorithm can tolerate one arbitrary processor failure in the worst case. The analysis and experimental data show that the performance of the heuristic algorithm is near-optimal.
Language
English
Date Received
20121029
Published
University of Virginia, Department of Computer Science, 1995
Published Date
1995
Collection
Libra Open Repository
Logo for In CopyrightIn Copyright

Availability

Access Online