Scheduling hard real-time jobs that allow imprecise results

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.U of I OnlyETDs are only available to UIUC Users without author permissio