Exact Fault-Sensitive Feasibility Analysis of Real-Time Tasks

In this paper, we consider the problem of checking the feasibility of a set of n real-time tasks while provisioning for timely recovery from (at most) k transient faults. We extend the well-known processor demand approach to take into account the extra overhead that may be induced by potential recov...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on computers 2007-10, Vol.56 (10), p.1372-1386
Main Author: Aydin, H.
Format: Article
Language:English
Subjects:
Algorithms
Circuit faults
Deadline-driven Systems
Fault tolerance
Faults
Feasibility
On-line systems
Online
Processor Demand Analysis
Processor scheduling
Real time
Real time systems
Real-time Scheduling
Recovery
Recovery Blocks
Redundancy
Studies
Tasks
Timing
Transient analysis
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper, we consider the problem of checking the feasibility of a set of n real-time tasks while provisioning for timely recovery from (at most) k transient faults. We extend the well-known processor demand approach to take into account the extra overhead that may be induced by potential recovery operations under earliest-deadline-first scheduling. We develop a necessary and sufficient test using a dynamic programming technique. An improvement upon the previous solutions is to address and efficiently solve the case where the recovery blocks associated with a given task do not necessarily have the same execution time. We also provide an online version of the algorithm that does not require a priori knowledge of release times. The online algorithm runs in O(m ldr k 2 ) time, where m is the number of ready tasks. We extend the framework to periodic execution settings: We derive a sufficient condition that can be checked efficiently for the feasibility of periodic tasks in the presence of faults. Finally, we analyze the case where the recovery blocks are to be executed nonpreemptively and we formally show that the problem becomes intractable under that assumption.
ISSN:0018-9340
1557-9956
DOI:10.1109/TC.2007.70739