Know-how: Von Deadlocks und Livelocks

In der vergangenen Woche habe ich unter der Headline Dem Speicherfehler auf der Spur: Intel Inspector XE 2011 bereits auf häufige Code-Probleme bei der Parallel-Programmierung und das sehr gute und aktuelle Fehleranalyse-Tool des Intel Inspector XE 2011 hingewiesen.

Gestern habe ich von Bernhard B. aus Ottweiler/Saar eine E-Mail erhalten mit der Bitte, die typischen Programmierfehler wie Deadlocks und Data Races doch einmal etwas ausführlicher zusammenzufassen. Das tue ich gerne im Rahmen einer kleinen Serie. Den Anfang machen die Deadlocks und Livelocks.

Zunächst eine kleine Analogie für alle, die die Begriffe gar nicht zuordnen können:

Zwei Männer vom Typ „Wrestling-Profi“  begegnen sich in einer schäbigen Kneipe auf dem engen Gang zum Klo. Der eine will rein, der andere raus. Der Gang bietet aber nur Platz für einen. Auge in Auge stehen sie sich gegenüber, keiner weicht zurück. Das kann Stunden dauern und ist ein klassischer Deadlock.

Auf dem Gang zum Mädchenklo der gleichen Kneipe begegnen sich die beiden Freundinnen. Die können sich aber über die Ausweichmanöver nicht einigen. Beide treten dummerweise gleichzeitig einen Schritt zurück, um die jeweils andere vorbeizulassen. Die Einladung nehmen aber beide an und treten wieder einen Schritt vor. Und so weiter. Ist auch blöd, weil auch hier – trotz ständiger Bewegung – eine Blockierung eintritt, die man als Livelock bezeichnet.

So weit zu den Kneipengeschichten. Etwas technischer, aber ebenso anschaulich widmen sich die Tutorials des Intel Inspector XE 2011 diesem Thema. Diese demonstrieren nicht nur die weitreichenden Analyse- und Fixing-Fähigkeiten des Tools, sondern schildern die Einsatzszenarien für Deadlocks und Data Races auch sehr praxisnah, teilweise in einsteigertauglichen Schritt-für Schritt-Workshops.

Zudem darf ich Ihnen das Buch „Multicore Programmierung“ von Shameem Ahjter und Jason Roberts empfehlen, das sich ebenfalls typischen Stolpersteinen bei der Code-Generierung widmet. Das Buch ist zwar schon fast 3 Jahre alt, aber die Probleme um Deadlocks, Livelocks und Data Races sind ja auch nicht erst gestern entstanden. Die Autoren behandeln diese Themen und adäquate Lösungen auf rund 50 Seiten.

Jetzt aber ein paar ausführliche Bemerkungen zu Deadlocks und Livelocks

Deadlocks: Hierbei warten zwei oder mehr Prozesse (Threads) auf Ereignisse, die wiederum selbst einem der Prozesse zugeordnet sind. Daraus ergibt sich – vereinfacht ausgedrückt – eine Endlosschleife, weil keiner der Prozesse abgeschlossen werden kann. Diese exklusive Inanspruchnahme bestimmter Ressourcen bedeutet auch „Sperre“.

Ein Deadlock kann nur auftreten, wenn alle der folgenden Bedingungen erfüllt sind:

• der Zugriff auf jede Ressource ist exklusiv
• ein Thread hält eine Ressource, während ein anderer sie anfordert
• kein Thread gibt die erworbene Ressource auf
• zyklisch versuchen alle beteiligen Threads die Ressource zu erwerben, die aber nicht freigegeben wird

Deadlocks lassen sich vermeiden, indem beispielsweise Ressourcen repliziert werden, so dass jeder Thread darauf zugreifen kann. Das ist der einfachste Weg – wenn auch nicht immer möglich.

Ein zweite Möglichkeit besteh darin, die Threads zu priorisieren und den Zugriff sequentiell zu regeln. Dabei hängt die Reihenfolge von der Topologie ab: Beispielsweise werden in einer Kettenstruktur die Ressourcen in der Reihenfolge gesperrt, in der sie in der Liste erscheinen. Das ist bei sehr komplexen Code-Strukturen mitunter sehr kompliziert. In dem Zusammenhang sei auch auf den so genannten Bankieralgorithmus verwiesen.

Die dritte Möglichkeit: Sie programmieren die Threads so, dass diese im Falle eines konkurrierenden Anspruchs automatisch den Anspruch auf die Ressource aufgeben. Die Threads versuchen es dann zu einem späteren Zeitpunkt. Klingt einleuchtend und praktisch, kann aber automatisch zu einem neuen Problemfeld führen, den…

… Livelocks: Diese sind sozusagen die „dynamischen“ Deadlocks. Dabei verharren die Threads nicht, bis sie eine bestimmte Ressource erwerben, sondern bewegen sich bis zu einem bestimmten, angestrebten Ereignis in einer Dauerschleife. Dieses Ereignis tritt aber nicht ein, so dass der gestartete Prozess nicht abgeschlossen werden kann.

Verhindern lassen sich Livelocks über Zeitintervalle, die den Threads zugeordnet werden. Kann ein Prozess in der Zeit “x” nicht abgeschlossen werden, gibt er alle Ressourcen wieder frei und „stellt sich hinten an“. Das funktioniert gut, sofern alle Prozesse gleich gewichtet sind. Sind einzelne Threads sofort erforderlich, sollten Sie mit Prioritäten und festen Reihenfolgen für die Sperren arbeiten.

Am einfachten aber überlassen Sie die Arbeit dem Intel Inspector XE 2011. Er findet sowohl Deadlocks als auch Livelocks und hilft mit konkreten Tipps bei der Code-Optimierung. Denn in der Regel ist die gewählte Methode unwichtiger als das korrekte Ergebnis.