Towards a Tractable Exact Test for Global Multiprocessor Fixed Priority Scheduling (the final, 3nd part)

An exact schedulability analysis of a system of sporadic tasks to be executed upon a multiprocessor platform is proved to be a weakly NP-hard computational problem. The available exact tests suffer from a high computation time and memory requirement, which make them intractable for large realistic real-time systems. On the other hand, the available approximate sufficient tests, which are faster and consume less memory, are very pessimistic in provisioning the execution requirements of a given system. Motivated by these observations, we propose an exact schedulability test for constrained-deadline sporadic tasks under global multiprocessor fixed-priority scheduler (GFP), which is significantly faster and consumes less memory, compared to any other available exact test. To derive a faster test, we exploit the idea of a state-space pruning, aiming at reducing the number of feasible system states to be examined by the test. The resulted test is multiple orders of magnitude faster with respect to other state-of-the-art exact tests. The C++ implementation of our test is publicly available.
Это будет заключительная третья часть доклада, первые две части были представлены на заседаниях семинара 6 марта и 24 апреля 2024 г. Есть рабочие записи на YouTube-канале ИСИ СО РАН первой (https://youtu.be/aafrS1zmL64) и второй (https://youtu.be/q6nSyqF5mO4) частей доклада, а также презентация доклада (https://persons.iis.nsk.su/files/persons/pages/burmyakov06mar24_0.pdf).
Это была третья заключительная часть доклада, представленного на заседаниях семинара 6 марта (https://www.mathnet.ru/present41888) и 24 апреля (https://www.mathnet.ru/present42561).
Есть рабочие записи на YouTube-канале ИСИ СО РАН первой (https://youtu.be/aafrS1zmL64), второй (https://youtu.be/q6nSyqF5mO4) и третьей (https://www.youtube.com/watch?v=i7nwvP8SWRg) частей, а также презентация всего доклада (https://persons.iis.nsk.su/files/persons/pages/burmyakov06mar22apr26jun24.pdf).