1. Zuhause
  2. Frage und Antwort
  3. Wie erstelle ich eine blocklose Warteschlange?

Wie erstelle ich eine blocklose Warteschlange?

2009-11-12 21 views
15

Ich habe heute in lockless Warteschlangen verbracht. Ich habe eine multiple Produzenten-, Mehrfachverbrauchersituation. Ich habe zum Testen ein System implementiert, das die Interlocked SList-Funktion unter Win32 verwendet, und es hat die Leistung meines Task-basierten Codes mit hohem Threading verdoppelt. Leider möchte ich jedoch mehrere Plattformen unterstützen. Das Interlocking auf mehreren Plattformen ist kein Problem und ich kann davon ausgehen, dass ich ohne Probleme eingreifen kann. Die tatsächliche Implementierung verliert mich jedoch.Wie erstelle ich eine blocklose Warteschlange?

Das große Problem scheint zu sein, dass Sie eine Liste garantieren müssen, Push/Pop wird nur einen Interlocked Anruf verwenden. Sonst lässt du Platz für einen anderen Thread, der einknickt und Dinge vermasselt. Ich bin mir nicht sicher, wie die Microsoft-Implementierung unter der Haube funktioniert und würde gerne mehr wissen.

Kann mir jemand auf nützliche Informationen hinweisen (Plattform und Sprache sind ziemlich irrelevant)?

Hinzu kommt, würde ich gerne wissen, ob es möglich ist, einen Lockless-Vektor zu implementieren. Das hätte enorme Mengen an Nutzen für mich :) Prost!

Edit: Nachdem ich DDJ-Artikel von Kraut gelesen habe, kann ich eine Warteschlange mit reduzierter Sperre sehen, die ziemlich ähnlich der ist, die ich bereits hatte. Wie auch immer, ich merke, dass es am Ende Papiere gibt, die mit einer Double-Compare-and-Swap-Operation (DCAS) die echte Lockless-Queue machen können. Hat jemand eine Warteschlange mit cmpxchg8b (oder cmpxchg16b für diese Angelegenheit) implementiert?

Ich denke nur an diesem Punkt (ohne die Papiere zu lesen), aber Sie könnten dieses System verwenden, um den Kopf- und den Endzeiger gleichzeitig zu aktualisieren und damit Probleme mit einem anderen Thread zwischen den 2 atomaren Operationen zu vermeiden. Allerdings müssen Sie immer noch den nächsten Kopfzeiger bekommen, um dies gegen den Schwanzzeiger zu testen, um zu sehen, ob Sie gerade den Schwanz modifiziert haben. Wie vermeidet man, dass ein anderer Thread diese Informationen ändert, während sich der andere Thread selbst darauf vorbereitet? Wie genau wird das in einer Lockless-Methode umgesetzt? Oder bin ich besser dran, die Unentschlüsselbarkeit zu lesen, die eine Forschungsarbeit ist? ;)

Quelle

2009-11-12 Goz

+5

siehe http://stackoverflow.com/questions/1164023/is-there-a-production-ready-lock-free-queue-or-hash-implementation-in-c – Mark

+0

Schande, Sie haben nicht geantwortet:) Ich hatte diese Warteschlange nicht gefunden, und außerdem hatte ich Herb Sutters Multiproductor/Consumer DDJ Artikel nicht gefunden :) Danke! – Goz

Antwort

11

Sie wahrscheinlich eine begrenzte Größe Warteschlange mit geringsten Schwierigkeiten implementieren könnte ... Ich war Ich habe in letzter Zeit darüber nachgedacht und kam mit diesem Design, aber Sie können wahrscheinlich viele andere interessante Ideen finden: (ACHTUNG: es könnte einige Probleme haben!

)
  • die Warteschlange ist ein Array von Zeigern auf Objekte
  • Sie 2 Zeiger zu verwalten haben (Kopf, Schwanz), die
  • wenn head == in gleicher Weise als Ringpuffer über den Schlangenarbeits tail gibt es derzeit keine Artikel
  • wenn Sie enqueue(ptr) wollen, Verzahnte-Swap tail mit NULL (prev_tail dem tauschte Wert ist)
    • wenn prev_tail == NULL, versuchen Sie es erneut
    • wenn prev_tail + 1 (mit Wraparound) == head, ist die Warteschlange voll
    • sonst setzen Sie Ihre ptr in *prev_tail und weisen prev_tail+1 zu tail (achten Sie auf Puffer Wraparound)
  • für dequeue() eine Kopie tmp_head = Kopf machen und tmp_head == tail
    • überprüfen, ob es wahr ist, Rückkehr, weil die Warteschlange leer
    • wenn es falsch
      • speichern *tmp_head als ptr
      • ein CAS tun: Vergleichen head mit tmp_head Swap head mit head+1
      • wenn CAS gescheitert - die ganze Funktion über
      • starten, wenn es gelungen - zurück ptr

Sie können sowohl auf Head- als auch auf Tail-CAS-Operationen warten, aber wenn die Warteschlange nicht konkurriert, sollten Sie das erste Mal ohne unnötige Sperren erfolgreich sein.

Unbegrenzte Warteschlangen sind "ein bisschen" härter;) Aber Sie sollten in der Lage sein, eine große Warteschlange für die meisten Bedürfnisse zu erstellen.

Quelle

2009-11-12 23:28:42 viraptor

+0

Wie werden Sie prüfen, ob 'head == tail' bei der Auslagerung ohne Sperre? –

+0

Ok - Ich habe diesen Schritt nicht richtig beschrieben.Sie müssen an den Anfang und nicht an den CAS selbst anschliessen. CAS erkennt, ob der Kopf bewegt wurde. – viraptor

+0

Klingt gut, ich stimme der erweiterten Erklärung zu. Einfach überprüfen :). –

2

These Leute haben, vielleicht könntest du dort ein wenig Inspiration finden. Die andere interessante Dateien sind yqueue.hpp und atomic_ptr.hpp

Quelle

2009-11-12 22:13:09 nos

1

Viraptor-Lösung ist Sperren, gibt es keine multiple Producer/Multiple Consumer Lockless-Warteschlange algotihms im Bewusstsein.

Quelle

2010-01-19 07:12:45 ben

+0

Ich würde argumentieren, es ist Lockless - es enthält keine Mutexe. Es erfordert zwar eine Synchronisierung, aber auch alles, was Thread-sicher ist. Sie können nichts Sicheres tun, ohne die Möglichkeit eines erneuten Versuches (entweder die Operation selbst oder die Mutex-Sperre). – viraptor

+0

Tut mir leid, dass ich nicht nah genug überprüft habe, dass Ihre Lösung die typische Single-Producer-/Consumer-Cas-Warteschlange ist. Ich dachte, es wäre ein Spinlock. Um MULIPLE CONSUMER UND MULTIPLE PRODUCER zu machen, gab es jedoch keine wissenschaftlichen Arbeiten zu einer CAS-Lösung, die alle versagen. – ben

Verwandte Themen

 Verwandte Themen