Multicore-Programmierung

Ohne Locks für Multicore-Systeme programmieren

| Autor / Redakteur: David Kalinsky * / Hendrik Härter

Beispiel 2: Lockfreie verknüpfte Liste

In Embedded-Software werden häufig Linked-Lists (verknüpfte Listen) zur Organisation größerer Sensordatenmengen und sonstiger Datenströme verwendet. Bei der Linked-List unten rechts sind die einzelnen Listenmitglieder als Rechteck dargestellt, jeweils mit einem Datenfeld und einem Zeiger zum nächsten Mitglied.

Beim lockfreien Programmieren lässt sich ein neues Mitglied einfach in eine Linked-List einfügen. Erst wird die gewünschte Listenposition für das neue Mitglied ermittelt und dann der Inhalt des neuen Mitglieds vorbereitet. Danach wird das neue Mitglied mittels einer einfachen CAS-Operation in die Liste eingefügt, wie nebenan dargestellt.

In dieser Situation überprüft CAS an einem bestehenden Listenmitglied den Zeiger zum nächsten Mitglied, um sicherzustellen, dass keine Manipulation stattgefunden hat, ehe CAS den Zeiger auf das neue Mitglied setzt. Manipulation bedeutet hier, dass bereits ein anderes Mitglied in diese Listenposition eingefügt wurde, während das andere neue Mitglied zum Einfügen vorbereitet wurde. In diesem Fall wären alle Vorbereitungen zum Einfügen des neuen Mitgliedes noch mal von vorne zu durchlaufen.

Auf den ersten Blick scheint es genauso einfach, das bestehende Listenmitglied B zu löschen – einfach mit CAS das Zeigerfeld des vorherigen Mitglieds A auf den Zeiger des nachfolgenden Mitglieds C setzen, so müsste es gehen. Hier kann jedoch eine „Race Condition“ (Wettlaufsituation) auftreten:

Parallel zum Löschen von Mitglied B könnte eine Operation „Mitglied Z hinter Mitglied B einfügen“ ausgeführt werden. Dadurch wäre kein Zugriff auf Mitglied Z möglich.

Hier zeigt sich, dass CAS kein Allheilmittel ist. Entwickler von lockfreien Programmen müssen selbst nachhelfen und Lösungen für Probleme wie z. B. Race Conditions finden. Abhilfe ließe sich wie folgt schaffen: Ehe das Programm „Mitglied B löschen“ CAS aufruft, sollte es absichtlich eine bestimmte Lösch-Markierung im Zeigerfeld von Mitglied B setzen und so eine parallele CAS-Operation in einem „Einfügen“-Aufruf verhindern, der Mitglied B involviert. In diesem Fall würde die „Einfügen“-Operation auf einen späteren Versuch verschoben, bei dem das neue Listenmitglied dann richtig eingefügt wird.

So lässt sich eine Linked-List effizient und lockfrei manipulieren. Doch auch hier sind wir einer Logik begegnet, die komplizierter als ihr lockbasiertes Pendant und somit schwerer zu verstehen und zu debuggen ist. Und auch hier ist die Ausführungszeit wegen des Loop-Charakters nicht kontrollierbar.

Auf der nächsten Seite: das Fazit

Kommentar zu diesem Artikel abgeben
Wenn ich auf "Artikel als PDF" gehe, kommen die Bilder groß nach dem Artikel (Seiten 5 und 6).  lesen
posted am 20.09.2011 um 08:50 von SLiebing

Ein toller Artikel, den ich mir gerne aufheben möchte. Leider sind die als Erklärung enthaltenen...  lesen
posted am 20.09.2011 um 08:09 von folco


Mitdiskutieren
copyright

Dieser Beitrag ist urheberrechtlich geschützt. Sie wollen ihn für Ihre Zwecke verwenden? Infos finden Sie unter www.mycontentfactory.de (ID: 28901070 / Software-Entwurf & Echtzeit-Design)