Universitšt Oldenburg
Fachbereich Informatik

Publications: Details


Document Description

Author: Olaf Maibaum
Title: Bestimmung symbolischer Laufzeiten in eingebetteten Echtzeitsystemen
Kind of Publication: Dissertation. Berichte aus dem Fachbereich Informatik 02/03, Universität Oldenburg, June 2003
Date: June 2003
Institution: Universitšt Oldenburg; Graphen und Netzwerke
Pages, Language 148 German
Keywords: Real Time Software, Embedded System, Worst Case Execution Time (WCET), Program Runtime
CR Classification: D.2.4[Software/Program Verification], D.4[Specifying and Verifying and Reasoning about Programs], I.1.4[Applications],
General Terms (ACM): Algorithms, Verification
up

Abstract

Embedded real time systems require both, functional correctness and timing correctness. There are several aproaches to check timing correctness of processes in embedded real time systems. They all calculate an upper bound for the computing time, i.e. worst case execution time (WCET), from annotations in the source code. However, the so calculated upper bound for the computing time of a process exceeds the measured computing time by far. This leads to a waste of the resource computing time. Therefore, an improvement in the calculation of the computing time is necessary.

This thesis presents a graph based approach to determine a symbolic representation of the computing time in dependency of the stimuli. This appoach allows an exact computation of the upper bound for the computing time of a process. Further, it is possible to determine functional expressions for process properties or for sets of stimuli with a maximal computing time of the process.

Kurzfassung

Eingebettete Echtzeitsysteme unterliegen neben der Anforderung nach einer funktionalen Korrektheit auch der Forderung nach einer zeitlichen Korrektheit. Zur Überprüfung der zeitlichen Korrektheit eines Prozesses in einem eingebetteten Echtzeitsystem liegen zur Zeit Verfahren vor, welche anhand von Annotationen im Quelltext eines Prozesses eine obere Schranke für die Laufzeit des Prozesses berechnen. Diese Zeit wird als Worst Case Execution Time bezeichnet. Die berechnete obere Schranke liegt jedoch weit über den meßbaren Laufzeiten eines Prozesses. Die Forderung nach einer besseren Auslastung der Ressource Rechenzeit verlangt deshalb nach einer Verbesserung der vorliegenden Verfahren.

In dieser Arbeit wird ein graphbasiertes Verfahren zur symbolischen Bestimmung der Laufzeit in Abhängigkeit der Stimuli vorgestellt. Diese Vorgehensweise erlaubt eine exakte Berechnung der oberen Schranke für die Laufzeit eines Prozesses. Desweiteren ist es mit dem vorgestellten Verfahren auch möglich, funktionale Eigenschaften innerhalb des Prozesses und kritische Stimuli zu bestimmen, unter denen ein Prozeß seine maximale Rechenzeit annimmt.
up

Download

up

Remarks

None.
up


Last change: 2006/02/26 (Stiege)