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

公共域，无许可证，可移植的C语言无锁算法实现。

开箱即用，适用于Windows和Linux。

在Linux上使用GCC，所以使用内部函数(嗯，除了128位CAS之外，没有内部使用的内联汇编)。

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

Answer 2

如果您的目标是生产代码，请不要这样做；使用锁。

在your previous question中，您已经获得了足够的信息来解释原因。由于the (in)famous ABA problem的存在，在没有垃圾收集器的情况下，即使是队列和堆栈等简单数据结构的正确无锁实现也是棘手和复杂的。不幸的是，由于某种原因，一些研究论文没有考虑到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语言，但请查看proposed Boost.Lockfree库。内部结构非常容易理解，可以移植到C，或者相反，你可以将Boost.Lockfree包装在wrap中并使用它。

同样，如果你对这个主题感兴趣，Boostcon 2010有很多关于自由编程和STM的讨论，值得一看。我找不到视频的链接，但Intel、IBM和AMD的演讲值得一看，因为他们在CPU级别处理STM。