Aufgabe 6: Synchronisation

Wir wollen unseren Anwendungen ein schlafen ermöglichen, also ein Zeitgesteuertes Warten. Das soll durch die Funktion sleep realisiert werden, welche Ähnlichkeiten mit dem gleichnamigen POSIX Gegenstück hat, aber bei uns die Zeitangaben in Millisekunden haben will. Wenn sich ein Faden schlafen legt, soll er analog zu den blockierten Threads beim wechselseitigen Ausschluss aus der Bereitschaftsliste entnommen und in ein Warte- bzw. Schlafzimmer überführt werden, zu welchem noch eine Schlafenszeit annotiert wird, im Beispiel 13 Millisekunden.

Für dieses Video werde ich dafür von nun an diese kompaktere aber äquivalente Darstellung für zeitbasierte Wartezimmer verwenden. Die Schlafenszeit wird jede Millisekunde um 1 verringert, bis sie die 0 erreicht und damit abgelaufen ist. Wir wecken den Faden wieder auf, in dem wir ihn wieder in die Bereitschaftsliste einreihen. Soweit so einfach, aber wie verwalten wir am besten die schlafenden Anwendungsfäden?

Als Beispiel legen wir drei Threads schlafen, foo für 666ms, bar für 23ms und baz für 42ms. Der einfachste Weg ist natürlich, diese Wartezimmer mittels verketteter Liste zu verwalten. Das hat aber den Nachteil, dass bei jedem Tick die ganze Liste durchlaufen werden muss. Die Komplexität beträgt nach der Landau-Notation O(n), also jeder der n Einträge muss bei jedem Tick geändert werden – und das durch unsere Taktung eben 1000 mal pro Sekunde, bei der Bearbeitung der Timerunterbrechung in der Epilogebene. Kann also bei vielen schlafenden Fäden schnell hässlich werden. Das muss doch besser gehen!

Wie wär es denn mit einer absoluten Zeit, welche mit jedem Tick um 1 hoch zählt. Wenn sich ein Faden schlafen legt, berechnen wir mithilfe der aktuellen Zeit die Aufwachzeit. Soweit haben wir von der Komplexität noch nichts gewonnen – es sei denn, wir verwenden zusätzlich eine Priority Queue. Dort kostet uns das Einordnen O(n), da wir die Schlange durchgehen müssen, um den Platz zu finden. Aber das Prüfen bei jedem Tick, ob der erste Eintrag der aktuellen Zeit entspricht, ist in der Regel dann ein konstanter Aufwand, O(1). Um das durchzuführen, müssen wir mit der absoluten Zeit einen neuen Zustand einführen. Und sollten natürlich 32 bit vermeiden, da hier ein Überlauf bereits nach knapp 50 Tagen auftritt. Das schöne aber an der Lösung ist, dass wir nur das erste Element in der Schlange anfassen müssen, können wir daraus nicht etwas stricken, was ohne die absolute Zeit auskommt?

Zum Beispiel können wir doch eine relative Delta-Zeit verwenden, also jeweils nur die Zeitdifferenz zum vorherigen Eintrag in der Schlange uns merken – und dabei natürlich keine negativen Differenzen zulassen, nur positive oder 0.

Zur Veranschaulichung nehmen wir wieder das vorherige Beispiel: foo will sich 666ms schlafen legen. Bis jetzt ist die Liste leer, aber implizit muss natürlich definiert sein, dass der "Vorgänger" des ersten Elements die Zeit t₀ mit 0ms hat. Somit beträgt die Zeitdifferenz auf das erste Element 666ms, wenn wir es einhängen.

Der zweite Thread bar möchte sich nur 23ms schlafen legen, dazu muss er von vorne beginnend an die richtige Stelle eingeordnet werden. Zuerst prüfen wir wieder gegen t₀ die Zeitdifferenz, diese beträgt mit 23ms weniger als des derzeitige erste Element – wir hängen es also an den Anfang der Liste. Für foo waren noch 666 verbleibende Millisekunden im Vergleich zu t₀ eingetragen, aber da wir es nun nach bar hängen wollen, müssen wir die Zeitdifferenz dazu berechnen: 643ms nach dem bar aufgeweckt wurde soll foo aufwachen. Wir haben bisher zum Einsortieren eine gesamte Komplexität von O(n).

Mit baz will sich der dritte Thread schlafen legen. Die Differenz zu t₀ beträgt mit 42ms mehr als bar noch Restzeit schläft, somit wird es nicht an der ersten Stelle eingefügt. Stattdessen berechnen wir die Zeitdifferenz zu bar, welche 19ms beträgt. Wir sehen bereits, dass wir für unsere Liste keine klassische Priority Queue verwenden können, da die Differenzzeitwerte nicht immer größer als die der Vorgänger sind. Nun müssen wir baz noch mit foo vergleichen, welches aber eine größere Zeitdifferenz hat. Also hängen wir es nach bar ein, und passen noch die Differenzzeit zu foo an.

Wenn nun eine Timerunterbrechung kommt, wird nur das erste Element um 1 verringert, also wieder konstanter Aufwand. Und sobald es 0 erreicht, wird es aufgeweckt, indem es aus dieser Liste genommen und der Faden wieder in die Bereitschaftsliste gehängt wird. Der Nachfolger wird dann der neue Head, hier baz. Als Sonderfall sollte man noch berücksichtigen, dass die Zeitdifferenz zum Nachfolger auch 0 sein kann, er also gleichzeitig mit dem Vorgänger aufgeweckt wird.