Aufgabe 4: Kontextwechsel

Bis jetzt hatten wir in unserem StuBS einen festen Faden pro CPU, haben also für jede Anwendung einen Kern exklusiv verwendet. Das wollen wir in dieser Aufgabe mittels kooperativen Scheduling so ändern, dass wir quasi beliebig viele Anwendungen gleichzeitig laufen lassen können. Im Beispiel laufen nun neun Zähleranwendungen parallel, dabei wird in der Ausgabe für jeden Kern eine eigene Farbe verwendet, um das Durchwechseln zu verdeutlichen. Externe Geräte wie die Tastatur bleiben natürlich auch weiterhin aktiv.

Für die Umsetzung müssen wir nun erst mal down the rabbit hole, uns sowohl tiefer in die x86 Architektur als auch die System V ABI einarbeiten, um in Assembler einen Kontextwechsel implementieren zu können. Im Anschluss sollen die Anwendungen so umgebaut werden, dass diese als Threads in einem Scheduler verwaltet werden können.

Diese Verwaltung soll im Ordner thread bereitgestellt werden, der systemnahe Kontextwechsel wird in machine implementiert. Der Scheduler erlaubt Threads zur Ausführung dynamisch hinzuzufügen – und wieder zu entfernen, mittels einer Liste von Zeigern auf Threadobjekten. Mit GuardedScheduler gibt es eine einfache Systemaufrufschnittstelle, damit dies auch von Anwendungen selbst gesteuert werden kann, zum Beispiel das Beenden einer anderen Anwendung.

Die Anwendungen selbst sind von der Klasse Thread abgeleitet, und werden in der Methode action implementiert. Diese Methode ist in Thread als pure virtual deklariert, muss also zwingend in jeder Ableitung implementiert werden. Eine Anwendung, welche das erste Mal per context_switch eingelastet wird, soll ihre Ausführung bei der Methode action() beginnen. Wir bräuchten also die Adresse dieser Methode als Einsprungsfunktion, allerdings ist diese Adresse gar nicht so trivial zu ermitteln, wenn wir nur den Pointer zum Thread Objekt haben: Sie ist ein virtueller Member, die tatsächliche Adresse der Funktion wird also dynamisch zur Laufzeit durch die vtable, der Tabelle virtueller Methoden, ermittelt, abhängig von welcher Anwendung das Objekt tatsächlich ist.

Und wie so eine vtable aufgebaut ist, ist natürlich wieder nicht im C++ Standard spezifiziert, sondern Abhängig vom jeweiligen Übersetzer. Wir wollen aber eine generische Lösung, versuchen also gar nicht erst, selbst dieser Struktur nachzulaufen, sondern lassen den Übersetzer den entsprechenden Code generieren – mittels der Hilfsfunktion kickoff: Diese bekommt als Parameter den Zeiger auf den Thread, und ruft damit dann action auf. Der Übersetzer muss für diesen Aufruf in kickoff entsprechend selbst die Auflösung mittels der vtable einbauen. Unsere Einsprungsfunktion ist somit nun also nicht die Methode action selbst, sondern kickoff, welches dann eben diese Methode aufruft.

Und entsprechend müssen wir auch den Stack vorbereiten – was wir über die Funktion prepareContext erledigen. Diese erhält als ersten Parameter die Adresse des top-of-stack (tos), also das obere Ende des jeweiligen Stacks. Dazu soll für jeden Thread ein 4096 Byte großer Speicher reserviert werden. Der zweite Parameter ist der Funktionszeiger zur eben erwähnten kickoff-Funktion, welcher mit den in param spezifizierten Parameter aufgerufen wird. Der Rückgabewert ist die Adresse des letzten Eintrags, der auf diesem Stack hinzugefügt wurde – somit also der initiale Stackpointer für den Thread. Die ganze Vorbereitung des Stacks wollen wir in C++ schreiben, und können für die einzelnen Einträge im Stack hervorragend die Pointerarithmetik nutzen.

Dazu hilft es, sich im Zweifelsfall den Stack nochmal mit einer Skizze zu veranschaulichen. Wir reservieren für den Stack unserer Anwendungen Foo und Bar jeweils 4 Kilobyte Speicher, zum Beispiel, indem wir ein char-Array mit 4096 Einträgen anlegen. Der Übersetzer wird uns die Arrays übrigens gleich richtig im Speicher ausrichten, alternativ könnte man das auch über das Schlüsselwort alignas erreichen. Unser top-of-stack bei Foo ist somit am oberen Ende des Arrays, 409**6** Bytes weiter als die Startadresse. Bitte nicht instinktiv 409**5** nehmen, wie man bei diesem Array auf den höchsten Eintrag zugreifen würde – denn das würde zwar derzeit auch noch funktionieren (solange wir kein SSE verwenden), aber die Speicherzugriffe auf dem Stack wären dann nicht mehr ausgerichtet, was eine langsamere Zugriffsgeschwindigkeit zur Folge hätte.

Da der C Standard keine Pointerarithmetik mit void* erlaubt, casten wir den Top-Of-Stack zu einem void** – dann geht auch wieder Pointerarithmetik. Ich habe die Variable passenderweise auch rsp genannt, und wir bilden da nun auch die Push-Semantik vom x86 Stack nach, um beispielsweise einen konstanten Wert draufzulegen. Zuerst ein rsp--, dass aufgrund der Pointerarithmetik bei 64 bit die Adresse um 8 Bytes verringert, und dann den Hexwert 0xDEAD BEEF 0BAD F00D an die resultierende Adresse schreibt. Dies wird dank Little Endian wieder "rückwärts", also beginnend mit dem kleinstwertigen Byte, an die derzeitige Adresse geschrieben – was im Feld 4088 des char Arrays 0x0d entspricht. Das höchstwertige Byte, 0xde, steht 7 Bytes weiter, in stackFoo[4095]. Wenn wir nun Zeiger auf Variablen und Funktionen auf diesen Stack legen wollen, funktioniert das genauso: Zuerst wieder auf den nächsten Speichereintrag springen, und in diesen dann die Adresse schreiben, hier von einem Thread-Objekt. Und so kann nun der ganze Stack vorbereitet werden, der Rückgabewert von prepareContext ist dann auch die Adresse, auf welche die Variable rsp am Ende zeigt.

Unschöne Probleme, welche uns in dieser Aufgabe leicht begegnen können, sind Stapelüberläufe. Die 4k Stack reichen zwar bei korrekter Nutzung vollkommen aus, sind aber bei Fehlern auch schnell voll. Und dann wird einfach der Speicher darunter weiter voll geschrieben, was nicht selten der nächste Anwendungsstack ist – im vorherigen Beispiel liegt auch direkt unter stackBar der stackFoo. Das ist besonders perfide, weil dann bei einem Fehler in Bar vielleicht Foo als Erstes in einen Trap läuft – und man dort dann lange nach einem Fehler suchen kann… Willkommen in der Debughölle!

Sehr schnell erreicht man dieses Problem übrigens auch, wenn für die Arrays der Anwendungstacks kein statischer Speicher zugewiesen wird, sondern diese auf dem initialen Stack anlegt werden – dieser ist nämlich selbst nur 4k groß, und in MPStuBS liegen die Stacks für die verschiedene Kerne ebenfalls direkt hintereinander. Einen Heap haben wir noch nicht – die dynamische Speicherverwaltung kommt erst später, ebenso wie dynamische Vergrößerung des Stacks, und zwar nächstes Semester in Betriebssystemtechnik. Aber wir können uns das leben trotzdem etwas vereinfachen, zum Beispiel, indem wir versuchen solche Überläufe zu erkennen. Dazu nehmen wir einen sogenannten Stack Canary, einen Stapelkanarienvogel.

Im Bergbau wurden früher die namensgebenden Kanarienvögel ganz mit nach unten genommen. Solange sie dort einfach rumgezwitschert haben war alles in Ordnung, aber wenn sie leise wurden und tot von der Stange fielen war Matte Wetter, zu wenig Sauerstoff in der Luft. Unser Kanarienvogel in StuBS besteht aus einem magischen Wert, den schreiben wir ganz unten auf jeden Stack, im Beispiel 0x55aa. Solang dieser magische Wert intakt ist, der Kanarienvogel also noch lebendig ist, passt alles. Aber wenn er mal nicht mehr dort steht, dann wird auch unsere Luft dünn, er wurde überschrieben, der Stapel ist vermutlich übergelaufen und es droht Ungemach. Ein guter Zeitpunkt um diesen Wert zu prüfen ist natürlich vor jedem Kontextwechsel. Ob ihr diesen Warnmechanismus implementieren wollt bleibt euch überlassen, er kann euch aber unter Umständen eine langwierige Suche nach Käfern ersparen.

Wir haben nun Stacks und Threads detailliert behandelt, widmen wir uns nun der Threadverwaltung – dem Scheduler. Dieser hat mit der Ready-Liste eine Warteschlange für Threads, welche über die Methode ready() gefüllt wird. schedule() startet die Ausführung des ersten Threads, übergibt also die Kontrolle den Koroutinen. Mit resume() wird zum nächsten Thread gewechselt, je nachdem was als Nächstes in der Ready-Liste liegt. Mit exit() kann ein Thread sich selbst, und mit kill() einen beliebig anderen beenden – er wird also nicht mehr in die Warteschlange hinzugefügt beziehungsweise aus ihr entfernt. Aber sorgt für diese Aufgabe unbedingt dafür, dass es immer genug Threads in der Warteschlange gibt, sie also auch trotz kill niemals leer läuft.

Da wir in dieser Aufgabe noch auf kooperatives Scheduling setzen, müssen unsere Anwendungen so geschrieben werden, dass sie die Kontrolle freiwillig abgeben, eben durch regelmäßige Aufrufe von Scheduler::resume(). In unserer main werden die Anwendungen zu Beginn instanziiert und nach der Initialisierung des Systems mittels ready in die Warteschlange eingefügt, und mit schedule die Kontrolle übergeben.

Bei der Ausführung dieses Codes wird zu Beginn bei schedule mittels Kontextwechsels erstmalig in den Thread AppFoo gewechselt. Dort wird kickoff aufgerufen, mit dem Zeiger auf den Thread als Parameter. Dadurch wird wiederum die action Methode aufgerufen, welche "foo" ausgibt und mittels resume dem nächsten Thread die Kontrolle übergibt – nämlich AppBar. Hier wird ebenfalls über kickoff in action gewechselt, "bar" ausgegeben und wieder ein Wechsel veranlasst. Der nächste Thread wird aus der Ready-Liste genommen, der derzeitige Thread wandert dorthin zurück. AppFoo setzt nun dort fort, wo zuletzt resume ausgeführt wurde, und wiederholt nur die Schleife, gibt also erneut "foo" aus, bevor mittels resume wieder nach Bar gewechselt wird, und so weiter.

Der ganze Ablauf spielt sich dabei auf der Anwendungsebene ab, sofern wir nicht durch externe Geräte unterbrochen werden – deren Behandlungsroutinen aus der vorherigen Aufgabe funktionieren aber weiterhin.

Der gezeigte Ablauf funktioniert so in OOStuBS problemlos, die Konsistenz ist immer gesichert. Aber in MPStuBS, hier können zum Beispiel gleichzeitig mehrere Kerne auf die Warteschlange zugreifen – und diese ist dafür nicht ausgelegt. Aber dafür haben wir doch in der letzten Aufgabe etwas entwickelt: Wir führen einfach die Operationen vom Scheduler, inklusive Kontextwechsel, ausschließlich auf der Epilogebene aus. Vor dem Schedule wird diese Ebene betreten, auf AppFoo gewechselt und dort kickoff ausgeführt. Nun müssen wir die Ebene verlassen, und um ein sauberes Design zu haben, wird dies gleich als Erstes in kickoff erledigt, damit action auch auf der Anwendungsebene ausgeführt wird. Dort wird wieder die Ausgabe getätigt, dann wieder Epilogebene betreten und der Kontextwechsel ausgeführt. AppBar beginnt analog in kickoff, Ebene verlassen, action und Ausgabe, Epilogebene wieder betreten, Kontextwechsel mittels resume. In AppFoo muss nun die Ebene erst verlassen werden, bevor die Ausgabe kommt und sie dann erneut betreten wird, für das nächste resume.

Dieser Ablauf wird besonders in der Ebenenübersicht deutlich. Und weil es mühselig ist, jedesmal guard.enter() und guard.leave() vor dem Aufruf einer Scheduler Methode zu schreiben, kapseln wir dies im GuardedScheduler. Er hat also nach außen hin die gleichen Schnittstellen wie der Scheduler, wechselt jedoch nur in die Epilogebene und agiert beim eigentlichen Aufruf als Proxy an Scheduler.