Startseite>Programmierbezogen>C/C++
Herunterladen

Xenium

xenium ist eine reine Header-Bibliothek, die eine Sammlung gleichzeitiger Datenstrukturen und Speicherrückgewinnungsalgorithmen bereitstellt. Die Datenstrukturen sind parametrisiert, sodass sie mit verschiedenen Wiederherstellungsschemata verwendet werden können (ähnlich wie die STL die Anpassung von Allokatoren ermöglicht).

  • Nur Kopfzeile
  • hochgradig anpassbar
  • Kein Initialisierungscode erforderlich
  • unterstützt dynamische Anzahl von Threads (keine feste Spezifikation der Kompilierzeit)

Weitere Einzelheiten finden Sie in der Dokumentation.

Dieses Projekt basiert auf meiner vorherigen Arbeit in https://github.com/mpoeter/emr

Anwendungsbeispiel 

# include < xenium/ramalhete_queue.hpp >
# include < xenium/reclamation/epoch_based.hpp >

struct msg { ... };

xenium::ramalhete_queue<
  std::unique_ptr<msg>,
  xenium::policy::reclaimer<xenium::reclamation::epoch_based<>>,
  xenium::policy::entries_per_node< 2048 >
> queue;

queue.push(std::make_unique<msg>());

std::unique_ptr<msg> data;
if (queue.try_pop(data)) {
    // do something with data
}

Datenstrukturen

Derzeit ist die Anzahl der bereitgestellten Datenstrukturen eher gering, da der Schwerpunkt bisher auf den Rekultivierungsschemata lag. Es ist jedoch geplant, in naher Zukunft mehrere weitere Datenstrukturen hinzuzufügen.

  • michael_scott_queue – eine unbegrenzte, sperrenfreie Multi-Produzenten-/Multi-Consumer-Warteschlange, vorgeschlagen von Michael und Scott [MS96].
  • ramalhete_queue – eine schnelle, unbegrenzte, sperrenfreie Multi-Produzenten-/Multi-Consumer-Warteschlange, vorgeschlagen von Ramalhete [Ram16].
  • vyukov_bounded_queue – eine begrenzte Multi-Producer/Multi-Consumer-FIFO-Warteschlange basierend auf der von Vyukov [Vyu10] vorgeschlagenen Version.
  • kirsch_kfifo_queue – eine unbegrenzte Multi-Produzenten/Multi-Consumer-k-FIFO-Warteschlange, vorgeschlagen von Kirsch et al. [KLP13].
  • kirsch_bounded_kfifo_queue – eine begrenzte Multi-Produzenten/Multi-Consumer-k-FIFO-Warteschlange, vorgeschlagen von Kirsch et al. [KLP13].
  • nikolaev_queue – eine unbegrenzte Multi-Produzenten/Multi-Consumer-Warteschlange, vorgeschlagen von Nikolaev [Nik19].
  • nikolaev_bounded_queue – eine begrenzte Multi-Produzenten/Multi-Consumer-Warteschlange, vorgeschlagen von Nikolaev [Nik19].
  • harris_michael_list_based_set – ein sperrfreier Container, der einen sortierten Satz einzigartiger Objekte enthält. Diese Datenstruktur basiert auf der von Michael [Mic02] vorgeschlagenen Lösung, die auf dem ursprünglichen Vorschlag von Harris [Har01] aufbaut.
  • harris_michael_hash_map – eine sperrenfreie Hash-Map basierend auf der von Michael [Mic02] vorgeschlagenen Lösung, die auf dem ursprünglichen Vorschlag von Harris [Har01] aufbaut.
  • chase_work_stealing_deque – eine Work-Stealing-Deque basierend auf dem Vorschlag von Chase und Lev [CL05].
  • vyukov_hash_map – eine gleichzeitige Hash-Map, die feinkörnige Sperren für Aktualisierungsvorgänge verwendet. Diese Implementierung ist stark von der von Vyukov [Vyu08] vorgeschlagenen Version inspiriert.
  • left_right – eine generische Implementierung des von Ramalhete und Correia [RC15] vorgeschlagenen LeftRight-Algorithmus.
  • seqlock – eine Implementierung der Sequenzsperre (oft auch als „sequentielle Sperre“ bezeichnet).

Rückgewinnungsprogramme

Die Implementierung der Rückgewinnungsschemata basiert auf einer angepassten Version der von Robison [Rob13] vorgeschlagenen Schnittstelle.

Die folgenden Sanierungsprogramme sind implementiert:

  • lock_free_ref_count [Val95, MS95]
  • hazard_pointer [Mic04]
  • hazard_eras [RC17]
  • quiescent_state_based
  • generic_epoch_based – Dies ist ein generalisierter epochenbasierter Reclaimer, der auf verschiedene Arten konfiguriert werden kann. Der Einfachheit halber sind die folgenden Aliase für die entsprechenden Konfigurationen vordefiniert.
    • epoch_based [Fra04]
    • new_epoch_based [HMBW07]
    • debra [Bro15]
  • stamp_it [PT18a, PT18b]

Gebäude

xenium ist eine reine Header-Bibliothek. Um sie zu verwenden, reicht es daher aus, den xenium-Ordner in Ihre Liste der Include-Verzeichnisse aufzunehmen. Es sind keine weiteren Bibliotheken von Drittanbietern erforderlich. Allerdings nutzt die Implementierung C++17-Funktionen, sodass ein Compiler mit ausreichender C++17-Unterstützung erforderlich ist. Die folgenden Compiler werden in den CI-Builds verwendet und werden daher bekanntermaßen unterstützt:

  • gcc9
  • clang10
  • Visual Studio 2019

Der Unit-Test erfordert googletest und die Benchmarks erfordern taocpp/json und taocpp/config . Diese Abhängigkeiten sind als Submodule enthalten, sodass die Unit-Tests und/oder Benchmarks wie folgt aufgebaut werden können: 

 git clone https://github.com/mpoeter/xenium.git && cd xenium
git submodule update --init --recursive
mkdir build && cd build
cmake ..
make gtest
make benchmark

Referenzen

[Bro15] Trevor Alexander Brown. Speicher für sperrenfreie Datenstrukturen zurückgewinnen: Es muss einen besseren Weg geben. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC) , Seiten 261–270. ACM, 2015.
[CL05] David Chase und Yossi Lev. Dynamische kreisförmige Arbeit stehlende Deque. In Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) , Seiten 21–28. ACM, 2005.
[Fra04] Keir Fraser. Praktische Schlossfreiheit . Doktorarbeit, University of Cambridge Computer Laboratory, 2004.
[Har01] Timothy L. Harris. Eine pragmatische Implementierung nicht blockierender verknüpfter Listen. In Proceedings of the 15th International Conference on Distributed Computing (DISC) , Seiten 300–314. Springer-Verlag, 2001.
[HMBW07] Thomas E. Hart, Paul E. McKenney, Angela Demke Brown und Jonathan Walpole. Leistung der Speicherrückgewinnung für sperrlose Synchronisierung. Journal of Parallel and Distributed Computing, 67(12):1270–1285, 2007.
[KLP13] Christoph Kirsch, Michael Lippautz und Hannes Payer. Schnelle und skalierbare k-FIFO-Warteschlangen ohne Sperren. In Proceedings of the International Conference on Parallel Computing Technologies (PaCT) , Seiten 208–223, Springer-Verlag, 2013.
[Mic02] Maged M. Michael. Leistungsstarke dynamische, sperrenfreie Hash-Tabellen und listenbasierte Sets. In Proceedings of the 14th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA) , Seiten 73–82. ACM, 2002.
[Mic04] Maged M. Michael. Gefahrenhinweise: Sichere Speicherrückgewinnung für sperrenfreie Objekte. IEEE Transactions on Parallel and Distributed Systems, 15(6):491–504, 2004.
[MS95] Maged M. Michael und Michael L. Scott. Korrektur einer Speicherverwaltungsmethode für sperrenfreie Datenstrukturen. Technischer Bericht, University of Rochester, 1995.
[MS96] Maged M. Michael und Michael L. Scott. Einfache, schnelle und praktische nicht-blockierende und blockierende gleichzeitige Warteschlangenalgorithmen. In Proceedings of the 15th Annual ACM Symposium on Principles of Distributed Computing (PODC) , Seiten 267–275. ACM, 1996.
[Nik19] Ruslan Nikolaev Eine skalierbare, tragbare und speichereffiziente, sperrenfreie Fifo-Warteschlange. In Proceedings of the 33rd International Symposium on Distributed Computing (DISC) , 2019.
[PT18a] Manuel Pöter und Jesper Larsson Träff. Kurze Ankündigung: Stamp-it, ein Thread-effizienteres, gleichzeitiges Speicherrückgewinnungsschema im C++-Speichermodell. In Proceedings of the 30th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) , Seiten 355–358. ACM, 2018.
[PT18b] Manuel Pöter und Jesper Larsson Träff. Stamp-it, ein Thread-effizienteres, gleichzeitiges Speicherrückgewinnungsschema im C++-Speichermodell. Technischer Bericht, 2018.
[Ram16] Pedro Ramalhete. FAAArrayQueue – MPMC-Warteschlange ohne Sperre (Teil 4 von 4). Blog, November 2016.
[RC15] Pedro Ramalhete und Andreia Correia. Links-Rechts – Eine Parallelitätskontrolltechnik mit wartefreien, ahnungslosen Lesevorgängen der Bevölkerung. Oktober 2015
[RC17] Pedro Ramalhete und Andreia Correia. Kurze Ankündigung: Gefahrenzeitalter – nicht blockierende Speicherrückgewinnung. In Proceedings of the 29th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) , Seiten 367–369. ACM, 2017.
[Rob13] Arch D. Robison. Richtlinienbasiertes Design für die sichere Zerstörung in gleichzeitigen Containern. Papier des C++-Standardisierungsausschusses, 2013.
[Val95] John D. Valois. Sperrfreie Datenstrukturen . Doktorarbeit, Rensselaer Polytechnic Institute, 1995.
[Vyu08] Dmitri Wjukow. Skalierbare Hash-Map. Google Groups-Beitrag, 2008.
[Vyu10] Dmitri Wjukow. Einfache und effiziente begrenzte MPMC-Warteschlange. Google Groups-Beitrag, 2010.
Expandieren
Zusätzliche Informationen
Ähnliche Anwendungen
Empfohlen für Sie
Ähnliche Nachrichten Alle