Scheduling Imprecise Hard Real-Time Jobs With Cumulative Error

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.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2014

Author dc:creator

• Cheong, Infan Kuok

Contributors dc:contributor

• Liu, Jane W.S.

• Computer Science

Identifier

(UMI)AAI9305490

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/72063