Echtzeit-Applikationen
Echtzeitschranken für Multicore-Prozessoren
Auf vielen Multicore-Prozessoren lassen sich Interferenzen zwischen den Cores weder vermeiden noch zeitlich exakt vorhersagen. Zur Bestimmung von Echtzeitschranken eignet sich ein hybrider Analyseansatz, der für alle Industriesektoren anwendbar ist und die Anforderungen der AMC 20-193 erfüllt.
Während bei Desktop-Anwendungen vor allem eine hohe durchschnittliche Leistung angestrebt wird, gelten für sicherheitskritische eingebettete Systeme spezielle Anforderungen. Ein Echtzeitsystem muss nicht nur logisch korrekt sein, sondern auch das richtige Zeitverhalten aufweisen. Eine Echtzeit-Task, die ihre Deadline verpasst, kann die Verfügbarkeit reduzieren und schwere Schäden verursachen. Um nachzuweisen, dass eine Task immer vor ihrer Deadline beendet wird, muss ihre Worst-Case-Ausführungszeit (engl. Worst-Case Execution Time, WCET) bekannt sein.
In einem Multitasking-System können Tasks auch vom Task-Scheduler unterbrochen oder blockiert werden. Dies wird bei der Worst-Case-Antwortzeit der Task berücksichtigt (engl. Worst-Case Response Time, WCRT), bei der Unterbrechungseffekte zur WCET hinzuaddiert werden. Alle aktuellen Sicherheitsnormen – darunter DO-178C im Luftfahrtbereich und ISO 26262 im Automobilsektor – verlangen, dass zuverlässige Grenzen für die Ausführungszeit von Echtzeit-Tasks bestimmt werden.
Für hochautomatisierte und autonome Systeme sind die Anforderungen sogar noch höher: Sie müssen ausfallsicher (engl. fail-operational) ausgelegt sein, d.h. ein Systemfehler darf nicht zum vollständigen Systemausfall führen; zumindest ein reduzierter Mindestfunktionsumfang muss weiterhin gewährleistet sein. Die erforderlichen Fehlertoleranztechniken sind teuer, sodass die Fehlervermeidung – z.B. durch die Einhaltung sicherer Zeitgrenzen – von wesentlicher Bedeutung ist.
Wie kann nun das Zeitverhalten methodisch bestimmt werden? Aufgrund von Caches und Pipelines hängt das Timing-Verhalten einer Maschineninstruktion von der Ausführungshistorie ab. Eine vollständige Testabdeckung würde somit bedeuten, jeden möglichen Pfad mit allen möglichen Eingangswerten und jedem möglichen Hardware-Zustand zu durchlaufen. Dies ist aus Komplexitätsgründen unmöglich. Bei direkten Zeitmessungen mit Logikanalysatoren, Debuggern oder Hardware-Simulation werden Zeiten nur für jeweils eine konkrete Eingabe ermittelt; die ermittelten Werte haben daher nur geringe Aussagekraft.
Direkte Ende-zu-Ende-Messungen bestimmen die Ausführungszeiten auf Task-Ebene und geben keinen Einblick in das Ausführungsverhalten und die erreichte Abdeckung innerhalb der Tasks. Messtechniken, die auf Code-Instrumentierung basieren, verändern den Code, was das Cache- und Pipeline-Verhalten signifikant verändern kann (Sondeneffekt). Die gemessenen Zeiten der instrumentierten Software können weit vom Zeitverhalten des ursprünglichen Systems abweichen. Die Aufnahme des Instrumentierungscodes in den Auslieferungsstand der Software erschwert den Entwicklungs- und Verifizierungsprozess und birgt zusätzliche Sicherheitsrisiken.
Jobangebote+ passend zum Thema
Erkennen von Deadline-Überschreitungen per statischer Analyse
Eine Methode, Deadline-Überschreitungen auszuschließen, ist sichere statische Analyse. Statische Analysen werden als sicher (engl. sound) bezeichnet, wenn mathematisch bewiesen wurde, dass sie keine relevanten Fehler übersehen. Solche Beweise sind durch Einsatz der »abstrakten Interpretation«, einer formalen Methode für statische Programmanalysen, möglich [1].
Statische Analysetools auf Basis der abstrakten Interpretation haben sich in den letzten Jahren zunehmend verbreitet und können als Stand der Technik zum Nachweis nichtfunktionaler Korrektheitseigenschaften angesehen werden, z.B. der Abwesenheit von Stack-Überläufen, ungültigen Zeigerzugriffen oder anderen Laufzeitfehlern [2, 3], und der Einhaltung von Zeitschranken [4].
Garantierte obere Schranken für die längstmögliche Ausführungszeit von Tasks können beispielsweise durch das Tool aiT WCET Analyzer berechnet werden [5]. Es analysiert vollständig gelinkte Executables und arbeitet dabei in mehreren Phasen. Im Decoding-Schritt wird das Executable decodiert, und ein Aufruf- und Kontrollflussgraph wird erzeugt. Eine anschließende Schleifen- und Wertebereichsanalyse berechnet sichere Grenzen für die Wertebereiche von Register und Speicherzellen an allen Programmpunkten, leitet daraus maximale Iterationsgrenzen für Schleifen ab und bestimmt Ziele von berechneten Sprüngen und Funktionszeigeraufrufen.
Zentrales Element der Analyse ist die kombinierte Cache- und Pipeline-Analyse, die eine abstrakte Interpretation der Änderungen des relevanten Maschinenzustands durch die Ausführung jeder Instruktion durchführt. Das Ergebnis der Cache- und Pipeline-Analyse ist eine Worst-Case-Ausführungszeit für jeden Basisblock und ein Vorhersage-Graph, der eine zyklengenaue Entwicklung der abstrakten Systemzustände darstellt.
Im letzten Schritt, der Pfadanalyse, wird der längstmögliche Ausführungspfad berechnet, der die Worst-Case-Ausführungszeit der Task ergibt. Statische WCET-Analysatoren sind für komplexe Prozessoren verfügbar und unterstützen im Allgemeinen Single-Core- und Multicore-Prozessoren. Voraussetzung ist, dass zuverlässige Modelle der Prozessoren bzw. System-on-Chips (SoC) ermittelt werden können und dass das Zeitverhalten des Prozessors vorhersagbar ist [6] – ein Beispiel ist der TriCore Aurix. Die berechneten WCET-Schranken können an Tools zur Analyse und Optimierung der Scheduling-Ebene übertragen werden, z.B. die Vector TA Tool Suite.
Herausforderung Multicore und Echtzeit
Viele moderne Hochleistungs-Multicore-Prozessoren enthalten jedoch nicht zeitvorhersagbare und/oder undokumentierte Komponenten, die das Zeitverhalten beeinflussen. Prinzipiell sind bei Multicore-Prozessoren nicht nur die Interferenzen innerhalb der einzelnen Cores zu berücksichtigen, hinzu kommen nun auch Interferenzen durch Zugriffe auf von unterschiedlichen Cores gemeinsam genutzte Ressourcen, darunter geteilter Speicher, Caches und Prefetch-Buffer.
Auf einem Freescale P4080 haben Nowotsch et al. [7] maximale Schreiblatenzen von 39 Zyklen gemessen, wenn nur ein Kern aktiv war, und maximale Schreiblatenzen von 1007 Zyklen, wenn alle acht Kerne aktiv waren – 25-mal länger als der beobachtete beste Fall. Da verschiedene Applikationen meist erst in der Integrationsphase gemeinsam betrachtet werden können, besteht zudem die Gefahr, dass Timing-Probleme erst sehr spät erkannt werden.
Die Richtlinie AMC 20-193 [8] der European Union Aviation Safety Agency (EASA) fasst die relevanten Probleme beim Einsatz von Multicore-Prozessoren für Echtzeitsysteme zusammen und formuliert konkrete Vorgaben. Das Ziel der Software-Verifikation ist der Nachweis, dass die definierten Zeitschranken nicht verletzt werden. Wenn die Plattform eine robuste Ressourcenpartitionierung und eine robuste Zeitpartitionierung bietet, kann die WCET der Applikationen auf unterschiedlichen Kernen separat bestimmt werden. Dies kann auf nicht zeitvorhersagbaren Systemen beispielsweise durch Zeitscheibenverfahren garantiert werden, bei denen jeweils nur ein Kern Zugriff auf gemeinsam genutzte Ressourcen hat. Wenn keine robuste Ressourcen- und Zeitpartitionierung garantiert werden kann, muss die WCET mit allen Softwarekomponenten auf allen Kernen in der vorgesehenen Endkonfiguration bestimmt werden.
- Echtzeitschranken für Multicore-Prozessoren
- Statische Analyse plus Zeit-Analyse
- Literatur
Lesen Sie mehr zum Thema
