Trochę googlowałem, szukając kolejki bez blokad w C ++. Znalazłem kod i kilka prób - ale nic, co mogłem skompilować. Przydałby się również hash bez blokady.

PODSUMOWANIE: Jak dotąd nie mam pozytywnej odpowiedzi. Nie ma biblioteki „gotowej do produkcji” i zadziwiająco żadna z istniejących bibliotek nie jest zgodna z API kontenerów STL.

Począwszy od 1.53, boost udostępnia zestaw struktur danych bez blokad , w tym kolejki, stosy i kolejki jednego producenta / pojedynczego konsumenta (tj. Bufory pierścieniowe).

Punktem wyjścia byłyby artykuły DDJ Herba Suttera dla jednego producenta i konsumenta lub dla wielu . Kod, który podaje (zaczynając od drugiej strony każdego artykułu) używa szablonu typu atomic <T> w stylu C ++ 0x; które możesz naśladować za pomocą biblioteki międzyprocesowej Boost.

Kod przyspieszenia jest ukryty w głębi biblioteki międzyprocesowej, ale po przeczytaniu odpowiedniego pliku nagłówkowego (atomic.hpp) implementacje niezbędnych operacji porównania i zamiany w systemach, które znam, wyglądają jak dźwięk.

Tak!

ja napisał kolejkę blokady wolne . Posiada funkcje ™:

• Całkowicie bez czekania (bez pętli CAS)
• Super szybki (ponad sto milionów operacji umieszczania w kolejce / usuwania z kolejki na sekundę)
• Używa semantyki ruchu w języku C ++ 11
• Rośnie w razie potrzeby (ale tylko jeśli chcesz)
• Czy zarządzanie pamięcią bez blokad dla elementów (przy użyciu wstępnie przydzielonych ciągłych bloków)
• Samodzielny (dwa nagłówki oraz licencja i plik Readme)
• Kompiluje się pod MSVC2010 +, Intel ICC 13 i GCC 4.7.2 (i powinien działać pod każdym w pełni zgodnym kompilatorem C ++ 11)

Jest dostępny na GitHub w ramach uproszczonej licencji BSD (nie krępuj się!).

Ostrzeżenia:

• Tylko dla architektury jednego producenta dla jednego konsumenta (tj. Dwa wątki)
• Dokładnie przetestowany na procesorach x86 (-64) i powinien działać na procesorach ARM, PowerPC i innych, w których wyrównane liczby całkowite o rodzimym rozmiarze oraz ładowanie i przechowywanie wskaźników są naturalnie atomowe, ale nie zostały przetestowane w terenie na procesorach innych niż x86 (jeśli ktoś jeden do przetestowania, daj mi znać)
• Nie mam pojęcia, czy naruszane są patenty (korzystasz na własne ryzyko itp.). Zwróć uwagę, że sam zaprojektowałem i wdrożyłem go od podstaw.

Wygląda na to, że Facebook's Folly ma struktury danych bez blokad oparte na C ++ 11 <atomic>:

• ProducerConsumerQueue z dokumentacją i przykładowym kodem tutaj .

• AtomicHashMap z dokumentacją i przykładowym kodem tutaj

Odważę się powiedzieć, że są one obecnie używane w produkcji, więc myślę, że można by je bezpiecznie wykorzystać w innych projektach.

Twoje zdrowie!

Jest taka biblioteka, ale jest w C.

Zawijanie do C ++ powinno być proste.

http://www.liblfds.org

Po sprawdzeniu większości udzielonych odpowiedzi mogę jedynie stwierdzić:

Odpowiedź brzmi NIE .

Nie ma takiego prawa, którego można by użyć zaraz po wyjęciu z pudełka.

boost.lockfree to próba stworzenia implementacji w c ++ stosu lockfree i klas FIFO.

publiczne repozytorium git

Najbliższą rzeczą, o której jestem świadomy, są listy pojedynczo połączone w systemie Windows Interlocked . Oczywiście jest to tylko system Windows.

Jeśli masz kolejkę / FIFO dla wielu producentów / jednego konsumenta, możesz łatwo utworzyć jedną LockFree za pomocą SLIST lub trywialnego stosu LIFO bez blokady. To, co robisz, to posiadanie drugiego „prywatnego” stosu dla konsumenta (który można również wykonać jako SLISTA dla uproszczenia lub dowolny inny wybrany model stosu). Konsument zdejmuje przedmioty z prywatnego stosu. Za każdym razem, gdy prywatne LIFO jest wyrzucane, zamiast wyskakiwania ze współdzielonego, równoczesnego SLIST, wykonujesz Flush zamiast wyskakiwania (chwytając cały łańcuch SLIST), a następnie przechodź po liście Flushed w kolejności, wpychając elementy na prywatny stos.

Działa to w przypadku jednego producenta / pojedynczego konsumenta i wielu producentów / jednego konsumenta.

Jednak nie działa w przypadku wielu konsumentów (z jednym lub wieloma producentami).

Ponadto, jeśli chodzi o tablice skrótów, są one idealnym kandydatem do „rozłożenia”, czyli podzielenia skrótu na segmenty z blokadą na segmenty pamięci podręcznej. W ten sposób robi to biblioteka współbieżna Java (używając 32 pasków). Jeśli masz lekką blokadę czytnika-zapisującego, do tablicy skrótów można uzyskać dostęp jednocześnie w celu jednoczesnych odczytów, a zatrzymanie się nastąpi tylko wtedy, gdy zapis odbywa się na spornych paskach (i być może, jeśli pozwolisz na powiększenie tabeli skrótów).

Jeśli wyrzucasz własne, upewnij się, że przeplatasz swoje zamki z wpisami z haszowaniem, zamiast umieszczać wszystkie swoje zamki w tablicy obok siebie, aby zmniejszyć prawdopodobieństwo fałszywego udostępniania.

Mogę się trochę spóźnić.

Brak rozwiązań (na zadane pytanie) wynika głównie z ważnej kwestii w C ++ (przed C ++ 0x / 11): C ++ nie ma (nie ma) modelu pamięci współbieżnej.

Teraz, używając std :: atomic, możesz kontrolować problemy z porządkowaniem pamięci i wykonywać odpowiednie operacje porównania i wymiany. Napisałem sobie implementację kolejki bez blokad Micheal & Scott (PODC96) przy użyciu C ++ 11 i wskaźników zagrożenia Micheala (IEEE TPDS 2004), aby uniknąć problemów z wczesnym wolnym i ABA. Działa dobrze, ale jest to szybka i brudna implementacja i nie jestem zadowolony z rzeczywistych wyników. Kod jest dostępny na Bitbucket: LockFreeExperiment

Możliwe jest również zaimplementowanie kolejki bez blokad bez wskaźników zagrożenia przy użyciu podwójnych słów CAS (ale wersje 64-bitowe będą możliwe tylko na x86-64 przy użyciu cmpxchg16b), mam na ten temat wpis na blogu (z nieprzetestowanym kodem kolejki) tutaj : Implementacja ogólnego porównywania i zamiany podwójnych słów dla x86 / x86-64 (blog LSE).

Mój własny test porównawczy pokazuje mi, że podwójnie zablokowana kolejka (również w artykule Micheal & Scott z 1996 r.) Działa równie dobrze jak ta wolna od blokady (nie osiągnąłem wystarczającej rywalizacji, aby zablokowane struktury danych miały problemy z wydajnością, ale moje wzorce są zbyt lekkie dla teraz), a kolejka równoległa z TBB Intela wydaje się jeszcze lepsza (dwa razy szybciej) dla stosunkowo niewielkiej liczby (w zależności od systemu operacyjnego, pod FreeBSD 9, najniższe ograniczenie, jakie do tej pory znalazłem, ta liczba to 8 wątków na i7 z 4 rdzeniami ht, a więc 8 logicznymi procesorami) wątków i mają bardzo dziwne zachowanie (czas wykonania mojego prostego testu porównawczego zmienia się z sekund na godziny!)

Kolejne ograniczenia dotyczące kolejek bez blokad w stylu STL: posiadanie iteratorów w kolejce bez blokad nie ma sensu.

A potem pojawiły się bloki konstrukcyjne Intel Threading . I przez jakiś czas było dobrze.

PS: szukasz concurrent_queue i concurrent_hash_map

O ile wiem, nie ma jeszcze takiej rzeczy publicznie dostępnej. Jedną z kwestii, którą musi rozwiązać implementator, jest to, że potrzebny jest alokator pamięci bez blokad, który istnieje, chociaż nie mogę teraz znaleźć łącza.

Poniższy tekst pochodzi z artykułu Herba Suttera na temat kolejki darmowej blokady równoległej http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1 . Dokonałem pewnych zmian, takich jak zmiana kolejności elementów kompilatora. Do skompilowania tego kodu potrzeba GCC v4.4 +.

#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;
}

Znalazłem inne rozwiązanie napisane w c:

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

Napisałem to w pewnym momencie prawdopodobnie w 2010 roku, na pewno z pomocą różnych odniesień. To wielu producentów Pojedynczy konsument.

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
    }

};