Lock-free 並非完全不使用 lock 的技巧，而是在高競爭情況下避免傳統 mutex 帶來的阻塞成本。昨天已提到 Lock-free programming 的兩大核心概念：Atomicity 確保多執行緒同時修改變數時的正確性；Memory Ordering 則定義其他執行緒觀察到這些修改的時間與順序。另一個 Lock-free 程式設計中非常常見的工具是 Compare-And-Swap (CAS)。

1. CAS 的 strong 與 weak

CAS 有以下幾個步驟。只有當目前的值仍然等於 expected 時，才把它更新成 desired。

• Compare：檢查記憶體目前的值，是否等於你預期的 expected 值。
• Swap：如果相同，就把記憶體的值更新成新的 desired 值。
• No Action：如果不同，代表有其他執行緒已經偷偷改過這個值了，這次更新就會失敗，且什麼都不做。

std::atomic<int> x{10};
int expected = 10;

x.compare_exchange_strong(expected, 20);

舉例來說，以上程式碼實際的含義是：

if (x == 10) {     // x == expected
    x = 20;        // x = desired
    return true;   // success
} else {
    // expected 被更新成目前的 x
    return false;  // fail
}

這種設計讓我們能在沒有 mutex 的情況下實作複雜的 atomic state transition：

auto old = value.load(std::memory_order_relaxed);

while (!value.compare_exchange_weak(old, old + 1, std::memory_order_relaxed)) {
}

這裡用到的 compare_exchange_weak 是 CAS 的弱版本。在某些硬體平台上，即使值相同有時也會發生 spurious failure，因此弱版本通常需要搭配 loop 使用。然而 CAS 並不是免費的。當很多 CPU core 同時對同一個 atomic variable 執行 CAS 時，cache line 會在 cores 之間頻繁移動，這種 cache-line bouncing 可能成為嚴重的效能瓶頸。

2. CAS Loop 與 Contention

很多 lock-free data structure 都會有 CAS loop：

int old = x.load();

do {
    int new_value = old + 1;
} while (!x.compare_exchange_weak(old, new_value));

這時候 contention 可能造成問題。假設有 8 個 threads：
T1 ─┐
T2 ─┤
T3 ─┤
T4 ─┼─ CAS → atomic counter
T5 ─┤
T6 ─┤
T7 ─┤
T8 ─┘

Threads 同時讀到 counter = 100，然後都算 new = 101。但 CAS 只有一個能成功：
T1:ㅤCASㅤ100 → 101ㅤSUCCESS
T2:ㅤCASㅤ100 → 101ㅤFAIL
T3:ㅤCASㅤ100 → 101ㅤFAIL
T4:ㅤCASㅤ100 → 101ㅤFAIL
...

失敗的 thread 必須重新：
load old → calculate new → CAS → retry

即便某一個 thread 一直 CAS 失敗，但只要其他 thread 不斷成功，整個 algorithm 仍然可能是 lock-free。所以 lock-free 其實只是把等待 lock的成本，轉換成 CAS retry + cache coherence + contention 的成本。

3. 真正重要的 Trade-off

可以把 Mutex 想成：
Contention → Thread blocks → Context switch → Wake up

Lock-free 在低 contention 的情境下或許非常有效：
Contention → CAS failure → Retry → Cache-line bouncing → Retry again

然而，lock-free algorithm 在高 contention 下，有機率比一個設計良好的 Mutex 還慢，最終導致一個很反直覺的結果：
CAS failure ⬆️ → Retry ⬆️ → Cache coherence traffic ⬆️ → CPU cycles wasted ⬆️

工程師或許能寫出 CAS 看似完全正確的 lock-free algorithm，卻因為低估了 memory ordering 錯誤造成的損害，在 ARM/POWER 等較弱 memory model 的 CPU 上出現非常難解決的 concurrency bug。

如果要真正學會 lock-free，可參考以下建議順序。

• Atomicity：atomic load/store、RMW、CAS。
• Memory Ordering：Relaxed、Acquire、Release、Acq-Rel、Seq-Cst。
• CAS Loop：compare_exchange_weak、compare_exchange_strong、retry behavior。
• Contention：cache coherence、false sharing、CAS failure、backoff、scalability。

ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤLock-Free Programming
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ│
ㅤㅤㅤㅤ┌──────────┼──────────┐
ㅤㅤㅤㅤ↓ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ↓ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ↓
Progress GuaranteeㅤㅤㅤVisibility / OrderingㅤㅤㅤAtomic Update
ㅤㅤㅤㅤ│ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ│ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ│
ㅤㅤLock-FreeㅤㅤㅤㅤㅤㅤㅤAcquire/ReleaseㅤㅤㅤㅤㅤㅤCAS
ㅤㅤㅤㅤ│ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ│ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ│
ㅤㅤㅤㅤ└──────────┼──────────┘
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ↓
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤContention
ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ│
ㅤㅤㅤㅤㅤㅤㅤㅤ┌──────┴──────┐
ㅤㅤㅤㅤㅤㅤㅤㅤ↓ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ↓
ㅤㅤㅤㅤㅤCAS succeedsㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤCAS fails
ㅤㅤㅤㅤㅤㅤㅤㅤ↓ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ↓
ㅤㅤㅤㅤㅤㅤㅤprogressㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤretry