Sep 18 – 20, 2024
Europe/Vienna timezone

Did you behave in real-time? A probabilistic evaluation with trace data

Sep 19, 2024, 3:00 PM
22m
"Hall N2" (Austria Center)

"Hall N2"

Austria Center

161
Real-time MC Real-time MC

Speaker

Mr Benno Bielmeier (OTH Regensburg)

Description

Ensuring temporal correctness of real-time systems is challenging.
The level of difficulty is determined by the complexity of hardware, software, and their interaction.
Real-time analysis on modern complex hardware platforms with modern complex software ecosystems, such as the Linux kernel with its userland, is hard or almost impossible with traditional methods like formal verification or real-time calculus.
We need new techniques and methodologies to analyse real-time behaviour and validate real-time requirements.

In this talk, we present a toolkit designed to evaluate the probabilistic Worst-Case Execution Time (pWCET) of real-time Linux systems.
It utilises a hybrid combination of traditional measurement-based and model-based techniques to derive execution time distributions considering variability and uncertainty in real-time tasks.
This approach provides assessment of execution time bounds and supports engineers to achieve fast and robust temporal prediction of their real-time environments.

Our framework models runtime behaviour and predicts WCET in a streamlined four-phase process: (1) model relevant aspects of the system as finite automaton, (2) instrument the system and measure latencies within the model, (3) generate a stochastic model based on semi-Markov chains, and (4) calculate pWCET via extreme value statistics.
This method is applicable across system context boundaries without being tied to specific platforms, infrastructure or tracing tools.

The framework requires injecting tracepoints to generate a lightweight sequence of timestamped events.
This can be done by existing Linux tracing mechanisms, for instance, BPF or ftrace.
Benefits include significantly reduced WCET measurement duration from days to minutes, dramatically accelerating development cycles for open-source systems with frequent code updates like Linux.
This efficiency doesn't compromise accuracy; our hybrid approach ensures robust temporal predictions, enabling developers to quickly assess real-time implications of changes and maintain system performance.

In our talk, we outline the steps taken towards this new evaluation method and discuss the limitations and potential impacts on the development process.
We invite interaction from the community to discuss the benefits and limitations of this approach.
Our goal is to refine this toolkit to enhance its utility for Linux kernel developers and maintainers, ultimately contributing to a more efficient and effective development process for real-time systems.

Primary author

Mr Benno Bielmeier (OTH Regensburg)

Co-authors

Ralf Ramsauer (OTH Regensburg) Prof. Wolfgang Mauerer (OTH Regensburg)

Presentation materials