Motivation
Along with the wave of embedded systems being swept into everyday life, ranging from mobile phone to cars real-time systems become also more ubiquitous. A embedded system is labeld to be also a real-time system, when correctness of operation is not just defined by performing a given function, but also keeping the time needed to perform this function within specified limits. An everyday example is an air-bag system in a car. The computer in this system has to evaluate the data of many sensors quasi continuously and identify a crash. This identification obviously takes time, but has to be performed fast enough, to allow the air-bags to be deployed in time to prevent serious injury of the passengers. The question in this example is: What kind of guarantees can we make that the computer systems identifies the crash in time for the air-bags to be deployed.
Now looking at the technical side how these guarantees can be derived. For this we take the more common case that there are several functions performed by the same computer system. In order to manage these, functions are implemented as tasks on the computer system, which are managed by an (real-time) operating system. The process of providing these guarantees is usually divided into two steps:
- Providing the worst-case execution (WCET) time of all software running on the computer system.
- Establish the worst case response time of the functions implemented by analysing the interactions of the different software parts of the system.
While WCET estimation has been done for application code, no kernel we know of has undergone complete and rigid analysis for its WCET despite being a essential input in performing the second step of the analysis.
Overview
This project aims to provide L4 with a analysis model, which allows on the spot analysis of the temporal behaviour of the kernel on a given platform. In terms of methodology this work is based on the measurement based approach similar to the one used in the RapiTime tool set commercialised by Rapita Systems Ltd. The roots of both are in work done at the University of York within the European NextTTA project published in a number of papers. Based on basic-block-level measurements and a tree representing the kernel, we come up with a worst-case execution time profile for all system calls.
More Detail
The work is based on the observation that a basic block has usually very few different execution times. This can be explained by the fact that on many architectures a cache miss will drain the pipeline. This covers even out-of-order execution units. Getting a basic block to exhibit its worst-case execution time (WCET) is easy. Making that happen for all basic blocks at the same time is not, which explains why end-to-end measurements don't work on modern architectures.
Measurements of small sections of code on basic block level build the core of the approach. The measurements describe a piece of code using the representation of an execution-time profile, a sample of which is depicted above. The execution-time profiles of describing different pieces of software are then combined using a tree to provide data for higher level units of the code. One of the research areas in this project is created by the highly optimised kernel code, which creates makes the generation of the tree particularly interesting. Another area is the establishment of sufficient measurement coverage.
The latter will be tackled using static analysis. But instead of modelling every aspect of the hardware, we focus on the modelling of caches. This allows us to verify that a basic block has been exposed to its worst-case number of cache misses, which accounts to a large degree for its WCET. The information of cache misses can also be used to get dependencies between basic blocks which in turn may be used to reduce overestimation. Watch this space for upcoming work.
The actual timing model will be created for a specific hardware. As a result the approach needs to be tractable for non worst-case execution time experts to be used in the field.
If you have furtehr questions about what we are doing and how we go about it, feel free to contact the project leader Stefan M. Petters.
People
Current
Past
- Rita Shen
- Stefan Schäfer
