Algorithms for real-time scheduling of error-cumulative tasks based on the imprecise computation approach

摘要

This paper presents several algorithms for real-time scheduling that have been developed following an approach known as Imprecise Computation. This technique prevents timing faults (i.e., results not produced in time) by offering an approximate result of an acceptable quality whenever the exact result of the desired quality cannot be obtained in time. In this work we focused our attention on the problem of scheduling a set of real-time error-cumulative periodic tasks for which errors in different periods have cumulative effects, making it necessary to generate timely, precise results sometimes. This problem is particularly relevant in applications such as route tracking and real-time control of complex industrial plants. The adopted approach consists in applying a transformation of the set of error-cumulative tasks into a set of error-noncumulative tasks that can be easily scheduled by means of an optimal algorithm like the earliest deadline first. This approach permits to obtain scheduling algorithms for some specific, but quite significant, problems. The algorithms have a polynomial complexity, whereas most of the solutions found in literature are NP-hard.