Aufgabe 6: Synchronisation

Bis jetzt konnten wir in unseren Benutzeranwendungen eine Synchronisation nur durch aktives Warten oder Betreten der Epilogebene erreichen, was wir so beispielsweise für die Ausgabe verwendet haben.

In dieser Aufgabe führen wir Synchronisationsobjekte ein, wodurch die Anwendungen sich nun gegenseitig über Ereignisse informieren beziehungsweise passiv darauf warten können – die Ausgabe kann nun mittels Semaphoren synchronisiert werden. Außerdem bekommen die Threads die Möglichkeit, sich für eine bestimmte Zeit schlafen zu legen. Anschaulich – beziehungsweise eher anhörlich – lässt sich das mittels des PC Speaker*s demonstrieren, in dem man nacheinander verschiedene Töne abspielt, also beim *PIT mittels Pulsdauermodulation (PWM) eine bestimmte Frequenz für eine gewisse Zeit einstellt, und sich daraus dann eine Melodie ergibt. Zugegeben, der piepsende Systemlautsprecher ist aus gutem Grund nur noch ein historisches Relikt, und hat seit Jahrzehnten dank der standardmäßig integrierten Soundkarten keinerlei Relevanz mehr. Aber vor 30 Jahren wurde das insbesondere bei Spielen intensiv – und auch durchaus sehr kreativ – genutzt. Und uns kann es beim Erkennen von fehlerhaften Implementierungen helfen.

Die Umsetzung beginnen wir mit den Semaphoren, neben der Ausgabe soll auch die Eingabe darüber synchronisiert werden: Mittels getKey() kann ein Thread die nächste gedrückte Taste bekommen – sofern alle vorherigen Tasten bereits abgerufen wurden, wird auf den nächsten Tastendruck gewartet. Ein solches Warten soll auch zeitgesteuert möglich sein, wer will, kann dies mittels des gezeigten PC Speaker*s testen, ein kurzer Beispielcode dafür ist in der Angabe gelistet. Damit müssen wir uns nun gegen ein neues Problem wappnen: Wenn gerade alle Threads schlafen, was soll dann ausgeführt werden? In solchen Fällen müssen wir uns um den Leerlauf des Prozessors kümmern. Wer will, kann dabei auch StuBS zu einem *Tickless Kernel umbauen, damit die Benutzeranwendungen bequem die neue Funktionalität verwenden können, wollen wir sie in Systemaufrufschnittstellen kapseln, wie wir das bereits mit dem GuardedScheduler getan haben.

Konkret betrifft dies folglich die Tastatur, Semaphore sowie das zeitgesteuerte Schlafen. Sowohl die Semaphore als auch die Bell, die das zeitgesteuerte Schlafen eines Threads umsetzt, werden beide von Waitingroom abgeleitet, welche wiederum lediglich eine Queue von wartenden Threads implementiert.

Für Semaphoren ist dies dabei offensichtlicher, das wir hier potenziell mehrere wartende Threads verwalten müssen. Bei der Bell hingegen erscheint das am Anfang etwas unnötig, da dieses Objekt nur für einen einzelnen Thread existiert, eben der sich gerade schlafen legen will. Allerdings spart uns die Verwendung der gemeinsamen Basisklasse Waitingroom einiges an doppelten Code, insbesondere im Scheduler, welcher sich nun auch mit dem neuen Zustand "wartend" rumschlagen muss.

Dass wir zum Synchronisieren über Threads hinweg gemeinsame Semaphorenobjekte brauchen, und somit diese eher statisch allokieren, dürfte kaum überraschen. Aber der Einsatz der Bell, dem Wecker, dürfte noch etwas unklar sein: Eine Bell kann auch dynamisch erstellt werden, als temporäres Objekt auf dem Stack des Threads, der sich damit selbst für eine gewisse Zeit schlafen legen will. Alle aktiven Wecker-Objekt werden vom Bellringer, zu Deutsch dem Glöckner, in einer verketteten Liste verwaltet, welcher regelmäßig prüft, ob deren Zeit schon fertig abgelaufen ist – und sie dann gegebenenfalls "läutet", also die ausgeschlafenen Threads wieder aufweckt, in dem er sie in die Ready-Liste des Schedulers einreiht. Angestoßen wird diese Prüfung natürlich durch den LAPIC Timer, welcher so eingestellt sein sollte, dass er im Millisekundentakt eine Unterbrechung auslöst. Es ist dabei ausreichend, wenn der Bellringer nur auf einem Kern ausgeführt wird, beispielsweise dem Bootstrapprozessor (BSP).

Wie bereits erwähnt, kann es nun sehr leicht vorkommen, dass unsere Threads alle schlafen oder auf eine Semaphore warten, also nicht bereit sind und somit die Ready-Liste des Schedulers leer ist. Was soll dann ausgeführt werden? Wir brauchen einen speziellen Leerlaufthread, der sich am besten selbst verdrängt, sobald wieder ein Thread bereit ist, also die Ready-Liste des Schedulers nicht mehr leer ist. Und haargenau das macht dieser Code… Leider in einer Endlosschleife, es wird dauernd aktiv auf eine Änderung der Bereitschaftsliste geprüft, wir verbrennen also die CPU Zyklen, haben also wieder einen Heizkörper programmiert. Besser wäre es, wenn die CPU sich schlafen legt, solange der Scheduler nichts zum Abarbeiten hat. Mittels Core::idle() können wir das ändern, die CPU schläft dadurch stromsparend bis zur nächsten Unterbrechung. Dies lässt sich dann auch einfach in den IdleThread implementieren… Aber der Code hat einen Schönheitsfehler. Was, wenn exakt nach dem Prüfen, ob die Bereitschaftsliste leer ist, die Schlafenszeit eines Threads abgelaufen ist und dessen Status wieder auf bereit gesetzt wird? Wir setzen die CPU in den Leerlauf, obwohl wir einen Thread hätten, haben also ein klassisches Lost-Wakeup-Problem implementiert. Damit wir das lösen können, müssen wir erst die Implementierung von Core::idle() verstehen. Diese führt einfach die Instruktionen sti und hlt aus.

Die erste Instruktion, Set Interrupt Flag, kennen wir doch bereits aus Aufgabe 2, das aktiviert schlicht Unterbrechungen. Und Halt stoppt laut Intel Manual die Ausführung weiterer Instruktionen und setzt die aktuelle CPU in den "Halt" Zustand, bis sie durch eine Unterbrechung wieder aufwacht – sofern Unterbrechungen aktiviert sind. Ohne aktiven Unterbrechungen wird hlt ewig schlafen, bis die CPU neu gestartet wird – wir nutzen dieses Verhalten zum Beispiel in Core::die().

Also wir brauchen beide Instruktionen, um Unterbrechungen zu aktivieren und dann zu schlafen, haben wir also immer zwischen den beiden eine potenzielle Dornröschenschlafgefahr? Nun, nicht ganz, Denn die sti Instruktion ist ein wenig komplexer, wie das Intel Manual offenbart: Sie aktiviert Unterbrechungen nicht direkt, sondern erst zusammen mit der nachfolgenden Instruktion. Dadurch wird sti quasi atomar mit hlt ausgeführt, wir können zwischen beiden Instruktionen nicht unterbrochen werden – sofern natürlich die Interrupts zuvor aus waren.

Entsprechend können wir nun auch den IdleThread anpassen, indem wir zuerst Unterbrechungen sperren, bevor wir die Bereitschaftsliste prüfen. Falls diese leer ist, werden atomar Unterbrechungen aktiviert und in den Schlafmodus gewechselt – bis die CPU durch eine Unterbrechung wieder aufgeweckt wird, dann wird erneut diese Schleife durchgearbeitet und die Bereitschaftsliste geprüft. Sobald diese Liste aber nicht leer ist, werden die eben gesperrten Unterbrechungen wieder aktiviert und die Kontrolle dem nächsten Thread übergeben.

Dadurch ist unser System schon deutlich sparsamer, aber so richtig lange schläft unsere CPU dennoch nicht: Wir bekommen 1000 Unterbrechungen in der Sekunde, entsprechend wird das System 1000 mal in der Sekunde aufgeweckt und geht wieder schlafen – pro Kern. Da die Thematik bezüglich des Energieverbrauchs von Jahr zu Jahr an Relevanz gewinnt, könnt ihr euch dazu die tickless Variante anschauen. Die Grundidee ist sehr einfach: Wir deaktivieren den LAPIC Timer, wenn wir die CPU in den Leerlauf schicken, direkt vor Core::idle(), mittels den neuen Funktionen Watch::block() und Watch::unblock(). Dabei sollten wir den Bellringer nicht außer acht lassen, sobald mindestens ein Thread sich zeitgesteuert schlafen gelegt hat, darf die CPU, die dies behandelt, natürlich nicht den Timer deaktivieren.

In MPStuBS kann es nun noch vorkommen, dass mehrere Threads bereit werden, aber sich die anderen CPUs noch im Tiefschlaf befinden. Während es bei aktivem LAPIC Timer dann eine Verzögerung von maximal einer Millisekunde bis zur Abarbeitung gibt, kann das bei Tickless Kernel prinzipiell ewig dauern. Wir wollen aber, das eine Abarbeitung sofort beginnt, also alle im Leerlauf befindlichen CPUs aufwachen und die Threads einlasten. Dies lässt sich natürlich mit einem WakeUp-IPI (einem Inter Processor Interrupt) umsetzen – analog zum killen von Threads, wie in der letzten Aufgabe.