StuBS
Gegenseitiger Ausschluss (Mutual Exclusion, Mutex)

Table of Contents

Als gegenseitigen Auschluss versteht man, dass zu einem Zeitpunkt im gesamten System ein kritischer Abschnitt kein zweites Mal betreten werden kann, solange der erste Thread / Prozessor / ... ihn nicht wieder verlassen hat. Ein kritischer Abschnitt ist ein Stück Programmcode, bei dem es zu unerwünschten Effekten kommen kann, wenn zwei Threads oder Prozessoren ihn gleichzeitig ausführen. Je nach Verzahnung der Instruktionen kann es bspw. dazu kommen, dass Variablen-Updates nicht durchkommen, weil sie vom anderen Thread direkt überschrieben werden.

Bspw. kann es bei folgendem Code zu Problemen kommen (die Annahme ist, dass thread1() und thread2() gleichzeitig oder zumindest verzahnt ausgeführt werden):

int sum = 42;
int thread1 () {
sum+=1;
}
int thread2 () {
sum-=1;
}

Die gemeinsame Variable wird von jedem Thread zunächst ausgelesen, dann editiert und zurückgeschrieben. Verzahnen sich die Instruktionen ungünstig, kann es zu verlorenen Updates (+1 oder -1) kommen, wenn bspw. Thread 2 den neuen Wert von Thread 1 mit seinem alten überschreibt.

Im Betriebssystem gibt es verschiedene Arten von Akteuren. Zum einen gibt es den normalen Programmablauf und Interrupt-Service-Routinen, die sich in die Quere kommen können. Zum anderen gibt es im Mehrkernsystem noch mehrere CPU-Kerne die gleichzeitig Programmcode ausführen. Nicht nur, dass hierbei beliebige Überschneidungen zwischen beliebigen Instruktionen und Daten geben kann, sondern es können auch gleichzeitig mehrere Unterbrechungsbehandlungen durchgeführt werden.

Ausschluss von Interrupts

Interrupts müssen an zwei Stellen ausgeschlossen werden. Zunächst muss das Betriebssystem sicherstellen, wenn es auf geteilte Datenstrukturen zugreift, dass kein Interrupt auftreten kann, der ebenfalls auf diese Datenstruktur zugreifen würde. Auch muss sich der*die Systemprogrammierer*in Gedanken darüber machen, ob Interrupt-Behandlungen nested, also ineinander verschachtelt, ausgeführt werden dürfen.

Zum Ausschluss von verschachtelten Interrupt-Behandlungen kann man einfach Interrupt-Gates verwenden, bei denen die Intel-Prozessoren weitere Unterbrechungsbehandlungen ausschließen. Für den normalen Programmablauf können Interrupts im Prozessor ausmaskiert werden. Dazu kann man die Instruktionen cli und sti zum Ausmaskieren und wieder Einschalten von Interruptanforderungen benutzen.

Ausschluss zwischen Prozessoren

Zwischen mehreren Kernen muss ebenfalls ein Auschluss geschehen, wenn auf geteilte Datenstrukturen zugegriffen werden. Dafür genügen die Anweisungen, die das Interrupt-Flag im Statusregister setzen, nicht aus. Um einen gegenseitigen Ausschluss zwischen Kernen sicherzustellen, wird eine Speichervariable verwendet, die (auf verschiedene Art und Weise) anzeigt, ob sich ein Aktivitätsträger gerade im kritischen Abschnitt aufhält oder nicht. Man verwendet für den Zugriff dieser Variable dann typischerweise die Operationen lock() und unlock(). Die lock()-Operation kehrt dann zurück, wenn der kritische Abschnitt betreten werden kann, während die unlock()-Operation diesen wieder freigibt. Ist der kritische Abschnitt nicht frei, wird lock() nicht zurückkehren.

Es gibt sehr viele Möglichkeiten, Locks zu implementieren. Wir werden das klassische Spinlock implementieren sowie optional das Ticketlock.

Spinlock

Ein Spinlock ist eine Datenstruktur, die durch eine boolesche Variable umgesetzt werden kann, d.h., die Variable ist gesetzt, wenn sich ein Aktivitätsträger im kritischen Abschnitt befindet und ansonsten ungesetzt.

Beim Betreten des kritischen Abschnitts muss daher gewartet werden, bis die Variable frei ist. Dann wird sie gesetzt und der kritische Abschnitt betreten. Beim Verlassen des kritischen Abschnitts wird die Variable zurückgesetzt.

Achtung: Wenn die Prüfung und das Setzen der Variable in zwei Schritten abläuft, kann es zu einer Race-Condition kommen, da ein zweiter parallel laufender Aktivitätsträger die Prüfung ebenfalls schon positiv ausgeführt haben könnte und den kritischen Abschnitt betritt, bevor der erste Aktivitätsträger die Variable setzen kann. Prüfen und Setzen müssen darum atomar, d.h. gleichzeitig, ablaufen.

Intel-Prozessoren liefern dazu passende Instruktionen mit, um solche Aktionen zeitgleich auszuführen, und der GCC bringt eingebaute Macros mit, die diese Instruktionen verfügbar machen.

Ticketlock

Ein Ticketlock wird von zwei Integer-Variablen umgesetzt. Dabei gehen alle Benutzer des Locks an einen „Schalter“ und ziehen sich beim Betreten-Wollen ein Ticket, also eine Nummer. Zeigt das Lock die Nummer des Threads an, kann der kritische Abschnitt betreten werden, ansonsten muss gewartet werden. Beim Verlassen des kritischen Abschnitts, wir der Zähler, der das aktuelle Ticket anzeigt erhöht, sodass der nächste wartende Thread den kritischen Abschnitt betreten kann. Welche Operationen müssen hier atomar sein?