Scheduling Imprecise Hard Real-Time Jobs With Cumulative Error
Cheong, Infan Kuok
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/72063
Description
Title
Scheduling Imprecise Hard Real-Time Jobs With Cumulative Error
Author(s)
Cheong, Infan Kuok
Issue Date
1992
Doctoral Committee Chair(s)
Liu, Jane W.S.
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)
Computer Science
Abstract
The imprecise computation approach is a way to satisfy all timing constraints and provide graceful degradation more easily during transient overloads in hard real-time systems. The basic idea of this approach is to trade precision for timeliness. In this approach, each task is divided logically into two subtasks: a mandatory subtask that produces a rough but acceptable result and an optional subtask that refines the rough result. The mandatory subtask must be completed by the deadline of the task for the task to produce an acceptable and usable result. The optional subtask can be left unfinished if necessary. When a transient overload occurs, the scheduler can discard the optional subtasks if they are not completed by their deadlines. Errors result from the early terminations of tasks. For some applications, the error in the result generated by an unfinished optional subtask has a cumulative effect on the results generated by the later tasks of the same periodic job. For each job of this type, there is a maximum threshold of cumulated error. When the cumulated error of the results produced in a number of periods exceeds the maximum threshold, the result is no longer considered to be correct. The focus of this thesis is on the problem of scheduling imprecise hard real-time jobs with cumulative error. A class of heuristic algorithms is proposed to schedule jobs such that the cumulated error of the results produced by each job will not exceed the maximum threshold. The proposed algorithms are evaluated using different transient overload workload models for a number of job sets with different characteristics. The results of this evaluation are presented and discussed in this thesis.
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.
