无锁队列的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

如何使用 Built-in functions for atomic memory access

__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

https://www.liblfds.org/

公共(public)领域、无许可证、可移植的 C 无锁算法实现。

为 Windows 和 Linux 开箱即用。

在 Linux 上使用 GCC，因此使用内部函数(好吧，除了 128 位 CAS 之外，没有内部函数 - 为此使用内联汇编)。

包含 M&S 队列。查看源代码，看看它是如何完成的。