Files in this item



application/pdf9305490.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Scheduling Imprecise Hard Real-Time Jobs With Cumulative Error
Author(s):Cheong, Infan Kuok
Doctoral Committee Chair(s):Liu, Jane W.S.
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(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.
Issue Date:1992
Description:169 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1992.
Other Identifier(s):(UMI)AAI9305490
Date Available in IDEALS:2014-12-17
Date Deposited:1992

This item appears in the following Collection(s)

Item Statistics