A Fault-Tolerant Scheduling Problem

Arthur L. Liestman, Roy H. Campbell

Research output: Contribution to journalArticle

Abstract

A real-time system must be reliable if a failure to meet its timing specifications might endanger human life, damage equipment, or waste expensive resources. Applications that require remote operation, timing accuracy, and long periods of activity need mechanisms to support reliability. Fault tolerance improves reliability by incorporating redundancy into the system design. A deadline mechanism has been proposed to provide fault tolerance in real-time software systems. The mechanism trades the accuracy of the results of a service for timing precision. Two independent algorithms are provided for each service subject to a deadline. The primary algorithm produces a good quality service, although its real-time reliability may not be assured. The alternate algorithm is reliable and produces an acceptable response. This paper introduces an algorithm to generate an optimal schedule for the deadline mechanism and discusses a simple and efficient implementation. The schedule ensures the timely completion of the alternate algorithm despite a failure to complete the primary algorithm within real time.

Original languageEnglish (US)
Pages (from-to)1089-1095
Number of pages7
JournalIEEE Transactions on Software Engineering
VolumeSE-12
Issue number11
DOIs
StatePublished - Jan 1 1986

Fingerprint

Scheduling
Fault tolerance
Real time systems
Redundancy
Systems analysis
Specifications

Keywords

  • Real-time systems
  • scheduling
  • software fault tolerance
  • software reliability

ASJC Scopus subject areas

  • Software

Cite this

A Fault-Tolerant Scheduling Problem. / Liestman, Arthur L.; Campbell, Roy H.

In: IEEE Transactions on Software Engineering, Vol. SE-12, No. 11, 01.01.1986, p. 1089-1095.

Research output: Contribution to journalArticle

Liestman, Arthur L. ; Campbell, Roy H. / A Fault-Tolerant Scheduling Problem. In: IEEE Transactions on Software Engineering. 1986 ; Vol. SE-12, No. 11. pp. 1089-1095.
@article{22a89a52b7534476a88c982fc72f0313,
title = "A Fault-Tolerant Scheduling Problem",
abstract = "A real-time system must be reliable if a failure to meet its timing specifications might endanger human life, damage equipment, or waste expensive resources. Applications that require remote operation, timing accuracy, and long periods of activity need mechanisms to support reliability. Fault tolerance improves reliability by incorporating redundancy into the system design. A deadline mechanism has been proposed to provide fault tolerance in real-time software systems. The mechanism trades the accuracy of the results of a service for timing precision. Two independent algorithms are provided for each service subject to a deadline. The primary algorithm produces a good quality service, although its real-time reliability may not be assured. The alternate algorithm is reliable and produces an acceptable response. This paper introduces an algorithm to generate an optimal schedule for the deadline mechanism and discusses a simple and efficient implementation. The schedule ensures the timely completion of the alternate algorithm despite a failure to complete the primary algorithm within real time.",
keywords = "Real-time systems, scheduling, software fault tolerance, software reliability",
author = "Liestman, {Arthur L.} and Campbell, {Roy H.}",
year = "1986",
month = "1",
day = "1",
doi = "10.1109/TSE.1986.6312999",
language = "English (US)",
volume = "SE-12",
pages = "1089--1095",
journal = "IEEE Transactions on Software Engineering",
issn = "0098-5589",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "11",

}

TY - JOUR

T1 - A Fault-Tolerant Scheduling Problem

AU - Liestman, Arthur L.

AU - Campbell, Roy H.

PY - 1986/1/1

Y1 - 1986/1/1

N2 - A real-time system must be reliable if a failure to meet its timing specifications might endanger human life, damage equipment, or waste expensive resources. Applications that require remote operation, timing accuracy, and long periods of activity need mechanisms to support reliability. Fault tolerance improves reliability by incorporating redundancy into the system design. A deadline mechanism has been proposed to provide fault tolerance in real-time software systems. The mechanism trades the accuracy of the results of a service for timing precision. Two independent algorithms are provided for each service subject to a deadline. The primary algorithm produces a good quality service, although its real-time reliability may not be assured. The alternate algorithm is reliable and produces an acceptable response. This paper introduces an algorithm to generate an optimal schedule for the deadline mechanism and discusses a simple and efficient implementation. The schedule ensures the timely completion of the alternate algorithm despite a failure to complete the primary algorithm within real time.

AB - A real-time system must be reliable if a failure to meet its timing specifications might endanger human life, damage equipment, or waste expensive resources. Applications that require remote operation, timing accuracy, and long periods of activity need mechanisms to support reliability. Fault tolerance improves reliability by incorporating redundancy into the system design. A deadline mechanism has been proposed to provide fault tolerance in real-time software systems. The mechanism trades the accuracy of the results of a service for timing precision. Two independent algorithms are provided for each service subject to a deadline. The primary algorithm produces a good quality service, although its real-time reliability may not be assured. The alternate algorithm is reliable and produces an acceptable response. This paper introduces an algorithm to generate an optimal schedule for the deadline mechanism and discusses a simple and efficient implementation. The schedule ensures the timely completion of the alternate algorithm despite a failure to complete the primary algorithm within real time.

KW - Real-time systems

KW - scheduling

KW - software fault tolerance

KW - software reliability

UR - http://www.scopus.com/inward/record.url?scp=0022810471&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022810471&partnerID=8YFLogxK

U2 - 10.1109/TSE.1986.6312999

DO - 10.1109/TSE.1986.6312999

M3 - Article

AN - SCOPUS:0022810471

VL - SE-12

SP - 1089

EP - 1095

JO - IEEE Transactions on Software Engineering

JF - IEEE Transactions on Software Engineering

SN - 0098-5589

IS - 11

ER -