Fachbereich Informatik  Abteilung
Betriebssysteme und Verteilte Systeme 		Universität Oldenburg   

Publications: Details

Document Description

Author: Olaf Maibaum
Title: Symbolic Execution Time Determination in Embedded Real-Time Systems
Kind of Publication: In Proceedings of the Conquest '99
Publisher: Arbeitskreis Software Qualität Franken e.V.
ISBN 3-00-004774-3
Date: September 1999
Pages, Language 350-358, English
Keywords: analysis of programs, system modelling embedded real-time systems, timing behaviour, worst case execution time
CR Classification: D.2.4 [Program Verification]; D.2.5 [Testing and Debugging] Test data generators;
General Terms (ACM): Theory, Verification
up

Abstract

We present an approach to determine symbolic expressions of the execution time of a task. The approach is based on a directed graph structure annotated with symbolic expressions for transformations issued by a task and the condition for each transformation. The computation time consumed by a task is seen as part of the transformations. From the graph structure we compute the basic paths of a task and the appropriate conditions and transformations. To analyse loops we use a further graph structure to express the structure of loops, and recurrence equations are used to prevent the explosion of the number of basic paths in the analysis.

The computed conditions and transformations can be used to determine the worst case execution time or to generate a set of stimuli for tests and simulations. An application for the scheduling of embedded real time systems is also mentioned.

Kurzfassung

Wir präsentieren einen Ansatz zum Bestimmen von symbolischen Ausdrücken der Ausführungszeit von Tasks. Der Ansatz basiert auf einer gerichteten Graphstruktur, welche annotiert ist. Die Annotationen sind symbolische Ausdrücke der durch den Task verursachten Transformationen und die Bedingung für jede der Transformationen. Die durch einen Task verbrauchte Berechnungszeit wird als Teil der Transformation des Tasks gesehen. Aus der Graphstruktur werden fü jeden Basispfad die zugehörige Bedingungen und Transformationen abgeleitet. Zur Analyse von Schleifen wird eine weitere Graphstruktur verwendet, um die Struktur von Schleifen auszudrücken. Um die Explosion der Anzahl der Basispfade während der Analyse zu verhindern, werden Differenzengleichungen verwendet.

Die berechneten Bedingungen und Transformationen können verwendet werden, um die WCET eines Tasks zu bestimmen oder um eine Menge von Stimuli zur Verwendung in Tests und Simulationen zu generieren. Eine Anwendung im Bereich des Schedulings von eingebetteten Echtzeitsystemen wird ebenfalls erwähnt.

up

Download

up

Remarks

None.
up


Last change: Sep 30, 1999 Maibaum