使用CAS進行原子交換（使用gcc sync builtins）

可以使用compare-and-swap函數以原子方式交換變量嗎？我在x86_64 RedHat Linux上通過gcc使用C/C++，特別是__sync內置函數。實施例：使用CAS進行原子交換（使用gcc sync builtins）

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和頭部）：

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

來源

2010-06-04 limalave

沒有。 x86上的CAS指令從寄存器獲取值，並將其與內存中的值進行比較/寫入。

爲了原子交換兩個變量，它必須使用兩個內存操作數。

至於x是否可以在&x和x之間變化？是的，當然可以。

即使沒有&，它也可能改變。

即使是在功能，如Foo(x, x)，你可以得到x的兩個不同的值，因爲爲了調用函數，編譯器必須：

取x的值，並將其存儲在所述第一參數的位置，根據該調用約定
取x的值，並將其存儲在第二個參數的位置，根據該調用約定

這兩個操作之間，另一個線程可以很容易地修改第e值爲x。

來源

2010-06-04 15:39:08 jalf

該操作可能實際上不會將新值存儲到目標中，因爲與另一個線程的比賽會在您嘗試同時更改該值。 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-04 16:15:50

這些代碼遭受ABA問題。 – ddoman 2011-10-20 05:39:10

@ddoman：你能否詳細說明你將如何解決它？或者你會只使用維基百科文章中提出的有關ABA問題的方法之一？ – Aktau 2013-04-25 22:40:37

我不確定ABA問題是否是一個問題 - 我已更新答案以表明原因。如果我錯了，我會很感激細節。 – 2013-04-26 00:48:18

看起來你正在尋找互鎖交換原語，而不是互鎖比較交換。這將無條件地將保持寄存器與目標內存位置進行原子交換。

但是，您在y作業之間的競賽條件仍然存在問題。有時候y是本地的，在這種情況下這將是安全的，但如果共享x和y您有一個主要問題，並且需要一個鎖來解決它。

來源

2013-10-04 20:28:11

使用CAS進行原子交換（使用gcc sync builtins）

回答

相關問題