Echtzeit-Applikationen
Echtzeitschranken für Multicore-Prozessoren
Fortsetzung des Artikels von Teil 1
Statische Analyse plus Zeit-Analyse
Die Lösung, die im hybriden WCET-Analysewerkzeug TimeWeaver [9] implementiert ist, kombiniert statische Wertebereichs-, Schleifen- und Pfadanalyse mit nichtinvasivem Echtzeit-Tracing auf Instruktionsebene, um das Zeitverhalten von Tasks zu erfassen. Im Vergleich zu End-to-End-Messungen besteht der Vorteil hybrider Ansätze darin, dass Messungen automatisch an kurzen Codeschnipseln vorgenommen werden. Wenn die gemessenen Ausschnitte das gesamte zu analysierende Programm abdecken, kann ein Worst-Case-Pfad berechnet werden.
Die Trace-Informationen können von eingebetteten Trace-Einheiten moderner Prozessoren produziert werden, z.B. Nexus IEEE-ISTO 5001, Arm CoreSight oder Infineon MCDS. Code-Instrumentierung ist nicht erforderlich, der Sondeneffekt wird vermieden. Diese Traces werden in der Regel offline analysiert, aber neue FPGA-basierte Ansätze erlauben es, sie online zu analysieren, was eine kontinuierliche, nichtintrusive Laufzeitüberwachung von eingebetteter Software ermöglicht [10]. Derzeit ist TimeWeaver für Arm, PPC, TriCore/Aurix und RISC-V verfügbar.
Jobangebote+ passend zum Thema
Die wichtigsten Eingaben für TimeWeaver sind ein vollständig gelinktes Executable, die gemessenen Echtzeit-Traces und die Eintrittspunkte der Tasks und Interrupt-Service-Routinen (ISRs). Die Analyse erfolgt in mehreren Schritten (Bild 1): Decodierung, Schleifen- und Wertebereichsanalyse, Trace-Analyse und Pfadanalyse. Die Schritte Decodierung und Schleifen- und Wertebereichsanalyse sind identisch mit den entsprechenden Schritten des aiT WCET Analyzer. Eine zusätzliche Option in der Decodierungs- und Wertanalysephase ist die Extraktion von Aufrufzielen und Schleifengrenzen aus den Eingabe-Traces.
Nach der Wertebereichsanalyse hat der Analysator jede Anweisung im Kontrollflussgraphen mit kontextsensitiven Analyseergebnissen annotiert. Diese Kontextsensitivität ist wichtig, weil die Genauigkeit einer Analyse erheblich verbessert werden kann, wenn die Ausführungsumgebung berücksichtigt wird. Wird zum Beispiel eine Routine von zwei verschiedenen Programmpunkten aus mit unterschiedlichen Registerwerten aufgerufen, kann die Ausführungszeit in beiden Situationen unterschiedlich sein. Die Unterscheidung zwischen den Kontexten führt somit zu einer höheren Genauigkeit des Analyseergebnisses.
Im Trace-Analyse-Schritt werden die gegebenen Traces so analysiert, dass jedes Trace-Ereignis auf einen Programmpunkt im Kontrollflussgraphen abgebildet wird. Diese Zuordnung definiert die Trace-Segmente und ist nicht nur Voraussetzung für die Analyse, sondern stellt auch sicher, dass der Input-Trace mit dem analysierten Binärcode übereinstimmt. Falls ein präemptives System betrachtet wird, werden Unterbrechungen erkannt und gemeldet. Die extrahierten Timing-Informationen, d.h. die Taktzyklen, die zwischen zwei aufeinanderfolgenden Trace-Punkten verstrichen sind, werden kontextsensitiv im Kontrollflussgraph annotiert.
Nach der Trace-Konvertierung steht ein Kontrollflussgraph zur Verfügung, der die Ergebnisse der Wertebereichsanalyse und die aus den Traces extrahierten Ausführungszeiten kombiniert. Dieser Graph ist der Input für den nächsten Schritt, die Pfadanalyse, die auf Basis der Trace-Segmentzeiten den längstmöglichen Ausführungspfad berechnet.
TimeWeaver leitet eine allgemeine obere Schranke der Ausführungszeit aus den in den Traces beobachteten Ausführungszeiten ab. Daher ist die Trace-Abdeckung des analysierten Codes eine wichtige Metrik, die die Qualität der berechneten WCET-Schätzungen beeinflusst. TimeWeaver berechnet die folgenden Abdeckungsmetriken:
- Blockabdeckung (engl. Block Coverage),
- Instruktionsabdeckung (engl. Instruction Coverage),
- Kantenüberdeckung (engl. Edge Coverage) und
- Flussüberdeckung (engl. Flow Coverage).
Die Metriken werden auf der Ebene des Maschinencodes berechnet; eine Abbildung auf die Ebene des Quellcodes ist verfügbar. Bei der Blockabdeckung gibt TimeWeaver für jeden Block an, ob er durch Messungen abgedeckt wurde und wenn ja, wie oft. Diese Information wird auch zur Berechnung der Befehlsabdeckung verwendet.
Pfade, die als unerreichbar erkannt werden, benötigen keine Messungen, sodass die zugehörigen Blöcke bei der Berechnung der Abdeckung ausgeschlossen werden. Auf diese Weise lassen sich fehlende Tests, die zum Auslösen bestimmter Ausführungsszenarien erforderlich sind, leicht erkennen. Die Überprüfung der Anzahl der Messungen für jeden Basisblock ermöglicht es, das Vertrauen in die gemessenen Zeiten zu bewerten.
Zusätzlich gibt TimeWeaver für jedes Trace-Segment auch die minimale, maximale und durchschnittliche Ausführungszeit sowie die Standardabweichung an. Die gleichen Informationen werden auch für alle Traces berechnet, sodass Ausreißer leicht zu erkennen sind. Außerdem werden Schleifen, für die die analytisch bestimmte maximale Iterationsanzahl nicht gemessen wurde, gemeldet.
Einige Basisblöcke sind von mehreren Vorgängern aus erreichbar, sodass eine vollständige Blockabdeckung nicht gewährleistet, dass jeder Weg, auf dem ein Block erreicht werden kann, beobachtet wurde. Dies ist jedoch eine wichtige Kennzahl für die Timing-Analyse, da viele leistungssteigernde Funktionen moderner Prozessoren die Ausführungshistorie mit einbeziehen. Daher berechnet TimeWeaver zusätzlich die Kantenabdeckung und die Flussabdeckung für jeden Block.
Volle Kantenabdeckung bedeutet, dass jede mögliche Kombination eines Blocks und seiner Vorgänger beobachtet wurde. Die Flussabdeckung verbessert diese Metrik, indem sie auch die Nachfolger berücksichtigt, d.h. jede mögliche Kombination von Vorgänger ⇒ Block ⇒ Nachfolger muss beobachtet werden, um eine vollständige Flussabdeckung zu erreichen. Die Flussabdeckung hilft dabei, versteckte Abhängigkeiten in den Messungen aufzudecken.
Zusätzliche Unterstützung bieten Visualisierungen, z.B. Polardiagramme, die es Benutzern ermöglichen, Abweichungen in den Ausführungszeiten von Tasks zu untersuchen oder durchschnittliche und maximale Preemption-Delays zu ermitteln (Bild 2).
Nicht nur für die Luftfahrt
Die EASA-Richtlinie AMC 20-193 formuliert konkrete Vorgaben für den Einsatz von Multicore-Prozessoren für Echtzeitsysteme. Die Methodik der statischen Worst-Case-Ausführungszeitanalyse liefert garantierte WCET-Grenzen für komplexe Prozessoren, wenn das Zeitverhalten des Prozessors vorhersagbar ist und asynchrone Interferenzen kontrolliert oder begrenzt werden können.
Die hybride Worst-Case-Ausführungszeitanalyse ermöglicht es, Schranken der Worst-Case-Ausführungszeit auch auf Hochleistungs-Multicore-Prozessoren zu berechnen, bei denen diese Bedingungen nicht erfüllt sind. Der hybride WCET-Analysator TimeWeaver kombiniert statische Wert- und Pfadanalysen mit Timing-Messungen auf der Grundlage von nichtinvasiven Echtzeit-Traces auf Instruktionsebene. Die Analyseergebnisse umfassen die berechnete WCET-Grenze mit dem zeitkritischen Pfad und Informationen über die erzielte Trace-Abdeckung.
Der Autor
Dr. Daniel Kästner
ist Mitgründer des Unternehmens AbsInt und seit 2003 Leiter der technischen Entwicklung. Er ist Mitglied der ISO-26262- und IEC-61508-Arbeitsgruppen zur Softwaresicherheit sowie der MISRA-C- und MISRA-SQM-Arbeitsgruppen. Seine fachlichen Schwerpunkte sind funktionale Sicherheit, Cybersicherheit, Echtzeitsysteme sowie Compilerbau und Programmanalyse für eingebettete Systeme.
kaestner@absint.com
- Echtzeitschranken für Multicore-Prozessoren
- Statische Analyse plus Zeit-Analyse
- Literatur
Lesen Sie mehr zum Thema
