Scheduling Periodic Jobs That Allow Imprecise Results

Jen Yao Chung, Jane W.S. Liu, Kwei Jay Lin

Research output: Contribution to journalJournal Article peer-review

168 Scopus citations

Abstract

This paper discusses the problem of scheduling periodic jobs in hard real-time systems that support imprecise computations [1]-[3]. Timing faults are avoided in such systems by making available intermediate, imprecise results of acceptable quality, when results of the desired quality cannot be produced in time. Two workload models of imprecise computations are presented. These models differ from traditional models in that a task may be terminated any time after it has produced an acceptable result. Each task is logically decomposed into two parts: a mandatory part followed by an optional part. In a feasible schedule, the mandatory part Of every task is completed before the deadline of the task. The optional part refines the result produced by the mandatory part to reduce the error in the result. Applications are classified as Type N and Type C, according to undesirable effects of errors. The two workload models characterize these two types of applications. The optional parts of the tasks in a Type N job need not ever be completed. The result quality of each Type N job is measured in terms of the average error in the results over several consecutive periods. A class of preemptive, priority-driven algorithms that leads to feasible schedules with small average error is described and evaluated. For Type C jobs, errors in different periods have cumulative effects, making it necessary to complete the optional part in one period among several consecutive periods. The question of schedulability for Type C jobs is discussed.

Original languageEnglish
Pages (from-to)1156-1174
Number of pages19
JournalIEEE Transactions on Computers
Volume39
Issue number9
DOIs
StatePublished - 09 1990
Externally publishedYes

Keywords

  • Programming environments
  • real-time systems
  • scheduling to meet deadlines

Fingerprint

Dive into the research topics of 'Scheduling Periodic Jobs That Allow Imprecise Results'. Together they form a unique fingerprint.

Cite this