Lock-Free Algorithmen

von zahlenfreak

Dieser Artikel nimmt am Artikelwettbewerb 2012/2013 teil.

Der Zugriff auf geteilte Datenstrukturen führt in Multithreading Systemen oft zu Problemen. Die Klassische Lösung setzt hier auf lockbasierte Algorithmen die zum Beispiel Mutexes verwenden. Dies kann allerdings zu unerwünschten Nebeneffekten wie z.B. Priority Inversion führen. Lock-Free Algorithmen vermeiden Mutexes und ähnliche Strukturen und damit auch viele Nachteile von Locks. Darüber hinaus können sie sogar zu gesteigerter Leistung führen. Dieses Paper befasst sich mit den Problemen Lock-basierter Algorithmen, zeigt, wie Lock-Free Algorithmen funktionieren und wie sie die Probleme Lock basierter Lösungen vermeiden.

Einführung

Sollen mehrere Threads schreibend oder lesend auf eine gemeinsame Datenstruktur zugreifen können, so müssen die Zugriffe untereinander synchronisiert werden. Andernfalls kann es zu fehlerhaften Daten oder zu Datenverlust kommen . Wollen zum Beispiel Thread A und Thread B einen neuen Knoten an eine einfach verkettete Liste anhängen kann folgendes Passieren: A hängt seinen Knoten an die Kette an und wird von B unterbrochen, bevor A den Tail-Pointer der Kette aktualisieren kann. Jetzt hängt B seinen Knoten an und aktualisiert Tail. Danach fährt A fort und überschreibt Tail, sodass er auf den von A angehängten Knoten zeigt. In der Kette hängt nun der von B angehängte Knoten, Tail zeigt aber auf den von A angehängten Knoten, die verkettete Liste ist also zerstört.

Klassischer Ansatz: Lock

Um solche Probleme zu vermeiden greift man klassischer Weise zu Lock-basierten Lösungen wie Mutexes oder Semaphoren . Dabei blockiert ein Thread den Zugriff auf eine Ressource bevor er darauf zugreift indem er einen Lock setzt. Nach dem Zugriff wird der Lock wieder gelöscht. Beim Setzen eines Locks muss dabei erst geprüft werden, ob dieser schon gesetzt ist. In diesem Fall schlägt der das Setzen fehl und der Thread muss warten, bis die entsprechende Ressource wieder freigegeben wird. Durch das erzwungene Warten bei Lock-basierten Algorithmen ergeben sich einige Probleme. Dazu zählen unter anderem: Deadlocks: Halten zwei Prozesse die Locks für jeweils eine Ressource und wollen zusätzelich auf die Ressource des jeweils anderen Threads zugreifen so blockieren sie sich gegenseitig und werden nie terminieren . Priority inversion: Blockiert ein niedrig priorer Thread eine Ressource auf die ein hochpriorer Thread zugreifen möchte so muss der hochpriore Thread warten bis der langsame Thread die Ressource wieder freigibt. Damit hat sich die Priorität der beiden Threads effektiv vertauscht . Mit Lock-Free Algorithmen lassen sich diese Probleme vermeiden .

Lock-Free Ansatz

Beim Typischen Ansatz von Lock-Free Algorithmen werden mit Hilfe der aktuellen Pointer einer Datenstruktur (z.B. Head/Tail bei einer einfach verketteten Liste) die neuen Pointer ermittelt. Das Zurückschreiben der neuen Pointerwerte geschieht dann allerdings nur, wenn sich die Pointer der Datenstruktur zwischenzeitlich nicht geändert haben (was passiert, wenn ein anderer Thread darauf zugegriffen hat).Viele Lock-Free Algorithmen verwenden dafür den atomaren Befehl CompareAndSwap (CAS), der den Inhalt einer angegebenen Speicherzelle mit einem gegebenen Wert vergleicht. Nur wenn der Wert der Speicherzelle und der gegebene Wert gleich sind wird ein dritter Wert in die Speicherzelle geschrieben. CAS gibt bei Erfolg TRUE, sonst FALSE zurück . Wird nun ein Thread A beim Anhängen eines Knotens von Thread B, der selbst einen Knoten anhängt, unterbrochen, so wird bei der Rückkehr zu Thread A die CAS-Anweisung zum Aktualisieren des Pointers fehlschlagen und Thread A seinen Versuch den Knoten anzuhängen wiederholen. Zwar kann so ein Thread von der Ausführung abgehalten werden, es ist aber garantiert dass das System als Ganzes Fortschritte machen wird (auch wenn dies durch einen anderen Thread bewirkt wird), wann immer ein Thread an einer Datenstruktur arbeitet . Es sei noch erwähnt, dass darüber hinaus noch Wait-Free Algorithmen exestieren. Diese garantieren zusätzlich auch den Fortschritt jedes einzelnen Threads, sollen hier aber nicht weiter betrachtet werden .

ABA-Problem

Zustandekommen des ABA-Problems bei dem im Listing gezeigten Algorithmus: a) Stack im Originalzustand; b) Thread 1 poppt und wird nach dem Anlegen der Pointer t und next unterbrochen; c) Thread 2 poppt zwei Knoten (A und B). Die Referenzen von Thread 1 auf diese Knoten bleiben bestehen; d) Thread 2 pusht A zurück auf den Stack; e) Thread 1 wird fortgesetzt und poppt A erfolgreich vom Stack womit der Stack zerstört wird;

Bei dem beschriebenen Ansatz ergibt sich jedoch ein Problem: Thread 1 liest eine Speicherstelle mit Wert A und wird dann von Thread 2 unterochen. Dieser ändert den Inhalt der Zelle nun von A auf B und wieder zurück auf A. Wird Thread 1 dann fortsetzt geht dieser davon aus, dass die Speicherstelle unverändert ist, obwohl der Wert geändert wurde. Sie enthält lediglich den gleichen Wert wie zuvor. Diese Konstallation nennt man ABA-Problem .

1: // Shared variables
2: Top:*NodeType; // Initially NULL
3:
4: Push(node:*NodeType) {
5:   repeat
6:   t = Top;
7:   node*.Next = t;
8: until CAS(&Top,t,node);
9: }
10:
11: Pop() : *NodeType {
12: repeat
13:   t = Top;
14:   if t=NULL then
15:     return NULL;
16:   end if
17:   next = t*.Next;
18: until CAS(&Top,t,next);
19: return t;
20: }

Listing: ABA-Anfälliger Stack nach Michael

An einem Stack kann das ABA-Problem gut beobachtet werden, es tritt prinzipiell aber auch in anderen Datenstrukturen auf und ist typisch für CAS-basierte Lock-Free Algorithmen. Die Push und Pop Funktionen eines ABA-anfälligen Lock- Free Stack werden in Abbildung 1 gezeigt. Soll ein Knoten gepoppt werden, so wird zuerst der Top-Pointer gelesen (Zeile 13), dann der Pointer auf den nächsten (nach dem Poppen obersten) Knoten ausgelesen (Zeile 17) und schließlich, falls Top nicht zwischenzeitlich von einem andern Thread geändert wurde, Top auf den neuen obersten Knoten gebogen (Zeile 18). Sollte sich Top zwischenzeitlich geändert haben wird der gesamte Pop-Vorgang erneut versucht. Der Push-vorgang läuft sehr ähnlich ab und sollte nun aus dem Listing ersichtlich werden . Abbildung 2 zeigt das Zustandekommen des ABA-Problems bei dem in Abbildung 1 gezeigten Algorithmus. Zu Beginn befinden sich die Knoten A, B und C auf dem Stack, Top zeigt auf A. Thread 1 versucht Knoten A zu poppen und wird unterbrochen, bevor der neue Top-Pointer zurückgeschrieben werden kann, jedoch nachdem der next-Pointer von A (dieser zeigt auf B) gelesen wurde. Thread 2 poppt nun erfolgreich zwei Knoten, also A und B und hängt daraufhin Knoten A wieder an. Wenn nun Thread 1 fortgesetzt wird, wird dessen CAS-Anweisung erfolgreich ausgeführt, da Top und auf den gleichen Knoten wie zuvor zeigt. Allerdings zeigt der next-Pointer von Thread 1 auf B, weshalb nun auch Top zu B hingebogen wird. B ist aber garnicht mehr teil des Stacks sondern in Besitz von Thread 2 oder leer. Der Knoten C und damit der gesamte restliche Stack gehen verloren, da auf C keine Referenz mehr existiert .

Lösungsansätze für das ABA-Problem

Für das ABA-Problem gibt es verschiedene Lösungsansätze, von denen hier einige vorgestellt werden sollen.

A next B next C next a) TOP b) c) t1 next1 A next B next C next TOP A next B next C next TOP t1 next1 d) A next B next C next TOP t1 next1 e) A next B next C next TOP t1 Abbildung 2. Zustandekommen des ABA-Problems bei dem in Abbildung 1 gezeigten Algorithmus: a) Stack im Originalzustand; b) Thread 1 poppt und wird nach dem Anlegen der Pointer t und next unterbrochen; c) Thread 2 poppt zwei Knoten (A und B). Die Referenzen von Thread 1 auf diese Knoten bleiben bestehen; d) Thread 2 pusht A zurück auf den Stack; e) Thread 1 wird fortgesetzt und poppt A erfolgreich vom Stack womit der Stack zerstört wird;

Modification-Counter

Eine Lösung für das ABA-Problem sind Modification-Counter. Dabei wird bei jedem schreibenden Zugriff auf einen Pointer ein zugehöriger Zähler um eins erhöht. Sollte sich der Wert des Zählers zwischen lesendem und schreibendem Zugriff auf den Pointer geändert haben, hat ein anderer Thread darauf zugegriffen. Selbst eine ABA-Änderung wird so erkannt, da sich der Wert des Modification-Counters geändert hat . Das Ändern des Modification-Counters muss dabei atomar mit dem schreiben des Pointers geschehen, was nur möglich ist, wenn auf beide mit nur einer CASAnweisung zugegriffen werden kann. DoubleCompareAndSwap (DCAS), das auf zwei Zellen gleichzeitig zugreifen könnte, wird von kaum einer Architektur unterstützt, weshalb hier andere Lösungen gefunden werden müssen . Auf 64 bit x86 Prozessoren lässt sich das 64 bit weite CAS der x64-Erweiterung als DCAS für 32 bit Programme nutzen. Für 64 bit Programme ist dies aber nicht anwendbar . Alternativ lässt sich auch der Modification-Counter mit dem Pointer in eine Zelle speichern. Dabei wird die bitweite des Pointers aber beschränkt und der adressierbare Bereich begrenzt . Bei genauerer Betrachtung wird das ABA-Problem durch Modification-Counter aber nicht verhindert, sondern nur extrem unwahrscheinlich. Läuft der Modification Counter über und erreicht wieder den ursprünglichen Wert, während ein Thread zwischen lesendem und schreibendem Zugriff unterbrochen wurde, so wird eine ABA-Änderung trotzdem nicht erkannt .

Reference Counter

Das ABA-Problem kann auch von der Seite des Speicher-Managements gesehen werden. Es tritt dann auf, wenn ein Knoten wiederverwendet wird, auf den noch eine Referenz in der Datanstruktur oder in einem Thread gehalten wird. Ein Knoten darf also erst dann wiederverwendet werden, wenn kein Pointer mehr auf ihn zeigt . Reference Counter wie sie von Valois sowie Michael und Scott verwendet werden nutzen dies aus, indem sie jedem Knoten einer einfach verketteten Liste einen Zähler zuordnen. Wird ein Pointer auf den Knoten angelegt, dann wird dieser Zähler um eins erhöht. Wird die Referenz auf den Knoten aufgegeben, so wird der Zähler um eins verringert. Steht der Zähler auf Null gibt es also keinen Pointer mehr auf diesen Knoten und er kann freigegeben werden. Zu beachten ist, dass auch die Pointer innerhalb der Datenstruktur gezählt werden, es kann also nur der letzte Pointer der Liste freigegeben werden . Diese Eigenschaft führt aber auch dazu, dass die Menge an benötigtigtem Speicher selbst bei beschränkter Listen-Länge unendlich ansteigen kann: Ein Thread A setzt eine Referenz auf einen Knoten in der Liste und wird dann unterbrochen. Daraufhin hängen andere Threads eine große Zahl von Knoten an und ab. Die Maximale Listenlänge wird so nie überschritten, allerdings können die abgehängten Knoten nicht freigegeben werden, da Thread A eine Referenz auf einen Knoten hält. Durch die einfach verkettete Liste besteht dann auch auf alle anderen Knoten eine Referenz .

Load linked, Store Conditional

Ein weiterer Weg das ABA-Problem zu umgehen ist die Verwendung von Load Linked (LL) und Store Conditional (SC). SC speichert dabei einen Wert nur, wenn seit dem Lesen der entsprechenden Speicherzelle mit LL nicht durch einen anderen Thread auf diese Zelle zugegriffen wurde. SC meldet ob der Speicherzugriff erfolgreich war (kein konkurrierender Zugriff seit LL) oder nicht. Verwendet man statt CAS nun SC und statt dem ursprünglichen Lesen des Pointers LL, dann wird das ABA-Problem per definitionem unmöglich . Allerdings wird LL und SC nur von wenigen Prozessorarchitekturen überhaupt unterstützt und die vorhandenen Implementierungen entsprechen nicht dem Ideal . Unter anderem Michael sowie Doherty et al. beschreiben Wege, LL und SC auf Basis von CAS nachzubauen. Zwar lassen sich damit Lock-Free Algorithmen implementieren, die ABA-immun sind, allerdings ist der Speicherbedarf für Software-LL/SC sehr groß, es muss im Voraus die Zahl der zugreifenden Threads bekannt sein, oder die Umsetzung ist realtiv aufwändig. Für Lock-Free Algorithmen auf Basis von LL und SC wäre eine bessere Hardwareunterstützung sehr hilfreich .

Memory Management

Werden für den Zugriff auf eine Datenstruktur Lock-Free Algorithmen verwendet, so muss auch das Speichermanagement lock-free implementiert werden. Andernfalls wäre zwar das An- und Abhängen von Knoten lock-free, das Allozieren und Freigeben dieses Speichers würde aber doch wieder zu den typischen Problemen lock-basierter Algorithmen führen. Sind die Betriebssystem-eigenen Algorithmen zum Speicher Anfordern und Freigeben lock-basiert, kann man auch selbst einen Pool von leeren Knoten vorhalten, auf den lock-free zugegriffen wird . Die Speicherverwaltung liefert auch einen weiteren Angriffspunkt gegen das ABA-Problem indem über die Speicherverwaltung sichergestellt wird, dass ein Knoten erst dann wieder verwendet wird, wenn kein Pointer mehr auf ihn zeigt .

Performance

Performanceanalysen wie sie Michael und Scott sowie Valois durchgeführt haben zeigen, dass Lock-Free Algorithmen nicht nur wichtige Probleme von Locks umgehen, sondern sich oft auch positiv auf die Performance auswirken. So zeigen Valois Ergebnisse, dass Lock-Free Algorithmen eine deutlich geringere Latenz von Enqueue- und Dequeueoperationen aufweisen als Lockbasierte. Je nach Algorithmus und Häufigkeit der Zugriffe beträgt die Latenz bis unter 50% derer von lockbasierten Algorithmen . Michael und Scotts Messungen zeigen, dass Lock-Free Algorithmen vor allem bei einer großen Zahl von Threads vorteilhaft sind. Sowohl viele Prozessoren, die auf die Datenstruktur zugreifen, als auch viele zugreifende Threads die auf einem Prozessor laufen begünstigen Lock-Free Algorithmen. Beachtet werden muss aber auch, dass dies nicht allgemeingültig ist. So hängt der tatsächliche Performancegewinn stark vom gewählten Algorithmus ab. Darüber hinaus kann bei einer kleinen Zahl von Threads ein Lockbasierter Algorithmus sogar leistungsfähiger sein .

Zusammenfassung

Bei multithreaded Programmierung muss für hohe Performance fast immer auch ein Weg gefunden werden, Daten zwischen den Threads effizient auszutauschen. Lock-Free-Algorithmen vermeiden dabei nicht nur die wichtigsten Probleme Lock-basierter Algorithmen wie Deadlocks und Priority Inversion, sondern können sogar den Datendurchsatz steigern und die Latenzen beim Zugriff auf Daten verringern. Durch den anhaltenden Trend zu immer mehr Prozessorkernen auch im Heimbereich wird auch hier multithreaded Programmierung immer wichtiger um die vorhandene Leistung nutzen zu können. Lock-Free Algorithmen dürften in Zukunft also weiter an Bedeutung gewinnen.