TY - JOUR

T1 - Polynomial Exact Schedulability and Infeasibility Test for Fixed-Priority Scheduling on Multiprocessor Platforms

AU - Garanina, Natalia

AU - Anureev, Igor

AU - Kondratyev, Dmitry

N1 - This work was supported by a grant for research centers, provided by the Analytical Center for the Government of the Russian Federation in accordance with the subsidy agreement (agreement identifier 000000D730324P540002) and the agreement with the Novosibirsk State University, dated 27 December 2023 No. 70-2023-001318.

PY - 2025/1/20

Y1 - 2025/1/20

N2 - In this paper, we develop an exact schedulability test and sufficient infeasibility test for fixed-priority scheduling on multiprocessor platforms. We base our tests on presenting real-time systems as a Kripke model for dynamic real-time systems with sporadic non-preemptible tasks running on a multiprocessor platform and an online scheduler using global fixed priorities. This model includes states and transitions between these states, allows us to formally justify a polynomial-time algorithm for an exact schedulability test using the idea of backward reachability. Using this algorithm, we perform the exact schedulability test for the above real-time systems, in which there is one more task than the processors. The main advantage of this algorithm is its polynomial complexity, while, in general, the problem of the exact schedulability testing of real-time systems on multiprocessor platforms is NP-hard. The infeasibility test uses the same algorithm for an arbitrary task-to-processor ratio, providing a sufficient infeasibility condition: if the real-time system under test is not schedulable in some cases, the algorithm detects this. We conduct an experimental study of our algorithms on the datasets generated with different utilization values and compare them to several state-of-the-art schedulability tests. The experiments show that the performance of our algorithm exceeds the performance of its analogues while its accuracy is similar.

AB - In this paper, we develop an exact schedulability test and sufficient infeasibility test for fixed-priority scheduling on multiprocessor platforms. We base our tests on presenting real-time systems as a Kripke model for dynamic real-time systems with sporadic non-preemptible tasks running on a multiprocessor platform and an online scheduler using global fixed priorities. This model includes states and transitions between these states, allows us to formally justify a polynomial-time algorithm for an exact schedulability test using the idea of backward reachability. Using this algorithm, we perform the exact schedulability test for the above real-time systems, in which there is one more task than the processors. The main advantage of this algorithm is its polynomial complexity, while, in general, the problem of the exact schedulability testing of real-time systems on multiprocessor platforms is NP-hard. The infeasibility test uses the same algorithm for an arbitrary task-to-processor ratio, providing a sufficient infeasibility condition: if the real-time system under test is not schedulable in some cases, the algorithm detects this. We conduct an experimental study of our algorithms on the datasets generated with different utilization values and compare them to several state-of-the-art schedulability tests. The experiments show that the performance of our algorithm exceeds the performance of its analogues while its accuracy is similar.

KW - Kripke model

KW - exact schedulability test

KW - fixed priority

KW - non-preemptive tasks

KW - real-time systems

KW - sufficient infeasibility test

UR - https://www.mendeley.com/catalogue/597486a2-655b-32ac-92fe-513881335299/

UR - https://www.scopus.com/record/display.uri?eid=2-s2.0-85218683181&origin=inward&txGid=6bae9884921b4805520d40329bd93b86

U2 - 10.3390/asi8010015

DO - 10.3390/asi8010015

M3 - Article

VL - 8

JO - Applied System Innovation

JF - Applied System Innovation

SN - 2571-5577

IS - 1

M1 - 15

ER -