Skip to main content

Probabilistic Temporal Analysis of Operating Systems Code (Potoroo)


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:

  1. Providing the worst-case execution (WCET) time of all software running on the computer system.
  2. 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.


This project aims to provide L4 with an 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.

               Example Profile

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.

Potoroo Toolset Overview

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.

Currently we have done the base analysis on an older version of the L4 kernel and move now towards the current OKL4 version. This creates new challenges as the kernel introduces preemption points and a single stack design using continuations. The static analysis portion is expected to deliver results in the next couple of months.




Abstract PDF Stefan M. Petters
Execution-time profiles
Technical Report, NICTA, January, 2007
Abstract PDF Mohit Singal and Stefan M. Petters
Issues in analysing L4 for its WCET
International Workshop on Microkernels for Embedded Systems, Sydney, Australia, January, 2007
Abstract PDF Stefan Schaefer, Bernhard Scholz, Stefan M. Petters and Gernot Heiser
Static analysis support for measurement-based WCET analysis
12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications, Work-in-Progress Session, Sydney, Australia, August, 2006
Abstract PDF Kevin Elphinstone, Gernot Heiser, Ralf Huuck, Stefan M. Petters and Sergio Ruocco
3rd Embedded Security in Cars Conference (escar), Cologne, Germany, November, 2005
Abstract PDF Stefan M. Petters
Deadline spanning: A graph based approach
Embedded Real-Time Computing Systems and Applications (RTCSA 2005), Hong Kong, China, August, 2005