Я довольно много искал в Google безблокировочную очередь в C ++. Я нашел код и несколько проб, но ничего, что мне удалось скомпилировать. Также приветствуется хеш-код без блокировки.

РЕЗЮМЕ: Пока у меня нет положительного ответа. Не существует «готовой к производству» библиотеки, и, что удивительно, ни одна из существующих библиотек не соответствует API контейнеров STL.

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

Отправной точкой могут быть статьи Херба Саттера DDJ либо для одного производителя и потребителя, либо для нескольких . Код, который он дает (встроенный, начиная со второй страницы каждой статьи), использует тип шаблона atomic <T> в стиле C ++ 0x; которые вы можете имитировать с помощью межпроцессной библиотеки 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 - это попытка создать на С ++ реализации lockfree stack и fifo классов.

публичный репозиторий git

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

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

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

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

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

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

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

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

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

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

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

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

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

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
    }

};