On means to provide flexibility in scheduling

It is well-known that scheduling tasks to meet deadlines in hard real-time systems is difficult. Algorithms (such as the rate-monotone algorithm [1,2]) that guarantee deadlines are met for wide ranges of task execution times and system load typically do not achieve high processor utilization. On the other hand, algorithms (such as the earliest-deadline-first algorithm [l-4]) that achieve optimal processor utilization may not degrade gracefully in the presence of transient overload. The imprecise computation approach was proposed recently [5-81 as a means to provide flexibility in scheduling. In a system that supports imprecise computations, intermediate results produced by prematurely terminated server processes are made available to their client processes. By making results of poorer quality available when the results of desirable quality cannot be obtained in time, real-time services, possibly of degraded quality, are provided on a timely basis. This approach makes it possible to have scheduling algorithms that guarantee schedulability and achieve high processor utilization while the system load fluctuates.