6

可以使用 compare-and-swap 函数以原子方式交换变量吗？我在 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

4

3 回答 3

3

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

所以，你的例子：

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

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

但是，这行代码还有另一个问题——即使head确实更新了，也有一小段时间head指向插入的元素，但该元素的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具有相同的标识符/地址，这是 ABA 问题的一个实例。

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

  • 清单是一致的，
  • 列表中没有任何对象丢失，并且
  • 没有其他对象X被添加到列表中（由这个线程）
于 2010-06-04T16:15:50.197 回答
0

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

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

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

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

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

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

在这两个操作之间，另一个线程可以轻松修改x.

于 2010-06-04T15:39:08.257 回答
0

似乎您正在寻找联锁交换原语，而不是联锁比较交换。这将无条件地将保持寄存器与目标内存位置进行原子交换。

但是，您仍然对分配给y. 有时y是本地的，在这种情况下这将是安全的，但如果两者x都y共享，您将遇到重大问题并且需要锁定来解决它。

于 2013-10-04T20:28:11.673 回答