与 CAS 的原子交换（使用 gcc 同步内置函数）

Question

比较和交换函数可以用于自动交换变量吗？ 我在 x86_64 RedHat Linux 上通过 gcc 使用 C/C++，特别是 __sync 内置函数。 例子：

   int x = 0, y = 1; 
   y = __sync_val_compare_and_swap(&x, x, y);

我认为这可以归结为x是否可以在&x和x之间变化；例如，如果 &x 构成一个操作，则 x 可能会在参数中的 &x 和 x 之间变化。我想假设上面隐式的比较总是正确的；我的问题是我是否可以。显然有 CAS 的 bool 版本，但是我无法将旧的 x 写入 y 。

一个更有用的示例可能是从链表的头部插入或删除（gcc 声称支持指针类型，因此假设 elem 和 head 就是这样）：

   elem->next = __sync_val_compare_and_swap(&head, head, elem); //always inserts?
   elem = __sync_val_compare_and_swap(&head, head, elem->next); //always removes?

参考： http://gcc.gnu.org/onlinedocs/gcc/Atomic-Builtins.html

Answer 1

该操作实际上可能不会将新值存储到目标中，因为与另一个线程发生竞争，该线程在您尝试的同时更改了该值。 CAS 原语不保证写入发生 - 仅当值已经是预期值时才会发生写入。如果该值不是预期的值，则原语无法知道正确的行为是什么，因此在这种情况下什么也不会发生 - 您需要通过检查返回值以查看操作是否有效来解决问题。

因此，您的示例：

elem->next = __sync_val_compare_and_swap(&head, head, elem); //always inserts?

不一定会插入新元素。如果另一个线程同时插入一个元素，则存在竞争条件，可能会导致该线程对 __sync_val_compare_and_swap() 的调用不更新 head（但该线程或如果你正确处理它，其他线程的元素就会丢失）。

但是，这行代码还有另一个问题 - 即使 head 确实更新了，也会有一小段时间 head 指向插入的元素，但该元素的 < code>next 指针尚未更新为指向列表的上一个头。如果此时另一个线程突然介入并尝试遍历列表，则会发生不好的事情。

要正确更新列表，请将该行代码更改为以下内容：

whatever_t* prev_head = NULL;
do {
    elem->next = head;  // set up `elem->head` so the list will still be linked 
                        // correctly the instant the element is inserted
    prev_head = __sync_val_compare_and_swap(&head, elem->next, elem);
} while (prev_head != elem->next);

或者使用 bool 变体，我认为这更方便：

do {
    elem->next = head;  // set up `elem->head` so the list will still be linked 
                        // correctly the instant the element is inserted
} while (!__sync_bool_compare_and_swap(&head, elem->next, elem));

它有点难看，我希望我做对了（它是很容易陷入线程安全代码的细节中）。它应该包装在 insert_element() 函数中（或者更好的是，使用适当的库）。

解决 ABA 问题：

我认为 ABA 问题与“向列表头部添加元素”代码无关。假设一个线程想要将对象 X 添加到列表中，并且当它执行 elem->next = head 时，head 的值为 <代码>A1。

然后，在执行 __sync_val_compare_and_swap() 之前，另一组线程出现并：

• 从列表中删除 A1，使 head 指向 B
• 对对象 A1 执行任何操作，并释放它并
• 分配另一个对象 A2，该对象恰好与 A1 位于同一地址> 将
• A2 添加到列表中，以便 head 现在指向 A2

因为 A1 和 A2< /code> 具有相同的标识符/地址，这是 ABA 问题的一个实例。

但是，在这种情况下并不重要，因为添加对象 X 的线程并不关心 head 指向与开始时不同的对象 - 所有这些关心的是，X入队时：

• 列表是一致的，
• 列表上没有对象丢失，并且
• 没有将X以外的对象添加到列表中（通过这个线程）

Answer 2

没有。 x86 上的 CAS 指令从寄存器中获取值，并将其与内存中的值进行比较/写入。

为了自动交换两个变量，它必须使用两个内存操作数。

至于x是否可以在&x和x之间变化？是的，当然可以。

即使没有 &，它也可能会改变。

即使在像 Foo(x, x) 这样的函数中，您也可以获得两个不同的 x 值，因为为了调用该函数，编译器必须：

• 获取 x 的值，并存储它在第一个参数的位置，根据调用约定
• 取出x的值，并将其存储在第二个参数的位置，根据

这两个操作之间的调用约定，另一个线程可以轻松修改x<的值/代码>。

Answer 3

看来您正在寻找互锁交换原语，而不是互锁比较交换。这将无条件地以原子方式将保持寄存器与目标内存位置交换。

但是，您仍然遇到 y 赋值之间的竞争条件问题。有时 y 是本地的，在这种情况下这将是安全的，但如果 x 和 y 都共享，则会出现重大问题，并且将需要一个锁来解决它。