¿Existe una implementación de cola FIFO optimista sin bloqueo?

Question

¿Hay alguna C aplicación ++ (códigos fuente) de "optmistic approach to lock-free FIFO queues" algorithm?

Answer 1

Herb Sutter cubre sólo una cola, como parte de su columna Concurency eficaz en el Dr. Dobbs Journal.

Writing Lock-Free Code: A Corrected Queue

Answer 2

Si' Estamos buscando una buena implementación de cola libre de bloqueo tanto Microsoft Visual Studio 2010 & Los bloques de construcción de subprocesos de Intel contienen una buena cola LF que es similar al papel.

Here's a link to the one in VC 2010

Answer 3

Quiero concluir la respuesta dada por greyfade, que se basa en http://www.drdobbs.com/high-performance-computing/212201163 (la última parte del artículo), el código optimizado sería (con algunas modificaciones para adaptarse a mi nombramiento y convenciones de codificación) : `

template <typename T> class LFQueue { 
private: 
    struct LFQNode { 
     LFQNode(T* val) : value(val), next(nullptr) { } 
     T* value; 
     AtomicPtr<LFQNode> next; 
     char pad[CACHE_LINE_SIZE - sizeof(T*) - sizeof(AtomicPtr<LFQNode>)]; 
    }; 

    char pad0[CACHE_LINE_SIZE]; 
    LFQNode* first;     // for one consumer at a time 
    char pad1[CACHE_LINE_SIZE - sizeof(LFQNode*)]; 
    InterlockedFlag consumerLock; // shared among consumers 
    char pad2[CACHE_LINE_SIZE - sizeof(InterlockedFlag)]; 
    LFQNode* last;     // for one producer at a time 
    char pad3[CACHE_LINE_SIZE - sizeof(LFQNode*)]; 
    InterlockedFlag producerLock; // shared among producers 
    char pad4[CACHE_LINE_SIZE - sizeof(InterlockedFlag)]; 
public: 
    LFQueue() { 
     first = last = new LFQNode(nullptr); // no more divider 
     producerLock = consumerLock = false; 
    } 

    ~LFQueue() { 
     while(first != nullptr) { 
      LFQNode* tmp = first; 
      first = tmp->next; 
      delete tmp; 
     } 
    } 

    bool pop(T& result) { 
     while(consumerLock.set(true)) 
     { }        // acquire exclusivity 
     if(first->next != nullptr) { // if queue is nonempty 
      LFQNode* oldFirst = first; 
      first = first->next; 
      T* value = first->value; // take it out 
      first->value = nullptr;  // of the Node 
      consumerLock = false;  // release exclusivity 
      result = *value;   // now copy it back 
      delete value;    // and clean up 
      delete oldFirst;   // both allocations 
      return true;    // and report success 
     } 
     consumerLock = false;   // release exclusivity 
     return false;     // queue was empty 
    } 

    bool push(const T& t) { 
     LFQNode* tmp = new LFQNode(t); // do work off to the side 
     while(producerLock.set(true)) 
     { }        // acquire exclusivity 
     last->next = tmp;    // A: publish the new item 
     last = tmp;      // B: not "last->next" 
     producerLock = false;   // release exclusivity 
     return true; 
    } 
}; 

`

otra pregunta es ¿cómo se define CACHE_LINE_SIZE? es diferente en CPU alguna vez, ¿verdad?

Answer 4

Aquí está mi implementación de un FIFO sin bloqueo.

Asegúrese de que cada elemento de T sea un múltiplo de 64 bytes (el tamaño de la línea de caché en las CPU Intel) para evitar el uso compartido falso.

Este código se compila con gcc/mingw y debe compilarse con clang. Está optimizado para 64 bits, por lo que para que se ejecute en 32 bits necesitaría algunas refactorizaciones.

https://github.com/vovoid/vsxu/blob/master/engine/include/vsx_fifo.h

vsx_fifo<my_struct, 512> my_fifo; 

remitente:

my_struct my_struct_inst; 
... fill it out ... 
while (!my_fifo.produce(my_struct_inst)) {} 

receptor:

my_struct my_struct_recv; 
while(my_fifo.consume(my_struct_recv)) 
{ 
    ...do stuff... 
}