# Aufgabe 6 - Task Scheduling ## 10.1. Tracing ### 10.1.1. Funktionsdefinition Unter Tracing bezeichnet man das Aufzeichnen des Programmablaufs, um diesen dann später zur Analyse von Fehlern zu nutzen. Die Analyse kann nach der Ausführung des Programms stattfinden. Auch Lese- und Schreibzugriffe auf Variablen können aufgezeichnet werden. Abstürze, bei denen die Ursache in einem Speicherüberlauf oder NullpointerExceptions vermutet wird, können damit gelöst werden. Tracing kann auf verschiedene Arten realisiert werden, die jeweils eigene Vor- und Nachteile mit sich bringen. (Hardware-)Tracing lässt sich aber auch einsetzen, um den zeitlichen Ablauf des Programms zu analysieren und so zum Beispiel Statistiken über die Worst-Case Execution Time (WCET) anzustellen. ***Software-Trace*** Das untersuchte Programm wird so verändert, dass es die benötigten Informationen selbst erzeugt. Dazu werden die gesammelten Daten in Variablen in den Zielgerät-RAM geschrieben und später vom Debugger ausgelesen. Vorteile dieser Variante sind, dass die Daten in beliebigem Umfang und beliebig genau bereitgestellt werden können. Gleichzeitig ist allerdings zu bedenken, dass die Hardware, auf der das Programm läuft, nun auch die Datensammlung bewerkstelligen muss. Die logische Konsequenz ist die Verringerung der Geschwindigkeit der Ausführung und ein erhöhter Speicherbedarf. Auf Systemen, auf denen kaum Leistung und Speicher zur Verfügung stehen, kann dies zu Problemen führen. Außerdem ergibt sich aus dieser Variante des Tracings ein hoher Einfluss auf das Zeitverhalten des Systems. Bestehende Fehler können, während der Ausführung mit Software Tracing, anders auftreten als ohne Software-Tracing.
Als Beispiel soll hier ein Programm dienen, welches durch einen externen Interrupt beeinflusst wird: Die Anwendung reagiert auf einen Interrupt und stürzt im betrachteten Fall ab. Dieser Absturz findet immer genau dann statt, wenn der Interrupt aktiviert wird, während sich das Programm in Methode XY befindet. Der Versuch diesen Fehler mit Hilfe von Software-Tracing zu lösen, verändert die Laufzeit des Programms so, dass der Interrupt nun zu einem anderen Zeitpunkt im Programm auftritt. Das Programm stürzt nun während des Debuggens nicht mehr ab. Jede dem Debuggen dienende Veränderung ändert das Zeitverhalten. ![Screenshot](img/jpg/PowerTrace-II.jpg)
Abbildung 10.1.: Lauterbach Trace Debugger PowerTrace-II ***Offchip-Trace*** Im Gegensatz zum Software-Tracing kommt diese Methode des Tracings nicht ohne externe Trace-Hardware aus (siehe Abbildung 10.2). Sollen Informationen zum Zustand des Systems zur Laufzeit aufgenommen werden, werden diese am Prozessor des Zielgerätes abgenommen. Die übliche Methode bei Mikroprozessoren ist das Auslesen des Adressbusses zum Speicher und einiger Steuersignale. Mithilfe dieser Daten kann der Programmablauf rekonstruiert werden. Bei modernen Chips sind CPU Kerne, Haupt- und Massenspeicher, Cache und Peripherie in einem Gehäuse integriert. Das macht es unmöglich den Speicherbus abzugreifen. Um diese Systeme trotzdem noch mit Trace-Debugging nutzen zu können, werden sogenannte Trace-Interfaces bereitgestellt. Auf ihnen wird in komprimierter Form der Programmfluss übertragen. Es handelt sich dabei meist um ein 4, 8 oder 16 Bit breiten Bus, über den mit Frequenzen bis 400 MHz Daten übertragen werden. Die bereitgestellten Informationen liegen so vor, wie sie auch in der CPU vorliegen würden, dass heißt es werden auch Speicherzugriffe aufgezeichnet. Es muss sich nicht um etwaige fehlende Informationen über Lese-, aber vor allem Schreibzugriffe auf den Cache gekümmert werden. ***Onchip-Trace*** Diese Methode des Tracings kommt ohne externen Trace-Speicher aus. Es gibt CPUs mit einem Trace-Speicher, der in das System integriert ist (siehe Abbildung 10.3). Auf diesem werden ähnlich der Methode des Offchip-Tracings die benötigten Daten gespeichert und können nach Beenden des Programms ausgelesen werden. Vorteil gegenüber dem Software-Tracing ist, dass keine Änderungen am Programm vorgenommen werden müssen. Im Vergleich zum Offchip-Tracing wird zwar kein externer Trace-Speicher benötigt, allerdings ist der interne Trace-Speicher aus Kostengründen und Platzgründen sehr klein gehalten. Um diesen Nachteil zumindest teilweise zu kompensieren, gibt es häufig die Möglichkeit das Programm zu stoppen und einen Interrupt auszulösen, wenn der interne Trace-Speicher voll ist. Dann können die Daten auf die Debugplattform übertragen und das Programm weiter ausgeführt werden. Der Nachteil dieser Variante ist das benötigte Starten und Stoppen und der damit verbundenen Eingriff in das Zeitverhalten des Systems. ![Screenshot](img/png/trace-offchip.png)
Abbildung 10.3.: Funktionsweise Onchip Tracing ### 10.1.2. Art der Anwendung, Nutzung des Werkzeugs Die Anwendungsmöglichkeiten von Tracing sind vielfältig. Oft ist es nötig, die Ausführungszeit einer Methode zu kennen. Auch ist es nützlich die Register und Variablen ohne Unterbrechung des Programms auslesen zu können. Wenn ein Programm abstürzt, macht es Tracing möglich genau nachzuvollziehen, welche Funktionsaufrufe mit welchen Werten vor dem Absturz getätigt wurden. Programmkomponenten, die sich mit den vorherigen Debugwerkzeugen nur schwer oder gar nicht analysieren ließen, können nun auf ihre Auswirkungen auf den Programmfluss überprüft werden. Dazu gehört zum Beispiel erhöhte Interruptlast oder Unterbrechung durch höherpriore Tasks. Fehleranalyse von Fehlern zur Laufzeit und die Analyse von Kommunikation über Busse wird einfacher. In dieser Aufgabe sollen sie Trace-Points nutzen, um den Wechsel von einer Funktion zur anderen darzustellen. Diese Tracepoints können zum Beispiel ein Taskset visualisieren, indem sie zu Beginn und am Ende eines Tasks gesetzt werden. ![Screenshot](img/png/trace-onchip/) ### 10.1.3. Grenzen und Nachteile Trotz dessen, dass die beiden in Kapitel [10.2](10_aufgabe6.md#102-lauterbach-wissen) vorgestellten Trace-Methoden von den Nachteilen bezüglich des Heisenbergeffekts beim SoftwareTracing nicht betroffen sind, haben sie Nachteile. Dazu gehört der sehr hohe Kaufpreis solcher Systeme, der sich im niedrigen fünfstelligem Bereich bewegt. Außerdem ist die Unterstützung von Tracing unter den Entwicklungsboards wesentlich weniger weit verbreitet, als das bei JTAG-Debugging der Fall ist. Das Interface benötigt aufgrund der hohen Datenraten bei der Übertragung viele Pins. Unterschiede zwischen den verschiedenen Trace-Methoden lassen sich in der Tabelle 10.1 finden. ![Screenshot](img/png/tabelle-trace-vergleich.png)
Tabelle 10.1.: Vergleich von Software-, Onchip- und Offchip- Trace Diese Aufgabe soll Ihnen Methoden vermitteln, mit denen Sie die Auslastung des Systems beurteilen und optimieren können. Grundstein für die Überlegungen dieser Aufgabe ist ein System mit mehreren Tasks. Es stellt sich nun die Frage, wann welcher Task CPU-Zeit in Anspruch nehmen darf. In der Aufgabe lernen Sie verschiede Scheduling Algorithmen kennen und analysieren sie auf die Auswirkungen auf das Task-Set. ***Alle benötigten Informationen zur Bearbeitung bekommen Sie aus den beigefügten Folien der Übung und Vorlesung zur Lehrveranstaltung Rechnerstrukturen 2. In den Vorlesungsfolien sind aus Kapitel 5, Folien 29 bis 59 relevant. Kapitel 9 und 10 der Übung helfen beim Anwenden der Verfahren. Sie finden das benötigte Material in Ihrem Repository unter RS2_Unterlagen.*** ## 10.2. Lauterbach-Wissen ### 10.2.1. Tracing Points Das Aufzeichnen des gesamten Programmflusses ist oftmals nicht notwendig und meistens eher störend beim Fehler finden, da die wichtigen Details in der Menge an Informationen untergehen. Daher ist es möglich das Tracing erst bei Bedarf zu aktivieren. Um das Handling zu erleichtern, ist die Syntax bei Lauterbach zwischen Break-Points und Tracing-Points sehr ähnlich (vgl. [9.1.1](9_aufgabe5.md#911-bedienung-des-lauterbach-debuggers)): ``` break.set /program /TraceEnable ``` TraceEnable aktiviert das Tracing für einen kurzen Moment beim eintreten der Bedingung oder des Events. Es erzeugt so zu sagen ein Snapshot. Dies ermöglicht es auch den Zugriff auf eine Variable zu tracen und den Rest des Systems auszublenden: ``` var .break.set / /TraceEnable ``` Leider stehen hardware-bedingt nur 4 TraceEnable-Points zur Verfügung. Daher greift man auf Trace-On/-Off-Points zurück. Beim Erreichen eines Trace-On-Points wird das Tracing aktiviert und wieder beendet beim Erreichen eines Trace-Off-Points. ``` break.set /program /TraceON break.set /program /TraceOFF ``` Das Setzen von Tracepoints ist auch über die GUI möglich z.B. indem man im Sourcecode ein Rechtsklick macht und Breakpoints->TraceEnable/-On/-Off auswählt.
Ebenso wie bei den Breakpoints ist die Verwendung des symbol-Befehls möglich [[tra](references.md), S.286] ![Screenshot](img/jpg/lauterbach_taskset_statistic_example.png)
Abbildung 10.4.: Verteilung dargestellt
Das Diagramm zeigt die Dauer zwischen OSQPost und OS_EventTaskRdy. ### 10.2.2. Darstellung Die Darstellung der aufgezeichneten Daten übernimmt die Trace32 Software und kann angezeigt werden mit (Abbildung 10.5): ``` trace.chart ``` Alternativ kann über die GUI gearbeitet werden mit Trace->Chart->Symbols. Je nach Dauer und Menge der Daten kann die Darstellung etwas dauern. Zudem kann Lauterbach die Verteilung bestimmter Werte in einer Statistik darstellen. Der folgende Befehl erzeugt ein Diagramm, dass die Verteilung der Dauer zwischen den beiden angegebenen Methoden darstellt (Abbildung 10.4). ``` Trace.STATistic.AddressDURation ``` Falls man erneut Tracen möchte, sollte man die gespeicherten Daten zurücksetzen mit: ``` Trace.Init ``` ![Screenshot](img/jpg/lauterbach_taskset_chart_example.png)
Abbildung 10.5.: Trace im Chart dargestellt
Ein langer und großer Trace, der zwar viele Daten enthält. Aber die wesentlichen Punkte sind nicht sofort ersichtlich. ## 10.3 Aufgabenteil Bearbeiten Sie das Arbeitsblatt und notieren Sie sich Ergebnisse und Vorgehensweisen. Beantworten Sie außerdem folgende Fragen: - Was ist der Unterschied zwischen Analyse und Simulation? - Welche Arten der Taskaktivierung gibt es? - Erklären Sie die Begriffe Periode und Jitter - Was ist Präemption im Bezug auf Scheduling? - Was sind die Unterschiede zwischen TDMA und Round Robin? - Was ist RMS? ***Hinweis: Nutzen sie für die Berechnungen das entsprechende Material aus der Vorlesung Rechnerstrukturen 2.*** ![Screenshot](img/png/TaskSet-Tabelle.png) ***Aufgabe 1:*** Vergeben Sie die Prioritäten der Tasks nach RMS. **Hinweis** 0 ist die höchste Priorität. ***Aufgabe 2:*** Berechnen Sie die maximale Last, wenn alle Tasks auf demselben Prozessorkern ausgeführt werden. Was fällt Ihnen auf, wenn Sie die berechnete Last mit der Auslastungsschranke aus dem Theorem von Liu/Layland zu RMS vergleichen? ***Aufgabe 3:*** Berechnen Sie für das gegebene Taskset die **BCRT** sowohl für SPP, als auch für SPNP Scheduling. **Hinweis:** Alle Tasks werden synchron zum Zeitpunkt t=0 aktiviert. Überlegen Sie sich die Eigenschaften des Tasksets. Hierfür wird keine Formel benötigt! ***Aufgabe 4:*** Ermitteln Sie für das gegebene Taskset die **WCRT**, sowohl für SPP als auch SPNP **zeichnerisch** ***Aufgabe 5:*** Ermitteln Sie für **Task 4** die **WCRT** für SPP und SPNP **rechnerisch**. **Hinweis:** Nutzen Sie für die Berechnung die Formel für die WCRT, welche Sie aus der Vorlesung kennen. ***Aufgabe 6:*** Nehmen Sie an, dass für das Taskset implizite Deadlines gelten, d.h. Deadline = Periode. Ist das Taskset unter diesen Voraussetzungen "scheduable"? ***Aufgabe 7:*** Angenommen die Aktivierung von **Task 1** hat einen **Jitter von 0,5ms**. Wie wirkt sich dies bei **SPP** Scheduling auf die BCRT und WCRT von **Task 2** und **Task 4** aus? ## 10.4. Aufgabenteil 2 Kompilieren Sie nun die Aufgabe 6 und laden diese auf das Board. In dieser Aufgabe wird ein Tasksetsimulator genutzt, indem sich mehrere Tasks nach dem P-J-D Modell konfigurieren lassen. Tragen Sie zunächst die korrekten Prioritäten der Tasks in der Datei src/gt_tasks.c ein. Untersuchen Sie zunächst mit Hilfe der Tracingtechniken des Lauterbachs die Kalibrierung des Tasksetsimulators. Der Simulator nutzt eine Schleife in der Funktion ``` __burn_wcet(CET,GT_CPU_OS_TASK_OFFSET,GT_CPU_CYCLE_SCALE); ``` um die BCET ≤ CET ≤ WCET zu simulieren. Das heißt der Task hat effektiv keine Funktion sondern verbraucht nur die Rechenzeit CET. Die CET wird dabei für jede Aktivierung zufällig zwischen der BCET und WCET gewählt. Um die Ausführungszeiten des Simulators auf den Prozessor anzupassen müssen bestimmte Parameter korrekt gesetzt werden, da ansonsten die CET nicht den Sollwerten entsprechen. Ihre Aufgabe ist es zunächst diese Parameter so zu konfigurieren, dass die Ergebnisse den Sollwerten entsprechen. Die Parameter unterteilen sich in einen Scale-Wert und einen Offset. Der Scale-Parameter garantiert die korrekte Ausführungszeit langer Delays. Der Offset muss korrekt gesetzt werden, damit kurze Delays genau genug für eine Simulation des Taskssets sind. Zu Beginn der Main-Funktion wird eine Methode zum Kalibrieren der Parameter aufgerufen. Der Kommentar zu der Methode erklärt die Funtionsweise. Messen Sie die Ausführungszeiten der von dem Taskset genutzen Funktion in der Methode GT_calibrate indem Sie Tracepunkte nutzen. Die CET wird dabei exponentiell von 0,1ms auf 51,2ms erhöht. Die Zeiten zwischen den Trace-Events können sie in der trace.list Darstellung ablesen. Nutzen Sie zunächst weiter das Onchip-Tracing (zc706_onchip_trace.cmm), da bei der Kalibrierung ja nur wenige Tracedaten generiert werden. Erstellen Sie sich eine Tabelle mit Soll- und Ist-Werten für die einzelnen Schleifen-Durchläufe in der Kalibrierungsfunktion. Nun können Sie das Verhältnis zwischen Soll- und Ist-Werten ausrechnen und in einem Diagram darstellen lassen. Stellen Sie die Parameter so ein, dass 0, 96 ≤ IST/SOLL ≤ 1, 0 gilt. **Tipp:** Passen Sie ihr .cmm Skript für Aufgabe 6 an, um wiederkehrende Arbeitsschritte wie das Setzen von Break-/ Tracepunkten zu automatisieren! Ist die Kalibrierung geglückt, sollen Sie das Taskset aus der theorethischen Aufgabe in den Simulator übertragen und visualisieren. Der Taskssetsimulator erlaubt es, mehrere Tasks nach dem Periode-Jitter Modell zu konfigurieren. Diese sind in der Datei APP/Aufgabe6/src/gt_tasks.c bereits mit den BCET und WCET Parametern aus dem Aufgabenblatt definiert. Nach der Bearbeitung des Arbeitsblattes und der Kalibrierung des Simulators sollen Sie nun untersuchen, wie sich das vorher berechnete Zeitverhalten auf einem realen System verhält. Nutzen Sie im Folgenden OffChip-Tracing, indem Sie die zc706_offchip_trace.cmm ausführen. Vergleichen Sie die zc706_offchip_trace.cmm und zc706_onchip_trace.cmm. Wo liegen die Unterschiede? Tipp: Tools wie meld oder vimdiff erleichtern die Arbeit. In der Datei finden sich auch die folgenden Methoden: ``` GT_TaskActivationHook GT_TaskStartHook GT_TaskEndHook GT_TaskSwHook ``` Mit ihnen lassen sich Aktionen auslösen, wenn ein Task bereit ist, gestartet, gescheduled oder beendet wird. - Erweitern Sie diese Methoden so, dass sie unterscheiden können, welcher Task aktiviert bzw. beendet wurde. - Benutzen Sie zu erst Trace-Enable Points, um das Scheduling eines einzelnen Tasks aufzuzeichnen (Activated, Scheduled, Not-Scheduled, Finished). - Benutzen Sie anschließend Trace-On/-Off Points, um das Verhalten aller Tasks zu untersuchen. - Erstellen Sie eine Statistik über die Verteilung der WCET und der WCRT jedes Tasks. - Vergessen Sie nicht ihre Ergebnisse zu dokumentieren z.B. mit Screenshots oder als Text-Export.