无锁队列的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开箱即用.

在Linux上使用GCC,因此使用内在函数(除了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（即队列节点）。