比較並交換（compare-and-swap, CAS）
/ kass /
假設兩個人都想更新同一個共享數字，而你需要更新是全有或全無——不能出現他們的寫入糾纏在一起的半成品爛攤。比較並交換（compare-and-swap, CAS）就是讓這成為可能的單一硬體指令。它在一個不可分割的步驟裡，檢查某個記憶體位置是否仍持有你預期的值，唯有如此才寫入你的新值。若有人搶先改了它，你的寫入會被拒絕，並且你會被告知。
精確地說，CAS(位址, 預期值, 新值) 以原子方式（atomic，當作其他執行緒無法打斷的單一操作）做三件事：讀取位址處的值；把該值與預期值比較；若相等就把新值存進位址並回報成功；若不等就維持記憶體不動並回報失敗（通常回傳它實際讀到的值）。重點全在於原子性：在讀與寫之間，沒有其他執行緒能溜進來。這是幾乎每個無鎖演算法的基石原語——你讀取目前狀態，算出想要的新狀態，再用 CAS 在「底下沒有任何改變」時才把它裝上去。在 x86-64 上這是 cmpxchg 指令，通常帶 lock 前綴；在 C11 中是 atomic_compare_exchange_strong；在 C++ 中是 std::atomic::compare_exchange_strong。
兩個誠實的提醒。第一，CAS 比較的是一個值的原始位元，而非它的意義——這個盲點正是 ABA 問題的根源：一個值變掉再變回原狀，CAS 卻誤以為什麼都沒發生。第二，有兩種版本：compare_exchange_strong，以及 compare_exchange_weak——後者容許假性失敗（即使值相符也可能回報失敗），但在某些 CPU 上能編譯成更快的程式碼；你會在重試迴圈裡使用弱版本，那裡一次假性失敗只不過意味著無害地多繞一圈。
/* 用 CAS 重試迴圈，無鎖地把 x 原子遞增。 */ uint64_t old, neu; do { old = atomic_load(&x); neu = old + 1; } while (!atomic_compare_exchange_weak(&x, &old, neu)); /* 失敗時，&old 會被刷新成目前的值，於是我們直接重試。 */
唯有當 x 仍是 old 時，CAS 才裝上 neu；否則回報失敗並更新 old，迴圈再試一次。
CAS 比較的是位元樣式，不是邏輯身分——即使值曾離開又繞回來，相等的位元看起來仍相同，這就是 ABA 問題。在迴圈內用 compare_exchange_weak，單次一試的檢查用 strong。