Существует ли оптимистичная реализация очереди FIFO без блокировки? - PullRequest
Новая
       62

Существует ли оптимистичная реализация очереди FIFO без блокировки?

10 голосов
/ 31 мая 2010

Существует ли реализация C ++ (исходные коды) алгоритма " Оптимистический подход к очередям FIFO без блокировки" ?

Ответы [ 5 ]

11 голосов
/ 31 мая 2010

Херб Саттер покрывал именно такую ​​очередь в своей колонке «Эффективная конкуренция» в журнале «Доктор Доббс».

Написание кода без блокировки: исправленная очередь

4 голосов
/ 01 июня 2010

Я хочу завершить ответ, заданный 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? это зависит от всех процессоров, верно?

1 голос
/ 14 октября 2014

Вот моя реализация FIFO без блокировки.

Убедитесь, что каждый элемент T кратен 64 байтам (размер строки кэша в процессорах Intel), чтобы избежать ложного совместного использования.

Этот код компилируется с помощью gcc / mingw и должен компилироваться с помощью clang. Он оптимизирован для 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...
}
0 голосов
/ 10 сентября 2018

Как насчет этого lfqueue

Это кроссплатформенная неограниченная очередь безопасности потоков в очереди, были протестированы multi deq, multi enq-deq и multi enq . Гарантия сохранности памяти.

Например 

int* int_data;
lfqueue_t my_queue;

if (lfqueue_init(&my_queue) == -1)
    return -1;

/** Wrap This scope in other threads **/
int_data = (int*) malloc(sizeof(int));
assert(int_data != NULL);
*int_data = i++;
/*Enqueue*/
 while (lfqueue_enq(&my_queue, int_data) == -1) {
    printf("ENQ Full ?\n");
}

/** Wrap This scope in other threads **/
/*Dequeue*/
while  ( (int_data = lfqueue_deq(&my_queue)) == NULL) {
    printf("DEQ EMPTY ..\n");
}

// printf("%d\n", *(int*) int_data );
free(int_data);
/** End **/

lfqueue_destroy(&my_queue);
0 голосов
/ 01 июня 2010

Если вы ищете хорошую реализацию очереди без блокировок, Microsoft Visual Studio 2010 и Intel Thread Building Blocks содержат хорошую очередь LF, которая похожа на статью.

Вот ссылка на тот, что в VC 2010

...