Laufzeit-Berechnung

Wie man die »Worst Execution Time« bestimmt

Software im sicherheitskritischen Bereich muss zeitliche Randbedingungen unter allen Umständen einhalten. Um dies nachzuweisen, wird häufig die „Worst-Case Execution Time“ herangezogen. Um diese maximale Laufzeit zu erhalten, gibt es verschiedene Herangehensweisen – bequeme und weniger bequeme.

Die immer höhere Leistungsfähigkeit moderner Prozessoren in Embedded-Systemen bringt es mit sich, dass auch die darauf laufende Software immer komplexer wird. Um zu verifizieren, dass eine maximale Reaktionszeit nicht überschritten wird, muss das zeitliche Verhalten der Software genau untersucht werden. Dort, wo die Zeitschranken nicht eingehalten werden, kann die Analyse Schwachstellen aufdecken, an denen sich eine Code-Optimierung lohnt. Besonders die „Worst-Case Execution Time“ (WCET) ist in diesen beiden Fällen von großem Interesse. Man kann versuchen, sie durch rein analytische Verfahren zu ermitteln oder sie durch einen kombinierten Ansatz aus statischer Analyse und echter Zeitmessung auf dem Zielsystem zu berechnen.

Der analytische Weg: Berechnung auf Grundlage von Simulation

Eine Möglichkeit, das zeitliche Verhalten einer Software zu ermitteln, ist die vollständig statische Analyse. Sie besteht im Groben aus zwei Schritten: Zunächst muss der Programm-Code analysiert werden. Dies kann entweder auf der Ebene der verwendeten Hochsprache, z.B. C, geschehen oder auf der Ebene des Maschinen-Codes. Hier muss versucht werden, vorherzusagen bzw. zu simulieren, wie der Code ausgeführt wird bzw. werden kann. Da dies aber nur in einem sehr beschränkten Maße vollautomatisch geschehen kann – an dieser Stelle sei auf Alan Turings und die Nichtentscheidbarkeit des Halteproblems sowie auf Kurt Gödels Unvollständigkeitssatz verwiesen –, muss man in der Praxis der Analyse- Software noch sehr viele zusätzliche Informationen geben, die sie selber, nur auf Basis des Programm- Codes, nicht herleiten kann (so genannte Annotationen). Es muss z.B. teilweise angegeben werden, welche Werte einige Variablen annehmen können oder wie sich externe Ereignisse auswirken können.

Der zweite Schritt besteht darin, zu verstehen, welche konkreten Zeiten sich aus der vorherigen Analyse auf der echten Hardware ergeben. Dazu benötigt man ein sehr genaues Modell der verwendeten Hardware. Gerade bei modernen Prozessoren mit mehrstufigen Pipelines und Caches ist die Erstellung eines solchen Modells sehr aufwendig. Der Vorteil eines solchen Verfahrens ist, dass, wenn es ein WCET-Ergebnis liefert, dieses analytisch hergeleitet wurde und eindeutig ist. Das trifft aber nur unter der Voraussetzung zu, dass alle gemachten Angaben sowie das Modell der Hardware korrekt sind! Der Aufwand für dieses Verfahren und die damit verbundenen Kosten sind allerdings sehr hoch.

 

Vollbild

Bild 1. Beim kombinierten Verfahren werden Zeitmessungen am echten Target durchgeführt. Die jeweils längsten Zeiten für verschiedene Wege durch den Programm-Code werden summiert und die Ergebnisse verglichen. Die längste mögliche Laufzeit ist die WCE

Schliessen

Bild 1. Beim kombinierten Verfahren werden Zeitmessungen am echten Target durchgeführt. Die jeweils längsten Zeiten für verschiedene Wege durch den Programm-Code werden summiert und die Ergebnisse verglichen. Die längste mögliche Laufzeit ist die WCE

Der pragmatische Weg: Messen und Berechnen

Eine weitere Möglichkeit, die Worst- Case Execution Time zu bestimmen, ist ein kombiniertes Verfahren aus statischer Code-Analyse und Zeitmessung auf dem echten Target. Hierbei wird zunächst eine statische Code- Analyse durchgeführt, um die möglichen Pfade zu analysieren, die die Software durch den Code nehmen kann. Das Ergebnis dieser Analyse ist ein so genannter Call- Tree. Als nächstes wird der Quelltext instrumentiert. Das bedeutet, dass in den Quelltext an allen entscheidenden Stellen (Anfang und Ende von Funktionen, Verzweigungen, Schleifen etc.) Instruktionen eingefügt werden, um bei der späteren Ausführung protokollieren zu können, wann welcher Code in welcher Reihenfolge ausgeführt wurde. Der so instrumentierte Code wird anschließend übersetzt und auf der Ziel-Hardware zum Laufen gebracht. An den Instrumentierungspunkten erzeugt das Programm dann jeweils eine eindeutige Ausgabe (Bild 1).

Gekoppelt mit den Zeitpunkten des Auftretens entsteht so ein Protokoll, wann sich das Programm wo befand, also wie lange es für die einzelnen Teilabschnitte benötigte. Um eine Aussage zur WCET zu machen, genügt es nicht, aus diesem Protokoll die längsten Ausführungszeiten für die einzelnen Programmteile zu extrahieren. Es besteht durchaus die Möglichkeit, dass die Bedingungen, unter denen es zur WCET kommt, während des Testlaufes gar nicht aufgetreten sind. Allerdings kann man sich der WCET durch eine Analyse des erstellten Protokolls in Kombination mit dem Call-Tree hinreichend genau nähern. Dazu werden die längsten gemessenen Ausführungszeiten der einzelnen Teilabschnitte des Programms herangezogen. Anhand des Call-Trees wird dann der zeitlich längste Pfad durch das Programm ermittelt – und damit die Worst-Case Execution Time. Die so ermittelte WCET lässt auch Rückschlüsse auf die Qualität der Testfälle zu, die während der Ausführung angewendet wurden.

Weicht die ermittelte WCET signifikant von der längsten tatsächlich gemessenen Zeit ab, gibt es zumindest einen Pfad durch das Programm, der gar nicht ausgeführt wurde. Zu diesem Ergebnis kann man kommen, wenn es sich entweder um einen Pfad handelt, bei dem sich z.B. zwei Verzweigungen im Programm logisch ausschließen, oder wenn der entsprechende Testfall fehlt. Der erste Fall kann ignoriert werden, im zweiten Fall muss der Testfall nachgepflegt werden. Ein weiteres Ergebnis, das sich aus dem aufgezeichneten Protokoll ergibt, ist eine Code-Coverage- Analyse, da bekannt ist, welche Code- Segmente tatsächlich ausgeführt wurden.

1. Teil: Wie man die »Worst Execution Time« bestimmt
2. Teil: Tool-Unterstützung für die Laufzeit-Analyse

Weiterführende Links:

• Zeitverhalten automatisch analysieren und optimieren: Kurzer Weg zum schnellen Code