Die Überprüfung des korrekten Zeitverhaltens nennt man Planbarkeitsanalyse (engl.: schedulability analysis). Ein Echtzeitsystem besteht häufig aus mehreren Teilprogrammen. In allen bekannten Ansätzen zur Planbarkeitsanalyse wird vorrausgesetzt, daß die schlimmste Ausführzeit (WCET, von engl. worst-case execution time) jedes einzelnen Teilprogramms bekannt ist.
Da die wirkliche Maximallaufzeit eines Programmes im allgemeinen nicht berechenbar ist, wird stattdessen eine obere Schranke berechnet. Bei Echtzeitsystemen müssen diese Vorhersagen sicher sein, d.h. die wirkliche Maximallaufzeit des Programmes darf niemals unterschätzt werden. Weiterhin sollten die Vorhersagen möglichst genau sein, um die Wahrscheinlichkeit einer erfolgreichen Planbarkeitsanalyse zu erhöhen.
Die meisten statischen Analysen, die WCET-Analyse eingeschlossen, untersuchen den Kontrollfluß eines Programmes. Da aber das Verhalten normalerweise vor Ablauf des Programms nicht bekannt ist, müssen Analysen mit einer Annäherung an den Kontrollfluß vorliebnehmen. Diese Annäherung nennt man Kontrollflußgraph.
Heutige Echtzeitsystem benutzen moderne Hardware, um deren Leistungsvorteile auszunutzen. Die Architekturen benutzen häufig heuristische Bausteine, wie Caches oder Pipelines, die die Ausführungsgeschwindigkeit des Programmes in häufig vorkommenden Situationen erhöhen sollen. Um starke Überschätzungen der Laufzeit zu vermeiden, muß eine WCET-Analyse typischerweise das Verhalten dieser Bausteine mitberücksichtigen.
Zur Vorhersage des Verhaltens von Hardwarebausteinen ist es normalerweise erforderlich, das Programm hardwarenah zu analysieren. Daher benutzt man für die Analyse das Maschinenprogramm. Die Ausführgeschwindigkeit hängt auch von den verarbeiteten Daten ab, vor allem von den Adressen, die zum Zugriff auf den Speicher benutzt werden. Auch aus diesem Grund verwendet man Maschinenprogramme, denn die nötigen Informationen sind dort vorhanden.
Im ersten Teil dieser Arbeit wird ein neuartiger Ansatz zur Rückberechnung von Kontrollflußgraphen aus Maschinenprogrammen vorgestellt. Die allgemeine Aufgabe ist schwierig, denn oft ist der mögliche Kontrollfluß nicht offensichtlich, z.B. bei der Verwendung von Funktionszeigern, switch-Tabellen oder dynamischen Methodenaufrufen. Desweiteren ist es häufig schwierig, vorherzusagen, welchen Einfluß bestimmte Befehlen auf den Kontrollfluß haben, da diese mitunter in verschiedenen Situationen auftauchen.
Der in dieser Arbeit vorgestellte Algorithmus zur Rückberechnung von Kontrollflußgraphen wurde unter besonderer Beachtung der speziellen Anforderungen von Echtzeitsystemanalyse entwickelt, denn ohne eine sichere Rückberechnung von Kontrollflußgraphen können darauf arbeitende Analysen ebenfalls nicht sicher sein.
Die Rückberechnung läßt sich in zwei Phasen zerlegen: a) die Erstellung einer Klassifizierung eines Maschinenbefehls bei Eingabe eines Byte-Stroms und der Adresse des Befehls, b) die automatische Rückberechnung eines sicheren und genauen Kontrollflußgraphen bei Eingabe einer Menge von Befehlsklassifikationen.
Um die erste Aufgabe zu lösen, werde ich einen sehr effizienten Entscheidungsbaum vorstellen, mit dessen Hilfe sich eine Folge roher Bytes in eine Befehlsklassifikation umwandeln läßt. Ein Algorithmus zur automatischen Berechnung eines solchen Entscheidungsbaums wird vorgestellt werden, der als Eingabe einzig eine Spezifikation erhält, die sich leicht aus der Architekturbeschreibung des Herstellers erstellen läßt. Dieser Ansatz befreit den Benutzer von fehlerträchtiger Programmierarbeit, die bisher nötig war.
Zur Rückberechnung eines Kontrollflußgraphen aus einer Menge von Befehlsklassifikationen wird ein Bottom-Up-Ansatz vorgestellt werden. Dieser überwindet Probleme von Top-Down-Ansätzen, die sich zwar gut zum Programmieren von Disassemblern oder Debuggern eignen, aber keineswegs den Anforderungen von Echtzeitsystemen gerecht werden. Unser Bottom-Up-Ansatz hingegen wird diesen gerecht und ist zudem sehr effizient implementiert.
Der zweite Teil dieser Arbeit behandelt die Analyse von Echtzeitsystemen selbst. Hardwarenahe WCET-Analyse kann man in zwei Teile aufspalten: a) die Analyse des Verhaltens der Hardwarebausteine für jeden Block des Programmes, b) die Berechnung einer oberen Schranke der WCET des Programms basierend auf den Ergebnissen der Analyse in a). b) nennt man Pfadanalyse.
Eine verbreitete Methode der Pfadanalyse benutzt Ganzzahlige Lineare Programmierung (ILP von engl. Integer Linear Programming). Die Idee dabei ist, daß man den Kontrollfluß des Programmes durch Nebenbedingungen beschreibt und die Laufzeiten der einzelnen Blöcke des Programmes in einer Zielfunktion zusammenfaßt. Das Maximierungsproblem der Zielfunktion unter Beachtung der Nebenbedingungen löst dann das Problem der Suche nach einer oberen Schranke für die Maximallaufzeit des Programmes.
Weil moderne Hardware sich komplex verhält, müssen normalerweise ausgefeilte Methoden zur WCET-Analyse verwendet werden. Beispielsweise sollten Routinenaufrufe nicht isoliert behandelt werden, da sich ihr Verhalten von Aufruf zu Aufruf stark unterscheiden kann. Das liegt daran, daß der Zustand der Hardwarebausteine die Ausführzeiten stark beeinflussen.
Aus diesem Grunde verbessert man die Vorhersagen für gewöhnlich, indem man Routinenaufrufe in verschiedenen Kontexten analysiert, wobei die Kontexte davon abhängen, was im Programm vorher schon ausgeführt wurde.
Um von Kontexten Gebrauch zu machen, müssen beide Teile der WCET-Analyse, die der Bausteine und die Pfadanalyse, sie verarbeiten können. Bisher war es nicht untersucht, wie man auf ILP beruhende Pfadanalysen mit beliebigen statisch berechneten Kontextzuweisungen durchführen kann. Diese Arbeit schließt diese Lücke und stellt einen Ansatz vor, der dem Benutzer des Analysewerkzeugs einen hohen Grad an Freiheit überläßt.
Alle in dieser Arbeit vorgestellten Algorithmen sind in Werkzeugen implementiert, die inzwischen in universitärem wie industriellem Gebrauch sind.