Aufgabe 6: Synchronisation

Wenn mehrere Threads dieselben Betriebsmittel verwenden, welche nur exklusiv benutzt werden können, müssen sie sich synchronisieren. Mittels gegenseitigem Ausschluss wird dabei verhindert, dass mehrere Fäden denselben kritischen Abschnitt betreten. Wie sieht das in StuBS aus? Wir haben doch mit der Umlaufsperre ein kreiselndes Warten implementiert.

Sowohl ticket- als auch spinlock bieten dazu die Methoden lock() zum Sperren und unlock() zum Entsperren des kritischen Abschnitts an.

Als Beispiel lassen wir mal im Einkernbetrieb drei Anwendungen einen wechselseitigen Ausschluss verwenden, zu Beginn befinden sich auch alle noch in der Bereitschaftsliste. Die erste Anwendung wird entnommen, und die Bearbeitung angefangen, sie ruft die Sperroperation auf dem Mutex auf und betritt damit den kritischen Abschnitt. Bei der Abarbeitung kann es nun jedoch vorkommen, dass unsere Zeitscheibe abläuft, während wir noch in diesem Abschnitt sind, der Timerinterrupt also veranlasst, dass wir rausgescheduled werden.

Dann wird mit App2 die nächste Anwendung aus der Bereitschaftsliste entnommen, und ausgeführt. Diese versucht ebenfalls den kritischen Abschnitt zu betreten, da aber Anwendung 1 sich noch darin befindet und entsprechend den lock hält, wird sie aktiv warten – und zwar so lange, bis die Zeitscheibe abgelaufen ist. Sobald auch hier die Timerunterbrechung kommt, wird sie unverrichteter Dinge wieder in die Bereitschaftsliste gelegt, die nächste Anwendung entnommen und ihr die Kontrolle übergeben. Und das Spiel wiederholt sich: Ein Betreten des kritischen Abschnitts ist zurzeit nicht möglich, es wird aktiv gewartet… Und zwar wieder die ganze Zeitscheibe, bis sie wieder rausgescheduled wird, und endlich App1 wieder zum Zuge kommt, den kritischen Abschnitt fertigstellen kann, und den mutex freigibt.

Wir haben also einen Großteil unserer Zeit mit aktivem Warten verbracht – ohne das wir währenddessen irgendeinen Fortschritt haben hätten können, haben somit im Endeffekt nur das Zimmer geheizt. Wie geht das besser?

Nun, wir könnten eine harte Synchronisation verwenden, eine Art deaktivieren der Unterbrechungen, aber weniger umfassend, nur auf den Scheduler beschränkt – dass dieser uns nicht innerhalb eines kritischen Abschnitts zurück in die Bereitschaftsliste schickt. Wie könnten wir das implementieren? Eine Möglichkeit wäre das temporäre Aussetzen des präemptiven Schedulings, beispielsweise indem wir die Timerunterbrechungen blockieren. Oder wir Erweitern den Scheduler, sodass wir ihn über die Abarbeitung kritischer Abschnitte informieren können und er währenddessen auf einen Fadenwechsel verzichtet. Zudem haben wir natürlich noch unsere Epilogebene, könnten den kritischen Abschnitt einfach dort abarbeiten, Timerepiloge werden dadurch erst beim Verlassen ausgeführt, wir werden also davor nicht verdrängt. Diese Varianten funktionieren und sind zudem auch vergleichsweise einfach umzusetzen.

Leider haben sie auch systemweite Auswirkungen, wir verzögern unter Umständen höherpriore Kontrollflüsse, und führen das außerdem immer vorbeugend aus. Gibt es da nicht was Besseres, ohne diese Probleme? Wie wäre es mit einem passivem Warten, dass wir also die blockierten Threads aus dem Scheduler nehmen, während der betreffende Abschnitt belegt ist?

Bis jetzt kennt unser Scheduler zwei Zustände, active für den aktuell laufenden Thread und ready für die Threads in der Bereitschaftsliste. Außerdem können sich Threads mittels exit() selbst beenden, oder mittels kill() beendet werden, sie sind dann tot. Wir wollen nun also einen neuen Zustand wartend einführen, in den ein aktiver Thread bei einer Blockierung wechseln kann. Sobald die Resource wieder frei ist, kann er aufgeweckt werden und wird wieder in die Bereitschaftsliste eingereiht. Und natürlich soll auch ein wartender Thread beendet werden können. Dazu führen wir für die blockierten Threads ein Wartezimmer ein, dies ist – wie die Bereitschaftsliste – nichts weiter als eine Queue von Threads.

Testen wir den neuen Ansatz am vorherige Beispiel mit den drei Anwendungen: Zuerst wird App1 aus der Ready-Liste genommen und ausgeführt, es sperrt den Mutex und bearbeitet den kritischen Abschnitt, bis mittels Timerinterrupt der Ablauf unterbrochen wird, sie wieder in die Bereitschaftsliste kommt und auf App2 gewechselt wird. Diese versucht nun ebenfalls das lock(), jedoch hat dies gerade App1 – sie ist blockiert, wechselt also in das Wartezimmer… Und die nächste Anwendung wird eingelastet. Dort wird ebenfalls versucht den gesperrten kritischen Abschnitt zu betreten, weshalb auch dieser Thread in das Wartezimmer geschoben wird.

Nun befindet sich nur noch App1 in der Bereitschaftsliste, wird entnommen und kann den kritischen Abschnitt weiter ausführen. Sobald sie damit fertig ist und unlock() aufruft, wird einer der wartenden Threads wieder auf bereit gesetzt. Danach läuft App1 aber noch weiter, bis irgendwann die Zeitscheibe abgelaufen ist, und der Scheduler nun App2 einlastet. Zuvor konnte diese nicht das lock erhalten und hat sich blockiert, nun aber ist der Bereich frei und sie erfolgreich, kann also den kritischen Abschnitt betreten. Und beim Verlassen wird dann wieder ein wartender Thread auf bereit gesetzt, in diesem Fall App3. Gut zu erkennen: Mit diesem Verfahren verschwenden wir kaum CPU Zeit, hat also einen deutlichen Vorteil.

Eine gängige Datenstruktur für den gezeigten wechselseitigen Ausschluss ist der Semaphore. Der Begriff steht für einen Signalisierungsmechanismus, aus dem Bereich der schienengebundenen Verkehrssysteme, ursprünglich mittels zweier Flaggen, um beispielsweise zu informieren, ob ein Gleisabschnitt befahrbar ist. Der Niederländer Dijkstra hat diesen Begriff für die von ihm entwickelte Datenstruktur verwendet, was auch die Namensgebung der p() und v() Operationen erklärt: Um einen kritischen Abschnitt zu betreten, wird die p() Operation aufgerufen, welches anfangs von Dijkstra als "Passering" (passieren) beschrieben wurde, und später zum Kunstwort "Proolag" umgedeutet: Dem Versuch den Zähler zu verringern. Sollte dies fehlschlagen, da er bereits bei Null ist, wird gewartet.

Die komplementäre Operation dazu ist v(), für "Vrijgave" (also Freigeben) bzw. später "Verhoog", dem Erhöhen des Zählers, falls kein anderer Faden mehr wartet. Durch den Zähler können wir dabei das Verhalten maßgeblich beeinflussen: Wird er mit 1 initialisiert, und nimmt auch im weiteren Ablauf keinen höheren Wert an, spricht man von einem binären Semaphor. Er dient beispielsweise dem Sichern kritischer Abschnitte, erlaubt also nur einen exklusiven Zugriff wie in den vorher gezeigten Beispielen, wobei p() dann mit lock() äquivalent ist und v() mit unlock().

Allerdings eignet sich diese Datenstruktur nicht nur für Konkurrenzsituation, sondern kann auch die Kooperation mehrerer Fäden unterstützen.