作業系統概念（進階）：當執行緒爭奪同一塊資料

兩個行程同時加一，為什麼結果可能不是加二？

你已經知道作業系統(operating system)用情境切換(context switch)製造出「多個程式同時執行」的錯覺。現在我們把這個錯覺拆開來問一個尖銳的問題：如果有兩個執行緒(thread)都在對同一個共享變數 counter 做「讀出、加一、寫回」，各做一千次，最後 counter 一定等於兩千嗎？

直覺說「當然」。但只要你真的在多核心機器上跑這段程式，會發現結果常常是一千多，偶爾才剛好兩千——而且每次跑都不一樣。這個看似違反算術的現象，正是作業系統與並行程式設計裡最核心、也最折磨人的難題：競爭條件(race condition)。入門篇告訴你 OS 製造了「並行」的假象；這篇要告訴你，這個假象底下藏著什麼樣的深淵，以及作業系統與硬體聯手用什麼工具把它填平。

為什麼「加一」不是一個動作

問題的根源在於：counter = counter + 1 在原始碼裡看起來是一行、像是一個不可分割的動作，但編譯成機器碼後，它其實是三個獨立的步驟。

load   R1, [counter]   ; 把 counter 的值讀進暫存器 R1
add    R1, R1, 1       ; R1 = R1 + 1
store  [counter], R1   ; 把 R1 寫回 counter

關鍵在於：作業系統可以在這三步的任何一步之後把 CPU 從這個執行緒手上搶走（這叫搶占, preemption），切去跑另一個執行緒。於是下面這種交錯(interleaving)就可能發生（假設 counter 起始為 5）：

時間軸    執行緒 A              執行緒 B           counter 實際值
 t1     load  R1 = 5                              5
 t2                          load  R1 = 5         5
 t3     add   R1 = 6                              5
 t4                          add   R1 = 6         5
 t5     store counter = 6                         6
 t6                          store counter = 6    6   ← 應該是 7！

兩個執行緒各自都「正確地」把值加了一，但因為它們都先讀到了還沒被對方更新的舊值 5，其中一次加一的效果被另一次覆蓋了。這就是經典的遺失更新(lost update)。注意這裡沒有任何程式碼是錯的——錯的是這兩段程式碼同時存取了共享資料，而存取動作沒有被妥善協調。

我們把「多個執行緒會存取共享資料、且至少一個是寫入」的這段程式碼，稱為臨界區段(critical section)。並行的全部難題，可以濃縮成一句話：如何保證同一時間至多只有一個執行緒進入臨界區段——這個性質叫互斥(mutual exclusion)。

軟體解法為什麼這麼難：你需要硬體幫忙

一個自然的念頭是：那我用一個旗標變數 lock 來把關不就好了？

// 看似可行，其實有致命缺陷
while (lock == 1) { /* 別人在用，空轉等待 */ }
lock = 1;          // 我要進去了
// ... 臨界區段 ...
lock = 0;          // 我出來了

問題是：「檢查 lock 是不是 0」和「把 lock 設成 1」本身又是兩個分開的動作！兩個執行緒可能同時讀到 lock == 0，然後雙雙設成 1、雙雙進入臨界區段。我們用來保護臨界區段的鎖，自己又掉進了同樣的競爭條件。這不是繞圈圈嗎？

歷史上電腦科學家曾用純軟體解決過這個問題（最著名的是 Dekker 與 Peterson 演算法），證明了「只靠 load/store 也能達成互斥」在理論上可行。但這些演算法繁瑣、只支援固定數量的執行緒，而且在現代亂序執行(out-of-order execution)的 CPU 上還會因記憶體重排序(memory reordering)而失效。實務上，我們需要的是硬體提供的原子指令(atomic instruction)。

所謂原子(atomic)，意思是「不可分割」：這條指令一旦開始，就會一口氣做完，中間不可能被任何其他執行緒插入。最關鍵的一族原子指令是「比較並交換」：

CAS(addr, expected, new):
    # 以下整段保證原子執行
    if *addr == expected:
        *addr = new
        return true     # 成功搶到
    else:
        return false    # 有人捷足先登

CAS(Compare-And-Swap，x86 上是 cmpxchg 指令)把「比較」和「寫入」綁成一個不可分割的動作。有了它，前面那個有缺陷的鎖就能修好：

// 用 CAS 實作的自旋鎖(spinlock)，這次是正確的
while (!CAS(&lock, 0, 1)) {
    /* CAS 失敗代表鎖被別人持有，繼續嘗試 */
}
// ... 臨界區段 ...
lock = 0;   // 釋放

這就是自旋鎖(spinlock)：拿不到鎖的執行緒就在原地「自旋」（空轉重試）。它是作業系統核心內部最基礎的同步原語(synchronization primitive)。所有更高階的鎖，幾乎都建立在 CAS 這類原子指令之上。

自旋還是睡眠：兩種等待哲學

自旋鎖有個明顯缺點：等不到鎖時它讓 CPU 空轉燒電。如果臨界區段很短（幾十個 cycle），自旋幾下就拿到了，比起切換執行緒還划算；但如果臨界區段很長，自旋就是純粹浪費。

於是有了另一種鎖：互斥鎖(mutex)。拿不到 mutex 的執行緒不會空轉，而是主動進入睡眠(sleep)——作業系統把它從可執行佇列移走，去跑別的執行緒，等鎖釋放時再叫醒它。這牽涉到一次系統呼叫與情境切換，成本較高，但 CPU 不會被白白浪費。

實務上的鎖常是混合策略：Linux 的 futex（fast userspace mutex）先在使用者空間用原子指令快速嘗試，只有在真的有競爭、必須等待時才掉進核心睡眠。沒競爭時完全不進核心，省下系統呼叫的成本——這正呼應了入門篇談過的「跨界昂貴，能不進核心就不進」。

比鎖更高階的工具：號誌與條件變數

鎖解決的是「互斥」，但並行程式還有另一種需求：協調(coordination)——讓某個執行緒等到「某件事發生」才繼續。例如生產者—消費者問題：消費者必須等到緩衝區裡「有東西」才能取，生產者必須等到緩衝區「有空位」才能放。

Dijkstra 在 1965 年提出的號誌(semaphore) 是這類問題的經典工具。一個號誌維護一個整數計數值，配兩個原子操作：

wait(S)   (又稱 P 操作)：
    S = S - 1
    if S < 0:  把自己加入等待佇列並睡眠

signal(S) (又稱 V 操作)：
    S = S + 1
    if 有人在等待佇列:  叫醒其中一個

當 S 初始為 1 時，號誌退化成一把互斥鎖；當 S 初始為 N 時，它能允許最多 N 個執行緒同時進入（例如限制連線池大小）。用一對號誌就能優雅地解決生產者—消費者問題（一個數「空位」、一個數「資料」）。

更貼近現代程式設計的是條件變數(condition variable)，它總是和一把 mutex 搭配使用，提供 wait／signal／broadcast，讓執行緒在持有鎖的情況下「放掉鎖去睡，等被通知時再醒來重新搶鎖」。幾乎所有高階語言的並行函式庫（Java 的 synchronized、Python 的 threading.Condition、C++ 的 std::condition_variable）骨子裡都是這套機制。

動手算一下：競爭視窗有多大？

很多人以為競爭條件「機率太小，不會中」。我們來估算一下這種僥倖有多危險。

假設臨界區段（那三條 load/add/store）執行需時約 $3\text{ ns}$，而程式總共要對 counter 做 $N = 10^7$ 次更新。一次更新中，「讀出舊值到寫回新值」之間的這段時間就是競爭視窗(race window)，大約 $w = 2\text{ ns}$。

在多核心上，兩個執行緒幾乎連續不斷地更新。我們粗略地問：另一個執行緒「剛好」在這 $2\text{ ns}$ 視窗內也來更新的機會有多大？若兩執行緒平均每 $3\text{ ns}$ 各更新一次，兩者落入同一視窗的碰撞機率大約是

$$ p \approx \frac{w}{\text{更新間隔}} = \frac{2}{3} \approx 0.67 \text{（量級上 } O(1)\text{）} $$

也就是說，在這種高頻共享寫入下，碰撞幾乎必然發生，難怪結果遠小於兩千萬。但若把更新頻率降到每秒才一次（更新間隔 $10^9\text{ ns}$），碰撞機率就驟降到

$$ p \approx \frac{2}{10^9} = 2 \times 10^{-9} $$

幾乎永遠不會中——但「幾乎永遠」不等於「永遠」。這正是並行 bug 最陰險之處：它可能在你的測試環境裡一年都不出現，卻在上線後流量爆增的某個深夜引爆。 競爭條件不是用測試「測掉」的，而是要靠正確的同步設計從根本上排除。

鎖會反咬一口：死結

加鎖能消除競爭，但鎖本身又會帶來新的災難：死結(deadlock)。設想兩個執行緒各需要兩把鎖 A 和 B：

執行緒 1：lock(A); lock(B); ...   # 先拿 A 再拿 B
執行緒 2：lock(B); lock(A); ...   # 先拿 B 再拿 A

如果執行緒 1 拿到了 A、執行緒 2 同時拿到了 B，接下來：1 想要 B（被 2 握著）、2 想要 A（被 1 握著）。兩者互相等待對方手上的鎖，永遠等下去，整個程式凍結。這就是著名的「哲學家用餐問題」的核心。

死結要同時滿足四個條件才會發生（Coffman 條件），缺一不可：

1. 互斥(mutual exclusion)：資源一次只能被一個執行緒持有。
2. 持有並等待(hold and wait)：執行緒握著資源的同時又去要別的。
3. 不可搶占(no preemption)：資源不能被強行奪走，只能自願釋放。
4. 循環等待(circular wait)：存在一個「A 等 B、B 等 C、…、最後一個又等 A」的環。

理解這四個條件的價值在於：只要破壞任何一個，就能預防死結。最常用、也最務實的手法是破壞第四個——強制所有執行緒以同一固定順序取得鎖（例如永遠先 A 後 B）。只要大家都遵守這個全域順序，就不可能形成循環等待，死結自然無從發生。這也是大型系統裡「鎖階層(lock ordering)」規範存在的理由。

重點回顧

• 競爭條件的根源是「看似一個動作的操作（如 counter+1）實際由多個機器指令組成」，而作業系統可在任意指令邊界搶占切換，導致交錯與遺失更新。
• 保護共享資料的那段程式碼叫臨界區段，並行的核心目標是達成互斥：同時至多一個執行緒進入。
• 純軟體互斥困難且脆弱，實務上仰賴硬體的原子指令（如 CAS/cmpxchg）；自旋鎖、mutex、號誌、條件變數都建立在其上。
• 自旋鎖原地空轉適合極短臨界區段，mutex 睡眠讓出 CPU 適合較長等待；Linux 的 futex 是「無競爭走使用者空間、有競爭才進核心」的混合策略。
• 鎖會引入死結，它需同時滿足 Coffman 四條件；破壞任一條件即可預防，最常見的是「固定取鎖順序」打破循環等待。

深入探討（研究所視角）

前面把鎖講得像萬靈丹，但研究所層級要面對的真相是：鎖本身既不充分、也常常不是最好的答案。

記憶體模型與重排序：原子性還不夠。 現代 CPU 與編譯器為了效能，會把指令重新排序、把寫入暫存在每個核心的 store buffer 裡延後對其他核心可見。這意味著即使每個操作都「原子」，不同核心觀察到記憶體事件的順序也可能不一致——這就是為什麼裸用 volatile 防不了並行 bug。正確的並行程式必須依據語言的記憶體模型(memory model)（如 C11/C++11 的 memory_order、Java 的 JMM）插入適當的記憶體屏障(memory barrier/fence)。最弱的 relaxed 只保證單一變數的原子性，acquire/release 建立跨執行緒的「happens-before」可見性保證，seq_cst（循序一致）最強也最貴。鎖之所以「能用」，正是因為它的取得／釋放隱含了 acquire/release 屏障，幫你把可見性順序釘好。

無鎖與等待自由：跳過鎖。 鎖會造成阻塞：持鎖執行緒若被搶占或崩潰，所有等鎖的人一起卡住（這叫優先序反轉, priority inversion，1997 年火星探路者號就栽在這上面）。無鎖(lock-free) 資料結構直接用 CAS 迴圈操作共享結構，保證「至少有一個執行緒能持續前進」，整體不會因單一執行緒停擺而全停。代價是 ABA 問題（值從 A 變 B 又變回 A，CAS 誤判沒變）與極高的設計難度。更強的等待自由(wait-free) 保證「每個執行緒都在有限步內完成」，但實作代價通常高到不切實際。

交易記憶體：把臨界區段當資料庫交易。 一個更上層的構想是軟體交易記憶體(Software Transactional Memory, STM)：程式設計師只要把一段操作標記為 atomic { ... }，執行期就樂觀地讓它跑，若偵測到與其他交易衝突就整段回滾重試——就像資料庫的交易隔離。它讓「組合多個操作」變容易（鎖很難安全組合），但有重試開銷與 I/O 不可回滾等限制。Intel 曾在硬體層提供 TSX(Transactional Synchronization Extensions) 嘗試加速，後因安全漏洞大多被停用，至今仍是活躍的研究方向。

形式化驗證：證明而非測試。 既然並行 bug 幾乎測不出來，最前沿的做法是用模型檢查(model checking) 工具（如 TLA+、SPIN）窮舉所有可能的執行緒交錯，數學上證明互斥與無死結成立。微型核心 seL4 更進一步，對整個核心做了機器檢查的形式化正確性證明。

這些議題向上連結到分散式系統（跨機器的共識與一致性，本質是並行問題的放大版）、向下連結到計算機組織（快取一致性協定 MESI 正是硬體在替你維護記憶體可見性）。可以說，「兩個行程同時加一」這個小到不能再小的問題，一路通往現代計算最深的理論核心：當多個獨立的執行流共享狀態時，我們究竟能保證什麼、又必須付出什麼代價。