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 и будете использовать выделенную кучу память для узлов, это приведет к недетерминированным ошибкам при использовании в реальном коде.

Если вы делаете это, чтобы получить опыт, то не ждите, что ТАК товарищи решат это за вас. Вы должны прочитать все цитируемые материалы и многое другое, убедиться, что вы действительно понимаете все нюансы алгоритмов без блокировок, таких как 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, посмотрите предлагаемую библиотеку Boost.Lockfree. Внутренние компоненты довольно просты в использовании и могут быть портированы на C, или, наоборот, вы можете обернуть Boost.Lockfree в C API и использовать это.

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

Answer 4

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

Answer 5

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

LFQ.

Его поддерживают многие производители, многие потребители.