He estado buscando en Google bastante una cola sin bloqueos en C ++. Encontré algo de código y algunas pruebas, pero nada que pudiera compilar. Un hash sin candados también sería bienvenido.

RESUMEN: Hasta ahora no tengo una respuesta positiva. No hay una biblioteca "lista para producción" y, sorprendentemente, ninguna de las bibliotecas existentes cumple con la API de los contenedores STL.

A partir de la versión 1.53, boost proporciona un conjunto de estructuras de datos sin bloqueo , que incluyen colas, pilas y colas de un solo productor / un solo consumidor (es decir, búferes de anillo).

El punto de partida sería cualquiera de los artículos DDJ de Herb Sutter para un solo productor y consumidor o para varios . El código que da (en línea comenzando en la segunda página de cada artículo) usa el tipo de plantilla atómica <T> estilo C ++ 0x; que puede imitar utilizando la biblioteca entre procesos de Boost.

El código de impulso está enterrado en las profundidades de la biblioteca entre procesos, pero después de leer el archivo de encabezado apropiado (atomic.hpp), las implementaciones para las operaciones necesarias de comparación e intercambio en los sistemas con los que estoy familiarizado parecen sólidas.

¡Si!

Yo escribí una cola sin bloqueo . Tiene Features ™:

• Totalmente sin espera (sin bucles CAS)
• Súper rápido (más de cien millones de operaciones de puesta en cola / retirada de cola por segundo)
• Utiliza semántica de movimiento de C ++ 11
• Crece según sea necesario (pero solo si lo desea)
• Gestiona la memoria sin bloqueos para los elementos (utilizando bloques contiguos preasignados)
• Independiente (dos encabezados más una licencia y un archivo Léame)
• Se compila bajo MSVC2010 +, Intel ICC 13 y GCC 4.7.2 (y debería funcionar con cualquier compilador compatible con C ++ 11)

Está disponible en GitHub bajo la licencia BSD simplificada (¡no dude en bifurcarlo!).

Advertencias:

• Solo para arquitectura de un solo productor y consumidor (es decir, dos subprocesos)
• Probado exhaustivamente en x86 (-64), y debería funcionar en ARM, PowerPC y otras CPU donde los enteros de tamaño nativo alineados y las cargas de puntero y los almacenes son naturalmente atómicos, pero no se han probado en el campo en CPU que no son x86 (si alguien tiene uno para probarlo avísame)
• No tengo idea de si se ha infringido alguna patente (utilice bajo su propio riesgo, etc.). Tenga en cuenta que lo diseñé e implementé yo mismo desde cero.

Folly de Facebook parece tener estructuras de datos sin bloqueo basadas en C ++ 11 <atomic>:

• ProducerConsumerQueue con documentos y código de ejemplo aquí .

• AtomicHashMap con documentos y código de ejemplo aquí

Me atrevería a decir que estos se utilizan actualmente en producción, por lo que supongo que podrían utilizarse con seguridad en otros proyectos.

¡Salud!

Existe tal biblioteca, pero está en C.

La conversión a C ++ debería ser sencilla.

http://www.liblfds.org

Después de haber verificado la mayoría de las respuestas dadas, solo puedo decir:

La respuesta es NO .

No existe tal cosa correcta que pueda usarse nada más sacarlo de la caja.

boost.

repositorio público de git

Lo más parecido que conozco son las listas enlazadas individualmente entrelazadas de Windows . Por supuesto, solo es Windows.

Si tiene una cola / FIFO de múltiples productores / consumidores individuales, puede crear fácilmente un LockFree usando SLIST o una pila LIFO de Lock Free trivial. Lo que hace es tener una segunda pila "privada" para el consumidor (que también se puede hacer como una SLIST para simplificar o cualquier otro modelo de pila que elija). El consumidor saca artículos de la pila privada. Siempre que se agota el LIFO privado, realiza un Flush en lugar de Pop off el SLIST concurrente compartido (agarrando toda la cadena SLIST) y luego recorre la lista Flushed en orden empujando los elementos a la pila privada.

Eso funciona para un solo productor / un solo consumidor y para múltiples productores / un solo consumidor.

Sin embargo, no funciona para casos de consumidores múltiples (ya sea con un solo productor o con múltiples productores).

Además, en lo que respecta a las tablas hash, son un candidato ideal para la "creación de bandas", que es simplemente dividir el hash en segmentos que tienen un bloqueo por segmentos de la caché. Así es como lo hace la biblioteca concurrente de Java (usando 32 rayas). Si tiene un bloqueo de lectura-escritura liviano, se puede acceder a la tabla hash simultáneamente para lecturas simultáneas y solo se detendrá cuando la escritura se produzca en franjas impugnadas (y posiblemente si permite el crecimiento de la tabla hash).

Si lanza el suyo, asegúrese de intercalar sus bloqueos con las entradas hash en lugar de poner todos sus bloqueos en una matriz uno al lado del otro para que sea menos probable que comparta información falsa.

Puede que llegue un poco tarde a esto.

La ausencia de soluciones (en la pregunta que se hizo) se debe principalmente a un problema importante en C ++ (antes de C ++ 0x / 11): C ++ no tiene (tiene) ningún modelo de memoria concurrente.

Ahora, con std :: atomic, puede controlar los problemas de ordenación de la memoria y realizar operaciones adecuadas de comparación e intercambio. Yo mismo escribí una implementación de la cola sin bloqueo de Micheal & Scott (PODC96) usando C ++ 11 y los Hazard Pointers de Micheal (IEEE TPDS 2004) para evitar problemas tempranos libres y ABA. Funciona bien, pero es una implementación rápida y sucia y no estoy satisfecho con el rendimiento real. El código está disponible en bitbucket: LockFreeExperiment

También es posible implementar una cola sin bloqueo sin punteros de peligro usando CAS de palabras dobles (pero las versiones de 64 bits solo serán posibles en x86-64 usando cmpxchg16b), tengo una publicación de blog sobre eso (con código no probado para la cola) aquí : Implementación de comparación e intercambio genérico de palabras dobles para x86 / x86-64 (blog de LSE).

Mi propio punto de referencia me muestra que la cola de doble bloqueo (también en el documento de Micheal & Scott 1996) funciona tan bien como la que no tiene bloqueo (no he alcanzado la suficiente contención para que las estructuras de datos bloqueadas tengan problemas de rendimiento, pero mi banco es demasiado liviano para ahora) y la cola simultánea del TBB de Intel parece incluso mejor (dos veces más rápido) para un número relativamente pequeño (dependiendo del sistema operativo, en FreeBSD 9, el límite más bajo que he encontrado hasta ahora, este número es de 8 subprocesos en un i7 con 4 ht-core, y por lo tanto 8 CPU lógicas) de subprocesos y tienen un comportamiento muy extraño (¡el tiempo de ejecución de mi punto de referencia simple se mueve de segundos a horas!)

Otras limitaciones sobre las colas sin bloqueo siguiendo el estilo STL: tener iteradores en la cola sin bloqueo no tiene sentido.

Y luego llegaron Intel Threading Building Blocks . Y durante un tiempo estuvo bien.

PD: está buscando concurrent_queue y concurrent_hash_map

Hasta donde yo sé, todavía no existe tal cosa disponible públicamente. Un problema que debe resolver un implementador es que necesita un asignador de memoria sin bloqueo, que existe, aunque parece que no puedo encontrar el enlace en este momento.

Lo siguiente es del artículo de Herb Sutter sobre la cola sin bloqueo simultáneo http://www.drdobbs.com/parallel/writing-a-generalized-concurrent-queue/211601363?pgno=1 . He realizado algunos cambios, como el reordenamiento del compilador. Se necesita GCC v4.4 + para compilar este código.

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

Encontré otra solución escrita en c:

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

Escribí esto en algún momento probablemente en 2010, estoy seguro con la ayuda de diferentes referencias. Consumidor único de múltiples productores.

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
    }

};