Linux singt das Schlaflied

Passiert dies, kommt der Kernel ins Spiel. Über den Systemcall »sys_futex()« erhält er neben der Adresse von »F« auch noch einen Sollwert: Nur wenn »F« diesen Sollwert besitzt, bettet der Kernel den aufrufenden Prozess wirklich zur Ruhe. Schließlich könnte ja wiederum - beispielsweise auf einem anderen CPU-Kern - der kritische Abschnitt soeben verlassen worden sein. Der Rückgabewert 0 der Funktion »xchg()« in Zeile 4 signalisiert dies, sodass der Thread die While-Schleife ab Zeile 5 nicht durchläuft.

Die Funktion zum Verlassen des kritischen Abschnitts ist glücklicherweise einfacher gestrickt. Sie liest den Wert von »F« aus und dekrementiert ihn gleichzeitig. Dabei sind nur zwei Fälle zu betrachten: War der Wert von »F« vor dem Dekrementieren 2, gibt es Rechenprozesse, die darauf warten, den kritischen Abschnitt betreten zu dürfen. Einen von ihnen weckt Linux mit Hilfe des Systemcalls »sys_futex()« wieder auf. Andernfalls beträgt der Wert vor dem Dekrementieren 1. Da niemand am Eingang des Abschnitts wartet, ist ein Aufwecken also unnötig. Der Fall, dass »F« den Wert 0 hat, tritt bei der Unlock-Operation nicht auf.

Der Kernel hat sich zum Futex »F« eine Liste angelegt, in der er die schlafenden Rechenprozesse verwaltet. Zum Aufwecken wird der erste aus der Liste entfernt und wachgerüttelt. Aber es gibt noch ein Problem: Was passiert, wenn eine Applikation in einem kritischen Abschnitt abstürzt? Anders als bei Filedeskriptoren, die der Kernel verwaltet und im Fall eines Programmabsturzes freigibt, ist das bei den Futexen zunächst nicht möglich. Aus Sicht des Kernels ist ein Futex nichts weiter als eine Speicherstelle.

Um bei Abstürzen Deadlocks zu verhindern, haben Torvalds und seine Mannen das "robuste Futex" entwickelt [5]. Hinter ihm verbirgt sich der Systemaufruf »sys_set_robust_list()«. Er macht das Futex - genauer eine Reihe von Futexen - vor der Benutzung dem Kernel als solches bekannt. Stürzt ein Programm jetzt ab, prüft der Kernel dessen Liste der verwendeten Futexe. Findet er aktive, informiert er die wartenden Prozesse über den Absturz.

Parameter verwirren Programmierer

Entwickler verwenden also den Systemcall »sys_futex()« dazu, einen Prozess schlafen zu legen oder aufzuwecken. Seine Parameter lassen sich sehr universell einsetzen und sind damit komplex und in der Praxis fehlerträchtig. Kein Wunder also, dass die Standardbibliothek keine Funktion bereithält, die die Systemcalls »sys_futex()« und »sys_set_robust_list()« explizit unterstützt. Allerdings verwenden die unter Linux üblicherweise eingesetzten Synchronisationsfunktionen »pthread_mutex_lock()« und »pthread_mutex_unlock()« intern den Syscall »sys_futex()«. Auf diese Weise setzten Programmierer unbemerkt bereits reichlich Fast-User-Mutexe ein. Die Pthread-Funktionen unterstützen übrigens insbesondere das robuste Futex.

Für Echtzeitprogrammierer wird es allerdings erst richtig spannend, wenn sie sich im Kernel die für ein Futex verwendete Technik ansehen: Futexe bauen auf den Realtime-Mutexen »rt_mutex« auf [4]. Darüber hinaus kommen sie auch mit den in Echtzeitanwendungen wichtigen Problemen zurecht, die sich durch unterschiedliche Prioritäten ergeben (siehe Kasten "Prioritätsinversion und Prioritätsvererbung"). Zusätzlich interessant: Realtime-Mutexe stehen sämtlichen Kernelfunktionen und Treibern zur Verfügung. Damit komplettieren sie das umfangreiche Arsenal von Schutzmechanismen, das bei Spinlocks beginnt und über Sequence-Locks zu Memory-Barrieren führt [1].

Prioritätsinversion und Prioritätsvererbung

Wenn ein Job mit mittlerer Priorität einen Job höherer Priorität aufhält, nennt man das "Prioritätsinversion" (Abbildung 4). Typischerweise sind daran mindestens drei Jobs beteiligt: Einer mit hoher (A), einer mit mittlerer (B) und eben einer mit niedriger Priorität (C). Außerdem teilen sich Job A und C ein Betriebsmittel. Sie haben also einen kritischen Abschnitt gemeinsam, den ein Lock (Semaphor, Mutex, Spinlock oder Futex) schützt. Zu einer Prioritätsinversion kommt es, wenn C den kritischen Abschnitt betreten hat, in den A eintreten will. In diesem Fall blockiert A so lange, bis C die Unlock-Funktion aufruft. Wird in dieser Situation Job B lauffähig, verzögert er die Weiterverarbeitung von C, denn der hat ja niedrigere Priorität. Indirekt bremst er so aber auch A, obwohl die Verarbeitung von A aufgrund der Priorität dringlicher wäre. Zur Entschärfung der Prioritätsinversion setzen Entwickler auf die so genannte Prioritätsvererbung. Sobald der hochpriorisierte Job A die Lock-Funktion beim Betreten des kritischen Abschnitts aufruft und das Semaphor oder das Mutex durch den niedrig priorisierten Rechenprozess C belegt ist, erbt C die hohe Priorität von A (Abbildung 5). So ausgestattet lässt C sich nicht mehr durch den mittelpriorisierte Job B verdrängen. Gibt er den Lock frei, nimmt er wieder seine ursprüngliche Priorität an und der hochpriorisierte Job betritt - mit signifikant kürzerer Latenzzeit - den kritischen Abschnitt. Abbildung 4: Eine Prioritätsinversion mit drei Jobs – A (rot, hohe Priorität), B (gelb, mittlere Priorität) und C (grün, niedrige Priorität) – entsteht, wenn der hochrangige Job A auf zwei nachrangige Jobs wartet. Abbildung 5: Prioritätsvererbung löst die Situation: Der langsame Job C erbt die hohe Priorität von A, solange dieser auf Einlass wartet. Job B wartet. Die Latenz von A ist insgesamt deutlich geringer.