Software-Parallelisierung für Multicore-Prozessoren, Teil 2: Deadlocks

23.03.2020 Von Oliver Oey *

Anbieter zum Thema

MicroConsult Microelectronics Consulting & Training GmbH

Ein Deadlock ist ein Programmzustand, in dem sich einzelne Teile blockieren und verhindern, dass das Programm weiter abgearbeitet werden kann. Wie Sie Deadlocks vermeiden, zeigt Teil 2 dieser Multicore-Serie.

Deadlock bei konkurrierendem Zugriff
(Bild: emmtrix)

Bei der Programmierung der auch im Bereich der eingebetteten Systeme immer weiter verbreiteten Mehrkernprozessoren, gibt es einige Fallstricke, die bei rein sequentieller Programmierung nicht auftreten. Im ersten Teil dieser Artikelreihe wurden die so genannten ‚Race Conditions‘ beschrieben, die das Verhalten der Anwendung unvorhersehbar machen können. In diesem zweiten Teil der Reihe wird auf das Problem der Deadlocks eingegangen.

Ein Deadlock, auf Deutsch auch ‚Verklemmung‘ genannt, beschreibt einen Programmzustand, in dem sich einzelne Teile blockieren und verhindern, dass das Programm weiter abgearbeitet werden kann. Sie können entstehen, wenn auf gemeinsam genutzte Ressourcen in unterschiedlicher Reihenfolge zugegriffen wird.

Ein Beispiel ist im Bild dargestellt. Neben den beiden Kernen 1 und 2 sind zwei gemeinsam genutzte Ressourcen 1 und 2 vorhanden. Im ersten Schritt fordern die beiden Kerne exklusiven Zugriff auf eine der beiden Ressourcen an: Kern 1 möchte Ressource 1 verwenden, Kern 2 die Ressource 2. Der exklusive Zugriff wird gewährt, da es in beiden Fällen keine konkurrierenden Anfragen gibt. Im zweiten Schritt benötigen beide Kerne zusätzlich die jeweils andere Ressource. Da hier nur exklusiver Zugriff möglich ist, beginnen Kern 1 und Kern 2 auf die gegenseitige Freigabe der Ressourcen zu warten. Das Ergebnis ist ein Deadlock, der die Abarbeitung des Programms blockiert.

Ähnlich wie bei den ‚Race Conditions‘ aus dem ersten Teil dieser Artikelreihe können kleine Änderungen am Timing der einzelnen Anfragen zu einem anderen Verhalten führen. Im beschriebenen Beispiel wäre dann eine Situation denkbar, bei der Kern 1 Zugriff auf beide Ressourcen bekommt, bevor Kern 2 exklusiven Zugriff auf Ressource 2 erhält. Der Deadlock tritt also nicht immer auf und man hat ein unbestimmbares Verhalten, das die Fehlerfindung erschwert.

Kann man Deadlocks überhaupt auflösen?

Ohne weitere Maßnahmen können Deadlocks nicht von den beteiligten Komponenten aufgelöst werden. Wird ein Deadlock erkannt, was durch einen Algorithmus geschehen kann, der die Ressourcenzugriffe überwacht, kann ein weiterer Prozess dafür sorgen, dass entweder die konkurrierenden Prozesse beendet werden oder die Ressourcen nach einem vorgegebenen System wieder freigegeben werden.

Dabei sollte darauf geachtet werden, dass nur eine Maßnahme zur gleichen Zeit greifen kann, um den Fall eines ‚Livelocks‘ zu verhindern. Dieser kann entstehen, wenn die Zugriffe auf die Ressourcen zwar durch einen weiteren Prozess abwechselnd vergeben werden, das Programm aber dennoch nicht weiter abgearbeitet werden kann, da ein Kern niemals alle benötigten Ressourcen zur gleichen Zeit bekommt.

Wie kann man Deadlocks verhindern?

In der Regel ist es besser, ein System bereits so zu entwerfen, dass Deadlocks gar nicht erst auftreten können. Gängige Methoden sind dabei:

Entfernen von exklusiven Zugriffsmechanismen. Dies kann beispielsweise durch einen Puffer oder eine Warteschlange realisiert werden, die alle Zugriffe auf die Ressource nacheinander abarbeitet.

Vorausschauendes Planen von Zugriffen auf gemeinsame Ressourcen, indem Kerne immer alle Ressourcen auf einmal anfordern, die sie für die aktuelle Verarbeitung benötigen. Nur, wenn alle verfügbar sind, wird der Zugriff gewährt.

Prioritäten vergeben. Fordert ein Kern mit höherer Priorität den Zugriff an, wird dem aktuellen Kern, falls möglich, der Zugriff entzogen und dem anderen Kern gewährt.

Reihenfolge von Zugriffen auf Ressourcen klar festlegen. Erfolgen Zugriffe auf verschiedene Ressourcen immer in der gleichen Reihenfolge, können die problematischen wechselseitigen Zugriffe wie im besprochenen Beispiel verhindert werden.

Durch Einsatz von automatisierten Parallelisierungslösungen wie emmtrix Parallel Studio können Deadlocks gänzlich umgangen werden. Beim automatischen ‚Scheduling‘ werden alle Tasks der Anwendung über die Zeit auf die verschiedenen Kerne verteilt. Dabei werden Zugriffe auf gemeinsame Ressourcen mitbetrachtet und durch Einbeziehung des gesamten zeitlichen Verhaltens werden konkurrierende Zugriffe auf Ressourcen gänzlich verhindert.

Im dritten und letzten Teil dieser Reihe (ELEKTRONIKPRAXIS-Ausgabe 8/2020) geht es schließlich um die Performanz-Abschätzung von parallelen Anwendungen.