Multicore-Programmierung

Ohne Locks für Multicore-Systeme programmieren

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

Bei der Programmierung paralleler Threads für Multicore Systeme identifizieren Softwareentwickler erst kritische Codeabschnitte und versehen sie mit einem Zugriffsschutz, einem sogenannten Lock.
Bei der Programmierung paralleler Threads für Multicore Systeme identifizieren Softwareentwickler erst kritische Codeabschnitte und versehen sie mit einem Zugriffsschutz, einem sogenannten Lock. ( Intel)

Viele Multicore-SOCs und auch einige Betriebssysteme bieten Möglichkeiten zur lockfreien Programmierung. Die Softwareentwicklung wird dadurch jedoch umständlicher als mit herkömmlichen Methoden.

Wenn sich Programmierer mit Multicore-SOCs und Multicore-Betriebssystemen beschäftigen, stellen sie oft fest, dass sich herkömmliche Multitasking-Designansätze in einer Multicore-Umgebung schwer umsetzen lassen. Mehrfach-Tasks warten oft lange auf gesperrte Locks. Dies beeinträchtigt die Parallelität, verlängert die Latenzzeiten und schmälert die Vorteile der Hardware.

Lockfreie Programmierung ist kein Allheilmittel, doch bei effizienter Anwendung birgt sie erhebliche Performance-Vorteile. Meist wird sie für Programmteile mit komplexen, tief verschachtelten und häufig ausgeführten Schleifen eingesetzt.

Die beste Art, lockfrei zu programmieren, besteht darin, die Software in große und unabhängige Codeblöcke zu unterteilen. Diese Blöcke können dann über lange Zeit parallel ablaufen, meist auf verschiedenen Kernen. Da keine Dateninteraktion stattfindet, wären hier keine Locks erforderlich. Dieses Vorgehen lässt sich jedoch nicht immer umsetzen.

Dateninteraktionen durch Compare-and-Swap steuern

Wenn Dateninteraktion unvermeidlich ist, lassen sich einfachere Interaktionen zwischen parallelen Codeblöcken über die lockfreie CAS-Operation steuern (atomisches Compare And Swap). Diese Operation ist in der Hardware diverser Multicore-SOCs und vieler Betriebssysteme verfügbar. Ihr Einsatz wird anhand mehrerer Beispiele erläutert.

Selbst in Single-CPU-Multitaskingumgebungen sind Lock-Mechanismen problematisch. In Multicore-Umgebungen kommen noch mehr Probleme hinzu, einmal durch den Parallelismus und zum anderen, weil das Task-Scheduling in Multicore-Betriebssystemen ungeordneter abläuft. Die häufigsten Probleme mit diesen Locks sind nachstehend beschrieben.

  • Deadlock

Als Deadlock bezeichnet man eine Situation, in der zwei (oder mehr) Tasks darauf warten, dass jeweils der andere Task eine Ressource freigibt. Da beide Tasks warten, werden keine Ressourcen freigegeben und keine Tasks mehr ausgeführt. In einem Multicore-System können Deadlock-Tasks auch in verschiedenen Kernen auftreten.

  • Lockout

Bei einem Lockout sperrt ein Task ein Lock und nutzt die Ressource, die von dem Lock bewacht wird. Jedoch gibt er anschließend das Lock nicht frei. Einem anderen (oder auch demselben) Task ist es danach nicht mehr möglich, das Lock zu sperren. Versucht ein anderer Task es trotzdem, wird der Applikationscode quasi lahm gelegt

  • Prioritätsinversion

Bei einer Prioritätsinversion hindert ein Task mit niedriger Priorität (nP) einen Task mit hoher Priorität (hP) an der Ausführung. Diese Situation tritt auf, wenn ein nP-Task ein Lock sperrt und einen hp-Task (der vielleicht gleichzeitig auf einem anderen Kern läuft) dasselbe Lock sperren will. Die hp-Task muss so lange warten, bis der np-Task das Lock freigibt. Ein langer Sperr- bzw. Wartevorgang kann die Performance des hp-Tasks massiv beeinträchtigen.

  • Performance-Einbußen

Betriebssysteme weisen den meisten Locks Task-Warteschlangen zu. Bei jeder Operation an einem Lock ist die jeweilige Task-Warteschlange zu behandeln, was oft viel Zeit kostet. Außerdem können Tasks in der Schlange hängen bleiben, wenn sie versuchen, ein Lock zu sperren, das gerade verwendet wird. In einer Multicore-Umgebung müssen oft mehrere Tasks auf mehreren Kernen warten.

Lesen Sie weiter: CAS prüft und aktualisiert kritische Variablen und Pointer

CAS prüft und aktualisiert kritische Variablen und Pointer

Das Code-Snippet oben zeigt eine CAS-Operation, dargestellt in einer C-ähnlichen Sprache. CAS vergleicht den aktuellen Inhalt von "var" mit einem "expected"-Wert. Ist der Wert wie erwartet (expected), wird "var" aktualisiert und damit "new". Ansonsten wird ‘var’ nicht aktualisiert. All dies erfolgt in einer einzigen, kontinuierlichen Operation.

Bei der Entwicklung von lockfreiem Code wird zuerst der Originalwert einer Variable (oder eines Zeigers) in "expected" kopiert. Dann wird durch einen weiteren Kopiervorgang in einer (möglicherweise langen und komplexen) Kalkulation ein "new"-Wert für die Variable erzeugt. Während der Verarbeitung hat aber vielleicht ein anderer Task – eventuell auf einem anderen Kern – den Originalwert der Variable schon geändert. Die Variable soll aber nur dann mit dem "new"-Wert aktualisiert werden, wenn sie zwischenzeitlich nicht durch einen anderen Task geändert wurde. CAS nimmt eine gemeinsame Überprüfung und Aktualisierung vor, ohne dass ein Lock-Konstrukt nötig ist.

Wenn CAS erkennt, dass die Variable nicht mehr den Original- oder "expected"-Wert hat, entscheidet die Applikationssoftware über die nächsten Schritte. Die Varianle wurde nicht mit dem "new"-Wert aktualisiert. Hier wird oft die gesamte Kalkulation wiederholt, diesmal basierend auf einem erneuten Auslesen des aktuellen Wertes der Variable. Dann wird wieder die CAS-Operation aufgerufen, um sicherzustellen, dass nun kein anderer Task den Wert verändert hat.

Beispiel 1: Erhöhen eines Zählwerts

Zunächst ein einfaches Beispiel: Zwei Tasks erhöhen beide einen Wert mittels des „++“-Operators aus der C-Sprache.

In einer Multicore-Umgebung können beide Tasks gleichzeitig aktiv werden, ob sie nun die gleiche Priorität haben oder nicht. Manchmal werden die ++-Operationen in beiden Tasks zur gleichen Zeit ausgeführt. Dadurch wird der im Zähler (counter) gespeicherte Wert beschädigt, oder es geht z. B. eine Erhöhung verloren.

Dies lässt sich umgehen, indem ein Lock verwendet wird, das die ++-Operation als kritische Sektion schützt. Wir wollen doch aber lockfrei programmieren! Der Beispielcode oben rechts zeigt, wie sich das gleiche Ziel lockfrei erreichen lässt

Dabei ist es unerheblich, ob die Operation „+1“ atomisch ist. Wichtig ist nur, ob eine andere Task die Variable "counter" während der Kalkulation manipuliert hat. Die CAS-Operation überprüft dies und aktualisiert "counter" nur, wenn keine Manipulation stattgefunden hat. Sonst wird dieser Code wieder an den Anfang zurückgeführt, und es findet ein weiterer Erhöhungsvorgang statt.

Dieser Code ist viel komplexer als sein lockbasiertes Gegenstück. Damit ist es auch schwieriger, ihn zu verstehen und zu debuggen. Zum anderen ist aufgrund des Schleifen-Verhaltens in diesem Code die Ausführungszeit nicht kontrollierbar (wenn immer wieder Manipulationen erkannt werden). Für Systeme mit harter Echtzeit eignet sich diese Programmiermethode oft nicht.

In manchen Applikationen lässt sich die Anzahl der Schleifeniterationen und damit die Worst-Case-Ausführungszeit begrenzen. Hierfür ist ggf. eine Wahrscheinlichkeitsberechnung erforderlich, die belegt, dass die maximale Anzahl der Iterationen möglichst selten erreicht wird.

Lesen Sie weiter: Beispiel 2 - Lockfreie verknüpfte Liste und das Fazit

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

Fazit: Lock-frei ist nicht gleichbedeutend mit Wait-frei

Wie sich gezeigt hat, kann auch eine lockfrei programmierte Applikation erhebliches Task- und Core-Waiting bedeuten. Wie in den Beispielen gezeigt, handelt es sich dabei meist um Busy-Waiting, wobei die Applikationssoftware weiter ausgeführt wird (und im „Running“-Zustand bleibt), während die nächste CAS-Operation vorbereitet wird.

Vielleicht haben manche erwartet, dass lockfrei für “Wait-frei” steht. Aber „Wait-freie“ Programme sind noch viel komplizierter zu erstellen als lockfreie Programme.

Dennoch bietet die lockfreie Programmierung klare Vorteile gegenüber lockbasierten Programmiermethoden, z. B. hinsichtlich der Performance bzw. der Vermeidung von Deadlocks, Lockouts und Prioritätsinversion. Die Programmausführung an kritischen Codeabschnitten lässt sich unter Umständen um den Faktor 2 oder mehr beschleunigen.

Vielleicht gibt es in Ihrer Software eine Nische, in der das Beseitigen von Locks einen Leistungszuwachs auslösen könnte. Denkbar wäre der Einsatz lockfreier Programmierung auch beim Entwurf von Bibliothekssoftware. Das wäre eine gute Gelegenheit, sich an die lockfreie Programmierung zu wagen. // FG

Literatur:

[1] D. Kalinsky: Multicore’s Fourth Semaphore: Multiple Reader – Writer Lock, EETimes[2] F. Siebert: Facing the Challenges for Real-Time Software Development on Multi-Cores, Embedded Systems Conference 2010 Boston, Paper ESC-422.[3] A. Alexandrescu: Lock-Free Data Structures, Dr. Dobb’s, 1. Okt 2004.

* * David Kalinsky ... ist Berater, Trainer und Dozent für Echtzeit- und Embedded-Programmierung in Sunnyvale/Kalifornien (USA).

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 © 2017 - Vogel Business Media