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

2022-01-01 00:00:00 linked-list gcc atomic c++ compare-and-swap

compare-and-swap 函数可以用来原子地交换变量吗?我在 x86_64 RedHat Linux 上通过 gcc 使用 C/C++，特别是 __sync 内置函数.示例:

Can the compare-and-swap function be used to swap variables atomically? I'm using C/C++ via gcc on x86_64 RedHat Linux, specifically the __sync builtins. Example:

   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.

I think this boils down to whether x can change between &x and x; for instance, if &x constitutes an operation, it might be possible for x to change between &x and x in the arguments. I want to assume that the comparison implicit above will always be true; my question is whether I can. Obviously there's the bool version of CAS, but then I can't get the old x to write into y.

一个更有用的例子可能是在链表的头部插入或删除(gcc 声称支持指针类型，所以假设这就是 elem 和 head 是什么):

A more useful example might be inserting or removing from the head of a linked list (gcc claims to support pointer types, so assume that's what elem and head are):

   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

推荐答案

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

The operation might not actually store the new value into the destination because of a race with another thread that changes the value at the same moment you're trying to. The CAS primitive doesn't guarantee that the write occurs - only that the write occurs if the value is already what's expected. The primitive can't know what the correct behavior is if the value isn't what is expected, so nothing happens in that case - you need to fix up the problem by checking the return value to see if the operation worked.

所以，你的例子:

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

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

won't necessarily insert the new element. If another thread inserts an element at the same moment, there's a race condition that might cause this thread's call to __sync_val_compare_and_swap() to not update head (but neither this thread's or the other thread's element is lost yet if you handle it correctly).

但是，那行代码还有另一个问题――即使 head 确实得到了更新，也有一小段时间 head 指向插入的元素，但是该元素的 next 指针尚未更新为指向列表的前一个头部.如果另一个线程在那一刻突然出现并试图遍历列表，那么糟糕的事情就会发生.

But, there's another problem with that line of code - even if head did get updated, there's a brief moment of time where head points to the inserted element, but that element's next pointer hasn't been updated to point to the previous head of the list. If another thread swoops in during that moment and tries to walk the list, bad things happen.

要正确更新列表，请将该行代码更改为:

To correctly update the list change that line of code to something like:

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 变体，我觉得这样更方便一些:

Or use the bool variant, which I think is a bit more convenient:

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() 函数中(或者甚至更好，使用适当的库).

It's kind of ugly, and I hope I got it right (it's easy to get tripped up in the details of thread-safe code). It should be wrapped in an insert_element() function (or even better, use an appropriate library).

解决 ABA 问题:

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

I don't think the ABA problem is relevant to this "add an element to the head of a list" code. Let's say that a thread wants to add object X to the list and when it executes elem->next = head, head has value A1.

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

Then before the __sync_val_compare_and_swap() is executed, another set of threads comes along and:

  • 从列表中删除A1，使head指向B
  • 对对象 A1 执行任何操作并释放它
  • 分配另一个对象，A2 恰好与 A1 位于同一地址
  • 将 A2 添加到列表中，以便 head 现在指向 A2
  • removes A1 from the list, making head point to B
  • does whatever with object A1 and frees it
  • allocates another object, A2 that happens to to be at the same address as A1 was
  • adds A2 to the list so that head now points to A2

由于 A1 和 A2 具有相同的标识符/地址，这是 ABA 问题的一个实例.

Since A1 and A2 have the same identifier/address, this is an instance of the ABA problem.

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

However, it doesn't matter in this case since the thread adding object X doesn't care that the head points to a different object than it started out with - all it cares about is that when X is queued:

  • 列表一致，
  • 列表中没有任何对象丢失，并且
  • 除 X 之外的任何对象都没有被添加到列表中(通过这个线程)
  • the list is consistent,
  • no objects on the list have been lost, and
  • no objects other than X have been added to the list (by this thread)

相关文章