The Quadratic Utilization Upper Bound for Arbitrary Deadline Real-Time Tasks

In high throughput applications, such as in multimedia, it is preferable to fully utilize computing resources, even at the price of some (bounded) delay. However, in real-time systems, where the maximum admissible delay is modeled by a deadline, most of the theory is developed with the assumption of a task deadline smaller than or equal to the task period. The reason of this limitation is in the intrinsic difficulty of the schedulability analysis in the arbitrary deadline case. The most notable guarantee test for sets of arbitrary deadline tasks was due to Lehoczky in 1990. In this paper, we propose the quadratic utilization bound applicable to tasks with arbitrary deadline, which extends Lehoczky’s result. The improvement is made possible by providing some information about the task periods.