Lock-Free-Fortschritt garantiert

Anekdotisch habe ich festgestellt, dass viele Programmierer fälschlicherweise glauben, dass “lock-free” einfach “gleichzeitige Programmierung ohne Mutexe” bedeutet. Normalerweise gibt es auch ein damit zusammenhängendes Missverständnis, dass der Zweck des Schreibens von Lock-Free-Code die bessere gleichzeitige performance ist. Natürlich ist die korrekte Definition von Lock-Free eigentlich über Fortschrittsgarantien . Ein Lock-Free-Algorithmus garantiert, dass mindestens ein Thread unabhängig davon, was andere Threads tun, einen Vorwärtsfortschritt erzielen kann.

Dies bedeutet, dass ein blockierungsfreier Algorithmus niemals Code haben kann, bei dem ein Thread von einem anderen Thread abhängt, um fortzufahren. Beispielsweise kann Code ohne Sperre keine Situation haben, in der Thread A eine Markierung setzt, und dann Thread B weiterläuft, während er darauf wartet, dass Thread A die Markierung aufhebt. Code wie dieser implementiert im Grunde eine Sperre (oder was ich einen verkappten Mutex nennen würde).

Andere Fälle sind jedoch subtiler und es gibt Fälle, in denen ich ehrlich gesagt nicht wirklich sagen kann, ob ein Algorithmus als frei von Sperren gilt oder nicht, weil der Begriff “Fortschritt machen” mir manchmal subjektiv erscheint.

Ein solcher Fall ist in der (gut angesehenen, afaik) concurrencysbibliothek, liblfds . Ich habe die Implementierung einer Multi-Producer / Multi-Consumer beschränkten Warteschlange in liblfds untersucht – die Implementierung ist sehr einfach, aber ich kann nicht wirklich sagen, ob sie als frei von Sperren gelten sollte.

Der relevante Algorithmus ist in lfds711_queue_bmm_enqueue.c . Liblfds verwendet benutzerdefinierte Atomics und Speicherbarrieren, aber der Algorithmus ist einfach genug, um in einem Absatz oder so zu beschreiben.

Die Warteschlange selbst ist ein zusammenhängendes zusammenhängendes Array (Ringpuffer). Es gibt einen gemeinsamen read_index und write_index . Jeder Slot in der Warteschlange enthält ein Feld für Benutzerdaten und einen sequence_number Wert, der im Grunde wie ein Epochenzähler ist. (Dies vermeidet ABA-Probleme).

Der PUSH-Algorithmus ist wie folgt:

  1. Laden Sie write_index
  2. Es wurde versucht, einen Slot in der Warteschlange bei write_index % queue_size Verwendung einer CompareAndSwap-Schleife zu reservieren, die versucht, write_index auf write_index + 1 .
  3. Wenn der CompareAndSwap erfolgreich ist, kopieren Sie die Benutzerdaten in den reservierten Steckplatz.
  4. Schließlich aktualisieren Sie den sequence_index auf dem Steckplatz, indem Sie ihn gleich write_index + 1 .

Der eigentliche Quellcode verwendet benutzerdefinierte Atomics und Speicherbarrieren, so dass ich ihn zur besseren Lesbarkeit kurz in (ungeprüfte) Standard-C ++ – Atomics zur besseren Lesbarkeit übersetzt habe:

 bool mcmp_queue::enqueue(void* data) { int write_index = m_write_index.load(std::memory_order_relaxed); for (;;) { slot& s = m_slots[write_index % m_num_slots]; int sequence_number = s.sequence_number.load(std::memory_order_acquire); int difference = sequence_number - write_index; if (difference == 0) { if (m_write_index.compare_exchange_weak( write_index, write_index + 1, std::memory_order_acq_rel )) { break; } } if (difference < 0) return false; // queue is full } // Copy user-data and update sequence number // s.user_data = data; s.sequence_number.store(write_index + 1, std::memory_order_release); return true; } 

Nun kann ein Thread, der ein Element aus dem Slot bei read_index will, dies nicht tun, bis er feststellt, dass die sequence_number des Slots gleich read_index + 1 .

Okay, also gibt es hier keine Mutexe, und der Algorithmus funktioniert wahrscheinlich gut (es ist nur ein einziger CAS für PUSH und POP), aber ist dieser Lock-Free? Der Grund, warum es mir unklar ist, ist, dass die Definition von “Fortschritt machen” undurchsichtig erscheint, wenn die Möglichkeit besteht, dass ein PUSH oder POP immer versagt, wenn die Warteschlange als voll oder leer angesehen wird.

Aber was mir fraglich ist, ist, dass der PUSH-Algorithmus im Wesentlichen einen Slot reserviert , was bedeutet, dass der Slot niemals POP’d werden kann, bis der Push-Thread es schafft, die Sequenznummer zu aktualisieren. Dies bedeutet, dass ein POP-Thread, der einen Wert abrufen möchte, davon abhängig ist, dass der PUSH-Thread die Operation abgeschlossen hat. Andernfalls gibt der POP-Thread immer den Wert false da er die Warteschlange als leer erachtet. Es erscheint mir fraglich, ob dies tatsächlich unter die Definition von “Fortschritte machen” fällt.

Im Allgemeinen beinhalten wirklich blockierungsfreie Algorithmen eine Phase, in der ein vorweggenommener Thread tatsächlich versucht, den anderen Thread beim Abschluss einer Operation zu assistieren. Um also wirklich frei von Sperren zu sein, würde ich meinen, dass ein POP-Thread, der ein PUSH in Bearbeitung beobachtet, tatsächlich versuchen müsste, das PUSH zu vervollständigen und dann erst danach den ursprünglichen POP-Vorgang auszuführen. Wenn der POP-Thread einfach zurückgibt, dass die Warteschlange leer ist, während ein PUSH ausgeführt wird, ist der POP-Thread im Grunde blockiert, bis der PUSH-Thread den Vorgang abschließt. Wenn der PUSH-Thread stirbt oder für 1000 Jahre in den Ruhezustand geht oder anderweitig in Vergessenheit gerät, kann der POP-Thread nichts weiter tun, als kontinuierlich zu melden, dass die Warteschlange leer ist.

Passt das zur Definition von Lock-Free? Aus einer Perspektive können Sie argumentieren, dass der POP-Thread immer Fortschritte machen kann, weil er immer melden kann, dass die Warteschlange leer ist (was zumindest eine Art von Fortschritt ist, denke ich.) Aber für mich macht das nicht wirklich Fortschritte , da der einzige Grund dafür ist, dass die Warteschlange als leer angesehen wird, weil wir durch eine gleichzeitige PUSH-Operation blockiert sind.

Meine Frage ist also : Ist dieser Algorithmus wirklich frei von Sperren? Oder ist das Indexreservierungssystem im Grunde ein verkappter Mutex?

Diese Warteschlangendatenstruktur ist durch die meiner Meinung nach vernünftigste Definition nicht absolut frei von Sperren . Diese Definition ist etwas wie:

Eine Struktur ist nur dann frei von Sperren, wenn ein Thread unbegrenzt an irgendeinem Punkt suspendiert werden kann, während die Struktur, die von den verbleibenden Threads verwendet werden kann, noch verbleibt.

Natürlich impliziert dies eine geeignete Definition von Nutzbarkeit , aber für die meisten Strukturen ist dies ziemlich einfach: Die Struktur sollte weiterhin ihre Verträge befolgen und Elemente erlauben, wie erwartet eingefügt und entfernt zu werden.

In diesem Fall verlässt ein Thread, der m_write_increment erfolgreich inkrementiert, aber noch nicht s.sequence_number geschrieben s.sequence_number den Container in einem Zustand, der bald unbenutzbar sein wird. Wenn solch ein Thread beendet wird, wird der Container schließlich sowohl “voll” als auch “leer” melden, push zu push bzw. zu pop , wodurch der Vertrag einer Warteschlange fester Größe verletzt wird.

Es gibt hier einen versteckten Mutex (die Kombination aus m_write_index und der zugehörigen s.sequence_number ) – aber es funktioniert im Grunde wie ein Mutex pro Element. Der Fehler wird also nur für Schreiber sichtbar , wenn Sie einmal herumgelaufen sind und ein neuer Schreiber versucht, den Mutex zu bekommen, aber tatsächlich haben alle nachfolgenden Schreiber ihr Element nicht in die Warteschlange eingefügt, da es kein Leser jemals sehen wird.

Dies bedeutet nicht, dass dies eine schlechte Implementierung einer gleichzeitigen Warteschlange ist. Bei manchen Anwendungen verhält es sich möglicherweise so, als ob es frei von Sperren wäre. Zum Beispiel kann diese Struktur die meisten nützlichen performanceseigenschaften einer wirklich verriegelungsfreien Struktur haben, aber gleichzeitig fehlen einige der nützlichen Korrektheitseigenschaften . Grundsätzlich beinhaltet der Begriff ” lock-free” normalerweise eine ganze Reihe von Eigenschaften, von denen nur eine Teilmenge für eine bestimmte Verwendung wichtig ist. Lassen Sie uns eins nach dem anderen betrachten und sehen, wie diese Struktur funktioniert. Wir werden sie grob in performances- und functionskategorien einteilen.

Performance

Unbegrenzte performance

Die unübertroffene oder “Best Case” -performance ist für viele Strukturen wichtig. Während Sie für die Korrektheit eine parallele Struktur benötigen, werden Sie in der Regel immer noch versuchen, Ihre Anwendung so zu gestalten, dass die Anzahl der Konflikte auf ein Minimum reduziert wird. Daher sind die unkontrollierten Kosten oft wichtig. Einige blockierungsfreie Strukturen helfen hier, indem sie die Anzahl der teuren atomaren Operationen im unüberdachten Fast-Path reduzieren oder einen syscall vermeiden.

Diese Warteschlangenimplementierung macht hier einen vernünftigen Job: Es gibt nur einen einzigen “definitiv teuren” Vorgang: den compare_exchange_weak und ein paar möglicherweise teure Operationen (den memory_order_acquire load und den memory_order_release store) 1 und wenig weiteren Overhead.

Dies steht im Vergleich zu etwas wie std::mutex das etwas wie eine atomare Operation für die Sperre und eine weitere für das Entsperren implizieren würde, und in der Praxis unter Linux haben die pthread-Aufrufe auch einen nicht vernachlässigbaren Overhead.

Ich erwarte also, dass diese Warteschlange im unübertroffenen schnellen Pfad einigermaßen gut funktioniert.

Bezogene performance

Ein Vorteil von blockfreien Strukturen ist, dass sie oft eine bessere Skalierung ermöglichen, wenn eine Struktur stark beansprucht wird. Dies ist nicht notwendigerweise ein inhärenter Vorteil: Einige auf Sperren basierende Strukturen mit mehreren Sperren oder Lese-Schreib-Sperren können eine Skalierung aufweisen, die einigen lockfreien Ansätzen entspricht oder diese überschreitet, aber in diesem Fall zeigen normalerweise blockierungsfreie Strukturen eine bessere Skalierung eine einfache One-Lock-to-Rule-die-alle-Alternative.

Diese Warteschlange funktioniert in dieser Hinsicht vernünftig. Die Variable m_write_index wird von allen Lesern m_write_index aktualisiert und ist ein Streitpunkt, aber das Verhalten sollte vernünftig sein, solange die zugrundeliegende Hardware-CAS-Implementierung vernünftig ist.

Beachten Sie, dass eine Warteschlange im Allgemeinen eine ziemlich schlechte gleichzeitige Struktur ist, da Einfügungen und Entnahmen alle an den gleichen Stellen (Kopf und Ende) stattfinden, so dass eine Konkurrenz in der Definition der Struktur inhärent ist. Vergleichen Sie dies mit einer Concurrent Map, bei der verschiedene Elemente keine bestimmte geordnete Beziehung haben: Eine solche Struktur kann eine effiziente konfliktfreie simultane Mutation bieten, wenn auf verschiedene Elemente zugegriffen wird.

Kontextwechsel Immunität

Ein performancesvorteil von blockierungsfreien Strukturen, der mit der obigen coredefinition (und auch mit den funktionalen Garantien) in Beziehung steht, besteht darin, dass ein Kontextwechsel eines Threads, der die Struktur mutiert, nicht alle anderen Mutatoren verzögert. In einem stark ausgelasteten System (insbesondere bei lauffähigen Threads >> verfügbaren coreen) kann ein Thread für Hunderte von Millisekunden oder Sekunden ausgeschaltet werden. Während dieser Zeit werden alle konkurrierenden Mutatoren blockiert und verursachen zusätzliche Planungskosten (oder sie werden sich drehen, was ebenfalls zu einem schlechten Verhalten führen kann). Auch wenn eine solche “unglückliche Planung” selten ist, kann das gesamte System, wenn es auftritt, eine ernsthafte Latenzspitze erleiden.

Sperrenfreie Strukturen vermeiden dies, da es keine “kritische Region” gibt, in der ein Thread kontextausgeschalten werden kann und anschließend den Vorwärtsfortschritt durch andere Threads blockieren kann.

Diese Struktur bietet einen teilweisen Schutz in diesem Bereich – deren Besonderheiten von der Warteschlangengröße und dem Anwendungsverhalten abhängen. Selbst wenn ein Thread in dem kritischen Bereich zwischen dem m_write_index Update und dem Sequenznummern-Schreibvorgang ausgeschaltet wird, können andere Threads weiterhin Elemente in die Warteschlange push , solange sie nicht vollständig um das laufende Element herum m_write_index der festgefahrene Faden. Threads können auch Elemente poppen, aber nur bis zum laufenden Element.

Während das push Verhalten für Warteschlangen mit hoher Kapazität kein Problem darstellt, kann das pop Verhalten ein Problem sein: Wenn die Warteschlange einen hohen Durchsatz im Vergleich zur durchschnittlichen Zeit hat, in der ein Thread kontextabhängig ist, und die durchschnittliche Fülle, wird die Warteschlange erscheint schnell für alle Consumer-Threads leer, selbst wenn über das in-progress- Element hinaus viele Elemente hinzugefügt wurden. Dies wird nicht von der Warteschlangenkapazität, sondern einfach vom Anwendungsverhalten beeinflusst. Dies bedeutet, dass die Verbraucherseite vollständig stehen bleiben kann, wenn dies auftritt. In dieser Hinsicht sieht die Warteschlange überhaupt nicht sehr frei von Sperren aus!

functionelle Aspekte

Asynchrone Thread-Beendigung

Mit dem Vorteil von lock-free Strukturen sind sie sicher für die Verwendung von Threads, die asynchron abgebrochen werden können oder ausnahmsweise in der kritischen Region enden können. Wenn Sie einen Thread an einem beliebigen Punkt abbrechen, bleibt die Struktur in einem konsistenten Zustand.

Dies ist nicht der Fall für diese Warteschlange, wie oben beschrieben.

Warteschlangenzugriff von Interrupt oder Signal

Ein damit verbundener Vorteil besteht darin, dass blockierungsfreie Strukturen üblicherweise von einem Interrupt oder Signal untersucht oder mutiert werden können. Dies ist in vielen Fällen nützlich, in denen ein Interrupt oder Signal eine Struktur mit regulären process-Threads teilt.

Diese Warteschlange unterstützt meistens diesen Anwendungsfall. Selbst wenn das Signal oder die Unterbrechung auftritt, wenn ein anderer Thread in der kritischen Region ist, kann der asynchrone Code immer noch ein Element in die Warteschlange push (was später nur durch das Konsumieren von Threads zu sehen ist) und kann trotzdem ein Element aus der Warteschlange entfernen.

Das Verhalten ist nicht so vollständig wie eine echte blockierungsfreie Struktur: Stellen Sie sich einen Signal-Handler vor, der den verbleibenden Anwendungsthreads (außer dem unterbrochenen) die Stilllegung anordnet und dann alle verbleibenden Elemente der Warteschlange ableitet. Mit einer echten blockierungsfreien Struktur würde dies dem Signal-Handler ermöglichen, alle Elemente vollständig zu entleeren, aber diese Warteschlange könnte dies nicht tun, falls ein Thread in der kritischen Region unterbrochen oder abgeschaltet wurde.


1 Insbesondere wird auf x86 nur eine atomare Operation für das CAS verwendet, da das Speichermodell stark genug ist, um die Notwendigkeit von Atomics oder Fencing für die anderen Operationen zu vermeiden. Jüngste ARM kann auch ziemlich effizient erwerben und veröffentlichen.

Ein Thread, der POP anruft, bevor die nächste Aktualisierung der Sequenz abgeschlossen ist, wird NICHT “effektiv blockiert”, wenn der POP-Aufruf sofort FALSE zurückgibt. Der Thread kann losgehen und etwas anderes tun. Ich würde sagen, dass diese Warteschlange als sperrfrei gilt.

Allerdings würde ich nicht sagen, dass es sich als “Warteschlange” qualifiziert – zumindest nicht die Art von Warteschlange, die Sie als Warteschlange in einer Bibliothek oder etwas veröffentlichen könnten – weil es nicht viele Verhaltensweisen garantiert Sie können normalerweise von einer Warteschlange erwarten. Insbesondere können Sie PUSH und Element und dann versuchen und FAIL zu POP es, weil ein anderer Thread beschäftigt ist, ein früheres Element zu schieben.

Trotzdem könnte diese Warteschlange in einigen lockfreien Lösungen für verschiedene Probleme nützlich sein.

Für viele Anwendungen würde ich mir jedoch Sorgen machen, dass Consumer-Threads ausgehungert werden können, während ein Producer-Thread vorweggenommen ist. Vielleicht macht liblfds etwas dagegen?

“Lock-free” ist eine Eigenschaft des Algorithmus , der einige functionen implementiert. Die Eigenschaft korreliert nicht mit einer Art und Weise, wie gegebene functionalität von einem Programm verwendet wird.

Wenn über die mcmp_queue::enqueue function gesprochen wird, die FALSE zurückgibt, wenn die zugrunde liegende Warteschlange voll ist, ist ihre Implementierung (in der Fragestellung angegeben) mcmp_queue::enqueue .

Die Implementierung von mcmp_queue::dequeue in lock-free-Weise wäre jedoch schwierig. Zum Beispiel ist dieses Muster offensichtlich nicht-lock-frei, da es sich auf die Variable dreht, die von einem anderen Thread geändert wurde:

 while(s.sequence_number.load(std::memory_order_acquire) == read_index); data = s.user_data; ... return data; 

Die meiste Zeit benutzen Leute lock-free, wenn sie wirklich lockless meinen. Lockless bedeutet eine Datenstruktur oder einen Algorithmus, der keine Sperren verwendet, aber es gibt keine Garantie für den Vorwärtsfortschritt. Überprüfen Sie auch diese Frage . Die Warteschlange in liblfds ist also gesperrt, aber wie BeeOnRope erwähnt ist nicht frei von Sperren.