原子操作 在

關於 原子操作

單一指令看起來可能像是一個不可分割的動作，但實際上完全不是這麼回事。以把記憶體中的某個值加上 5 為例：

add qword [rel counter], 5

在底層，處理器並沒有直接對記憶體做加法的辦法。它會把這一道指令拆成三個更小的步驟，稱為微運算：

1. 從記憶體讀取目前的值；
2. 在暫存器中修改這個值，把它加上 5；
3. 把結果寫回。

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

這是一種常見的模式，稱為讀取、修改、寫入（RMW）。

請注意，讀取（或載入）與寫入（或儲存）是兩個獨立的事件，因此它們之間存在一段時間窗口。我們通常不會察覺到這件事，因為在單一核心上，每道指令都保證會在下一道指令之前完整產生作用。因此這個窗口是看不見的，add也會表現得像一個單一單位。

然而，現代 CPU 很少是單核心的，應用程式也經常同時在許多核心上執行，彼此之間沒有任何順序安排。當好幾個核心在同一瞬間執行時，另一個核心可能就在這個窗口內，也就是在這個核心載入之後、儲存之前，讀取或寫入counter。兩個執行緒各自載入相同的舊值，各自加上 5，再各自把自己的結果寫回。發生了兩次加法，但值只增加了 5。有一次更新就這樣無聲無息地消失了。

這就是資料競爭，也是多執行緒程式碼中常見的問題。

並不是每個值都會以這種方式暴露出來。每個執行緒都有自己的暫存器與堆疊，因此存放在暫存器中的值，或執行緒堆疊上的區域變數，都是該執行緒專屬的，不會發生競爭。只有執行緒共用的記憶體，例如上面的counter，才需要保護。

x86-64 提供了一組指令來解決這個問題，做法是讓指令變得不可分割。它不僅對處理它的那個核心而言是單一單位，對其他每個核心也是如此。一個能夠保持完整、不被其他核心拆開的操作，就稱為原子操作。

原子交換

xchg指令會交換兩個運算元。目的運算元會變成來源運算元先前的值，而來源運算元則會變成目的運算元先前的值。概念上，可以把它想成兩道mov指令同時發生。

一如往常，它可以搭配兩個暫存器運算元，或搭配一個記憶體運算元與一個暫存器運算元：

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

當搭配記憶體運算元使用時，xchg_永遠_是原子的。處理器會在這段期間對該位置宣告鎖定，這和接下來會說明、lock前置字元用於其他指令的機制相同。

lock前置字元

在 x86-64 中，讓一道指令變成原子操作最常見的方法，就是加上lock前置字元。它會把讀取、修改與寫入融合成一個不可分割的步驟。這表示核心在整個過程中獨佔這塊記憶體，因此其他核心無法在這段期間讀取或寫入該位置。

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lock只有在目的端是記憶體時才有效，而且只適用於會對該記憶體進行讀取、修改、寫入的指令：

1. 算術運算，例如add、sub、inc、dec、neg；
2. 位元運算，例如and、or、xor、not；
3. 位元操作bts、btr、btc；
4. 其他一些專用指令，例如xadd與cmpxchg，會在下面說明。

用在任何其他指令上，例如普通的mov，這個前置字元就是無效的，處理器會引發無效運算碼的錯誤。單獨的一次載入或單獨的一次儲存並不需要前置字元：自然對齊的存取本身就已經是原子的。

原子位元操作

在可鎖定的指令中，位元測試與本文最後的自旋鎖正好是天作之合。bts、btr與btc各自會把選定的一個位元複製到進位旗標中，然後將它設為 1、清除或反轉。加上lock前置字元後，這就變成一次一位元的讀取、修改、寫入：位元以原子方式被改變，而CF則會回報它原本的狀態。

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

一次設定動作如果發現該位元已經是 1，就表示另一個執行緒先搶走了它。這是以單一位元呈現的版本，對應的是xchg對整個字組所做的搶佔旗標動作。

交換與相加

單純的lock add會更新記憶體，卻把舊值丟掉。很多時候，舊值正是我們想要的，例如要發給每個執行緒一個不同的號碼牌。

xadd指令（x代表交換）會在相加的同時回傳先前的值。它會把總和寫入目的端，並把目的端原本的值留在來源暫存器中。

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

加上lock前置字元後，這就是一次原子的提取並相加。當許多執行緒對同一個計數器執行它時，每次呼叫都會回傳不同的舊值。

和lock add一樣，計數器最後會剛好等於呼叫的次數。不過，和lock add不同的是，每一個中間值也都被回傳了，每個呼叫者各得到一個。

來源可以是任何通用暫存器，運算元寬度從一個位元組到一個四字組都有。加上負值，同一道指令就變成一次提取並相減。

比較與交換

xadd會相加，xchg會覆寫，但兩者都無法讓新值取決於目前的值，並且只在底下的東西沒有改變時才套用它。這種有條件的更新，正是cmpxchg（比較並交換）所提供的，也是這些基本操作中最通用的一個。

cmpxchg dest, src會使用rax作為隱含的累加器，並將它與dest比較：

• 如果dest == rax，則dest = src且ZF = 1。
• 如果dest != rax，則rax = dest且ZF = 0。

累加器會跟著運算元大小而變：一個位元組用al，更寬的形式則依序用ax、eax與rax。

請注意，只有當dest等於預期值（也就是先前載入rax的值）時，它才會被更新。這個相等性保證dest仍然持有計算新值時所依據的那個值，因此根據過期讀取所作的更新永遠不會被套用。這使得cmpxchg成為原子更新的建構基礎，也稱為比較並交換（CAS）：

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

這個重試迴圈是無鎖更新的核心。讀取與比較並交換之間的那段窗口，正是另一個執行緒可能介入的時機，而cmpxchg會藉由拒絕寫入由過期讀取算出的值來攔住這種情況。

有一個細節值得知道。cmpxchg檢查的是值是否等於先前讀到的值，而不是這個位置從未被動過。如果另一個執行緒在這段窗口內把值從A移到B再移回A，這次交換_仍然會成功_，即使底下的世界已經改變了。

對單純的計數器來說這無傷大雅，因為相同的計數就是一樣好的計數。但對於無鎖串列開頭的一個記憶體位址來說就不是了，因為同一個位址現在可能指向別的地方。這就是ABA 問題。

針對這個問題，常見的解法是把值搭配某種「印記」，例如一個只會不斷遞增的計數器。由於印記只會往前推進，相符的印記就能證明這個位置在這段期間沒有被動過，而不只是看起來沒變而已。

不過，要讓這在多執行緒環境中可行，記憶體位址和它的印記必須一起更新。由於在 x86-64 中，一個記憶體位址就佔滿一個四字組，單靠cmpxchg並不足以同時更新它以及另一個值。

有一個稱為 cmpxchg16b 的雙倍寬度指令，語意上和cmpxchg相同，但一次作用於 16 個位元組，可以用在這種情況下。它沒有來源運算元，而是用rcx:rbx當作取代值。它唯一的運算元是一個 16 位元組對齊的記憶體位置。這道指令也用rdx:rax當作累加器，而不只是rax。

記憶體排序

到目前為止的每個操作都只碰觸單一位置。當執行緒透過不只一個位置互相協調時，就會出現一個新問題：一個執行緒的寫入，會以什麼順序被另一個執行緒看見。回答這個問題的規則，就是處理器的記憶體排序。

無分支程式碼這個概念介紹過一個想法：現代核心不會一次一道地慢慢爬過指令。它會同時讓許多指令在途，並且盡可能地往前跑。這意味著某個寫入可能比程式所暗示的時機更晚才被其他核心看見，而它之後的指令卻已經先跑掉了。

x86-64 在普通的載入與儲存之間維持強記憶體排序，因此在每個核心上：

1. 一次載入永遠不會被重排到較晚的載入之後；
2. 一次儲存永遠不會被重排到較晚的儲存之後；
3. 一次載入永遠不會被重排到較晚的儲存之後。

唯一可能的重排，是一個儲存看起來在較晚、且針對_不同_位址的載入之後才完成。

加上lock前置字元的指令，或搭配記憶體運算元的xchg，是一道完整的屏障：沒有任何東西看起來能從任一方向跨越它。這就是為什麼在多數情況下，它們就足以確保完整的排序。

唯一殘存的那種重排，背後的機制是儲存緩衝區。為了持續往前跑，核心會把每個儲存暫時擱在那個緩衝區裡，讓之後的指令在儲存抵達其他核心看得見的記憶體之前就繼續進行。因此，一個寫入後面接著對不同位置的讀取，就可能顯得次序顛倒：寫入可能還待在緩衝區裡，而較晚的讀取已經先跑了。這個模型，除了那個寫入後讀取的落差之外一切都保持順序，稱為全儲存排序。

光是那一個落差，就足以讓「先儲存再檢查」的握手失效。如果兩個執行緒各自寫下自己的旗標，然後讀取對方的旗標，兩邊的讀取都可能得到未設定的結果，因為兩邊的儲存都還沒離開自己的儲存緩衝區。mfence指令會藉由清空儲存緩衝區來補上這個落差：在它之前的每個寫入，都會比在它之後的任何讀取更早被看見。

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

另外還有兩種範圍較窄的屏障：

• sfence負責排序彼此之間的寫入，主要與串流、非時序的儲存有關；
• lfence負責排序讀取。

對上面那些普通的原子模式來說，加上lock前置字元的指令本身就帶有完整排序，因此只有在像上面那樣由普通儲存與載入組成的握手時，才需要明確的屏障。

這些保證的名稱適用範圍超出了 x86。當沒有任何較晚的存取看起來能移到某個操作之前時，該操作就具有獲取排序；而當沒有任何較早的存取看起來能移到它之後時，就具有釋放排序。在 x86 上，每次載入都是一次獲取，每次儲存都是一次釋放，而加上lock前置字元的指令，或搭配記憶體的xchg，則同時兼具兩者。

自旋與pause

會設定某個旗標、同時又回傳它先前狀態的指令，稱為測試並設定。它們可以作為自旋鎖的基礎，確保某個核心對程式中某一部分擁有獨佔存取權。

以下是整體演算法，使用xchg指令搭配一個二元旗標：

1. 旗標一開始是0。
2. 為了取得鎖，核心會把旗標裡的值與1交換。
3. 如果回傳的值是1，表示鎖正被另一個核心_持有_。目前這個核心便會等待，然後再次嘗試取得鎖。
4. 如果回傳的值是0，表示鎖原本是空的。xchg此時已把它設為1，其他核心會等待，直到這個核心釋放它。
5. 目前這個核心完成工作後，把旗標更新為0就釋放了鎖。

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

等待迴圈中的pause指令並不會改變程式碼計算出的結果。它是在向處理器提示，這是一種自旋等待。CPU 便能降低等待中執行緒的耗電，並讓位給共用同一核心的兄弟執行緒。沒有pause的自旋迴圈依然正確，只是浪費而已。

請注意，在測試並設定中，像xchg這樣的指令永遠會設定旗標，即使它原本就已經設定。這表示每一次自旋它都會取得該記憶體的獨佔存取權，即使鎖很可能還被持有著。

這個演算法有一個變體，稱為測試並測試並設定，它會先測試（讀取）旗標，檢查它是否已經被設定。然後只有在鎖看起來是空的時候，才嘗試測試並設定（在這裡就是xchg）：

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

執行緒完成工作後，可以用mov把0直接儲存進去來釋放鎖。所需的就只是個mov，因為在 x86-64 上，載入與儲存永遠不會被重排到較晚的儲存之後。一個永遠不會超越它之前那些存取的儲存，就說它具有釋放排序，而在 x86 上，每個普通的儲存都帶有這種排序。