SysWCET: Ende-zu-Ende-Antwortzeiten für OSEK-Systeme

Anbieter zum Thema

MicroConsult Microelectronics Consulting & Training GmbH

Parasoft® Deutschland GmbH

RTI Real-Time Innovations

Ganzheitliche Systemanalyse von OSEK Systemen

Die Grundlage von SysWCET bildet eine Analyse[2] für gesamte OSEK Systeme, welche nicht nur die statische Konfiguration in Betracht zieht, sondern auch die dynamische Interaktion zwischen Anwendungscode und Betriebssystem. Zusammengefasst lässt sich diese Interaktion durch den globalen Kontrollfluss beschreiben, der sich sowohl durch die Programmlogik der Anwendung und als auch des Kernels webt: ein Thread setzt einen Systemaufruf ab und verändert damit den Kernzustand; der Kernel reagiert auf diese Veränderung und wechselt zum Kontrollfluss eines anderen Threads.

Der OSEK-OS Standard, der zum größten Teil auch in AUTOSAR enthalten ist, bildet dabei die Grundlage unserer Systeme. Der OSEK Standard, welcher in der Automobilindustrie entwickelt wurde, beschreibt statische Echtzeitsysteme die auf Steuergeräten zum Einsatz kommen. Statisch bezieht sich hierbei darauf, dass die Systemkonfiguration bereits zur Übersetzungszeit fest steht. In einer Konfigurationsdatei (OIL File) legt der Entwickler zum Beispiel fest: welche Threads es gibt, wo deren Einstiegspunkte sind, welche Priorität sie haben und ob ein Thread auf ein Software-Ereignis warten kann.

Bildergalerie

Im ersten Schritt unserer Analyse lesen wir diese Konfiguration ein und extrahieren aus dem Anwendungscode die Kontrollflussgraphen (engl. control-flow graphs, CFGs) aller Funktionen. Um die extrahierte Anwendungslogik leichter zu analysieren, fassen wir größere Regionen innerhalb der CFGs zu atomaren Basisblöcken (engl. atomic basic blocks, ABB) zusammen, die aus der Perspektive des Betriebssystemkerns atomar ausgeführt werden. Ein ABB umfasst also den Code zwischen zwei Systemaufrufen.

Im nächsten Analyseschritt kombinieren wir nun die CFGs, die Systemkonfiguration und die OSEK Semantik um den Zustandsgraphen des Systems (engl. state-transition graph, STG) zu erhalten. Beginnend beim Zustand des Betriebssystems beim Booten, gehen wir alle Systemzustände explizit ab und erhalten somit alle möglichen Pfade durch das gesamte System in einem Graphen. Dies wird nun am folgenden Beispiel veranschaulicht.

In Abbildung 3 ist ein Beispielsystem mit 3 Threads und einer ISR abgebildet. Der niederpriore Thread Low wird gestartet und aktiviert der hochprioren Thread High in seinem rechten Pfad. Der Interrupt, welcher die ISR aktiviert, kann (um das Beispiel übersichtlich zu halten) nur in ABB 1 und ABB 4 auftreten. Wird die ISR ausgeführt, so aktiviert sie in jedem Fall den mittelprioren Thread Med.

In Abbildung 4 ist der gesamte Zustandsgraph für die Beispielanwendung abgebildet. Hierbei entspricht jeder Knoten einem einzelnen Systemzustand, welcher unter anderem den Programmzähler des aktuell laufenden Threads und die Liste alle lauffähigen Threads beinhaltet (nicht gezeigt). Die Kanten geben an wie zwischen diesen Zuständen durch Systemaufrufe, Interrupts oder die Anwendungslogik gewechselt werden kann. Im Startzustand (Kante a) wird Thread Low den ABB 1 ausführen, wobei 3 Dinge passieren können: (1, Kante f) der linke Pfad in A wird genommen und wir führen ABB3 als Nächstes aus. (2, Kante b) Wir führen ABB 2 als Nächstes aus, welcher wiederum Thread High aktiviert (Kante c). (3, Kante x) Ein Interrupt tritt auf, Low wird verdrängt und der von der ISR aktivierte Thread Med wird zuerst ausgeführt, bevor Thread Low in ABB 1 fortgesetzt wird (Kante h).

Antwortzeitanalyse als ILP Problem

Der STG ist die Vereinigung aller möglichen Instruktionsfolgen (Ausführungspfade) durch das Gesamtsystem (inkl. Interrupts und RTOS). Um die schlimmstmögliche Antwortzeit für eine Aufgabe zu errechnen, müssen wir den längsten Pfad auf dem STG zwischen erster und letzter Instruktion der Aufgabe finden. Zu diesem Zwecke wenden wir die Technik der impliziten Pfadaufzählung (engl. implicit path-enumeration technique, IPET) aus Systemebene an.

Die IPET wird auf der Programmebene bereits genutzt um die WCET eines Programms zu bestimmen. Dabei wird der Kontrollflussgraph eines Programms als Optimierungsproblem formuliert und hierfür in ein ganzzahlig lineares Programm (engl. integer linear program, ILP) übersetzt. Während der Optimierung wird die Ausführungsfrequenz für jeden Basisblock bestimmt und mit seiner Ausführungsdauer gewichtet.

Da der STG ein Kontrollflussgraph ist, können wir mittels IPET ein ILP formulieren, welches für jeden Systemzustand eine Zustandsfrequenz enthält, die angibt wie häufig dieser Zustand im schlimmstmöglichen Fall besucht wird. Weiterhin betten wir für jeden ABB ein, mittels IPET formuliertes, ILP Fragment ein und leiten seine Aktivierungsfrequenz aus den Zustandsfrequenzen ab. Auf diese Weise erhalten ein integriertes ILP, welches sowohl die möglichen globalen Kontrollflüsse, die sich aus der Ablaufplanung ergeben, als auch die Instruktionsebene enthält.

Um die Skalierbarkeit der SysWCET Methodik zu ermitteln, haben wir die Kontrollsoftware eines Quadrocopters untersucht, welche aus 11 Threads, 3 Alarmen und einer ISR besteht. Innerhalb weniger Minuten konnten wir die WCRT für verschiedene Aufgaben in dieser Anwendung untersuchen, obwohl diese sich gegenseitig mittels Interrupts unterbrechen und das RTOS zur Synchronisation verwenden.

Zusammenfassung

Mit SysWCET haben wir einen Analyseansatz für systemweite Antwortzeitanalysen entwickelt, der alle relevanten Aktivitäten des Echtzeitsystems berücksichtigt und in einer einheitlichen Problemformulierung zusammenfasst. Unter vertretbarem Analyseaufwand von wenigen Minuten können vollständige Systeme automatisch analysiert werden, um verlässliche Schranken der Antwortzeiten zu bestimmen. Die Implementierung von SysWCET ist unter einer Open-Source-Lizenz verfügbar.

Die Autoren

* Christian Dietrich (M.Sc.) arbeitet als Wissenschaftlicher Mitarbeiter an der Leibniz Universität Hannover im Fachbereich System- und Rechnerarchitektur. Sein Hauptinteresse gilt dabei der Interaktionsanalyse zwischen Anwendung und Echtzeitbetriebssystem, sowie der Möglichkeit daraus maßgeschneiderte Systeme automatisch abzuleiten.

* Peter Wägemann (M.Sc.) arbeitet als Wissenschaftlicher Mitarbeiter am Lehrstuhl für Verteilte Systeme und Betriebssysteme der Friedrich-Alexander-Universität Erlangen-Nürnberg. In seiner Forschung beschäftigt er sich mit energiebeschränkten Echtzeitsystemen sowie deren statischer Analyse.

Literatur

[1] C. Dietrich, P. Wägemann, P. Ulbrich, D. Lohmann; SysWCET: Whole-System Response-Time Analysis for Fixed-Priority Real-Time Systems; in Proceedings of the 23nd Real-Time and Embedded Technology and Applications Symposium (RTAS '17), 2017

[2] C. Dietrich, M. Hoffmann, D. Lohmann; Global Optimization of Fixed-Priority Real-Time Systems by RTOS-Aware Control-Flow Analysis; ACM Transactions on Embedded Computing Systems (ACM TECS), no. 16, 2017

(ID:45658264)