Aufgabe 5: Zeitscheiben

Auf den ersten Blick hat sich in StuBS im Vergleich zur vorherigen Aufgabe nicht viel geändert, unsere Anwendungsfäden inkrementieren weiterhin fröhlich vor sich hin, vielleicht ein wenig schneller als zuvor. Die Ausgabe rechts oben ist neu, es wird die Zeit angezeigt, aber das ist optional.

Die eigentliche Änderung ist wieder nur unter der Haube zu sehen: Unsere Anwendung sah in vorherigen Aufgaben in etwa so aus. Nun verschwindet aber der kooperative Wechsel der Anwendung mittels scheduler.resume(), dennoch werden alle Fäden bedient – Dank einer regelmäßig auftretenden Unterbrechung, welche den Wechsel initiiert.

Während dieses präemptive Scheduling natürlich Anwendungsentwickler das Leben vereinfacht, muss StuBS selbst unter Umständen erst noch abgesichert werden, denn diese Unterbrechungen können nun jederzeit, also an jeder Stelle des Codes geschehen – potenzial für viele interessante Fehler.

Was müssen wir dafür tun? Für das präemptive Scheduling wollen wir den LAPIC Timer verwenden, der dazu zuerst konfiguriert und kalibriert werden muss. Neben dem Umbau der Anwendung und den Schutz kritischer Abschnitte müssen nun in MPStuBS Kerne unter Umständen bei bestimmten Ereignissen benachrichtigt werden. Außerdem gibt es die Möglichkeit, freiwillig weitere Timer einzubauen, wie die in der Musterlösung gezeigte Real-Time-Clock, welche die aktuelle Uhrzeit und Datum anzeigt. Das wird dann über die Clock gesteuert. Daneben gibt es noch die Watch, welche bei vom LAPIC ausgelöste Unterbrechungen den Threadwechsel auslöst.

Sie stellt dabei folgende Methoden zur Verfügung: Windup stellt das gewünschte Unterbrechungsintervall ein, und zwar in Mikrosekunden. Es ist für die Aufgabe außerordentlich hilfreich, Mikro- und Millisekunden nicht zu verwechseln und im Zweifelsfall nochmals genau zu lesen. Wenn die Uhr nun "aufgezogen" wurde, kann sie aktiviert werden, damit die Unterbrechungen kommen. Im Mehrkernbetrieb muss das nun auf jedem Kern gemacht werden, denn jeder hat einen eigenen LAPIC. Beim windup reicht jedoch ein einzelner Aufruf, da die APIC Busfrequenz für alle Kerne gleich ist. Und da die Watch ein Gerät ist, muss sie auch einen prolog und epilog anbieten. Dabei fordert der Prolog nur einen Epilog an – und tätigt vielleicht zu Testzwecken mal eine Ausgabe. Sobald wir dann in der Epilogebene sind, wird der Threadwechsel ausgeführt.

Der LAPIC Timer hat nun leider jedoch keine uns bekannte Basisfrequenz, sondern nimmt den APIC-Bus Takt – welcher wiederum je nach Hardware komplett unterschiedlich sein kann. Er entspricht entweder der Processor Core Clock, der Core Crystal Clock oder auch etwas ganz anderem. Und ein Auslesen solcher Werte mittels cpuid und Model Specific Register (MSR) ist auch keineswegs schön, wie man am Beispiel des Timestamp Counters (TSC) sehen kann.

Wie können wir nun einfach die Frequenz feststellen, möglichst generisch damit es auf jeder Hardware läuft? Nun, wir messen einfach die Zeit, wie lange ein Tick dauert, und zwar mithilfe eines anderen Timers, welcher auf jeder Hardware vorhanden ist und dessen Frequenz wir kennen: dem Programmable Interval Timer (PIT).

Dieser ist bereits in StuBS fertig implementiert, wir setzen die Warte Zeit auf einen möglichst großen Zeitraum, und merken uns die Start- und Endwerte des LAPIC Current Counter Registers. Daraus können wir dann die Anzahl der LAPIC Ticks in einer Millisekunde berechnen. Dazu muss noch eine Funktion zum Konfigurieren des LAPICs geschrieben werden – um euch dabei das Leben etwas einfacher zu machen haben wir die Strukturen der Register sowie relevante Konstanten bereits für euch vom Datenblatt abgetippt.

Um den Timer für ein gewünschtes Intervall einzustellen, müssen Startwert und Vorteiler berechnet und gesetzt werden. Als Einheit für die zeitgesteuerten Unterbrechungen nutzen wir Mikrosekunden, die Berechnung des Startwertes ist somit die gewünschte Intervalldauer multipliziert mit der Anzahl von LAPIC Ticks pro Millisekunde, was – wegen der unterschiedlichen Einheit – durch 1000 geteilt werden muss. Außerdem muss ebenfalls noch der Vorteiler berücksichtigt werden, wenn dieser aktiv ist, also Werte größer 1 annimmt. Dabei sollte für eine gute Genauigkeit immer der kleinstmögliche Vorteiler verwendet werden, es darf jedoch keinen Überlauf geben.

Zur Veranschaulichung ein Beispiel: Die Watch wird auf 5 Millionen Mikrosekunden gestellt – also 5 Sekunden. Der LAPIC Timer hat beispielsweise 1 Million Ticks pro Millisekunde. Testen wir mit einem Vorteiler von 1, bekommen wir nach unserer Formel oben einen Startwert von 5 Milliarden – was knapp jenseits der 32 bit Grenze ist, welche für vorzeichenlose Ganzzahlen bei rund 4.3 Milliarden liegt. Also nächster Vorteiler, 2: Ergibt die Hälfte, 2.5 Milliarden und ist damit verwendbar, wir können somit sowohl Divide Configuration als auch Initial Count Register des *LAPIC Timer*s für 5 Sekunden Unterbrechungsintervalle setzen. Während solche langen Zeitscheiben natürlich den Overhead reduzieren, wir haben ja fast Batchbetrieb hier, bevorzugen wir zum Testen von StuBS deutlich kürzere Zeitscheiben – mit einer Dauer von je einer Millisekunde. Dadurch erhöht sich die Wahrscheinlichtkeit, dass wir Wettlaufsituationen entdecken, die noch geschützt werden müssen.

Wenn nun StuBS mit zwei Anwendungen läuft, dann wird das mittendrin in etwa so aussehen: Die erste Anwendung ist aktiv, wird dann durch den Timer unterbrochen und der Watch::prolog ausgeführt. Dieser tut nichts anderes als einen Epilog anfordern, welcher wiederum Scheduler::resume ausführt – und auf Anwendung 2 wechselt. Nach dem leave wird auf die Anwendungsebene zurückgewechselt und dort die zweite Anwendung ausgeführt, bis wieder der Timer zuschlägt, Prolog fordert Epilog an, dieser führt das resume aus, und wir sind wieder im Kontext von Anwendung 1. Ein leave, und die Anwendung wird weiter abgearbeitet. Im Gegensatz zur vorherigen Aufgabe weiß die Anwendung selbst nun nicht mehr, dass sie weg geschedulet wurde – der unterbrochene Ablauf wird zeitversetzt transparent weitergeführt.

In dem Beispiel gehen wir nun davon aus, dass die Epilogebene frei ist. Was aber, wenn dies nicht der Fall ist? So soll unsere Anwendung 1 gleich mit enter auf die Epilogebene wechseln. Eine eintretende Timerunterbrechung wird zwar auf die Interruptebene wechseln und dort den Prolog ausführen, aber beim relay wird festgestellt, dass die Ebene ½ belegt ist. Dann wird der Epilog in die Warteschlange gesteckt und der Ablauf fortgeführt. Bei leave wird nun der wartende Watch::epilog gestartet, welcher resume ausführt, Kontext wechselt und mit leave auf die Anwendung von app2 zurückkehrt. Die nächste Timerunterbrechung führt mit prolog, relay und resume im Epilog die bekannte Abfolge durch, es wird wieder auf den Kontext von Anwendung 1 gewechselt, mit leave kommen wir wieder auf die Anwendungsebene zurück. Auch hier merkt die Anwendung den Kontextwechsel nicht.

Bei den bisherigen Beispielen sind wir immer davon ausgegangen, dass beide Anwendungen zuvor bereits aktiv waren. Nun wollen wir aber den Ablauf beim Start eines neuen Kontextes sehen. Dazu fügt unsere Anwendung 1 auf der Epilogebene die Anwendung 2 mittels ready in die Warteliste des Schedulers ein. Wenn nun die Timerunterbrechung kommt, wird wie gehabt vom Prolog ein Epilog angefordert, welcher auf der Ebene ½ resume aufruft. Hier starten wir also beim in Aufgabe 4 manuell präparierten Stack, welcher über kickoff die Ebene ½ verlässt und mit Thread::action() in die Anwendung 2 springt. Da wir das Scheduling bereits auf der Epilogebene durchführen ist somit hier keine besondere Behandlung notwendig.

Trotzdem, ganz ohne weitere Anpassungen kommen wir nicht aus, zumindest nicht im Mehrkernbetrieb. Besondere Beachtung braucht das Beenden eines Anwendungsfadens, sofern es von einer anderen Anwendung initiiert wurde. Bei einem Kern ist es ausreichend, zuerst zu prüfen, ob man selbst der zu beendende Faden ist, sich also selbst abschiesst, und in diesem Fall einfach wie bei exit() agiert. Sollte dies nicht der Fall sein, sorgt man einfach dafür, dass der Faden nicht mehr eingescheduled wird, in dem man ihn entweder aus der Ready-Liste entfernt oder in einem Threadattribut vermerkt, dass er nicht mehr ausgeführt werden soll.

Bei MPStuBS kann es nun jedoch zusätzlich auch vorkommen, dass der Faden gerade auf einem anderen Kern ausgeführt wird. Um Wettlaufsituationen zu vermeiden, sollte einfach immer zuerst das Kill-Flag gesetzt werden. Danach suchen wir ihn in der Ready-Liste. Sollten wir ihn nicht finden, läuft er vermutlich gerade auf einem anderen Kern. Dieser Kern muss nun benachrichtigt werden, und zwar mittels eines Inter-Processor Interrupts, kurz IPI.

Damit können die Kerne sich untereinander Nachrichten in Form von Interrupts schicken. Wir können dabei unter anderem alle Kerne gleichzeitig, aber auch einen konkreten Kern direkt adressieren – um die Nachrichtenlast zu minimieren, soll die zuletzt genannte Variante bevorzugt werden. Der so benachrichtigte Kern soll dann aber nicht einfach blind den gerade laufenden Anwendungsfaden verdrängen, denn es kann sein, das gerade, zwischen Absetzen des IPIs und dem Empfang, der Scheduler aktiv war und nun ein neuer Faden eingelastet wurde. Stattdessen soll anhand des Kill-Flags das weitere Vorgehen geprüft werden: Thread wechseln oder zurückkehren.

Aber wie funktioniert der dazu benötigte Inter-Processor Interrupt? Dafür wird wie bei den Unterbrechungen durch externe Geräte der APIC genutzt. Wenn nun der erste Kern dem zweiten einen IPI schicken will, instruiert er seinen LAPIC, welcher eine Nachricht auf den APIC-Bus legt, die an den LAPIC des zweiten Kerns adressiert ist. Dieser verfährt dabei genauso wie bei anderen Interrupts und unterbricht die CPU.

Diese Funktionalität wird über den Namespace LAPIC::IPI angeboten, für das direkte adressieren gibt es dort die Funktion send. Der zweite Parameter (vector) ist dabei einfach der auszulösende Interruptvektor. Der erste Parameter ist der Empfänger – und damit ist nicht die ID des Kerns, sondern des LAPIC*s gemeint. Um nun von einem Kern die *LAPIC ID herauszubekommen, gibt es die Funktion getLAPICID im Namespace APIC, welche dies beim Systemstart von ACPI erfährt und in einer Lookuptabelle vermerkt.

Wenn ihr diese Indirektion vergessen solltet, dann kann es schon sein das es läuft – aber nur im Emulator. Denn die CPU und LAPIC ID*s sind in *Qemu identisch. Auf der Testhardware ist dies aber nicht der Fall. Bitte ebenfalls Beachten: Falls man irgendwann mal sendGroup verwenden will, welche IPIs an mehrere Kerne gleichzeitig schicken kann, so muss dafür eine Maske aus logischen APIC IDs übergeben werden. Diese sind von uns selbst definiert, und etwas anderes als die vorgegebenen LAPIC IDs.

Selbst wenn man bisher alles richtig implementiert hat, so gibt es noch stellen im alten Code, die nun problematisch sind. Zum Beispiel dieser Code, der sich bestimmt in einer ähnlichen Art bei euch findet. Sieht harmlos aus, oder? Was kann da schon passieren? Nun, einiges, da dies kein atomarer Befehl ist.

Schauen wir uns dazu nur den Assemblercode von der abgebildeten Zeile an: Ein Funktionsaufruf, dessen Rückgabewert – gespeichert in rax – verwendet wird um den Speicher zu adressieren, welcher dann auf 1 gesetzt wird. Nicht schlimm… Es sei denn exakt zwischen diesen beiden Zeilen kommt ein Timerinterrupt. Nehmen wir mal an, wir sind auf Kern 1 gelaufen, entsprechend hat nun das Register rax den Wert 1, wenn der Kontext gesichert wird. Der Thread wird in die Ready-Liste gesetzt, und später vielleicht auf Kern 3 wieder eingelastet, der Kontext wiederhergestellt, und dann das mov ausgeführt, welches nun die zum Kern 1 gehörende Speicheradresse ändert. Vermutlich nicht was wir wollen.

Und das Fiese ist: Dieser Fehler tritt nicht sofort auf, nur nach längerem Laufen, vielleicht so alle 20 Minuten. Betriebssystemprogrammierung ist nicht einfach.