Exact schedulability test for sporadic mixed-criticality real-time systems using antichains and oracles

Abstract

This work addresses the problem of exact schedulability assessment in uniprocessor mixed-criticality real-time systems with sporadic task sets. We model the problem by means of a finite automaton that has to be explored in order to check for schedulability. To mitigate the state explosion problem, we provide a generic algorithm which is parameterised by several techniques called oracles and simulation relations. These techniques leverage results from the scheduling literature as "plug-ins" that make the algorithm more efficient in practice. Our approach achieves up to a 99.998% reduction in the search space required for exact schedulability testing, making it practical for a range of task sets, up to 8 tasks or maximum periods of 350. This method enables to challenge the pessimism of an existing schedulability test and to derive a new dynamic-priority scheduler, demonstrating its good performance. This is the full version of an RTNS 2024 paper.

In the proceedings of 32nd International Conference on Real-Time Networks and Systems, RTNS24, ACM, 2024

References in corpus (4)

• Algorithms for Omega-Regular Games with Imperfect Information
• Antichains for the Automata-Based Approach to Model-Checking
• Efficient Schedulability Test for Dynamic-Priority Scheduling of Mixed-Criticality Real-Time Systems
• Exact schedulability test for sporadic mixed-criticality real-time systems using antichains and oracles

Cited by in corpus (1)

• Exact schedulability test for sporadic mixed-criticality real-time systems using antichains and oracles