Scheduling Periodic Jobs That Allow Imprecise Results

This paper discusses the problem of scheduling periodic jobs in hard real-time systems that support imprecise computations [1]-[3]. Timing faults are avoided in such systems by making available intermediate, imprecise results of acceptable quality, when results of the desired quality cannot be produced in time. Two workload models of imprecise computations are presented. These models differ from traditional models in that a task may be terminated any time after it has produced an acceptable result. Each task is logically decomposed into two parts: a mandatory part followed by an optional part. In a feasible schedule, the mandatory part Of every task is completed before the deadline of the task. The optional part refines the result produced by the mandatory part to reduce the error in the result. Applications are classified as Type N and Type C, according to undesirable effects of errors. The two workload models characterize these two types of applications. The optional parts of the tasks in a Type N job need not ever be completed. The result quality of each Type N job is measured in terms of the average error in the results over several consecutive periods. A class of preemptive, priority-driven algorithms that leads to feasible schedules with small average error is described and evaluated. For Type C jobs, errors in different periods have cumulative effects, making it necessary to complete the optional part in one period among several consecutive periods. The question of schedulability for Type C jobs is discussed. © 1990 IEEE