Nachweislich keine Deadlocks

Beim Ausführen mehrerer Threads kann es vorkommen, dass sich mehrere Mutexe blockieren. Dadurch kann keiner der Threads weiter arbeiten – es kommt also zum Deadlock. Nachfolgend erfahren Sie, wie Sie diese Problematik umgehen.

Das erwartet Sie im folgenden Blog-Beitrag:

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.

Werden alle Mutex-Level in einer vordefinierten Reihenfolge aufgerufen, besteht kein Deadlock-Potential.
Ein System wird früher oder später ein Thread (Thread X) a.getInfo() aufrufen und gleichzeitig wird ein anderer Thread (Thread Y) b.modify() aufrufen. Das Resultat ist ein Deadlock.

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.

Werden alle Mutex-Level in einer vordefinierten Reihenfolge aufgerufen, besteht kein Deadlock-Potential.
Werden alle Mutex-Level in einer vordefinierten Reihenfolge aufgerufen, besteht kein Deadlock-Potential.

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.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert

Bitte beachte unsere Nutzungsrichtlinien

Mehr zu diesem Thema

Deadlock durch Logging

Deadlocks sind oft ein schwer zu lösendes Problem. Wenn dann dabei auch noch die Logging-Komponente, wie z.B. log4net, beteiligt ist, dann ist das nicht nur

Weiterlesen »
Um unsere Webseite für Sie optimal zu gestalten und fortlaufend verbessern zu können, verwenden wir Cookies. Weitere Informationen finden Sie in unserer Datenschutzerklärung.