Skip to Main content Skip to Navigation

A New EDF Feasibility Test

Bruno Gaujal 1 Nicolas Navet 2
2 TRIO - Real time and interoperability
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We present a new algorithm for testing the feasibility of a set of non-recurrent tasks (or jobs) with real-time constraints scheduled under the EDF policy (Earliest Deadline First). The proposed feasibility test has a lower complexity than the previously known test. The first step of the algorithm is to construct the Hasse diagram of the set of tasks where the partial order is defined by the inclusion relation on the tasks. Then, the algorithm constructs the shortest path in a geometrical representation at each level of the Hasse diagram. Depending on the maximal slope of each path, the set of tasks is either feasible of not. The worst-case complexity of this feasibility test depends on structural characteristics of the set of jobs since it is the sum of the levels in the Hasse diagram. Whatever the set of jobs, this is better than the worst-case complexities of existing approaches. Furthermore, we provide a probabilistic analysis of the complexity when the tasks are random. For Poisson arrivals and exponentially distributed latencies, we show that the asymptotic complexity for assessing feasibility is O(N (N)). As an interesting by-product, the algorithm provides a new way to derive the best speeds of the processor so as to minimize the total energy consumption while meeting the deadline of each task. The exact complexity of this algorithm (sub-cubic in the number of tasks) is lower than the complexity of all the algorithms solving the same problem, known by the authors.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:36:34 PM
Last modification on : Friday, February 4, 2022 - 3:11:29 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:16:02 PM


  • HAL Id : inria-00071458, version 1


Bruno Gaujal, Nicolas Navet. A New EDF Feasibility Test. [Research Report] RR-5125, INRIA. 2004. ⟨inria-00071458⟩



Record views


Files downloads