Performance of algorithms for scheduling periodic jobs to avoid timing faults
J.-Y. Chung, J.W.S. Liu · 2003
The authors describe and evaluate a class of heuristic algorithms, called length-monotone algorithms, for scheduling periodic jobs on systems that support imprecise computations. The algorithms are designed to keep the cumulative error in the results produced over a number of consecutive periods below a threshold. The approach taken is to consider each task as consisting of a mandatory part followed by an optional part. The mandatory part must be completed before the deadline of the task for the task to produce an acceptable result. The optional part must be completed occasionally to keep the cumulative error from exceeding an upper limit. The rate-monotone algorithm is used to schedule the mandatory parts to meet all deadlines. Different algorithms are used to schedule the optional parts. The performance of these algorithms is evaluated, and the schedulability criteria for jobs with the same repetition period and simply periodic jobs are discussed.>