1. An evaluation of approaches to model checking real-time task schedulability analysis.
- Author
-
Nxumalo, Madoda, Timm, Nils, and Gruner, Stefan
- Subjects
- *
TASK analysis , *CONFERENCE papers , *CLOCKS & watches , *INTEGERS - Abstract
This article is a follow-up contribution that extends the conference paper (Nxumalo, in: Laarman, Sokolova (eds)Model Checking Software - 27th International Symposium, 2021) which presented the spotlight abstraction method to enable an efficient model checking of schedulability properties of real-time operating systems. Our approach is based on iterative spotlight abstraction whereby the real-time task queue is divided into a so-called spotlight and a shade. Initially, an abstract state space model is generated from the spotlight, which contains a small number of tasks that appear at the front of the queue and the shade contains the remaining tasks. The schedulability of the spotlight tasks is model checked, whereas the behavior of the shade is summarized, and the result is saved for later re-use. If this result is still inconclusive, more tasks are iteratively brought from the shade into the spotlight, with which the model checker can proceed. These steps are repeated until a decisive schedulability result is obtained. In this article, we enrich the encoding of real-time systems into timed automata by separating operations over clock variables from operations based on other variables such as Boolean and integers. We enforce to maintain a reasonable size of the spotlight model by applying counter abstraction to the tasks that were previously confirmed schedulable in the previous iterations. We compare our approach against Timestool and RTLib, an Uppaal template, in the analysis of the schedulability of real-time tasks for the First-In-First-Out and Shortest-Deadline-First scheduling policies. Empirical results show that our approach can handle more tasks than Timestool and RTLib. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF