C код безблокировочной очереди

Question

Как я могу реализовать этот псевдокод очереди без блокировки в C?

ENQUEUE(x)
    q ← new record
    q^.value ← x
    q^.next ← NULL
    repeat
        p ← tail
        succ ← COMPARE&SWAP(p^.next, NULL, q)
        if succ ≠ TRUE
            COMPARE&SWAP(tail, p, p^.next)
    until succ = TRUE
    COMPARE&SWAP(tail,p,q)
end

DEQUEUE()
    repeat
        p ← head
        if p^.next = NULL
            error queue empty
    until COMPARE&SWAP(head, p, p^.next)
    return p^.next^.value
end

Как бы использовать встроенные функции для доступа к атомарной памяти

__sync_bool_compare_and_swap (type *ptr, type oldval type newval, ...)

У меня сейчас

typedef struct queueelem {
    queuedata_t data;
    struct queueelem *next;
} queueelem_t;

typedef struct queue {
    int capacity;
    int size;
    queueelem_t *head;
    queueelem_t *tail;
} queue_t;

queue_t *
queue_init(int capacity)
{
    queue_t *q = (queue_t *) malloc(sizeof(queue_t));
    q->head = q->tail = NULL;
    q->size = 0;
    q->capacity = capacity;
    return q;
}

Answer 1

http://www.liblfds.org

Общественное достояние, нет лицензии, переносимая реализация алгоритмов без блокировки в C.

Сборка из коробки для Windows и Linux.

Использует GCC в Linux, поэтому использует встроенные функции (ну, кроме 128-битного CAS, встроенного нет - для этого используется встроенная сборка).

Содержит очередь M & S. Посмотрите на исходный код и посмотрите, как это делается.

Answer 2

Если вашей целью является производственный код, просто не делайте этого;использовать замки.

В вашем предыдущем вопросе у вас достаточно информации, объясняющей почему.Правильные реализации без блокировок даже простых структур данных, таких как очередь и стек, при отсутствии сборщика мусора являются сложными и сложными из-за (в) известной проблемы ABA .К сожалению, некоторые исследовательские работы не принимают ABA во внимание по каким-либо причинам;Ваш псевдокод, кажется, взят из одной из таких статей.Если вы преобразуете его в C и используете выделенную кучу память для узлов, это приведет к недетерминированным ошибкам при использовании в реальном коде.

Если вы делаете этот материал для получения опыта, то не ожидайте, что SO товарищи решатэто для вас.Вы должны прочитать все цитируемые материалы и многое другое, убедиться, что вы действительно понимаете все нюансы алгоритмов без блокировок, таких как ABA, изучаете различные методы, предназначенные для решения этой проблемы, изучаете существующие реализации без блокировок и т. Д.

Наконец, небольшое руководство по переводу данного псевдокода на C:

q^.value ← x означает q_elem->data = x;
repeat ... until COMPARE&SWAP(head, p, p^.next) эквивалентно do {...} while (!__sync_bool_compare_and_swap(q_obj->head, q_elem, q_elem->next);

, где q_obj является экземпляром типа queue_t (т.е. очередью), а q_elem является экземпляром типа queueelem_t (то есть узлом очереди).

Answer 3

Я использую C для написания минимизации реализации очереди без блокировки.

lfq .

Он поддерживает многих производителей, многих потребителей.

Answer 4

Звучит так, как вы хотите, это называется блокировкой очереди MCS (хотя и с обманчивым названием, она действительно без блокировки, но не без ожидания), и здесь есть несколько хороших псевдокодов: http://www.cs.rochester.edu/research/synchronization/pseudocode/ss.html#mcs

Answer 5

Хотя это и не совсем C, посмотрите предлагаемую библиотеку Boost.Lockfree . Внутренние компоненты довольно просты в использовании и могут быть портированы на C, или, наоборот, вы можете обернуть Boost.Lockfree в C API и использовать это.

Аналогичным образом, Boostcon 2010 было много дискуссий о программировании без блокировок и STM, на которые стоит обратить внимание, если вы заинтересованы в этой теме. Я не могу найти ссылку на видео, но разговоры с Intel, IBM и AMD стоили посмотреть, так как они имеют дело с STM на уровне процессора.