Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.18308 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914986893246464 |
|---|---|
| author | Picard, Simon Paolillo, Antonio Geeraerts, Gilles Goossens, Joël |
| author_facet | Picard, Simon Paolillo, Antonio Geeraerts, Gilles Goossens, Joël |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_18308 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exact schedulability test for sporadic mixed-criticality real-time systems using antichains and oracles Picard, Simon Paolillo, Antonio Geeraerts, Gilles Goossens, Joël Operating Systems 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. |
| title | Exact schedulability test for sporadic mixed-criticality real-time systems using antichains and oracles |
| topic | Operating Systems |
| url | https://arxiv.org/abs/2410.18308 |