Czy istnieje gotowa do produkcji kolejka bez blokad lub implementacja skrótu w C ++ [zamknięte]

80

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.

RED SOFT ADAIR
źródło
4
Program Visual Studio 2010 zawiera kolejkę wolną od blokady w <concurrent_queue.h>
Rick
1
I jest tam hash_map i unordered_map na code.msdn.com/concrtextras
Rick
2
Należy zauważyć, że, co ciekawe, termin „bez zamków” niekoniecznie oznacza, że ​​nie ma żadnych blokad. Zobacz en.wikipedia.org/wiki/Non-blocking_algorithm dla jednej definicji.
Kristopher Johnson,
8
Wow pytanie, jak rozwiązać powszechny, ale trudny problem w programowaniu wielowątkowym, który ma wiele rozwiązań, wywołał wiele dyskusji i zdobył mnóstwo głosów poparcia ... Potem 9 lat później zamykałeś to jako nie na temat. Dziękujemy za wkład w StackOverflow, NathanOliver, Sir E_net4 the Wise Downvoter, Jean-François Fabre, Machavity i gre_gor / s
muusbolla
1
Powiedziałbym, że ludzie, którzy zamknęli pytanie, prawdopodobnie go nie rozumieją.
Derf Skren

Odpowiedzi:

40

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).

Nova
źródło
boost :: lockfree :: queue działa tylko z typami POD i przez większość czasu nie jest całkiem przydatna. Jestem pewien, że gdyby istniał sposób na zapewnienie bardziej elastycznej struktury, boost by go wprowadził.
rahman
1
@rahman, gdzie jest z tym problem? Jeśli chcesz przekazać cokolwiek innego, zwłaszcza obiekty z nieprzezroczystymi, prawdopodobnie blokującymi efektami ubocznymi, nie rozumiesz całego celu projektowania bez blokowania.
Ichthyo
Why boost zapewnia kolejkę i stos bez blokady, oba oparte na połączonej liście. Ale nie zapewniają listy połączonej bez blokad?
Deqing
25

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.

Steve Gilham
źródło
1
Steve, interesują mnie również atomowe implementacje Boost, ale wydaje się, że znajdują się one w szczegółach / w Interprocess i nie są udokumentowane. Czy są one bezpieczne w użyciu? Dzięki!
Kim Gräsman
Znam bardzo dobrze artykuły Herba Suttera - gdzie znalazłeś źródła? Nie są publikowane przez DDJ ani na jego stronie (a może jestem niewidomy?).
RED SOFT ADAIR
1
Kod znajduje się w tych artykułach, zaczynając od odpowiednich drugich stron.
Steve Gilham
3
Jeśli chcesz prawdziwie pozbawiony blokad kodu, dla wielu producentów lub konsumentów, to odpadam. Przykład kolejki wielu producentów Suttera nie jest wolny od blokad - istnieje blokada do serializacji producentów i blokada do serializacji konsumentów. Jeśli możesz go znaleźć, też byłbym zainteresowany.
Steve Gilham
1
Istnieje projekt boost :: lockfree na tim.klingt.org/git?p=boost_lockfree.git ; na które możesz spojrzeć. Jednym z jego celów jest dostarczenie wersji nie :: details :: atomowych prymitywów.
sstock
17

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.
Cameron
źródło
2
Brzmi bardzo dobrze, ale potrzeba wielu producentów i / lub wielu konsumentów, aby wykorzystać rzeczywistą wielowątkowość.
RED SOFT ADAIR
2
@RED: Zależy od aplikacji. Pojedynczy producent / konsument był wszystkim, czego potrzebowałem, więc to wszystko, co zbudowałem ;-)
Cameron
@Cameron: Świetna rzecz! Czy porównałeś swoją kolejkę z szaleństwem Facebooka ProducerConsumerQueue ? Zrobiłem to za pomocą twojego kodu porównawczego i wydaje się, że radykalnie przewyższa zarówno twój RWQ, jak i SPSC Dmitry'ego. Jestem na OS X 10.8.3 z 3,06 GHz Core 2 Duo (T9900) i skompilowałem kod używając Clang z -O3. Zrobiłem to, ponieważ patrzę obecnie na kolejkę jednego producenta / pojedynczego konsumenta dla jednego z moich projektów i uważam twojego kandydata :)
André Neves
@ André: Właśnie sprawdziłem :-) Szaleństwo Facebooka jest nieco szybsze niż moje podczas usuwania z kolejki z pustej kolejki i nieco wolniejsze podczas usuwania z kolejki niepustej kolejki w jednym wątku. Wszystkie inne operacje mają prawie taką samą prędkość (było to z g ++ -O3 na maszynie wirtualnej). Jakiego rozmiaru używasz do kolejki szaleństwa? (Użyłem MAX.) Zarówno moje, jak i Dmitry rosną w miarę potrzeb, podczas gdy szaleństwo zostało naprawione - i oczywiście najszybsza operacja kolejkowania jest wtedy, gdy nie ma miejsca i po prostu się nie udaje. Patrząc na kod, wydaje się, że szaleństwo używa tych samych pomysłów co moje, ale bez możliwości zmiany rozmiaru.
Cameron
@ André: Och, zapomniałem wspomnieć jeszcze o jednej rzeczy - w przypadku mojego kodu porównawczego test porównawczy „surowe puste usunięcie” wykonuje zdecydowanie najwięcej iteracji (ponieważ jest tak prosty, że uzyskanie wymiernego wyniku wymaga więcej), aby nieproporcjonalnie wpłynąć na ostateczne „średnie operacje / operacje”. Mnożniki (i płaskie wartości taktowania) są na ogół bardziej przydatne. W każdym razie przy tych prędkościach wszystkie te kolejki będą dość szybkie, jeśli faktycznie zostaną użyte do czegoś bardziej mięsistego niż moje głupie syntetyczne testy porównawcze ;-)
Cameron
15

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

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!

André Neves
źródło
Mają też kolejkę MPMC. twierdzą, że jest to „opcjonalne blokowanie”. Wydaje się, że nie jest częścią ich zwykłej dokumentacji, nie jestem pewien, czy zaleca się go używać.
Rusty Shackleford
10

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.

RED SOFT ADAIR
źródło
4
100% poprawne. Do tego samego wyniku doszedłem z pomocą grupy dyskusyjnej comp.programming.threads. Jednym z powodów jest to, że obszar struktur danych wolnych od zamków jest polem minowym. Więc nawet komercyjne biblioteki, takie jak Intels, unikają tego.
Lothar
To jest C, nie C ++. Przeczytaj pytania przed głosowaniem w dół.
RED SOFT ADAIR
Przeprosiny. Zwracam uwagę, że SO nie pozwoli mi cofnąć mojego głosu, ponieważ wydaje mi się, że głosowanie jest zbyt stare. Myślę, że programiści SO muszą zrobić więcej - wydaje się, że dodają coraz więcej niekorzystnych zachowań.
3
Dlaczego ta odpowiedź ma tyle głosów pozytywnych. Pytanie można łatwo edytować. Lub może to być komentarz.
użytkownik
6

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

Nemanja Trifunovic
źródło
Wow - wydaje się, że to wszystko. Potrzebuję trochę czasu, aby to sprawdzić (obecnie nie mogę tego zrobić), ale wrócę do Ciebie.
RED SOFT ADAIR
Interlocked Singly Linked List to wspaniałe narzędzie, ale niestety nie jest to FIFO.
ali_bahoo
To nie jest właściwa lista, o ile pamiętam. Nie możesz odłączyć dowolnych elementów; jedyne, co możesz zrobić, to usunąć całą listę. Być może od tamtej pory to się
5

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.

Adisak
źródło
Dzięki za odpowiedź. Szukam rozwiązania / szablonu "gotowego do produkcji" w C ++. Nie chcę robić własnego. Znasz taką realizację?
RED SOFT ADAIR
4

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.

Marwan Burelle
źródło
3

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

PS: szukasz concurrent_queue i concurrent_hash_map

Edouard A.
źródło
6
Te nie są wolne od zamków. Zobacz software.intel.com/en-us/forums/intel-threading-building-blocks/…
RED SOFT ADAIR
1
Wiem, ze ścisłym poczuciem braku blokad, ale mimo to pomyślałem, że może to pomóc OP w jego problemie, ponieważ rzecz bez blokad to tylko szczegół implementacji. Wydawało mi się, że szuka kolekcji, które dobrze współpracują z jednoczesnym dostępem.
Edouard A.
Bez blokad to nie tylko szczegół implementacji. To zupełnie inna bestia.
arunmoezhi
1

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.

Tobias
źródło
Nie ma dla mnie sensu, dlaczego jest dostępny alokator pamięci. Po prostu użyj datastruktur z wewnętrznymi wskaźnikami (znasz stary dobry sposób, dopóki nie oszalałeś z kontenerami i utraconymi umiejętnościami, aby wdrożyć nawet proste Hashtables).
Lothar
1

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;
}
entuzjastyczny
źródło
4
To nie jest wolne od zamków. Jasne, że nie używa blokady zapewnionej przez system operacyjny, ale sposób, w jaki obraca się na (na przykład) „atomic <bool> consumerLock”, jest zdecydowanie blokowaniem. Jeśli wątek ulegnie awarii, gdy zawiera jeden z tych blokad, nie można już wykonać żadnej pracy. Nawet sam Herb tak mówi (myślę, że na stronie 4 tego artykułu).
James Caccese
0

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
    }

};
kędzierzawy geniusz
źródło