क्या आशावादी लॉक-फ्री फीफो कतार कार्यान्वयन मौजूद है?

Question

"की optmistic approach to lock-free FIFO queues" algorithm?

Answer 1

Herb Sutter बस जैसे डॉ डोब्स जर्नल में उसकी प्रभावी Concurency स्तंभ के हिस्से के रूप एक कतार कवर वहाँ किसी भी सी ++ कार्यान्वयन (स्रोत कोड) है।

Writing Lock-Free Code: A Corrected Queue

Answer 2

आप अगर ' माइक्रोसॉफ्ट विजुअल स्टूडियो 2010 & इंटेल के थ्रेड बिल्डिंग ब्लॉक्स में एक अच्छी लॉक फ्री कतार कार्यान्वयन की तलाश है, जो एक अच्छी एलएफ कतार है जो पेपर के समान है।

Here's a link to the one in VC 2010

Answer 3

मैं greyfade, जो http://www.drdobbs.com/high-performance-computing/212201163 (लेख के अंतिम भाग) पर आधारित है द्वारा दिए गए जवाब है, अनुकूलित कोड होगा (कुछ संशोधन मेरी नामकरण और कोडिंग सम्मेलन सूट करने के लिए) के साथ समाप्त करने के लिए चाहते हैं : `

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

`

एक और सवाल यह है कि आप CACHE_LINE_SIZE परिभाषित करते है? यह हमेशा सीपीयू पर भिन्न होता है?

Answer 4

यहां लॉक-फ्री फीफो का मेरा कार्यान्वयन है।

सुनिश्चित करें कि टी की प्रत्येक वस्तु झूठी साझाकरण से बचने के लिए 64 बाइट्स (इंटेल CPUs में कैश लाइन आकार) का एक बहु है।

यह कोड gcc/mingw के साथ संकलित करता है और क्लैंग के साथ संकलित होना चाहिए। इसे 64-बिट के लिए अनुकूलित किया गया है, इसलिए इसे 32-बिट पर चलाने के लिए कुछ रिफैक्टरिंग की आवश्यकता होगी।

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

vsx_fifo<my_struct, 512> my_fifo; 

प्रेषक:

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

रिसीवर:

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