| RUS ENG |
| Полная версия |
|
|
|
| СЕМИНАРЫ |
|
Российский гибридный семинар STEP-2023 по фундаментальным вопросам программной инженерии
теории и экспериментальному программированию
|
|||
|
|
|||
|
[Towards a Tractable Exact Test for Global Multiprocessor Fixed Priority Scheduling (2nd 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 марта 2024 г. (https://www.mathnet.ru/present41888). Есть рабочие записи на 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). Язык доклада: английский Website: https://persons.iis.nsk.su/en/STEP-2024
|
|||