An earlier time for inserting and/or accelerating tasks

摘要

In a periodic real-time system scheduled by the EDF (Earliest Deadline First) algorithm (Liu and Layland, J. ACM 20(1), 40-61, 1973; Barauh, Proc. of the 27th IEEE International Real-Time Systems Symposium, 379-387, 2006; Buttazzo, J. Real-Time Syst. 29(1), 5-26, 2005), when new tasks have to be inserted into the system at run-time and/or current tasks request to increase their rates in response to internal or external events, the new sum of the utilizations after the insertion and/or acceleration should be limited, otherwise, one or more current tasks should usually be compressed (their periods being prolonged) in order to avoid overload. Buttazzo offered a time from which on this kind of adjustment can be done without causing any deadline miss in the system (Buttazzo et al., IEEE Trans. Comput. 51(3), 289-302, 2002). It is, however, not early enough. In this paper, an earlier time is given and formally proved.