Sperrfreie Datenstrukturen. Warteschlangendissektion


    Seit dem vorherigen Beitrag ist viel Zeit vergangen, um die Lebensdauer von verschließbaren Containern zu verlängern. Ich hatte erwartet, schnell eine Fortsetzung der Abhandlung über Warteschlangen zu schreiben, aber es gab ein Problem: Ich wusste, worüber ich schreiben sollte, aber ich hatte diese Ansätze in C ++ nicht. "Es ist nicht gut zu schreiben, dass ich es nicht selbst ausprobiert habe", dachte ich und versuchte daher, neue Warteschlangenalgorithmen in libcds zu implementieren .
    Jetzt ist der Moment gekommen, in dem ich meinen Argumentationszyklus fortsetzen kann. Dieser Artikel endet mit den Warteschlangen.

    Erinnern Sie sich kurz, wo ich aufgehört habe. Einige interessante Algorithmen für schlossfreie Warteschlangen wurden in Betracht gezogen, und der Vorhang zeigt die Ergebnisse ihrer Arbeit an einigen synthetischen Tests. Die Hauptschlussfolgerung ist, dass alles schlecht ist! Die Hoffnungen, die der lock-free-Ansatz beim Magic Compare-and-Swap (CAS) weckt, wenn auch nicht linear, aber mit zunehmender Anzahl von Threads immerhin eine gewisse Leistungssteigerung, haben sich nicht erfüllt. Warteschlangen skalieren nicht. Was ist der Grund? Die

    Antwort auf diese Frage liegt in der Architektur moderner Prozessoren. Das CAS-Grundelement ist ein ziemlich umfangreicher Befehl, der den Cache und das interne Synchronisationsprotokoll stark belastet. Bei der aktiven Verwendung von CAS über dieselbe Cache-Zeile kümmert sich der Prozessor hauptsächlich um die Aufrechterhaltung der Cache-Kohärenz, wie dies ausführlicher von Professor Paul McKenney beschrieben wirdmit meiner Hilfe bereits schrieb ich .

    Stapel und Warteschlangen sind für den sperrfreien Ansatz von Datenstrukturen sehr unfreundlich, da sie nur eine geringe Anzahl von Einstiegspunkten haben. Für den Stapel gibt es nur einen solchen Punkt - die Oberseite des Stapels, für die Warteschlange gibt es zwei davon - Kopf und Schwanz. CAS konkurriert um den Zugriff auf diese Punkte, während die Leistung bei 100% Prozessorauslastung sinkt - alle Threads sind mit etwas beschäftigt, aber nur einer gewinnt und erhält Zugriff auf den Kopf / Schwanz. Entspricht nichts? Dies ist ein klassischer Spin-Lock! Es stellt sich heraus, dass wir mit dem Lock-Free-Ansatz auf CASs die externe Synchronisation durch den Mutex losgeworden sind, aber die interne Synchronisation auf Prozessorbefehlsebene erhalten haben und wenig gewonnen haben.
    Begrenzte Warteschlangen
    Es ist zu beachten, dass alle oben genannten Punkte für unbegrenzte (unbegrenzte) MPMC-Warteschlangen (Multiple Producer / Multiple Consumer) gelten. In Warteschlangen, die in Bezug auf die Anzahl der Elemente, die in der Regel auf der Grundlage eines Arrays erstellt werden, begrenzt sind, ist dieses Problem möglicherweise nicht so ausgeprägt, da die Elemente der Warteschlange genau über das Array verteilt sind. Schnellere Algorithmen können auch für Warteschlangen mit einem Schreiber und / oder einem Leser erstellt werden.


    Das Problem der wirksamen Umsetzung wettbewerbsfähiger Warteschlangen ist für Forscher nach wie vor von Interesse. In den letzten Jahren hat das Verständnis zugenommen, dass verschiedene Arten von Tricks bei der Implementierung von schlossfreien Warteschlangen „auf der Stirn“ nicht das erwartete Ergebnis liefern und einige andere Ansätze erdacht werden sollten. Weiter werden wir einige von ihnen betrachten.

    Flaches Kombinieren


    Ich habe diese Methode bereits im Artikel über den Stapel beschrieben, aber das flache Kombinieren ist eine universelle Methode, daher gilt sie für die Warteschlange. Ich sende Leser zum Video meiner Präsentation bei C ++ User Group, Russland , die sich der Implementierung von Flat Combining widmet.
    Als Werbung
    Ich nutze diese Gelegenheit, um Support-Strahlen an sermp zu senden - den Inspirator und Organisator der C ++ User Group, Russland. Sergey, deine selbstlose Arbeit auf diesem Gebiet ist von unschätzbarem Wert!
    Ich fordere die Leser auf, diesem Ereignis Aufmerksamkeit zu schenken und es mit ihrem Auftritt sowie mit Präsentationen zu unterstützen, die etwas zu teilen haben. Aus eigener Erfahrung war ich davon überzeugt, dass Live-Kommunikation viel cooler ist, als ein habr zu lesen.
    Ich mache Sie auch auf die bevorstehende C ++ Russia- Konferenz vom 27. bis 28. Februar 2015 in Moskau aufmerksam - kommen Sie!


    Reihe von Warteschlangen



    Ein Ansatz, der an der Oberfläche liegt, aber dennoch schwierig umzusetzen ist, mit vielen Fallstricken, wurde 2013 in einem Artikel mit dem Titel „Ersetzen des Wettbewerbs durch Zusammenarbeit bei der Implementierung einer skalierbaren Warteschlange ohne Sperre“ vorgeschlagen , der perfekt zum Thema dieses Beitrags passt .
    Die Idee ist sehr einfach. Anstelle einer einzelnen Warteschlange wird ein Array der Größe K erstellt, von dem jedes Element eine sperrfreie Warteschlange ist, die durch eine einfach verbundene Liste dargestellt wird. Ein neues Element wird zum nächsten (Modulo K) Slot des Arrays hinzugefügt. Somit wird die Überfüllung am Ende der Warteschlange ausgeglichen - anstelle eines Endes haben wir K Endpunkte, sodass wir erwarten können, dass wir eine lineare Skalierbarkeit bis zu K parallelen Flüssen erhalten. Natürlich müssen wir einen bestimmten allgemeinen atomaren monoton ansteigenden Push-Operations-Zähler haben, um jedes Insert in seinen Array-Slot zu multiplexen. Natürlich wird dieser Zähler ein einziger "Knackpunkt" für alle Push-Streams sein. Aber die Autoren behaupten (nach meinen Beobachtungen nicht unangemessen), dass die AnweisungxaddAtomic Addition (in unserem Fall Increment) auf der x86-Architektur ist etwas schneller als CAS. Wir können also davon ausgehen, dass wir auf x86 einen Gewinn erzielen. Auf anderen Architekturen Atome fetch_addemuliert CAS'om, so dass der Gewinn nicht so stark bemerkbar sein wird.
    Der Code zum Löschen eines Elements aus der Warteschlange ist ähnlich: Es gibt einen Atomzähler für gelöschte Elemente (Pop-Counter), auf dessen Grundlage ein Array-Slot modulo K ausgewählt wird. Um die Verletzung der Haupteigenschaft der Warteschlange - FIFO - zu beseitigen, enthält jedes Element eine zusätzliche Last ( ticket) - den Wert des Push-Zählers zum Zeitpunkt des Hinzufügens des Elements, und zwar die Seriennummer des Elements. Beim Löschen im Slot wird das Element mit ticket= nach dem aktuellen Wert des Pop-Counters durchsucht , das gefundene Element ist das Ergebnis der Operation pop().
    Eine interessante Möglichkeit, das Problem des Entfernens aus einer leeren Warteschlange zu lösen. Bei diesem Algorithmus folgt auf das atomare Inkrement des Löschzählers (Pop-Counter) zunächst eine Suche im entsprechenden Slot. Möglicherweise ist der Steckplatz leer. Dies bedeutet, dass die gesamte Warteschlange leer ist. Der Pop-Zähler ist jedoch bereits inkrementiert, und seine weitere Verwendung führt zu einer Verletzung des FIFO und sogar zum Verlust von Elementen. Sie können nicht rückgängig machen (dekrementieren) - plötzlich und gleichzeitig fügen andere Threads Elemente hinzu oder entfernen sie (im Allgemeinen ist "Zurückspielen-nicht-unmöglich" eine integrale Eigenschaft des sperrfreien Ansatzes). Wenn sich eine Situation pop()aus einer leeren Warteschlange ergibt , wird das Array für ungültig erklärt. Dies führt dazu, dass beim nächsten Einfügen des Elements ein neues Array mit neuen Push- und Pop-Zählern erstellt wird.

    Leider haben sich die Autoren nicht mit dem Problem der Speicherfreigabe befasst (da sie aus Platzgründen schreiben) und nur einige Vorschläge mit einer oberflächlichen Beschreibung der Anwendung des Hazard Pointer-Schemas auf ihren Algorithmus gemacht. Ich konnte ihre Hinweise noch nicht entschlüsseln, daher gibt es keine Implementierung dieses interessanten Algorithmus in der Bibliothek libcds. Darüber hinaus ist der Algorithmus einer unbegrenzten Anhäufung gelöschter Elemente unterworfen, wenn die Warteschlange niemals leer ist, d. H. Wenn das Array nicht ungültig gemacht wird, da keine Elemente aus der Liste der Array-Slots entfernt werden sollen. pop()Es wird nur nach dem Element mit dem aktuellen ticket'th im entsprechenden Slot gesucht, aber der physische Ausschluss des Elements aus der Liste erfolgt erst, wenn das gesamte Array ungültig ist.

    Zusammenfassend können wir sagen: Der Algorithmus ist interessant, aber das Speichermanagement wird nicht klar genug beschrieben. Weitere Studien sind erforderlich.

    Segmentierte Warteschlangen


    Eine andere Möglichkeit, die Skalierbarkeit einer Warteschlange zu erhöhen, besteht darin, ihre primäre First-In-Eigenschaft, First-Out (FIFO), zu verletzen. Ist es wirklich so beängstigend? Es kommt auf die Aufgabe an: Für manche ist die strikte Einhaltung des FIFO verpflichtend, für andere - in gewissen Grenzen durchaus akzeptabel.
    Natürlich möchte ich die FIFO-Haupteigenschaft nicht wirklich radikal verletzen - in diesem Fall erhalten wir eine Datenstruktur, die als Pool bezeichnet wird und in der überhaupt keine Reihenfolge eingehalten wird: Die Operation pop()gibt ein beliebiges Element zurück. Dies ist nicht mehr an der Reihe. Für eine Warteschlange mit einer FIFO-Verletzung möchte ich einige Garantien für diese Verletzung haben, zum Beispiel: Die Operation gibt pop()eines der ersten K-Elemente zurück. Für K = 2 bedeutet dies, dass für eine Warteschlange mit den Elementen A, B, C, D, ... pop()A oder B zurückgegeben wird. Solche Warteschlangen werden aufgerufensegmentiert oder K-segmentiert , um die Wichtigkeit des K-Faktors hervorzuheben - FIFO-Verletzungseinschränkungen. Offensichtlich ist für eine strenge (faire) FIFO-Warteschlange K = 1.
    Soweit ich weiß, wurde die einfachste segmentierte Warteschlange im Jahr 2010 erstmals ausführlich in einer Arbeit behandelt, die sich ausschließlich der zulässigen Entlastung von Anforderungen an sperrenfreie Datenstrukturen widmete. Die interne Struktur der Warteschlange ist recht einfach (Abbildung aus dem obigen Artikel, K = 5):

    Die Warteschlange ist eine einfach verbundene Liste von Segmenten, wobei jedes Segment ein Array von K Elementen in der Größe ist. Headund Tailgeben das erste und letzte Segment in der Liste an. Operation push()fügt ein neues Element einIn einen willkürlichen freien Schlitz im hinteren Segment pop()extrahiert die Operation ein Element aus einem willkürlich belegten Schlitz im Kopfsegment. Bei diesem Ansatz ist es offensichtlich, dass die FIFO-Eigenschaft umso weniger verletzt wird, je kleiner das K-Segment ist. für K = 1 bekommen wir eine strenge Warteschlange. Somit können wir durch Variieren von K den Grad der Verletzung des FIFO steuern.
    In dem beschriebenen Algorithmus kann sich jeder Steckplatz eines Segments in einem von drei Zuständen befinden: frei, belegt (enthält ein Element) und "Müll" (ein Element wurde aus dem Steckplatz gelesen). Beachten Sie, dass die Operation pop()den Steckplatz in den Status "Garbage" versetzt, was nicht der Fall istDas Äquivalent zum Status "Frei": Der Status "Müll" ist der Endstatus des Slots, das Schreiben eines Werts in einen solchen Slot ist nicht zulässig. Dies ist ein Nachteil des Algorithmus - ein Slot im "Garbage" -Zustand kann nicht wiederverwendet werden, was zur Verteilung neuer Segmente führt, selbst in einer solchen typischen Abfolge von Operationen wie einer abwechselnden push() / pop(). Dieses Manko wurde korrigiert andere Arbeit auf Kosten der erheblichen Komplikation des Codes.

    Erforschen


    In libcds wurden zwei neue Algorithmen für Warteschlangen implementiert: FCQueue und SegmentedQueue. Lassen Sie uns ihre Leistung sehen und versuchen zu verstehen, ob es sich gelohnt hat, mit ihnen umzugehen.
    Leider wurde der Server, auf dem ich Tests für den vorherigen Artikel ausgeführt habe, mit anderen Aufgaben geladen und stürzte anschließend ab. Ich musste die Tests auf einem anderen, weniger leistungsstarken Server ausführen - AMD Opteron 1,5 GHz mit 2 x 12 Kernen und 64 G Arbeitsspeicher unter Linux, der mit 95% fast kostenlos war - im Leerlauf.

    Ich habe die Visualisierung der Ergebnisse geändert - anstelle der Testausführungszeit entlang der Y-Achse verschiebe ich jetzt die Anzahl der Megaoperationen pro Sekunde (Mop / s). Lassen Sie mich daran erinnern, dass der Test ein klassischer Produzent / Konsument ist: nur 20 Millionen Vorgänge - 10 Millionen Push und 10 Millionen Pop ohne jegliche Nutzlastemulation, dummes Anstehen. Alle schlossfreien Warteschlangentests verwenden Hazard Pointer, um Speicher sicher freizugeben.

    Alte Daten in neuen Papageien
    Die Tabelle aus dem vorherigen Artikel in den neuen Papageien - MOP / s sieht so aus



    Zunächst ein Exkurs: Wonach streben wir? Was möchten wir über Skalierbarkeit erfahren?

    Ideale Skalierung ist eine lineare Zunahme von Mop / s mit einer Zunahme der Anzahl von Fäden, wenn das Eisen physikalisch so viele Fäden unterstützt. Wirklich gutes Ergebnis wird sein , einiger Anstieg Mop / s, mehr wie ein Murmeltier. Wenn die Anzahl der Threads zunimmt und die Leistung abnimmt, kann der Algorithmus nicht oder nur begrenzt skaliert werden.

    Ergebnisse für aufdringliche Warteschlangen (ich möchte Sie daran erinnern, dass ein aufdringlicher Container dadurch gekennzeichnet ist, dass er einen Zeiger auf die Daten selbst und keine Kopie davon enthält, wie in STL; daher ist es nicht erforderlich, Speicher für eine Kopie von Elementen zuzuweisen, die in der Welt ohne Sperren als schlechte Manieren betrachtet wird).

    Es ist zu sehen, dass Flat Combining nicht umsonst implementiert wurde - diese Technik zeigt ein sehr gutes Ergebnis gegenüber anderen Algorithmen. Ja, es erhöht nicht die Produktivität, aber es gibt auch kein signifikantes Absinken. Ein wesentlicher Vorteil ist außerdem, dass der Prozessor praktisch nicht geladen wird - es funktioniert immer nur ein Kern. Andere Algorithmen zeigen eine 100% ige CPU-Auslastung mit einer großen Anzahl von Threads.
    Eine segmentierte Warteschlange erweist sich als Außenseiter. Möglicherweise liegt dies an den Besonderheiten des implementierten Algorithmus: Speicherzuordnung für Segmente (in diesem Test beträgt die Segmentgröße 16), Unfähigkeit, Segment-Slots wiederzuverwenden, was zu permanenten Zuordnungen führt, Implementierung der Liste der Segmente basierend auf boost :: intrusive :: slist under lock (Ich habe zwei Arten von Sperren ausprobiert - Spin-Lock und std :: mutex; die Ergebnisse sind praktisch gleich).
    Ich hatte die Hoffnung, dass die Hauptbremse falsches Teilen ist. Bei der Implementierung einer segmentierten Warteschlange war ein Segment ein Array von Zeigern auf Elemente. Bei einer Segmentgröße von 16 belegt ein Segment 16 * 8 = 128 Bytes, dh zwei Cache-Zeilen. Bei einer konstanten Menge von Datenströmen im ersten und letzten Segment kann sich eine falsche Aufteilung als voll im Wachstum befindlich erweisen. Deshalb habe ich eine zusätzliche Option im Algorithmus eingeführt - die erforderliche Auffüllung. Wenn padding = Cache-Zeilengröße (64 Bytes), erhöht sich die Segmentgröße auf 16 * 64 = 1024 Bytes. Auf diese Weise wird jedoch eine falsche gemeinsame Nutzung vermieden. Leider hat sich herausgestellt, dass das Auffüllen praktisch keinen Einfluss auf die Leistung von SegmentedQueue hat. Möglicherweise liegt dies daran, dass der Algorithmus für die Segmentzellensuche probabilistisch ist, was zu vielen erfolglosen Versuchen führt, ausgelastete Zellen zu lesen. das ist wieder falsches Teilen. Oder falsches Teilen ist überhaupt nicht die Hauptbremse für diesen Algorithmus und Sie müssen nach dem wahren Grund suchen.

    Trotz des Verlusts gibt es eine interessante Beobachtung: SegmentedQueue zeigt kein Absinken der Leistung, wenn die Anzahl der Threads zunimmt. Dies lässt hoffen, dass die Algorithmen dieser Klasse eine Perspektive haben. Sie müssen sie nur anders und effizienter implementieren.

    Für STL-ähnliche Warteschlangen mit der Erstellung einer Kopie des Elements haben wir ein ähnliches Bild:


    Zum Schluss möchte ich, nur aus Gründen des Interesses, das Ergebnis einer begrenzten Warteschlange angeben - einen Dmitry Vyukov-Algorithmus, der auf einem Array basiert, einer aufdringlichen Implementierung:

    Bei der Anzahl der Threads = 2 (ein Leser und ein Schreiber) zeigt diese Warteschlange 32 MOp / s, die nicht in das Diagramm passten. Mit zunehmender Anzahl der Threads wird auch eine Verschlechterung der Leistung beobachtet. Als Entschuldigung kann angemerkt werden, dass falsches Teilen für Vyukovs Warteschlange ebenfalls ein sehr bedeutender Hemmfaktor sein kann, aber die Option, die das Auffüllen entlang der Cache-Zeile beinhaltet, ist noch nicht in libcds dafür enthalten.

    für Liebhaber von fremden
    Ich bin auch auf einen ungewöhnlichen Linux-Server mit IBM Power8 gestoßen - zwei 3,42-GHz-Prozessoren mit jeweils zehn Kernen, von denen jeder gleichzeitig bis zu 8 Befehle ausführen kann, was insgesamt 160 logischen Prozessoren entspricht. Hier sind die Ergebnisse der gleichen Tests darauf.
    Aufdringliche Warteschlangen:

    STL-ähnliche Warteschlangen:

    Wie Sie sehen, gibt es keine grundlegenden Änderungen. Obwohl nein, gibt es eine Sache: Die Ergebnisse für eine segmentierte Warteschlange werden mit einer Segmentgröße von K = 256 angezeigt. Dies ist genau das, was K für den angegebenen Server nahe am Besten war.


    Abschließend möchte ich eine interessante Bemerkung machen. In den obigen Tests gibt es keine Nutzlast für Leser und Schreiber. Unser Ziel ist es lediglich, die Warteschlange zu pushen und daraus zu lesen. In realen Aufgaben gibt es immer eine Art von Last - wir machen etwas mit den Daten, die aus der Warteschlange gelesen werden, und bevor wir sie in die Warteschlange stellen, bereiten wir die Daten vor. Es scheint, dass Nutzlast zu einem Absacken der Leistung führen sollte, aber die Praxis zeigt, dass dies bei weitem nicht immer der Fall ist. Ich habe wiederholt beobachtet, dass die Nutzlast zu einem signifikanten Anstieg der MOp / s- Papageien führt . Der Grund scheint mir das Entladen des internen Cache-Synchronisationsprotokolls zu sein, siehe P.McKenney. Das Fazit liegt auf der Hand: Sie müssen an realen Aufgaben testen.


    In diesem Artikel habe ich einen kleinen Teil der Arbeit angesprochen, der den Warteschlangen gewidmet ist, und zwar nur dynamisch (unbegrenzt), ohne die Anzahl der Elemente einzuschränken. Wie ich bereits sagte, ist die Warteschlange eine der beliebtesten Datenstrukturen für Forscher, anscheinend, weil sie sich nur schwer skalieren lässt. Viele andere Arbeiten blieben außerhalb des Untersuchungsbereichs - über begrenzte Warteschlangen, Work-Stealing-Warteschlangen, die in Task-Schedulern verwendet werden, Warteschlangen für Einzelverbraucher oder Einzelproduzenten - die Algorithmen solcher Warteschlangen werden von einem Schreiber oder Leser erheblich geschärft, und daher ist es oft einfacher und / oder oder viel produktiver - etc. usw.
    Nachrichten aus der Mikrowelt libcds
    Seit dem vorherigen Artikel wurde Version 1.6.0 der Bibliothek veröffentlicht, in der zusätzlich zur Implementierung der Techniken Flat Combining und SegmentedQueue eine Reihe von Fehlern behoben und SkipList und EllenBinTree grundlegend überarbeitet wurden.
    Das Repository für die kommende Version 2.0 ist auf Github umgestiegen , und Version 2.0 selbst widmet sich dem Übergang zum C ++ 11-Standard, dem Kämmen des Codes, der Vereinheitlichung der Schnittstellen, was die berüchtigte Abwärtskompatibilität zur Folge hat (was bedeutet, dass einige Entitäten umbenannt werden) und dem Entfernen von Krücken Unterstützung für alte Compiler (und wie üblich das Korrigieren gefundener und das Erzeugen neuer Fehler).

    Я рад, что мне удалось-таки, несмотря на большой временной лаг, довести повествование об очередях и стеках до логического конца, ибо это не самые дружественные для lock-free подхода и современных процессоров структуры данных, да и не очень для меня интересные.
    Впереди нас ждут куда более увлекательные структуры — ассоциативные контейнеры (set/map), в частности, hash map, с красивыми алгоритмами и, надеюсь, более благодарные в плане масштабируемости.
    Продолжение, думаю, воспоследует…


    Jetzt auch beliebt: