与CAS的原子交换(使用gcc sync内置函数) [英] atomic swap with CAS (using gcc sync builtins)

问题描述

可以使用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指向的对象与开始时指向的对象不同-它关心的只是当已排队:

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)

这篇关于与CAS的原子交换(使用gcc sync内置函数)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！