Ich habe ziemlich viel nach einer Warteschlange ohne Sperren in C ++ gegoogelt. Ich habe Code und einige Versuche gefunden - aber nichts, was ich kompilieren konnte. Ein sperrfreier Hash wäre ebenfalls willkommen.

ZUSAMMENFASSUNG: Bisher habe ich keine positive Antwort. Es gibt keine "produktionsbereite" Bibliothek, und erstaunlicherweise entspricht keine der vorhandenen Bibliotheken der API von STL-Containern.

Ab 1.53 bietet Boost eine Reihe sperrenfreier Datenstrukturen , einschließlich Warteschlangen, Stacks und Warteschlangen für einzelne Produzenten / einzelne Konsumenten (dh Ringpuffer).

Ausgangspunkt wäre entweder der DDJ-Artikel von Herb Sutter für einen einzelnen Produzenten und Verbraucher oder mehrere . Der von ihm angegebene Code (inline ab der zweiten Seite jedes Artikels) verwendet den atomaren <T> -Vorlagentyp im C ++ 0x-Stil. die Sie mithilfe der Boost-Interprozessbibliothek imitieren können.

Der Boost-Code ist in den Tiefen der Interprozessbibliothek vergraben, aber nachdem ich die entsprechende Header-Datei (atomic.hpp) durchgelesen habe, sind die Implementierungen für die erforderlichen Vergleichs- und Austauschvorgänge auf den Systemen, mit denen ich vertraut bin, gut.

Ja!

Ich habe eine sperrenfreie Warteschlange geschrieben . Es hat Features ™:

• Völlig wartungsfrei (keine CAS-Schleifen)
• Superschnell (über hundert Millionen Enqueue / Dequeue-Vorgänge pro Sekunde)
• Verwendet die C ++ 11-Verschiebungssemantik
• Wächst nach Bedarf (aber nur, wenn Sie es möchten)
• Führt eine sperrfreie Speicherverwaltung für die Elemente durch (unter Verwendung vorab zugewiesener zusammenhängender Blöcke)
• Standalone (zwei Header plus Lizenz und Readme)
• Kompiliert unter MSVC2010 +, Intel ICC 13 und GCC 4.7.2 (und sollte unter jedem C ++ 11-kompatiblen Compiler funktionieren)

Es ist auf GitHub unter der vereinfachten BSD-Lizenz verfügbar (zögern Sie nicht!).

Vorsichtsmaßnahmen:

• Nur für Single-Producer-Single-Consumer-Architektur (dh zwei Threads)
• Gründlich getestet auf x86 (-64) und sollte auf ARM, PowerPC und anderen CPUs funktionieren, bei denen ausgerichtete Ganzzahlen und Zeigerladevorgänge und -speicher von Natur aus atomar sind, aber nicht auf Nicht-x86-CPUs getestet wurden (falls jemand dies getan hat) eine, um es zu testen, lass es mich wissen)
• Keine Ahnung, ob Patente verletzt werden (Verwendung auf eigenes Risiko usw.). Beachten Sie, dass ich es selbst von Grund auf neu entworfen und implementiert habe.

Facebooks Folly scheint sperrfreie Datenstrukturen zu haben, die auf C ++ 11 basieren <atomic>:

• ProducerConsumerQueue mit Dokumenten und Beispielcode hier .

• AtomicHashMap mit Dokumenten und Beispielcode hier

Ich würde es wagen zu sagen, dass diese derzeit in der Produktion verwendet werden, also denke ich, dass sie sicher in anderen Projekten verwendet werden könnten.

Prost!

Es gibt eine solche Bibliothek, aber sie ist in C.

Das Umschließen auf C ++ sollte unkompliziert sein.

http://www.liblfds.org

Nachdem ich die meisten der gegebenen Antworten überprüft habe, kann ich nur sagen:

Die Antwort lautet NEIN .

Es gibt kein solches Recht, das sofort verwendet werden könnte.

boost.lockfree ist ein Versuch, C ++ - Implementierungen von lockfree-Stack- und Fifo-Klassen zu erstellen.

öffentliches Git-Repository

Das nächste, was mir bekannt ist, sind Windows Interlocked Singly Linked Lists . Natürlich ist es nur Windows.

Wenn Sie eine Warteschlange / ein FIFO mit mehreren Produzenten / Einzelkonsumenten haben, können Sie mit SLIST oder einem trivialen Lock Free LIFO-Stack ganz einfach ein LockFree erstellen. Sie haben einen zweiten "privaten" Stapel für den Verbraucher (der der Einfachheit halber auch als SLIST oder für jedes andere von Ihnen ausgewählte Stapelmodell verwendet werden kann). Der Verbraucher nimmt Artikel vom privaten Stapel. Immer wenn das private LIFO überfordert ist, führen Sie einen Flush durch, anstatt die gemeinsam genutzte gleichzeitige SLIST (Popup der gesamten SLIST-Kette) zu entfernen und dann die Flushed-Liste der Reihe nach zu durchsuchen, um Elemente auf den privaten Stapel zu verschieben.

Das funktioniert für Einzelproduzenten / Einzelverbraucher und für Mehrfachproduzenten / Einzelverbraucher.

Es funktioniert jedoch nicht für Fälle mit mehreren Verbrauchern (entweder mit Einzelproduzenten oder mit mehreren Produzenten).

Was Hash-Tabellen angeht, sind sie auch ein idealer Kandidat für "Striping", bei dem der Hash nur in Segmente mit einer Sperre pro Segment des Caches unterteilt wird. So macht es die Java Concurrent Library (mit 32 Streifen). Wenn Sie über eine leichte Lese- / Schreibsperre verfügen, kann gleichzeitig auf die Hash-Tabelle zugegriffen werden, um sie gleichzeitig zu lesen. Sie werden nur dann blockiert, wenn auf umstrittenen Streifen geschrieben wird (und möglicherweise, wenn Sie die Hash-Tabelle vergrößern möchten).

Wenn Sie Ihre eigenen würfeln, stellen Sie sicher, dass Sie Ihre Sperren mit den Hash-Einträgen verschachteln, anstatt alle Ihre Sperren in einem Array nebeneinander zu platzieren, damit die Wahrscheinlichkeit einer falschen Freigabe geringer ist.

Ich komme vielleicht etwas spät.

Das Fehlen von Lösungen (bei der Frage wurde gestellt) ist hauptsächlich auf ein wichtiges Problem in C ++ (vor C ++ 0x / 11) zurückzuführen: C ++ hat (hat) kein gleichzeitiges Speichermodell.

Mit std :: atomic können Sie jetzt Probleme mit der Speicherreihenfolge steuern und ordnungsgemäße Vergleichs- und Austauschvorgänge ausführen. Ich habe mir eine Implementierung der sperrenfreien Warteschlange (PODC96) von Micheal & Scott unter Verwendung von C ++ 11 und der Gefahrenzeiger von Micheal (IEEE TPDS 2004) geschrieben, um frühzeitige freie und ABA-Probleme zu vermeiden. Es funktioniert gut, aber es ist eine schnelle und schmutzige Implementierung und ich bin mit den tatsächlichen Leistungen nicht zufrieden. Code ist auf bitbucket verfügbar: LockFreeExperiment

Es ist auch möglich, eine sperrenfreie Warteschlange ohne Gefahrenzeiger mit Doppelwort-CAS zu implementieren (64-Bit-Versionen sind jedoch nur auf x86-64 mit cmpxchg16b möglich). Ich habe hier einen Blog-Beitrag darüber (mit nicht getestetem Code für die Warteschlange) : Implementierung eines generischen Doppelwortvergleichs und -austauschs für x86 / x86-64 (LSE-Blog.)

Mein eigener Benchmark zeigt mir, dass die doppelt gesperrte Warteschlange (ebenfalls in Micheal & Scott 1996) genauso gut funktioniert wie die sperrenfreie (ich habe nicht genügend Konflikte erreicht, sodass gesperrte Datenstrukturen Leistungsprobleme aufweisen, aber meine Bank ist zu leicht für jetzt) ​​und die gleichzeitige Warteschlange von Intels TBB scheint für eine relativ kleine Anzahl noch besser (zweimal schneller) zu sein (je nach Betriebssystem unter FreeBSD 9, der niedrigsten Grenze, die ich bisher gefunden habe, beträgt diese Anzahl 8 Threads auf einer i7 mit 4 ht-Core und damit 8 logischen CPUs) von Threads und sehr seltsamem Verhalten (Ausführungszeit meines einfachen Benchmarks von Sekunden auf Stunden verschieben!)

Eine weitere Einschränkung bei Warteschlangen ohne Sperren, die dem STL-Stil folgen: Iteratoren in Warteschlangen ohne Sperren zu haben, hat keinen Sinn.

Und dann kamen Intel Threading Building Blocks . Und eine Zeit lang war es gut.

PS: Sie suchen nach concurrent_queue und concurrent_hash_map

Nach meinem besten Wissen gibt es so etwas noch nicht öffentlich. Ein Problem, das ein Implementierer lösen muss, ist, dass Sie einen sperrfreien Speicherzuweiser benötigen, der vorhanden ist, obwohl ich den Link derzeit nicht zu finden scheint.

Das Folgende stammt aus dem Artikel von Herb Sutter über die Warteschlange ohne gleichzeitige Sperre http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1 . Ich habe einige Änderungen vorgenommen, z. B. das Neuordnen von Compilern. Man benötigt GCC v4.4 +, um diesen Code zu kompilieren.

#include <atomic>
#include <iostream>
using namespace std;

//compile with g++ setting -std=c++0x

#define CACHE_LINE_SIZE 64

template <typename T>
struct LowLockQueue {
private:
    struct Node {
    Node( T* val ) : value(val), next(nullptr) { }
    T* value;
    atomic<Node*> next;
    char pad[CACHE_LINE_SIZE - sizeof(T*)- sizeof(atomic<Node*>)];
    };
    char pad0[CACHE_LINE_SIZE];

// for one consumer at a time
    Node* first;

    char pad1[CACHE_LINE_SIZE
          - sizeof(Node*)];

// shared among consumers
    atomic<bool> consumerLock;

    char pad2[CACHE_LINE_SIZE
          - sizeof(atomic<bool>)];

// for one producer at a time
    Node* last;

    char pad3[CACHE_LINE_SIZE
          - sizeof(Node*)];

// shared among producers
    atomic<bool> producerLock;

    char pad4[CACHE_LINE_SIZE
          - sizeof(atomic<bool>)];

public:
    LowLockQueue() {
    first = last = new Node( nullptr );
    producerLock = consumerLock = false;
    }
    ~LowLockQueue() {
    while( first != nullptr ) {      // release the list
        Node* tmp = first;
        first = tmp->next;
        delete tmp->value;       // no-op if null
        delete tmp;
    }
    }

    void Produce( const T& t ) {
    Node* tmp = new Node( new T(t) );
    asm volatile("" ::: "memory");                            // prevent compiler reordering
    while( producerLock.exchange(true) )
        { }   // acquire exclusivity
    last->next = tmp;         // publish to consumers
    last = tmp;             // swing last forward
    producerLock = false;       // release exclusivity
    }

    bool Consume( T& result ) {
    while( consumerLock.exchange(true) )
        { }    // acquire exclusivity
    Node* theFirst = first;
    Node* theNext = first-> next;
    if( theNext != nullptr ) {   // if queue is nonempty
        T* val = theNext->value;    // take it out
        asm volatile("" ::: "memory");                            // prevent compiler reordering
        theNext->value = nullptr;  // of the Node
        first = theNext;          // swing first forward
        consumerLock = false;             // release exclusivity
        result = *val;    // now copy it back
        delete val;       // clean up the value
        delete theFirst;      // and the old dummy
        return true;      // and report success
    }
    consumerLock = false;   // release exclusivity
    return false;                  // report queue was empty
    }
};

int main(int argc, char* argv[])
{
    //Instead of this Mambo Jambo one can use pthreads in Linux to test comprehensively
LowLockQueue<int> Q;
Q.Produce(2);
Q.Produce(6);

int a;
Q.Consume(a);
cout<< a << endl;
Q.Consume(a);
cout<< a << endl;

return 0;
}

Ich habe eine andere Lösung in c gefunden:

http://www.ddj.com/hpc-high-performance-computing/219500200

Ich habe das wahrscheinlich 2010 geschrieben, ich bin mir sicher, mit Hilfe verschiedener Referenzen. Es Multi-Produzent Einzelverbraucher.

template <typename T>
class MPSCLockFreeQueue 
{
private:
    struct Node 
    {
        Node( T val ) : value(val), next(NULL) { }
        T value;
        Node* next;
    };
    Node * Head;               
    __declspec(align(4)) Node * InsertionPoint;  //__declspec(align(4)) forces 32bit alignment this must be changed for 64bit when appropriate.

public:
    MPSCLockFreeQueue() 
    {
        InsertionPoint = new Node( T() );
        Head = InsertionPoint;
    }
    ~MPSCLockFreeQueue() 
    {
        // release the list
        T result;
        while( Consume(result) ) 
        {   
            //The list should be cleaned up before the destructor is called as there is no way to know whether or not to delete the value.
            //So we just do our best.
        }
    }

    void Produce( const T& t ) 
    {
        Node * node = new Node(t);
        Node * oldInsertionPoint = (Node *) InterLockedxChange((volatile void **)&InsertionPoint,node);
        oldInsertionPoint->next = node;
    }

    bool Consume( T& result ) 
    {
        if (Head->next)
        {
            Node * oldHead = Head;
            Head = Head->next;
            delete oldHead;
            result = Head->value;
            return true;
        }       
        return false;               // else report empty
    }

};