Autoren: Christian Dietrich, Leibniz Universit\u00e4t Hannover, Peter W\u00e4gemann, Friedrich-Alexander Universit\u00e4t Erlangen-N\u00fcrnberg<\/p>\n
Um die Rechtzeitigkeit von Aufgaben in Echtzeitsystemen garantieren zu k\u00f6nnen, ist die Bestimmung von schlimmstm\u00f6glichen Antwortzeiten unerl\u00e4sslich. Hierbei ist die Herausforderung die pr\u00e4zise Analyse aller Aktivit\u00e4ten des Gesamtsystems, wie synchrone Systemaufrufe und asynchrone Interrupts, ohne allzu pessimistische Annahmen zu treffen. Zur L\u00f6sung dieses Problems haben wir den Analyseansatz SysWCET entwickelt, der die erste integrierte Formulierung des Antwortzeitproblems erm\u00f6glicht. Diese Formulierung umfasst dabei das vollst\u00e4ndige Rechensystem unter Ber\u00fccksichtigung aller Aufgaben, aller Interrupts und der Ablaufplanung.<\/strong><\/p>\n Die schlimmstm\u00f6gliche Antwortzeit (engl. worst-case response time, WCRT) f\u00fcr die Abarbeitung einer Aufgabe ist eine entscheidende Gr\u00f6\u00dfe von Echtzeitsystemen, die innerhalb bestimmter Zeitschranken Ergebnisse bereitstellen m\u00fcssen. Die WCRT bemisst die Dauer vom Auftreten eines (physikalischen) Ereignisses (z.B. Eintreffen eines Hardwareinterrupts) bis zur Bereitstellung des Ergebnisses (z.B. Setzen eines Motorstellwertes). Sie kennzeichnet somit die Ende-zu-Ende-Antwortzeit einer Aufgabe. Betrachtet man nun ein System, das mehrere Aufgaben mittels mehrerer F\u00e4den (engl. Threads) abarbeitet, so ist die Berechnung der WCRT einer Aufgabe deutlich komplexer als die Berechnung der schlimmstm\u00f6glichen Ausf\u00fchrungszeit der Aufgabe unter Vernachl\u00e4ssigung anderer Threads. Beispielsweise k\u00f6nnen Hardwareinterrupts einen in Ausf\u00fchrung befindenden Thread asynchron unterbrechen, was zu einer Verl\u00e4ngerung der Antwortzeit des unterbrochenen Threads f\u00fchrt. Au\u00dferdem kann die Aktivierung des Echtzeitbetriebssystems (engl. real-time operating system, RTOS) mittels eines Systemaufrufs zu einer Verdr\u00e4ngung f\u00fchren, falls ein h\u00f6herpriorer Thread lauff\u00e4hig wird. Beide F\u00e4lle, asynchrone und synchrone Verdr\u00e4ngungen, k\u00f6nnen dar\u00fcber hinaus auch kombiniert auftreten, wenn das RTOS in der Interruptbehandlung aktiviert wird. Folglich muss in jedem Fall f\u00fcr die korrekte Berechnung der WCRT einer Aufgabe immer das gesamte System (RTOS, Interrupts, andere Threads) ber\u00fccksichtigt werden.<\/p>\n Traditionell wird die WCRT-Analyse in zwei Schritten vollzogen. Zuerst wird jede Aktivit\u00e4t (Threads und Interruptbehandlungen) in Isolation betrachtet und eine WCET pessimistisch berechnet. Hierbei agiert das RTOS als eine Grenze, welche die Analyse nicht \u00fcberschreiten kann. Im zweiten Schritt werden dann diese WCETs pessimistisch anhand der Schedulingstrategie akkumuliert. So werden auf die WCET der betrachteten Aufgabe die WCETs aller h\u00f6herprioren Aufgaben aufgeschlagen (siehe Abbildung 1,\u00a0PDF<\/a>).<\/p>\n Im Beispiel wird zun\u00e4chst f\u00fcr beide Threads (A, B), die Interruptserviceroutine (ISR) und das RTOS eine WCET berechnet (ISR=300, A=103, B=200, RTOS=21). Will man nun die WCRT f\u00fcr Thread A berechnen, so startet man mit der WCET von A: 103 Zyklen. Hat nun Thread B eine h\u00f6here Priorit\u00e4t, so kommen die Kosten f\u00fcr B und die zweifache Aktivierung des RTOS (hin und zur\u00fcck) hinzu: 103+2×21+200=345 Zyklen. Bei einer Aktivierung der ISR kommt man auf insgesamt: 345+2×21+300=687 Zyklen.<\/p>\n Das Problem mit dieser zusammengesetzten WCRT-Analyse ist zum einen ihre grobe Granularit\u00e4t auf Threadebene sowie die fehlende M\u00f6glichkeit, Beeinflussungen zwischen den Threads zu formulieren. In den wenigsten Echtzeitsystemen sind die einzelnen Aufgaben unabh\u00e4ngig voneinander. Der l\u00e4ngste Pfad in einem Thread kann unter Umst\u00e4nden nicht zeitgleich mit dem l\u00e4ngsten Pfad im anderen Thread auftreten. Dazu wird nun das vorherige Beispiel in gr\u00f6\u00dferer Detailtiefe betrachtet (siehe Abbildung 2,\u00a0PDF<\/a>).<\/p>\n Aus dem Kontrollflussgraph von Thread A wissen wir, dass Thread B nur dann aktiviert werden kann, wenn der rechte Pfad, welcher nicht der l\u00e4ngste Pfad durch A ist, abgelaufen wird. Au\u00dferdem ist anzunehmen, dass nicht jeder Pfad durch den Kernel die gleiche Ausf\u00fchrungszeit hat. Bereits mit diesem Wissen, das direkt aus der Struktur des Gesamtsystems ableitbar ist, kann eine pr\u00e4zisere WCRT-Absch\u00e4tzung vorgenommen werden.<\/p>\n Weiterhin haben Dom\u00e4nenexperten h\u00e4ufig weiteres Wissen \u00fcber das Verhalten des Systems. Zum Beispiel kann das Auftreten von Interrupts eingeschr\u00e4nkt sein und nur im linken Pfad von Thread A auftreten. Au\u00dferdem ist es m\u00f6glich, dass die ISR den ersten der beiden Ausg\u00e4nge nimmt, wenn sie Thread A unterbricht.<\/p>\n Bringt man nun all dieses Wissen zusammen, so ist zu erkennen, dass der Pfad, der die l\u00e4ngste WCRT f\u00fcr dieses Beispielsystem ausmacht, folgenden Verlauf hat: Start in Thread A, rechter Pfad, Aktivierung und Wechsel zu Thread B, Abarbeitung von B, Wechsel zu A, Ende in A. In Summe ergibt das eine WCRT von 1+10+14+200+11+2=238 Zyklen, welche deutlich pr\u00e4ziser ist als die durch zusammengesetzte Analyse bestimmte WCRT von 687 Zyklen.<\/p>\n In unserer Forschung haben wir SysWCET[1] entwickelt: eine automatisierte Ende-zu-Ende-Antwortzeitanalyse f\u00fcr OSEK-Systeme. In einer integrierten Problemformulierung fangen wir nicht nur Anwendungs- und Kernelcode ein, sondern bieten zudem die M\u00f6glichkeit, thread\u00fcbergreifende Abh\u00e4ngigkeiten zu formulieren.<\/p>\n Die Grundlage von SysWCET bildet eine Analyse[2] f\u00fcr gesamte OSEK-Systeme, welche nicht nur die statische Konfiguration in Betracht zieht, sondern auch die dynamische Interaktion zwischen Anwendungscode und Betriebssystem. Zusammengefasst l\u00e4sst sich diese Interaktion durch den globalen Kontrollfluss beschreiben, der sich sowohl durch die Programmlogik der Anwendung als auch des Kernels webt: Ein Thread setzt einen Systemaufruf ab und ver\u00e4ndert damit den Kernzustand; der Kernel reagiert auf diese Ver\u00e4nderung und wechselt zum Kontrollfluss eines anderen Threads.<\/p>\n Der OSEK-OS-Standard, der zum gr\u00f6\u00dften 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\u00e4ten zum Einsatz kommen. Statisch bezieht sich hierbei darauf, dass die Systemkonfiguration bereits zur \u00dcbersetzungszeit feststeht. In einer Konfigurationsdatei (OIL-File) legt der Entwickler zum Beispiel fest, welche Threads es gibt, wo deren Einstiegspunkte sind, welche Priorit\u00e4t sie haben und ob ein Thread auf ein Software-Ereignis warten kann.<\/p>\n 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\u00f6\u00dfere Regionen innerhalb der CFGs zu atomaren Basisbl\u00f6cken (engl. atomic basic blocks, ABB) zusammen, die aus der Perspektive des Betriebssystemkerns atomar ausgef\u00fchrt werden. Ein ABB umfasst also den Code zwischen zwei Systemaufrufen.<\/p>\n Im n\u00e4chsten 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\u00e4nde explizit ab und erhalten somit alle m\u00f6glichen Pfade durch das gesamte System in einem Graphen. Dies wird nun am folgenden Beispiel veranschaulicht.<\/p>\n In Abbildung 3 (siehe\u00a0PDF<\/a>) 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 \u00fcbersichtlich zu halten) nur in ABB 1 und ABB 4 auftreten. Wird die ISR ausgef\u00fchrt, so aktiviert sie in jedem Fall den mittelprioren Thread Med.<\/p>\n In Abbildung 4 (siehe\u00a0PDF<\/a>) ist der gesamte Zustandsgraph f\u00fcr die Beispielanwendung abgebildet. Hierbei entspricht jeder Knoten einem einzelnen Systemzustand, welcher unter anderem den Programmz\u00e4hler des aktuell laufenden Threads und die Liste aller lauff\u00e4higen Threads beinhaltet (nicht gezeigt). Die Kanten geben an, wie zwischen diesen Zust\u00e4nden durch Systemaufrufe, Interrupts oder die Anwendungslogik gewechselt werden kann. Im Startzustand (Kante a) wird Thread Low den ABB 1 ausf\u00fchren, wobei 3 Dinge passieren k\u00f6nnen: (1, Kante f) der linke Pfad in A wird genommen und wir f\u00fchren ABB3 als N\u00e4chstes aus. (2, Kante b) Wir f\u00fchren ABB 2 als N\u00e4chstes aus, welcher wiederum Thread High aktiviert (Kante c). (3, Kante x) Ein Interrupt tritt auf, Low wird verdr\u00e4ngt, und der von der ISR aktivierte Thread Med wird zuerst ausgef\u00fchrt, bevor Thread Low in ABB 1 fortgesetzt wird (Kante h).<\/p>\n Der STG ist die Vereinigung aller m\u00f6glichen Instruktionsfolgen (Ausf\u00fchrungspfade) durch das Gesamtsystem (inkl. Interrupts und RTOS). Um die schlimmstm\u00f6gliche Antwortzeit f\u00fcr eine Aufgabe zu errechnen, m\u00fcssen wir den l\u00e4ngsten Pfad auf dem STG zwischen erster und letzter Instruktion der Aufgabe finden. Zu diesem Zweck wenden wir die Technik der impliziten Pfadaufz\u00e4hlung (engl. implicit path-enumeration technique, IPET) auf Systemebene an.<\/p>\n 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\u00fcr in ein ganzzahlig lineares Programm (engl. integer linear program, ILP) \u00fcbersetzt. W\u00e4hrend der Optimierung wird die Ausf\u00fchrungsfrequenz f\u00fcr jeden Basisblock bestimmt und mit seiner Ausf\u00fchrungsdauer gewichtet.<\/p>\n Da der STG ein Kontrollflussgraph ist, k\u00f6nnen wir mittels IPET ein ILP formulieren, welches f\u00fcr jeden Systemzustand eine Zustandsfrequenz enth\u00e4lt, die angibt, wie h\u00e4ufig dieser Zustand im schlimmstm\u00f6glichen Fall besucht wird. Weiterhin betten wir f\u00fcr jeden ABB ein mittels IPET formuliertes ILP-Fragment ein und leiten seine Aktivierungsfrequenz aus den Zustandsfrequenzen ab. Auf diese Weise erhalten wir ein integriertes ILP, welches sowohl die m\u00f6glichen globalen Kontrollfl\u00fcsse, die sich aus der Ablaufplanung ergeben, als auch die Instruktionsebene enth\u00e4lt.<\/p>\n 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\u00fcr verschiedene Aufgaben in dieser Anwendung untersuchen, obwohl diese sich gegenseitig mittels Interrupts unterbrechen und das RTOS zur Synchronisation verwenden.<\/p>\n Mit SysWCET haben wir einen Analyseansatz f\u00fcr systemweite Antwortzeitanalysen entwickelt, der alle relevanten Aktivit\u00e4ten des Echtzeitsystems ber\u00fccksichtigt und in einer einheitlichen Problemformulierung zusammenfasst. Unter vertretbarem Analyseaufwand von wenigen Minuten k\u00f6nnen vollst\u00e4ndige Systeme automatisch analysiert werden, um verl\u00e4ssliche Schranken der Antwortzeiten zu bestimmen. Die Implementierung von SysWCET ist unter einer Open-Source-Lizenz verf\u00fcgbar:\u00a0https:\/\/gitlab.cs.fau.de\/syswcet<\/a><\/p>\n [1] C. Dietrich, P. W\u00e4gemann, 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<\/p>\n [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<\/p>\n Beitrag als PDF-Datei downloaden<\/strong><\/a><\/p>\n Wollen Sie sich auf den aktuellen Stand der Technik bringen?<\/strong><\/p>\n Dann informieren Sie sich\u00a0hier<\/strong>\u00a0<\/a>zu Schulungen\/ Seminaren\/ Trainings\/ Workshops und individuellen Coachings von MircoConsult zum Thema Embedded- und Echtzeit-Softwareentwicklung.<\/p>\n Training & Coaching zu den weiteren Themen unseren Portfolios finden Sie\u00a0hier<\/a>.<\/strong><\/p>\n Wertvolles Fachwissen zum Thema Embedded- und Echtzeit-Softwareentwicklung steht\u00a0hier<\/strong>\u00a0<\/a>f\u00fcr Sie zum kostenfreien Download bereit.<\/p>\nAntwortzeitanalyse von Echtzeitsystemen<\/h2>\n
Probleme mit zusammengesetzter Antwortzeitanalyse<\/h2>\n
Ganzheitliche Systemanalyse von OSEK-Systemen<\/h2>\n
Antwortzeitanalyse als ILP-Problem<\/h2>\n
Zusammenfassung<\/h2>\n
Literatur<\/h2>\n
\nEchtzeit – MicroConsult Trainings & Coachings<\/h2>\n
\nEchtzeit – Fachwissen<\/h2>\n