c++ - 楽観的なロックフリー FIFO キューの実装は存在しますか?

Question

「ロックフリー FIFO キューへの楽観的アプローチ」アルゴリズムの C++ 実装 (ソース コード) はありますか?

Answer 1

Herb Sutterは、Dr。DobbsJournalのEffectiveConcurencyコラムの一部として、まさにそのようなキューを取り上げました。

ロックフリーコードの記述：修正されたキュー

Answer 2

http://www.drdobbs.com/high-performance-computing/212201163 (記事の最後の部分) に基づいたgrayfadeの回答を締めくくりたいと思います。私の命名規則とコーディング規則に合わせてください) : `

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

`

もう 1 つの質問は、CACHE_LINE_SIZE をどのように定義するかです。それは今までのCPUで変わりますか？

Answer 3

優れたロック フリー キューの実装を探している場合は、Microsoft Visual Studio 2010 と Intel のスレッド ビルディング ブロックの両方に、論文に似た優れた LF キューが含まれています。

これはVC 2010のものへのリンクです