Une implémentation de file d'attente FIFO sans verrouillage optimiste existe-t-elle?

Question

Y at-il implémentation C++ (codes sources) de "optmistic approach to lock-free FIFO queues" algorithm?

Answer 1

Herb Sutter couvert une telle file d'attente dans le cadre de sa colonne efficace Concurency dans Dr. Dobbs Journal.

Writing Lock-Free Code: A Corrected Queue

Answer 2

Si vous re à la recherche d'une bonne mise en œuvre de la file d'attente verrouillée à la fois Microsoft Visual Studio 2010 & Les blocs de création de threads d'Intel contiennent une bonne file d'attente LF qui est similaire au papier

Here's a link to the one in VC 2010

Answer 3

Je veux conclure la réponse donnée par greyfade, qui est basé sur http://www.drdobbs.com/high-performance-computing/212201163 (la dernière partie de l'article), le code optimisé serait (avec quelques modifications en fonction de ma dénomination et convention de codage) : `

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

`

une autre question est de savoir comment définissez-vous CACHE_LINE_SIZE? cela varie sur les processeurs jamais à droite?

Answer 4

Voici ma mise en œuvre d'un FIFO sans verrouillage.

Assurez-vous que chaque élément de T est un multiple de 64 octets (la taille de la ligne de cache dans les processeurs Intel) afin d'éviter un faux partage.

Ce code est compilé avec gcc/mingw et doit être compilé avec clang. Il est optimisé pour 64 bits, donc pour l'exécuter sur 32 bits, il faudrait un refactoring.

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

vsx_fifo<my_struct, 512> my_fifo; 

Auteur:

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

Récepteur:

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