Improved Low Time-Complexity Schedulability Test for Nonpreemptive EDF on a Multiprocessor

In real-time embedded systems, nonpreemptive earliest deadline first (NP-EDF) is one of the most popular scheduling algorithms to offer timing guarantees of a set of nonpreemptive real-time jobs (tasks). While most existing schedulability tests for NP-EDF on a multiprocessor platform have paid attention to improving schedulability performance at the expense of increasing time complexity, only a few studies can be used for the situation where low time complexity is critical. In this letter, based on an existing low time-complexity schedulability test for NP-EDF, we develop schedulability tests that improve schedulability performance but maintain low time complexity. Our experiments show that the proposed schedulability tests improve schedulability performance up to 592.4%, compared to the existing low time-complexity one, and they can find some additional task sets schedulable by NP-EDF, which cannot be covered by existing high time-complexity NP-EDF schedulability tests.