Please use this identifier to cite or link to this item:
doi:10.22028/D291-25778
Title: | Control flow graphs for real-time systems analysis: reconstruction from binary executables and usage in ILP-based path analysis |
Author(s): | Theiling, Henrik |
Language: | English |
Year of Publication: | 2002 |
SWD key words: | Echtzeitsystem ; Worst-Case-Laufzeit ; Statische Analyse ; Planbarkeitsanalyse ; Kontrollflussdiagramm ; Pfadanalyse |
DDC notations: | 004 Computer science, internet |
Publikation type: | Dissertation |
Abstract: | Real-time systems have to complete their actions w.r.t. given timing constraints. In order to validate that these constraints are met, static timing analysis is usually performed to compute an upper bound of the worst-case execution times (WCET) of all the involved tasks. This thesis identifies the requirements of real-time system analysis on the control flow graph that the static analyses work on. A novel approach is presented that extracts a control flow graph from binary executables, which are typically used when performing WCET analysis of real-time systems. Timing analysis can be split into two steps: a) the analysis of the behaviour of the hardware components, b) finding the worst-case path. A novel approach to path analysis is described in this thesis that introduces sophisticated interprocedural analysis techniques that were not available before. Echtzeitsysteme müssen ihre Aufgaben innerhalb vorgegebener Zeitschranken abwickeln. Um die Einhaltung der Zeitschranken zu überprüfen, sind für gewöhnlich statische Analysen der schlimmsten Ausführzeiten der Teilprogramme des Echtzeitsystems nötig. Diese Arbeit stellt die Anforderungen von Echtzeitsystem an den Kontrollflussgraphen vor, auf dem die statischen Analysen arbeiten. Ein neuartiger Ansatz zur Rückberechnung von Kontrollflußgraphen aus Maschinenprogrammen, die häufig die Grundlage der WCET-Analyse von Echtzeitsystemen bilden, wird vorgestellt. WCET-Analysen können in zwei Teile zerlegt werden: a) die Analyse des Verhaltens der Hardwarebausteine, b) die Suche nach dem schlimmsten Ausführpfad. In dieser Arbeit wird ein neuartiger Ansatz der Pfadanalyse vorgestellt, der für ausgefeilte interprozedurale Analysemethoden ausgelegt ist, die vorher hier nicht verfügbar waren. |
Link to this record: | urn:nbn:de:bsz:291-scidok-2973 hdl:20.500.11880/25834 http://dx.doi.org/10.22028/D291-25778 |
Advisor: | Reinhard Wilhelm |
Date of oral examination: | 4-Feb-2003 |
Date of registration: | 12-Jul-2004 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
HenrikTheiling_ProfDrReinhardWilhelm.pdf | 997,74 kB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.