Начиная с версии 1.53, boost предоставляет набор структур данных без блокировок, включая очереди, стеки и очереди с одним источником/одним потребителем (т. е. кольцевые буферы).

Отправной точкой может быть любая из статей DDJ Херба Саттера либо для одного производителя и потребителя, либо для несколько. Код, который он дает (в строке, начиная со второй страницы каждой статьи), использует тип шаблона C++0x типа atomic‹T›; которые вы можете имитировать с помощью межпроцессной библиотеки Boost.

Код буста спрятан в недрах межпроцессной библиотеки, но, прочитав соответствующий заголовочный файл (atomic.hpp), реализации необходимых операций сравнения и замены на знакомых мне системах выглядят солидно.

Да!

Я написал очередь без блокировок. Он имеет Особенности ™:

• Полностью без ожидания (без циклов CAS)
• Сверхбыстро (более ста миллионов операций постановки/удаления из очереди в секунду)
• Использует семантику перемещения C++11.
• Растет по мере необходимости (но только если вы этого хотите)
• Управление памятью без блокировки для элементов (с использованием предварительно выделенных смежных блоков)
• Автономный (два заголовка плюс лицензия и файл readme)
• Компилируется под MSVC2010+, Intel ICC 13 и GCC 4.7.2 (и должен работать под любым полностью совместимым компилятором C++11)

Он доступен на GitHub по упрощенной лицензии BSD (не стесняйтесь разветвлять ее!).

Предостережения:

• Только для архитектуры с одним производителем и одним потребителем (т. е. два потока)
• Тщательно протестировано на x86 (-64) и должно работать на ARM, PowerPC и других процессорах, где выровненные целые числа собственного размера, а загрузка и сохранение указателей являются естественными атомарными, но не тестировались в полевых условиях на процессорах, отличных от x86 (если кто-то один, чтобы проверить это, дайте мне знать)
• Не знаю, нарушены ли какие-либо патенты (используйте на свой страх и риск и т. д.). Обратите внимание, что я разработал и реализовал его сам с нуля.

Facebook Folly, похоже, имеет структуры данных без блокировки, основанные на C++11 <atomic>:

• ProducerConsumerQueue с документацией и примером кода здесь.

• AtomicHashMap с документами и примерами кода здесь

Я осмелюсь сказать, что они в настоящее время используются в производстве, поэтому я думаю, что их можно безопасно использовать в других проектах.

Ваше здоровье!

Есть такая библиотека, но она на C.

Обтекание C++ должно быть простым.

http://www.liblfds.org

boost.lockfree — это попытка создать C++ реализации стека lockfree и классов fifo.

общедоступный репозиторий git

Проверив большинство данных ответов, я могу только констатировать:

Ответ НЕТ.

Нет такой вещи, которую можно было бы использовать прямо из коробки.

Самое близкое, что я знаю, это переплетенные односвязные списки Windows . Конечно, это только Windows.

Если у вас есть очередь/FIFO с несколькими производителями/одним потребителем, вы можете легко создать одну LockFree, используя SLIST или тривиальный стек Lock Free LIFO. Что вы делаете, так это имеете второй «частный» стек для потребителя (который также может быть выполнен как SLIST для простоты или любой другой модели стека, которую вы выберете). Потребитель выталкивает элементы из частного стека. Всякий раз, когда частный LIFO исчерпан, вы выполняете Flush, а не Pop из общего параллельного SLIST (захватывая всю цепочку SLIST), а затем проходите по сброшенному списку по порядку, помещая элементы в частный стек.

Это работает для одного производителя / одного потребителя и для нескольких производителей / одного потребителя.

Однако он не работает для случаев с несколькими потребителями (как с одним производителем, так и с несколькими производителями).

Кроме того, что касается хеш-таблиц, они являются идеальным кандидатом для «чередования», которое просто делит хэш на сегменты, имеющие блокировку для каждого сегмента кеша. Вот как это делает параллельная библиотека Java (используя 32 полосы). Если у вас есть облегченная блокировка чтения-записи, к хеш-таблице можно одновременно обращаться для одновременного чтения, и вы остановитесь только тогда, когда запись происходит на оспариваемые полосы (и, возможно, если вы разрешите увеличение хеш-таблицы).

Если вы создаете свои собственные, не забудьте чередовать свои блокировки с хеш-записями, а не помещать все свои блокировки в массив рядом друг с другом, чтобы свести к минимуму вероятность ложного совместного использования.

Я могу немного опоздать с этим.

Отсутствие решений (при заданном вопросе) в основном связано с важной проблемой в C++ (до C++0x/11): C++ не имеет (не имеет) модели параллельной памяти.

Теперь, используя std::atomic, вы можете управлять проблемами упорядочения памяти и иметь правильные операции сравнения и замены. Я написал для себя реализацию очереди без блокировки от Micheal&Scott (PODC96), используя C++11 и указатели опасности Micheal's (IEEE TPDS 2004), чтобы избежать проблем с ранним освобождением и ABA. Он работает нормально, но это быстрая и грязная реализация, и я не удовлетворен реальными показателями. Код доступен на битбакете: LockFreeExperiment

Также можно реализовать очередь без блокировки без указателей опасности с использованием CAS с двойными словами (но 64-битные версии будут возможны только на x86-64 с использованием cmpxchg16b), у меня есть сообщение в блоге об этом (с непроверенным кодом для очереди) здесь : Реализация общего двойного слова сравнить и поменять местами для x86/x86-64 (блог LSE.)

Мой собственный тест показывает, что очередь с двойной блокировкой (также в статье Майкла и Скотта 1996 г.) работает так же хорошо, как и очередь без блокировки (я не достиг достаточного количества состязаний, поэтому заблокированные структуры данных имеют проблемы с производительностью, но мой тест слишком легкий для сейчас), и параллельная очередь от Intel TBB кажется даже лучше (в два раза быстрее) для относительно небольшого числа (в зависимости от операционной системы, под FreeBSD 9, самая низкая оценка, которую я нашел до сих пор, это число составляет 8 потоков на i7 с 4 ht-ядрами и, следовательно, 8 логическими процессорами) потоков и имеет очень странное поведение (время выполнения моего простого теста переходит с секунд на часы!)

Еще одно ограничение для незаблокированных очередей в стиле STL: наличие итераторов в незаблокированной очереди не имеет смысла.

А затем появились Intel Threading Building Blocks. И какое-то время это было хорошо.

PS: вы ищете concurrent_queue и concurrent_hash_map

Насколько мне известно, в открытом доступе такого еще нет. Одна проблема, которую должен решить разработчик, заключается в том, что вам нужен распределитель памяти без блокировки, который существует, хотя я не могу найти ссылку прямо сейчас.

Нижеследующее взято из статьи Херба Саттера о параллельной очереди без блокировки http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1. Я внес некоторые изменения, такие как переупорядочение компилятора. Для компиляции этого кода нужен 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;
}

Я нашел другое решение, написанное на c:

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

Я написал это в какой-то момент, вероятно, еще в 2010 году, я уверен, что с помощью разных ссылок. Это мульти-производитель, один потребитель.

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
    }

};