開幕之夜

原子操作

一條指令看起來可能像是一個不可分割的動作，但實際上完全不是這麼回事。 以把記憶體中的某個值加上 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前綴

在 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。

交換並相加

單純的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。

注意，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會藉由拒絕儲存由過期讀取算出的值來攔截這點。

記憶體排序

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

無分支程式碼的概念曾介紹過一個觀念：現代核心不會一步一步慢慢處理指令。 它會同時讓許多指令在進行中，並在可以的時候預先跑在前面。 這代表某個寫入對其他核心變為可見的時間，可能比程式所暗示的還晚，而它之後的指令卻已經先跑了。

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

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

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

加上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的自旋迴圈仍然正確，只是浪費資源。

執行緒完成工作後，可以用mov直接儲存0來釋放這個鎖。 只需要一個mov就夠了，因為在 x86-64 上，載入與儲存永遠不會被重新排序到較晚的儲存之後。 一個永遠不會超越在它之前存取的儲存，稱為具有釋放排序，而在 x86 上，每個一般的儲存都帶有這種性質。