Manche Applikationen müssen verhindern, dass die CPU bestimmte Codesequenzen mehrfach betritt. Dazu aktivieren sie Realtime-Mutexe im Kernel. Die sind nicht nur besonders effizient, sondern beherrschen auch die für Echtzeitanwendungen wichtige Prioritätsinversion.

Der Schutz kritischer Abschnitte gehört zu den diffizilsten und unangenehmsten Aufgaben eines Programmierers. Er muss diese Codeteile identifizieren (siehe Kasten "Kritischer Abschnitt") und dazu aus einer Unzahl von Schutzmöglichkeiten die effizienteste Variante auswählen [1]. Sehr verbreitet sind das bekannte Semaphor und das Mutex. Seit Kernel 2.6 hat Linus Torvalds zusätzlich das so genannte Futex in seinen Kernel aufgenommen [2]. "Ein Futex", so verspricht die Werbebroschüre, "ist ein Fast-User-Mutex, das deshalb so schnell ist, weil es ohne den Kernel auskommt."

Kernel kontrolliert Eintritt

Das entspricht allerdings nur der halben Wahrheit. Richtig ist, dass ein Futex schnell ist. Unwahr hingegen, dass es ohne den Kernel auskommt. Auch das Futex benötigt Kernelunterstützung: Befindet sich bereits ein Thread im kritischen Abschnitt, legt Linux nachfolgende Threads schlafen beziehungsweise weckt sie wieder auf. Die Kernelentwickler sprechen in diesem Fall von einem Slow-Path, dem langsamen Weg. Im Fast-Path, dem schnellen Weg also, ist der Kernel tatsächlich nicht beteiligt.

Da im Userspace keine Codesequenz wirklich atomar abläuft, beruhen Futexe ausschließlich auf einzelnen Maschinenbefehlen. Einer davon ist »cmpxchg«, der in einem Schritt eine Speicherzelle verändert und gleichzeitig deren Wert überprüft. Die das Futex repräsentierende Speicherstelle »F« kann dabei einen Wert von 0, 1 oder 2 haben (Tabelle 1). Die Operation »futex_lock()« lässt sich damit auf Applikationsebene wie in Abbildung 1 realisieren [3]: Betritt der Kontrollfluss den kritischen Abschnitt, setzt er Futex »F« auf 1. So zeigt er an, dass der Abschnitt ab jetzt nicht mehr frei ist (Abbildung 1, Zeile 2). Je nach dem bisherigen Wert von »F« treten jetzt drei Fälle auf.

Tabelle 1: Werte einer Futex-Speicherzelle

War der bisherige Wert 0, ist der kritische Abschnitt bislang frei. Das ist der Fast-Path und bedeutet, dass die Applikation ohne anzuhalten den kritischen Abschnitt betreten darf. Das Futex benötigt dazu keine Hilfe vom Kernel.

Im zweiten Fall ist der ursprüngliche Wert von »F« 1. Ein anderer Prozess belegt also bereits den kritischen Abschnitt, doch warten keine weiteren Rechenprozesse. Daher setzt der Thread das Futex »F« nun auf den Wert 2 (Zeile 4). Das ist das Zeichen dafür, dass ein Rechenprozess wartet. Das Betriebssystem weckt diesen Schläfer wieder auf, sobald der Abschnitt frei ist.

Abbildung 1: Zur Implementierung eines Locks benötigen Entwickler im Userland nur wenige Zeilen Code. Bibliotheken setzen die vom Kernel bereitgestellten Mechanismen um, hier ein Mutex.

Prozesse treten einzeln ein

Während andere Prozesse die Zeilen 2 bis 4 abarbeiten, kann der Thread, der sich bis jetzt im kritischen Abschnitt befindet, die Funktion »futex_unlock(F)« aufrufen. Damit gibt er das Lock wieder frei. Auf einer SMP-Maschine tritt so ein Fall häufig auf. Er lässt sich am Rückgabewert von 0 in Zeile 4 leicht erkennen. Der Rechenprozess wartet dann doch nicht (er durchläuft dann die While-Schleife ab Zeile 5 nicht), sondern beendet die Funktion »futex_lock()«.

Damit betritt er direkt den kritischen Abschnitt. Allerdings hat »F« jetzt den Wert 2, obwohl in Wirklichkeit doch gar kein Prozess wartet. Die Konsequenz dieser Konstellation: Signalisiert der Prozess durch Aufruf der Funktion »futex_unlock(F)«, dass er den kritischen Abschnitt verlassen hat, durchläuft er unnötigerweise den Slow-Path und setzt einen Systemaufruf zum Aufwecken eines Rechenprozesses ab.

Die dritte Alternative bekommt Bedeutung, wenn der ursprüngliche Wert 2 war. Dann war der kritische Abschnitt belegt und es warten bereits weitere Rechenprozesse darauf, ihn betreten zu dürfen. In diesem Fall legt Linux den Prozess direkt mit Hilfe des Systemcalls »sys_futex()« schlafen.

Kritischer Abschnitt

Entwickler bezeichnen Codesequenzen, in denen sie auf gemeinsam genutze Betriebsmittel zugreifen, als kritischen Abschnitt. Das gemeinsam genutzte Betriebsmittel ist zumeist eine Datenstruktur, etwa im Kernel die Liste aller Rechenprozesse. Damit es beim Zugriff auf das Betriebsmittel zu keinen Inkonsistenzen kommt, dürfen keine parallelen Zugriffe stattfinden. Die notwendige Sequenzialisierung realisieren die Programmierer über ein Lock (Semaphor, Mutex, Spinlock). Dazu rufen sie zu Beginn der Codesequenz eine Funktion »lock()« oder »P()« auf und zeigen das Ende des Abschnitts mittels »unlock()« oder »V()« an (Abbildung 2). Abbildung 2: Anwender schützen kritische Abschnitte in ihren Programmen, damit diese sich nicht inkonsistent verhalten. Dazu umgürten sie betroffene Codeteile mit den Funktionsaufrufen »P()« und »V()«.

Sie können diesen Artikel als PDF für 99 Cent kaufen. Klicken Sie dazu einfach auf eine der beiden Bezahloptionen Paypal oder ClickandBuy.

Manche Applikationen müssen verhindern, dass die CPU bestimmte Codesequenzen mehrfach betritt. Dazu aktivieren sie Realtime-Mutexe im Kernel. Die sind nicht nur besonders effizient, sondern beherrschen auch die für Echtzeitanwendungen wichtige Prioritätsinversion.