Maximale Laufzeit

Die maximale Laufzeit oder maximale Ausführungszeit (englisch Worst Case Execution Time, WCET) gibt die längste Zeit an, die ein Computerprogramm oder Programmteil auf einer bestimmten Plattform zur Ausführung benötigen kann. Sie wird bestimmt durch:

• die Programmlogik (Kontrollflussgraph),
• die Eingabedaten (Auswirkungen auf Schleifendurchlaufzahlen etc.),
• den Compiler (Optimierungsstufe) und
• die Architektur und Taktfrequenz des Ausführungsrechners (Ausführungsgeschwindigkeit unter Berücksichtigung von Cache- und Pipelining-Effekten).

Die Kenntnis der WCET oder zumindest einer sicheren oberen Schranke ist ein notwendiges Kriterium zur Implementierung eines harten Echtzeitsystems. Bei Echtzeitsystemen ist es sehr wichtig, das logisch richtige Ergebnis zu exakten Zeitpunkten zu erhalten. Nur kurze Verzögerungen könnten katastrophale Auswirkungen haben. Die wichtigsten Anwendungsgebiete für Echtzeitsysteme sind z. B. Autoairbagsteuerungen, Flugzeugsteuerungen, Steuerungen in Kraftwerken. Bei Autosteuerungen kann das verspätete Herausschleudern des Airbags tödliche Folgen für die Insassen des Kraftfahrzeuges haben. Daher ist es wichtig, dass Echtzeitsysteme das richtige Ergebnis in einer bestimmten Zeit bereitstellen.

Die Ausführungszeit

Grundsätzlich wird zwischen BCET (best case execution time) und WCET (worst case execution time) unterschieden. Die BCET ist die schnellste Ausführungsdauer, indem das Programm ein Ergebnis liefert, d. h. das Programm kann unter keinen Umständen schneller ausgeführt werden. Die WCET ist die längstmögliche Ausführungsdauer, in der der Programmcode ein Ergebnis bereitstellt.

Grundsätzliche Probleme der Laufzeitbestimmung

Theoretische Grenzen

Im allgemeinen Fall ist es unmöglich die maximale Ausführungszeit für ein beliebiges Programm zu bestimmen.

Um die maximale Ausführungszeit zu bestimmen, müsste man folgendes Problem lösen: Gegeben ist ein Programm P. Gesucht ist ein weiteres Programm WCET, das die maximale Ausführungszeit von P, also WCET(P), berechnet. Da alle jene Programme, die in eine Endlosschleife laufen, eine maximale Ausführungszeit $\infty$ haben, könnte man das Programm WCET benutzen, um zu entscheiden, ob das zugrundeliegende Programm überhaupt terminiert und somit das Halteproblem lösen. Das Halteproblem ist jedoch nachweislich unentscheidbar, somit kann es das Programm WCET nicht geben.

Eine Obergrenze der WCET kann aber für eine relevante Untermenge aller möglichen Programme bestimmt werden.

Praktische Probleme

Die Schedulingstrategien moderner Betriebssysteme verhindern eine zuverlässige Voraussage zu welchem Zeitpunkt ein Task dran kommt. Abhilfe schaffen hier Echtzeitbetriebssysteme oder Direktimplementierungen ohne Betriebssystemschicht.

Auf modernen Prozessorarchitekturen hängt die Ausführungszeit eines Tasks mitunter stark von dem Zustand des Prozessorcaches ab. Selbst bei Verwendung eines Echtzeitbetriebssystems kann es so zu Beeinflussungen zweier Tasks über den Cache kommen.

Methoden zur Bestimmung

Es gibt verschiedene Methoden die WCET zu berechnen, die sich allerdings nur durch Genauigkeit und Anwendbarkeit unterscheiden. Eine wichtige Bedeutung ist es, wie genau die WCET abgeschätzt werden kann. Die Methoden versuchen daher so nahe wie möglich an die wirkliche Ausführungszeit heranzukommen, das Ergebnis darf aber nie kleiner als die tatsächliche Ausführungszeit sein.

Eine Möglichkeit zur Abschätzung der WCET sind Messmethoden. Bei diesen Methoden wird durch verschiedenste Testläufe auf der Zielhardware die Zeit gemessen, welche der Code benötigt, um ein Ergebnis zu liefern. Diese Methode ist sehr aufwändig, da nie alle Zustände getestet werden können (Kombinatorische Explosion).

Bei der WCET-Analyse wird hingegen der längste Ausführungsweg ermittelt und die Ausführungszeit für eine bestimmte Zielhardware so errechnet.

Messbasierte Ansätze

Die messbasierten Ansätze führen statt einer Analyse des Codes das Programm einfach auf der Zielhardware aus und messen die Ausführungszeit. Messbasierte Ansätze führen jedoch im Allgemeinen zu einer Unterschätzung der WCET, da die Ausführungszeit von Programmen generell von den Eingabedaten abhängt. Durch Analyse des Sourcecodes können jedoch Eingabedatensätze erzeugt werden, welche alle Pfade des zu testenden Programms abdecken. Diese Methode vereinfacht zwar die Portierung einer Software, leidet aber ebenfalls unter komplexen Prozessorarchitekturen.

WCET-Analyse

Die WCET-Analyse berechnet den schlechtesten Fall der Ausführungszeit eines bestimmten Codes einer Anwendung, jedoch besteht keine Garantie der Richtigkeit der Ergebnisse des Codes. Weiter ist die WCET vom Programmcode und von der zugrundeliegenden Hardware abhängig, d. h. verschiedene Programmcodes haben auf verschiedenen Rechnerarchitekturen unterschiedliche Worst Case Execution Times. Daher sollte die Analyse immer mit den Hardwarekomponenten durchgeführt werden die auch das Zielsystem besitzt. Bei dieser Methode wird der Programmcode untersucht und der tatsächlich längste Ausführungsweg ermittelt. Dann addiert man die benötigten Prozessorzyklen aller im Pfad befindlichen Maschinencodebefehle und man erhält die WCET.

Probleme bei der WCET-Analyse

Es gibt drei Problemdomänen bei der WCET-Analyse. Einerseits das Herausfinden des auszuführenden Pfades, die Übersetzung des Sourcecodes in den Maschinencode und die Maschinencodeanalyse.

Bestimmung des auszuführenden Pfades (Programmfluss): Ein Problem der WCET-Analyse ist es, den längsten Weg bezüglich der Laufzeit des Sourcecodes herauszufinden. Ein gutes Beispiel dafür sind Schleifen, die nach Abhängigkeit der Eingabe eine andere Ausführungszeit benötigen. Hierbei muss jeder Eingabefall durchgespielt werden. Allerdings ist das bei komplexeren Systemen unmöglich, weil es zu viele verschiedene Eingabemöglichkeiten gibt.

Übersetzung vom Sourcecode in den Maschinencode: Wenn der Pfad bekannt ist, kann der Sourcecode in den Maschinencode übersetzt werden. Das Problem in diesem Fall ist, dass bei neuen Übersetzern sich auch der Programmfluss im Maschinencode ändert. Daraus folgt dann, dass der gefundene Programmfluss mit übersetzt werden muss damit er mit dem Maschinencode übereinstimmt.

Maschinencodeanalyse: Die Dauer der Ausführung ist auch von der verwendeten Hardware abhängig. Der Cache und die Befehlspipelines bestimmen den Zustand der Hardware. Dabei hängt der Cache wieder vom gesamten bis dahin ausgeführten Programm ab. Es kann somit nicht angenommen werden, dass kein Cache existiert. Des Weiteren können auch keine statischen Werte verwendet werden, da sonst die WCET zu ungenau werden würde.

Lösungsansätze der Probleme

Es gibt Lösungsansätze für jedes der drei Probleme, die bei der WCET-Analyse auftreten.

Programmflussanalyse: bei der Programmflussanalyse gibt es mehrere Lösungsansätze. Einer davon wäre, Programmiersprachen zu verwenden, die keinen unüberschaubaren Code erlauben, wie z. B. Rekursionen oder zeitlich unbegrenzt laufende Schleifen. Ein anderer Lösungsansatz wäre es, dem Programmierer im Sourcecode eine Möglichkeit zu geben, Informationen über den Sourcecode zu vermerken. Für diesen Vorschlag müsste jedoch ein spezieller Compiler entwickelt und verwendet werden. Falls man keine speziellen Compiler dafür verwenden will, kann der Programmierer auch seine Informationen außerhalb des Sourcecodes in einer Beschreibungssprache angeben. Eine Bestimmung der Ausführungszeit ist aber nur auf Maschinencodeebene möglich. Somit muss ein WCET-Analyse Tool eine Abbildung von Sourcecodeannotationen auf Maschinencode vornehmen, was nur unter genauer Kenntnis des Compilerverhaltens möglich ist. Dies erfordert eine enge Zusammenarbeit mit dem Analysetool- und Compilerhersteller.

Übersetzung vom Sourcecode in den Maschinencode: das größte Problem liegt jedoch in der Umwandlung des Programmflusses des Sourcecodes in den Programmfluss des Maschinencodes. Ein Lösungsansatz in diesem Fall wäre es, den Programmfluss erst im Maschinencode zu ermitteln. Dadurch fällt die Übersetzung weg. Jedoch ist diese Variante nur schwer lösbar, da der Maschinencode schwer lesbar ist. Die Qualität der WCET-Abschätzung leidet auch darunter, da genaue Informationen zur Ausführungszeit nur im Sourcecode vermerkt werden können.

Maschinencodeanalyse: Einer der sichersten Ansätze um die WCET zu ermitteln ist es, immer einen Cache-Miss anzunehmen, bis die Variable im Datencache steht. Bei der Maschinencodeanalyse wird die Zeit einzelner Befehle und die Beeinflussung anderer Befehle bestimmt. Meistens ist bekannt, wie lange ein Prozessor benötigt, um bestimmte Befehle abzuarbeiten.

Berechnungsmethoden

Die Berechnung der WCET erfolgt aus den Informationen aus Maschinencodeanalyse und Programmflussanalyse. Es gibt verschiedene Möglichkeiten, die WCET zu berechnen. Bei der pfadbasierenden Methode werden alle möglichen Pfade im Programm ermittelt und ihre Ausführungszeit berechnet. Danach wird das Maximum der Ausführungszeit ermittelt. Eine weitere Methode zur Berechnung der WCET ist die baumbasierende Methode. Hierbei wird das gesamte Programm durch einen Parse-Baum ersetzt. Dann wird zu jeder Gruppe von Befehlen eine Ausführungszeit ermittelt. Mit dieser Methode können Programmflussinformationen nur schwer eingebaut werden. Die letzte Methode verwendet einen Integer-Linear-Programm-Solver. Bei dieser Methode wird in jeder möglichen Programmverzweigung eine Integervariable angegeben. Diese Variable erfasst, wie oft der bestimmte Codeteil ausgeführt wurde. Die Zeit für einen bestimmten Pfad im Programm wurde durch die Maschinencodeanalyse ermittelt. Mit dieser Methode wird zusätzlich auch noch der längste Pfad ermittelt.

Liste von Maximale-Laufzeit-Analyse-Tools

• RapiTime
• Bound-T
• aiT
• OTAWA

Siehe auch

• Komplexitätstheorie
• Landau-Notation
• Zeitkomplexität

Literatur

• Reinhard Wilhelm, Jakob Engblom, Andreas Ermedahl, Niklas Holsti, Stephan Thesing, David Whalley, Guillem Bernat, Christian Ferdinand, Reinhold Heckmann, Frank Mueller, Isabelle Puaut, Peter Puschner, Jan Staschulat, and Per Stenström: The Determination of Worst-Case Execution Times-Overview of the Methods and Survey of Tools. ACM Transactions on Embedded Computing Systems (TECS), 7(3), 2008.

Weblinks

• Heiko Falk: Der WCET-Bewusste C-Compiler WCC. Infoseite über das Forschungsgebiet und die -aktivität an der TU Dortmund