Warum Mutexe sinnvoll sind
Beim Schreiben von Multi-Threaded Code ist es unumgänglich, die einzelnen Threads miteinander zu synchronisieren, um Race Conditions zu vermeiden. Im Allgemeinen werden Mutexe verwendet, um kritische Bereiche des Codes zu schützen.
Mutexe haben zwei Methoden: mutex.acquire() und mutex.release(). Für jeden Codeblock, der von einem mutex.acquire() (sperren) und einem mutex.release() (freigeben) eingerahmt ist, ist gewährleistet, dass es nur von einem Thread gleichzeitig ausgeführt werden kann. Wenn ein Thread den Codeblock ausführt und ein anderer erreicht den mutex.acquire(), wird der zweite Thread blockiert, bis der erste Thread den Aufruf von mutex.release() erreicht.
So weit, so gut.
In einem komplexen System gibt es oft viele solche Critical Sections. Aus Gründen der Performance, der Skalierbarkeit und des Ansprechverhaltens, werden meist verschiedene Mutexe verwendet. Würden alle Critical Sections durch nur einen Mutex geschützt, würden Threads, die unabhängige Codeteile ausführen, unnötig blockiert. Stattdessen finden sich Mutexe oft lokal in einer Klasse oder einem Objekt und schützen die Integrität der internen Daten.
Das Problem: Deadlocks können auftreten
Wenn man mehrere Mutexe in einem System hat, entsteht ein potenzielles Problem: Wenn zwei Threads zwei Mutexe in unterschiedlicher Reihenfolge sperren, besteht die Möglichkeit eines Deadlocks zwischen den beiden Threads. Schauen wir uns ein Stück Code an:
class a {
private:
mutex ma;
data stuff;
b partnerb;
public:
void modify() {
ma.acquire();
stuff.modify();
ma.release();
}
int getInfo() {
int res;
ma.acquire();
res = partnerb.getInfo();
res += stuff.count();
ma.release();
return res;
}
}
class b {
private:
mutex mb;
data stuff;
a partnera;
public:
void modify() {
mb.acquire();
partnera.modify();
stuff.modify();
mb.release();
}
int getInfo() {
int res;
mb.acquire();
res = stuff.count();
mb.release();
return res;
}
}
Ein System, bei dem zwei oder mehr Threads die Klassen a und b verwenden und manchmal entweder getInfo()– oder modify()-Methoden aufrufen, kann für eine Weile laufen. Früher oder später wird jedoch ein Thread (Thread X) a.getInfo() aufrufen und gleichzeitig wird ein anderer Thread (Thread Y) b.modify() aufrufen.
Wenn das passiert, wird X ma.acquire() in a.getInfo() and dann mb.acquire() in b.getInfo() aufrufen. Y wird mb.acquire() in b.modify() und dann ma.acquire() in a.modify() aufrufen.
Wenn das Timing passt, wird X erfolgreich den Mutex ma sperren und Y wird erfolgreich den Mutex mb sperren.
Dann wird X versuchen, den Mutex mb zu sperren und Y versuchen, den Mutex ma zu sperren. Beide Threads werden ewig blockieren und wir haben einen perfekten Deadlock.
Im obigen Beispiel ist der Fehler einfach zu beheben. Man muss nur die Aufrufe partnera.modify() und partnerb.getInfo() aus den kritischen Abschnitten herauslösen und die Blockade ist verschwunden. In komplexen Systemen könnten jedoch die Auslöser dieses Problems durch viele Codeschichten getrennt sein. Außerdem kann es sein, dass sich das Problem nur sehr selten äußert – so selten, dass es während der Tests nie auftritt.
So lassen sich Deadlocks vermeiden
Um Deadlocks zu vermeiden, kann man eine sehr einfache Regel anwenden:
Beim Sperren mehrere Mutexe muss sichergestellt werden, dass sie immer in der gleichen Reihenfolge gesperrt werden.
Diese einfache Regel sorgt dafür, dass man keine Deadlock-Probleme durch die Verwendung von Mutexen bekommt. Die Schwierigkeit ist, diese Regel tatsächlich zu befolgen. In obigem Beispiel wird die Regel verletzt: ein Thread, der a.getInfo() ruft, sperrt erst ma und dann mb, während ein Thread, der b.modify() ruft, zuerst mb sperrt und dann ma. Selbst in diesem einfachen Beispiel sieht man den möglichen Deadlock nicht auf den ersten Blick. In einem komplexen System sind solche Probleme durch Code Review kaum zu finden. Was kann man also tun?
Der erste Schritt besteht darin, die Reihenfolge, in der Mutex erworben werden, bewusst zu definieren. D. h. man definiert einen Mutex-Level mit folgender Semantik: ein Mutex kann nur von einem Thread gesperrt werden, wenn kein Mutex mit gleichem oder höherem Mutex-Level von diesem Thread gehalten wird. Um diese Regel durchzusetzen, implementiert man eine Wrapper-Klasse für Mutexe (nennen wir sie LevelMutex). LevelMutex erwartet einen Mutex-Level im Konstruktor und speichert ihn. Beim Sperren eines Mutex (acquire) wird überprüft, dass nur Mutexe mit einem niedrigeren Mutex Level gesperrt wurden. Wenn die Überprüfung fehlschlägt, wird eine Fehlermeldung erzeugt. Die Buchhaltung über die gesperrten Mutexe kann (je nach Sprache/System) im Thread Local Storage oder in einer Map geführt werden.
Wenn man diese Infrastruktur verdrahtet hat, geht man in den Test. Bei vollständiger Code Coverage kann man nun bei Ausbleiben von Fehlermeldungen nachweisen, dass kein Deadlock-Potential besteht.
Fallstricke
Testabdeckung
Die ganze Vorgehensweise steht und fällt mit der Testabdeckung. Nur wenn alle Codepfade durch die Tests abgedeckt sind, kann man sicher sein, dass das System Deadlock-frei ist. Dies ist immerhin besser, als wenn man versuchen muss, durch massive Tests mit wechselnden Lastszenarien die Deadlocks zu erwischen.
Andere Synchronisationsmechanismen
Oft werden in Softwaresystemen nicht nur Mutexe, sondern auch noch andere Synchronisationsmechanismen eingesetzt (Semaphore, notify/wait, events, etc). Solche Mechanismen müssen in der Systematik und der Instrumentierung dann mitberücksichtigt werden.
Externe Synchronisationspunkte
Leider sind die eigenen Mutexe (und sonstigen Synchronisationsmechanismen, die man einsetzt) oft nicht die einzigen Synchronisationspunkte. Aufrufe in Bibliotheken und externe Systeme können einen Thread auch blockieren. Ein Beispiel dafür sind Datenbankzugriffe. Je nach Isolation Level können sich Datenbank-Queries durchaus gegenseitig blockieren. Um solche zusätzlichen Synchronisationspunkte in den Griff zu bekommen, muss man sie in das Schema mit einbeziehen, beispielsweise indem man sie über Wrapper-Klassen analog zu Mutexen behandelt.
Auflösen von potentiellen Deadlocks
Wenn man nun über die geschilderte Vorgehensweise feststellt, dass ein System Deadlock-Potential in sich trägt, stellt sich natürlich die Frage, wie man das Problem eliminiert. Letztendlich ähnelt das Jonglieren mit den Mutex-Levels und das Umstrukturieren des Codes dann einem Sodoku Puzzle. Trotzdem gibt es ein paar Ansätze, die helfen können, besonders harte Nüsse zu knacken.