Über Deadlock Bugs: ein Exkurs durch die Qualen des zirkulären Wartens

Koordinierung ist kompliziert und Computer sind kompliziert. Es ist also nicht verwunderlich, dass bei der Koordinierung in Computern einiges schief gehen kann. Im Computing-Kontext bezeichnet man Koordinierung, also die Fähigkeit eines Systems, mehrere Dinge gleichzeitig und damit schneller auszuführen, als Nebenläufigkeit oder Concurrency. 

Geschwindigkeit ist definitiv von Vorteil, aber das Schreiben von nebenläufiger Software erfordert, dass sich die Entwickler der Wechselwirkungen zwischen den nebenläufigen Elementen in ihren Programmen genau bewusst sind. Und weil das nicht immer der Fall ist, kommt es zu einer nicht unerheblichen Anzahl von Concurrency Bugs. Diese Fehler sind besonders tückisch, weil sie nicht nur sehr unauffällig und damit schwer zu erkennen, zu diagnostizieren und zu vermeiden sind, sondern auch ein spürbares Problem für die Systemstabilität darstellen.

Deadlocks sind eine Art von Concurrency Bug. Sie können Anwendungen blockieren, zum Einfrieren oder sogar zum Abstürzen bringen, was wiederum die Erreichung von Verfügbarkeitszielen gefährden kann. Diese Art von Fehler tritt auf, wenn Teile eines Programms hängenbleiben, weil sie auf Ressourcen warten, die in hängengebliebenen Programmteilen enthalten sind, die ihrerseits wiederum auf Ressourcen in hängengebliebenen Programmteilen warten … Das Heimtückische an Deadlocks ist also ihre rekursive Eigenschaft – besonders, wenn sie in der Produktivumgebung auftreten.

In diesem Blogpost erfahren Sie, wie Deadlock-Bugs entstehen, einige Facetten ihrer faszinierenden und frustrierenden Eigenart und wie Sie damit in Ihren eigenen Systemen umgehen können.

Koordinierung ist kompliziert

Computer verfügen über zahlreiche Ressourcen wie Dateien, Netzwerkverbindungen oder Datenstrukturen im Zwischenspeicher, die Programme nutzen müssen, um ihren Zweck bzw. ihre Zwecke zu erfüllen. Zu den Instanzen, die möglicherweise exklusiven Zugriff auf eine Ressource benötigen, gehören Threads, Prozesse, Actors und Fibers. Der Einfachheit halber beschränken wir uns darauf, Deadlocks aus der Prozessperspektive zu betrachten. 

Was ist, wenn mehrere Prozesse dieselbe Ressource gleichzeitig nutzen wollen?Der Mechanismus zur Verwaltung dieser Forderungen funktioniert über den gegenseitigen Ausschluss (auch „Mutex“ genannt). Er bestimmt, wann eine Ressource von einem Prozess oder einem anderen verwendet werden soll. 

Nehmen wir z. B. das Programm /bin/texttransform, das Vorgänge wie das Lesen, Schreiben oder Löschen von Textzeilen in Dateien durchführt. Verschiedene Instanzen dieses Programms können gleichzeitig ausgeführt werden, um unterschiedliche Anfragen zu bearbeiten und dabei die Ressourcen zu nutzen, die zur Ausführung des Vorgangs erforderlich sind. Ein Beispiel wären mehrere Kopien von /bin/texttransform, die auf einem Webserver laufen, der gleichzeitige Anfragen von verschiedenen Clients zum Lesen einer Textzeile aus FileA.txt verarbeitet.

Wie verwalten Sie aber, welcher Prozess die Datei wann verwendet, wenn eine Instanz des Programms eine Textzeile in FileA.txt schreiben soll, während eine andere Instanz des Programms eine Textzeile in derselben Datei löschen soll?

Daraus ergibt sich die Notwendigkeit eines Mechanismus zum gegenseitigen Ausschluss, um eine effiziente Koordinierung zu ermöglichen – oder, um es computergerechter auszudrücken – der Synchronisierung des gleichzeitigen Zugriffs auf Ressourcen. Ihr Browser muss zum Beispiel sicherstellen, dass alle von Ihnen geöffneten Tabs (in meinem Browser viel zu viele) den Zugriff auf Ihre Browserverlaufsdatenbank sicher koordinieren können. 

Der Mutex-Mechanismus umfasst zwei Hauptvorgänge:

1. Besitzerwerb eines Mutex: Damit übernehmen Sie die Berechtigung, die mit dem Mutex verknüpfte Ressource zu nutzen (in unserem Beispiel FileA.txt). Wenn ein anderer Prozess bereits berechtigt ist, die Ressource zu nutzen, müssen Sie warten, bis dieser andere Prozess sein Recht freigibt, bevor Sie das Recht zur Nutzung der Ressource erfolgreich übernehmen können. Der Mutex wird auch als „Sperre“ bezeichnet, da er alle anderen von der Nutzung der Ressource ausschließt, während Sie das Recht haben, sie zu nutzen. 

2. Release des Mutex: Hiermit geben Sie Ihr Recht auf die Nutzung der mit dem Mutex verbundenen Ressource ab: Die „Sperre“ für den Zugriff wird gelöst. Wenn ein anderer Prozess auf die Ressource wartet, erhält er sofort das Recht, sie zu nutzen, nachdem Sie sie freigegeben haben.

Solange jeder den gegenseitigen Ausschlussmechanismus konsequent anwendet und nicht gegen die Regeln verstößt, gibt es keine Probleme. Durch die gleichzeitige Ausführung werden Abläufe beschleunigt und die Programmziele schneller erreicht. Das verteilte System reitet einem traumhaften Sonnenuntergang entgegen und sonnt sich in seiner vollkommenen Nebenläufigkeit.

Doch die Realität sieht anders aus. Alles Mögliche kann schiefgehen und geht auch schief, und auch der Mutex bleibt nicht von diesem Schicksal verschont. Trotz des Begriffs „Sperre“ ist ein Mutex eher mit einer Ampel vergleichbar: Jeder muss mit den Regeln vertraut sein und sie befolgen, damit sie funktionieren. Bei einem Mutex-System sind einige offensichtliche Fehler möglich, die in verteilten Systemen katastrophale Folgen haben können, darunter Ausfälle oder Latenzspitzen.Sehen wir uns das näher an.

Chaos durch Deadlocks im Multi-Mutex

Was, wenn mehr als eine Ressource gleichzeitig benötigt wird? 

Angenommen, eine der Aufgaben des texttransform-Programms besteht darin, eine Zeile aus einer Quelldatei (FileA.txt) zu entfernenund sie an eine Zieldatei (FileB.txt) anzuhängen. Wenn texttransform gleichzeitig auf FileA.txt und FileB.txt zugreifen will, muss es gleichzeitig über die Mutexe für beide verfügen. Das Programm kann beim Start den Besitz der Mutexe für die Quelldatei und einen weiteren Mutex für die Zieldatei erwerben, die Weitergabe des Textes durchführen und dann beide Mutexe wieder freigeben, sobald der Vorgang abgeschlossen ist.

Und genau an dieser Stelle besteht die Gefahr eines Deadlocks.Dem Entwickler, der diese Mutex-Designentscheidung getroffen hat, wird wahrscheinlich nicht sofort auffallen, dass dies problematisch ist. Was sollte bei einer Sperre für sämtliche Ressourcen schon schiefgehen?

Was aber, wenn /bin/texttransform mit dem Request gestartet wird, Text von FileA.txt zu FileB.txt zu verschieben, und zwar zur gleichen Zeit, zu der eine andere Instanz des Programms aufgefordert wird, Zeilen in der umgekehrten Reihenfolge zu verschieben, also von FileB.txt zu FileA.txt? Das erste Programm erhält zwar das Recht, FileA.txt zu verwenden, muss aber auf die Verwendung von FileB.txt warten. Das andere Programm kann auf FileB.txt zugreifen, muss aber auf die Verwendung von FileA.txt warten (ein Zustand, der als „zirkuläres Warten“ bezeichnet wird). Beide Programme warten auf Rechte, die niemals freigegeben werden!

Hierbei handelt es sich um den gefürchteten Deadlock. Die Ressourcensperren werden nie gelöst, und es gibt keinen Diener, der dem System sagt, „der Mutex, mein Herr, ist tot“.Dateien oder andere Ressourcen in einem System können von mehreren Prozessen gleichzeitig angefordert werden, sodass sie bis in alle Ewigkeit in einem digitalen Fegefeuer landen, in dem alle darauf warten, Zugriff zu erhalten, und keine von ihnen vorankommt. 

Die Folgen eines Deadlocks für das System können ein Hängenbleiben der Anwendung oder sogar ein Systemabsturz sein, wodurch die wertvolle Verfügbarkeit in verteilten Systemen gefährdet wird. Selbst völlig unzusammenhängende Prozesse können zum Stillstand kommen – eine Sackgasse, der man nur durch ein Wunder entkommen kann, denn nichts außer der Abschaltung und eines Reboots des Systems (sowie einigen Opfern an die Götter der Fehlersuche in der Hoffnung, reichhaltige Debug-Informationen zu erhalten) reicht aus, um die Ursache der Blockade zu simulieren und zu beheben.

Wie können Mutex-Designentscheidungen zu Deadlocks führen?

Eine Designentscheidung, die zu Deadlocks führt (ein Mutex für jede Ressource) ist eine natürliche Schlussfolgerung für Entwickler, wenn es um den Umgang mit Nebenläufigkeit geht.Eine solche Designentscheidung liegt zwar auf der Hand, ist aber nicht die einzige Option. Wie kommt es also zu einem solchen Schlamassel?

Es kann beispielsweise sein, dass jede Instanz eines Prozesses auch den Zugriff auf mehrere Dateien (wie FileA.txt, FileB.txt,FileC.txt und FileD.txt) koordinieren muss, sodass alle diese Ressourcen gegenseitige Ausschlüsse erzwingen müssen.In solchen Fällen wünschten die meisten Entwickler, sie lebten in einer abgelegenen Holzhütte und Computer würden gar nicht erst existieren, da die Mutex-Anforderungen völlig außer Kontrolle geraten.

Aber wie können wir diese Komplexität in den Griff bekommen? Eine Möglichkeit wäre, dass der Entwickler die Komplexität reduziert, indem er das Mutex-Design vereinfacht und nur einen einzigen Mutex verwendet. Dabei kann er festlegen, dass ein Prozess, der das Nutzungsrecht an einer Ressource besitzt, auch das Recht zur Nutzung einer andere Ressource hat. Dies ist eine sinnvolle Entscheidung, wenn eine Ressource nur gleichzeitig mit einer anderen benötigt wird. 

Kehren wir zu unserem vorherigen Beispiel zurück: Eine der Aufgaben von /bin/texttransform besteht darin, eine Zeile aus einer Quelldatei (FileA.txt) zu entfernen und sie an eine Zieldatei (FileB.txt) anzuhängen.Der Entwickler kann einen einzigen Mutex implementieren, um sicherzustellen, dass der Prozess sich bereit erklärt, vor der Durchführung dieses Vorgangs die entsprechenden Rechte für beide Dateien zu erwerben und den Mutex anschließend wieder freizugeben. Tatsächlich gilt dieser Mutex für alle Aufrufe des Prozesses, unabhängig davon, auf welche Dateien zugegriffen wird. Prozessinstanzen, die auf unterschiedliche Dateien zugreifen, müssen schließlich dennoch koordiniert werden. 

Das Problem mit dem Single-Mutex-Design ist, dass es zu ungenutzten Ressourcen führen kann.Wenn eine andere Instanz des Prozesses bereits läuft und über den entsprechenden Mutex verfügt, wartet der Prozess, bis diese andere Instanz den Mutex freigibt, bevor er mit seinen eigenen Vorgängen fortfährt. Wenn es jedoch Aufgaben gibt, die nur die erste Ressource benötigen, und andere Aufgaben, die nur die zweite Ressource benötigen, kann es passieren, dass eine der Ressourcen ungenutzt bleibt, selbst wenn ein Prozess sie benötigt. Dies beeinträchtigt die Systemperformance und frustriert menschliche Nutzer (und vermutlich auch Computer).

Um dieses Problem der ungenutzten Ressourcen zu lösen, könnten Entwickler natürlich mehrere Mutexe in Betracht ziehen, um eine größere Nebenläufigkeit zu unterstützen. Möglicherweise ist es sinnvoll, einen weiteren Mechanismus einzuführen, damit der Zugriff auf eine Ressource getrennt vom Zugriff auf die andere Ressource koordiniert werden kann. Der Entwickler beschließt, von einem einzigen Mutex, der sich auf alle möglicherweise benötigten Dateien erstreckt, zu individuellen Mutexen für jede einzelne Datei überzugehen, deren Besitz der Prozess in sequentieller Reihenfolge erwirbt und jeweils freigibt, sobald der entsprechende Vorgang abgeschlossen ist. 

Im Fall von texttransform, das Zugriff auf FileA.txt und FileB.txt benötigt, führt diese Entscheidung zu zwei Mutexen.Wenn der Prozess eine Zeile aus FileA.txt entfernen und an FileB.txt anhängen will, muss er dafür den Besitz des Mutex für FileA.txt erwerben, die Zeile aus FileA.txt entfernen und den Mutex für FileA.txt freigeben, den Besitz des Mutex fürFileB.txt erwerben, die Zeile an FileB.txt anhängen und den Mutex für FileB.txt freigeben.

Leider ergibt sich dabei ein unterschwelliges kleines Problem: Die Zeilen können durcheinander geraten, wenn sie gleichzeitig von einer Datei zur anderen weitergegeben werden. Sehen wir uns zwei Aufrufe unseres Programms an, die die letzte Zeile der Quelldatei PaleFire.txt kopieren und an die Zieldatei EmptyFire.txt anhängen sollen:

PaleFire.txt

1 Ich war der im Schatten des Seidenschwanzes, erschlagen
2 vom falschen Blau der Fensterscheibe;
3 ich war der Fleck aus aschfahlem Flaum und
4 lebte weiter, flog weiter, im reflektierten Himmel.

Wenn die beiden Prozessaufrufe ihre erste Aufgabe ungefähr zur gleichen Zeit ausführen, hat der erste Aufruf jetzt Zeile 4 in seinem Speicher und ist bereit, den Besitz von Mutex von Datei B zu erwerben, während der zweite Aufruf jetzt Zeile 3 in seinem Speicher hat und ebenfalls bereit ist, den Besitz der Mutex von Datei B zu erwerben. Da jeder Aufruf als nächstes auf Datei B zugreifen möchte, liefern sie sich ein Wettrennen, wer den Mutex zuerst übernimmt. Der Gewinner schreibt seine Zeile zuerst in Datei B (und freut sich ungemein). 

Es ist allerdings nicht klar, welcher Prozess gewinnen wird. Das kann das Ganze zwar etwas spannender machen, wenn die Reihenfolge der Ausgabe keine Rolle spielt, weil sie zu einer stärkeren gleichzeitigen Nutzung der Ressourcen führt, wenn aber (wie in der Poesie) das Gegenteil der Fall ist, können die Folgen eines Bugs, der als „Race Condition“ bekannt ist, katastrophal ausfallen.Wenn also in unserem Beispiel der zweite Aufruf das Rennen macht, liest sichEmptyFire.txt am Ende wie Kauderwelsch:

EmptyFire.txt

1 lebte weiter, flog weiter, im reflektierten Himmel.
2 ich war der Fleck aus aschfahlem Flaum und

Aber wie lässt sich dieses mögliche Textdurcheinander beheben? Natürlich, indem der Entwickler den Prozess mit der Voraussetzung versieht, die Mutexe für jede Ressource gleichzeitig zu halten ... womit wir wieder beim ersten Design wären, bei dem es zu Deadlocks kommen kann.Wie der Titel dieses Posts bereits verrät, wird der Entwickler zu Dante auf einer Reise durch die konzentrischen, kreisförmigen, qualvollen Warteschleifen im Inneren der Maschine.

Vermeidung von Deadlocks

Die Jagd auf Deadlock-Bugs kann sich auf alle Fälle wie ein Teufelskreis anfühlen . Was können Entwickler also tun, um sich dieser Herausforderung zu stellen? Es gibt zahlreiche Workarounds und Lösungen für Deadlocks, die für Entwickler, die mit Mutexen arbeiten, unterschiedlich praktikabel sind.   

Die naheliegendste Lösung für Deadlocks ist die Rückkehr zum einfachsten Design: ein einziger Mutex, der den Zugriff auf beide Elemente schützt. Dies schränkt natürlich die Möglichkeit ein, Objekte gleichzeitig zu verwenden, was wiederum zu dem Problem mit den ungenutzten Ressourcen führt. Wenn Entwicklerteams also jedes Mal bei diesen Probleme den Weg der einfachsten Lösung nehmen, führt das zu einer endlosen Kafka-trifft-auf-Sisyphus-Schleife: 

1. Wir implementieren einen einzigen Mutex für den gleichzeitigen Zugriff auf zwei Ressourcen (wie FileA.txt und FileB.txt).

2. Da dies zu ungenutzten Ressourcen und damit zu Ineffizienzen führen würde, implementieren wir stattdessen ein Mutex für jede Ressource.

3. Oh nein, jetzt kommt es zu einem Deadlock. Dies wollen wir vermeiden, indem wir einen einzigen Mutex für den gleichzeitigen Zugriff auf beide Ressourcen implementieren.

4. Und das Ganze geht bis in alle Ewigkeit wieder von vorne los.

Um diese Schleife zu vermeiden, können Entwickler die Reihenfolge, in der der Besitz der Mutexe erworben wird, sorgfältig auswählen (was besonders wichtig ist, um zirkuläres Warten zu vermeiden). Vielleicht wird zum Beispiel FileA.txt immer vor FileB.txt benötigt. Wenn das so ist, können Sie diese Reihenfolge durch die adäquate Platzierung von Mutexen in Ihrem Programm erzwingen. 

Die genaue Reihenfolge der Sperrenübernahme spielt keine Rolle, solange sie im gesamten System konsistent ist. Daher können Entwickler den cleveren Trick anwenden, eine beliebige Reihenfolge anzugeben, z. B. die alphabetische Reihenfolge. Wenn mehr als ein Mutex gleichzeitig benötigt wird, werden sie immer in der angegebenen Reihenfolge angefordert, z. B. Mutex A -> Mutex B -> Mutex C. Die alphabetische Reihenfolge ist für die Prozesse unbedeutend, aber sie vermeidet zirkuläres Warten.

Wenn Entwickler Programme entwerfen und erweitern, fügen sie Mutexe in das Programm ein, um den Bedarf an nebenläufigen Ressourcen zu berücksichtigen. Aber damit ihnen das gelingt, müssen sie sich bewusst sein, welche Ressourcen durch welche Mutexe geschützt werden sollten. Ein noch größerer kognitiver Aufwand besteht darin, sich bewusst zu werden, wann Sperren übernommen und freigegeben werden müssen. Der Zugriff auf Ressourcen muss nicht nur sicher, sondern auch konsistent im Hinblick auf die Gesamtvorgänge sein, die ein Programm durchführt – denn selbst ein „sicherer“ Zugriff auf Daten kann zu inkonsistenten Ergebnissen führen. Außerdem müssen Entwickler wissen, welche Teile des Systems tatsächlich sperren, denn Sperren können Auswirkungen nach außen haben und so können zwei Komponenten, die nur indirekt miteinander verbunden sind, trotzdem kollidieren.

In einer Welt mit unordentlichem Spaghetti-Code, der in einer dicken Komplexitätssauce ertrinkt, ist die Ordnungsoption daher nicht so einfach zu implementieren, da sie im Grunde davon abhängt, dass sich die Entwickler des gesamten Kontrollflusses des Programms bewusst sind, um Mutexe richtig zu platzieren. Das menschliche Gehirn ist für eine solche Aufgabe aber nicht gedacht, vor allem nicht bei Systemen, die sich im Laufe der Zeit ändern, wenn neue Funktionen hinzugefügt werden. 

Eine andere Möglichkeit ist also die Deadlock-Erkennung. Ein Prozess kann seine Arbeit zurückfahren, seine Zugriffsrechte für einen anderen Prozess freigeben und diese Rechte zurückfordern, sobald der andere Prozess beendet ist. Zum Beispiel könnte /bin/texttransform die Löschung des Textes in FileA.txt verwerfen, die Zugriffsrechte an die andere Prozessinstanz freigeben und versuchen, FileA.txt erneut anzufordern, sobald der andere Prozess damit fertig ist (was viele Datenbanksysteme tun, wenn sie zwei Transaktionen erkennen, die gleichzeitig exklusiven Zugriff auf Daten benötigen).

 Zu den bestehenden Ansätzen zur Erkennung von Deadlocks gehören die Datenflussanalyse (einschließlich Ressourcenzuweisungsdiagramme und Warten-auf-Diagramme), Modellprüfung und typbasierte Ansätze . Leider sind die Ergebnisse in der Regel durchwachsen, und die Implementierung kann exorbitante Kosten verursachen, was oft zu Vorbehalten bezüglich des Einsatzes in der Produktivumgebung führt. Linux bietet zum Beispiel die lockdep-Option, die einen Algorithmus aktiviert, der einige (aber nicht alle) Deadlocks erkennt. Dadurch dauert aber auch das Sperren deutlich länger, weshalb nur wenige diese Option in Produktivumgebungen aktivieren. 

Es ist extrem schwierig, vor Beginn der Arbeit zu wissen, ob ein Deadlock jemals auftreten könnte, ohne eine ausgeklügelte Analyse des gesamten Programms durchzuführen – was automatisierte Lösungen schwierig macht. Schon das Erkennen von Deadlocks, die tatsächlich auftreten, ist schwierig! 

Noch verwirrender ist, dass auch ein einzelner Prozess (oder ein Single-Thread-Programm) in einen Deadlock geraten kann. Wenn der Prozess das Recht zur Nutzung einer Ressource erwirbt, aber (aufgrund eines Bugs) vergisst, dass er dies getan hat, wartet er bei einem erneuten Versuch auf die Freigabe der Ressource durch sich selbst, was natürlich nie passieren wird. Das ist so, als wenn Sie nicht los könnten, weil Sie Ihre Sonnenbrille nicht finden können, die bereits auf Ihrem Kopf sitzt. 

Was passiert zum Beispiel, wenn texttransform aufgefordert wird, eine Zeile aus der Quelldatei an die Zieldatei weiterzugeben – und beide Dateien sind FileA.txt? In diesem Fall versucht der Prozess zweimal, den Mutex für FileA.txt zu erwerben: einmal, weil FileA.txt die Quelldatei ist, die gelesen und gekürzt werden soll, und ein weiteres Mal, weil sie die Zieldatei ist, an die etwas angehängt werden soll. Der Prozess gerät in einen Deadlock, wenn er versucht, den Mutex ein zweites Mal zu erwerben. Da er den Mutex bereits besitzt, wartet er für die Freigabe auf sich selbst.

Eine besondere Art von Mutex, der rekursive Mutex, ermöglicht es einem einzelnen Prozess (oder Thread), den Mutex mehr als einmal zu erwerben. Von seiner Verwendung wird jedoch oft abgeraten, da sich dahinter Fehler bei der Sperrenübernahme verbergen können – wie zu vergessen, den Mutex freizugeben. Wenn in unserem Beispiel eine Kopie von /bin/texttransform vergisst, die Verwendung von FileA.txt freizugeben, nachdem sie damit fertig ist, wird der anderen Prozessinstanz die Datei vorenthalten und er bleibt stecken, obwohl die Datei von niemandem verwendet wird.

Andererseits gibt es auch den relativ häufigen Fehler, dass die Rechte gar nicht erst erworben werden. Ein Prozess könnte eine Ressource verwenden, ohne zuvor die Rechte übernommen zu haben, was zu merkwürdigen, obskuren Fehlern führt. Vergessen Sie nicht, dass Mutexe eher wie Ampeln sind. Ein Entwickler kann sich eine Mutex-Konvention für sein Programm ausdenken, aber Programme, die von anderen Entwicklern geschrieben werden, werden sich nicht daran halten (weil sie nicht einmal davon wissen). Das Versäumnis, die Rechte überhaupt zu übernehmen, ist also wie das Überfahren einer roten Ampel.

In unserem Beispiel sieht dieser Fehler so aus, als ob ein Programm eines anderen Entwicklers (textyeet zu unserem texttransform) vergisst, das Recht an FileA.txt zu erwerben, aber trotzdem damit beginnt, Vorgänge auf dieser Datei auszuführen. Wenn unser Programm dann versuchen würde, FileA.txt zu verwenden, nachdem es die Rechte daran übernommen hat, käme es mit textyeet zu einer Kollision wie bei zwei Köche in einer Küche. Dies würde erhebliche Sicherheitsbedenken für das System nach sich ziehen!Wir sind uns sicher alle einig, dass wir verteilte Systeme ohne Sicherheitsrisiken betreiben wollen.  

Niemand hat (bis jetzt) eine einfache allgemeine Lösung für Deadlock-Bugs gefunden. Selbst die zuverlässige Erkennung eines Deadlocks ist immer noch ein ungelöstes Problem. Systeme können oft einfach nicht vorankommen, ohne dass es zu Fehlern kommt, sodass die Bediener eingreifen und nachforschen müssen. Ähnlich wie beim Stillstandproblem ist es möglich zu beweisen, dass es bei manchen Programmen zum Deadlock kommen wird – oder eben nicht. Einen pauschalen Beweis für beliebige Programme gibt es allerdings nicht.

Natürlich ist es nicht so, dass es bei Programmen, die keine Mutexe verwenden, per se nicht zu Deadlocks kommt (aber sie sind vielleicht auch nicht so performant). Man kann zwar beweisen, dass einige Verwendungen von Mutexen frei von Deadlocks sind, aber es ist äußerst schwierig, dies auf echte Programme (wie solche, die in verteilten Systemen laufen) zu übertragen.

Mutex-Alternativen

Ehrlich gesagt, ist es wahrscheinlich am besten, wenn Sie das Problem jemand anderem überlassen – ziehen Sie einfach ein anderes System hinzu, das die Gleichzeitigkeit für Sie handhabt. Grundsätzlich ist es bei allem, bei dem es zu nebenläufigen Schreibvorgängen (oder Lesevorgängen) kommen kann – wie bei Datenbanken, Loadbalancern, Caches, Stream-Processing-Frameworks, Message-Bussen, Autoscaling und vielem mehr – ratsam, die Koordinierung der Sperren spezialisierten Anbietern zu überlassen, anstatt sich selbst damit abzumühen.(Wenn Sie selbst zu diesen spezialisierten Anbietern gehören, haben Sie wirklich keine andere Wahl, als über diese schwierigen Probleme nachzudenken).

Verwenden Sie zum Beispiel Apache Kafka oder Kinesis, anstatt Ihre eigene nebenläufige Warteschleife zu schreiben. In unserem texttransform-Beispiel mit PaleFire.txt konnte der Entwickler Poesie in einer Datenbank speichern und eine Transaktion verwenden, um Text von einem Datensatz auf einen anderen Datensatz zu übertragen.Anstatt dass sich der Entwickler darüber Gedanken machen musste, sorgte die Datenbank für die Sperren und kümmerte sich um alle Nebenläufigkeiten.

Wenn ein Entwickler Probleme mit Deadlocks hat, dann ist die Antwort wahrscheinlich nicht, dass er etwas ebenso komplexem nachgehen sollte, wie CPU-Atomwissenschaft (z. B. fetch-and-add oder compare-and-swap), lock-free programming oder read-copy-update.Diese führen zu noch mehr Komplexität und sind noch schwieriger zu bewerkstelligen als die oben beschriebene Festlegung der Sperrreihenfolge. 

Fazit

Deadlock-Bugs sind ein faszinierendes und zugleich schauriges Symptom komplexer Softwaresysteme. Wenn sie auftreten, sind sie schwer zu debuggen und in der Regel noch schwieriger zu beheben. Je parallelisierter und nebenläufiger unsere Software-Ökosysteme werden, desto wahrscheinlicher ist es, dass Deadlock-Bugs nach und nach auftauchen und an unseren Gehirnen nagen (oder zumindest unsere kognitive Energie in Anspruch nehmen).

Um die Geißelhaft eines Deadlocks zu überleben, ist es am besten, das Thema Nebenläufigkeit wenn möglich ganz auszulagern. Wenn Sie aber dennoch Ihre eigene Nebenläufigkeit entwickeln müssen, verwenden Sie eine beliebige und konsistente Reihenfolge der Mutexe (alphabetisch, numerisch oder eine andere konsistent angewandte Gesamtreihenfolge). Alles gleichzeitig zu sperren, funktioniert nicht bei einem System, das schnell und skalierbar sein muss (im Grunde also bei den meisten verteilten Systemen). Wenn Sie ein verteiltes System betreiben, das schnell und skalierbar sein soll, und Nebenläufigkeit ein Kernstück des Wertversprechens an Ihre Kunden ist, dann ist trotz der zweifelhaften Effizienz auch ratsam, gewisse Anstrengungen in die Deadlock-Erkennung zu stecken.