FöRFATTARE
Leijon, Viktor

INSTITUTION
Systemteknik / EISLAB

SAMMANFATTNING
There are two important questions to ask regarding the correct execution of a real-time program:

(i) Is there a platform such that the program executes correctly?

(ii) Does the program execute correctly on a particular platform?

The execution of a program is correct if all actions are taken within their execution window, i.e. after their release time but before their deadline. A program which executes correctly on a specific platform is said to be feasible on that platform and an incorrect program is one which is not feasible on any platform.

In this thesis we develop a timed process calculus, based on the pi-calculus, which can help answer these questions. We express the time window in which computation is legal by use of two time restrictions, before and after, to express a deadline and a release time offset respectively.

We choose to look at correctness through the traces of the program. The trace of a program will always be a sequence of interleaved internal reductions and time steps, because programs have no free names. We define the meaning of a feasible program by use of these traces. In particular we define the speed of a particular system as the ratio between work steps and time steps.

Based on this calculus we show how the two questions above can be answered in terms of traces of the process calculus and prove the classical utilization limit for Earliest Deadline First scheduling holds.

ISSN 1402-1757 / ISRN LTU-LIC--08/33--SE / NR 2008:33