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.
Odpowiedzi:
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.
ja napisał kolejkę blokady wolne . Posiada funkcje ™:
Jest dostępny na GitHub w ramach uproszczonej licencji BSD (nie krępuj się!).
Ostrzeżenia:
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!
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.
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:
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
}
};