Improving the Efficiency of Global EDF Exact Schedulability Test

Exact schedulability tests are a key element of the analysis of real-time systems as they check temporal constraints without sacrificing processing capacity. However, achieving both exactness and computational efficiency for the same test may be challenging. For instance, Global Earliest Deadline First (GEDF) on multi-cores has no known worst-case scenario for tasks releases, implying that an exact test must check all possible release scenarios. Consequently, existing GEDF exact tests can only check 4-5 tasks with tiny parameters executed upon 2 cores. We propose an improved exact GEDF schedulability test for sporadic real-time tasks. Our test is many orders of magnitude faster and less memory consuming than any other available exact test for GEDF. Its C++ implementation is publicly available.