c - 如何在 C/Linux 中实现双重比较和交换？

Question

我正在阅读论文“简单、快速、实用的非阻塞和阻塞并发队列算法”，我意识到他们假设计算机原子地实现了以下伪代码：

CAS(Q->Tail,tail,<next.ptr,next.count+1>)

其中 Q->Tail 和 tail 是一个指针和一个包含指针和计数器的结构的实例。

我知道 gcc 为 c 中的单个单词比较和交换提供了几个内置插件。但是，是否可以从 c 中的单个比较和交换（使用 Linux）实现非阻塞原子双重比较和交换？这是实现参考论文伪代码的正确方法吗？

Answer 1

我不知道在两个不同的内存位置上工作的任何 CAS 操作。但是，该论文有可能使用指针和计数器的结构作为解决方法，将这两个字段视为更大的类型，因此，原子地更改两者。

假设你有一个包含两个字段的结构，一个指针和一个计数器：指针大小为 4 字节，计数器大小为 4 字节；正确对齐而不填充到 8 字节的结构大小。假设您还有一个处理 8 字节值的 CAS 操作（例如指向 64 位整数的指针）。您可以单独准备结构值，并在整个结构上使用 CAS 操作一次更改两个值。

Answer 2

Gcc 还为双字 CAS 提供了内置函数，如果 sizeof(*Q->Tail) == sizeof(tail) == sizeof(third_arg) == 8，则可以使用 __sync_bool_compare_and_swap。所以如果可以递增，一切正常执行 CAS 之前的“next.count”。