SCHEDULING REAL-TIME, PERIODIC JOBS USING IMPRECISE RESULTS.

A discussion is presented of the problem of scheduling periodic jobs to meet deadlines on a system that provides the programming language primitives and run-time support for processes to return imprecise results. This problem differs from the traditional scheduling problems in that a task may be terminated before it is completed, producing an acceptable but imprecise result with a nonzero error. Consequently, the amounts of processor time assigned to tasks in a valid schedule can be less than the amounts of time required to complete the tasks. A formulation of this problem taking into account the quality of the overall result is discussed. Depending on whether the effects of errors in results produced in different periods are accumulative or nonaccumulative, jobs are classified as type A or type N, respectively. Three algorithms for scheduling type-N jobs are described, and their relative merits are evaluated.