Scheduling hard real-time jobs that allow imprecise results
Chung, Jen-Yao
This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/19091
Description
Title
Scheduling hard real-time jobs that allow imprecise results
Author(s)
Chung, Jen-Yao
Issue Date
1989
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Operations Research
Computer Science
Language
eng
Abstract
One way to avoid timing faults in hard real-time systems is to use the imprecise computation approach. In this approach, an intermediate result of acceptable quality is used whenever a result of the desired quality cannot be produced before its deadline. This thesis discusses the problem of scheduling periodic jobs to meet deadlines on systems that support imprecise computations. In our workload models, each real-time task is logically decomposed into two parts: a mandatory part and an optional part. The mandatory part must be completed in order for the task to produce an acceptable result, and the optional part refines the result produced by the mandatory part to reduce the error in the result. The mandatory part has a hard deadline, and the optional part has a soft deadline. Our workload models differ from traditional models in that a task may be terminated due to time constraint at any time throughout its optional part. Depending on different kinds of undesirable effects of errors, jobs are classified as error-noncumulative or error-cumulative. For error-noncumulative jobs, the effects of errors in the results produced in different periods are not cumulative. The optional parts of the tasks never need to be completed. The result quality of each job is measured in terms of the average error in the results produced over several consecutive periods. A class of preemptive, priority-driven algorithms that lead to feasible schedules with small average error is described and evaluated. For error-cumulative jobs, the undesirable effects of errors produced in different periods are cumulative, making it necessary to complete the optional part at least once in several consecutive periods. A class of heuristic algorithms is designed to schedule the optimal parts. The performance of these algorithms is evaluated and the schedulability criteria are discussed.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
