Learning Objectives
- 說明 counter++ 為什麼不是一個動作，以及遺失更新怎麼發生
- 親手排出讓結果出錯的交錯順序，再用隨機執行看同一支程式可能有哪些結果
- 找出程式裡的臨界區，用 mutex 保護它
- 說明為什麼「測試跑過一次是對的」不能證明沒有競爭條件
同一支程式，每次答案都不一樣
兩個執行緒各把同一個變數加 300 萬次，答案應該是 600 萬。這支程式放到真正的 Linux 上跑六次：
第 1 次：counter = 4056803
第 2 次：counter = 4543638
第 3 次：counter = 4251054
第 4 次：counter = 5945684
第 5 次：counter = 4110325
第 6 次：counter = 4082710
在真正的 Linux 上實際執行的結果（Compiler Explorer 的 Linux x86-64 環境，gcc 13.3，2026-11-03）。
沒有一次是 600 萬，而且每次都不同。程式沒有用亂數，也沒有讀外部資料，只有 counter++ 這一行在做事。
這種「結果取決於執行順序」的錯誤叫競爭條件（race condition）。這一課要親手把它排出來。
教學核心跑的是同一種程式，只是圈數少很多，讓你可以一步一步看。
counter++ 其實是三個動作
C 語言寫起來只有一行，CPU 做的是三件事：
load counter 把記憶體裡的 counter 讀到暫存器
add 1 暫存器加 1
store counter 把暫存器寫回記憶體
每個執行緒有自己的暫存器，記憶體裡的 counter 則是共用的。作業系統隨時可能在兩個指令之間暫停一個執行緒、換另一個上來（上一課的內容切換），暫存器的內容會保存起來，下次輪到時原封不動放回去。
如果 A 讀到 0 之後被換下來，B 也讀到 0，兩個人都算出 1、都寫回 1：加了兩次，結果只多 1。這叫遺失更新（lost update）。
臨界區與互斥
會存取共用資料、而且不能和別人交錯執行的那段程式，叫臨界區（critical section）。上面的臨界區就是 counter++ 這一行。
解法要滿足三個條件：
| 條件 | 意思 |
|---|---|
| 互斥（mutual exclusion） | 同一時間最多一個執行緒在臨界區裡 |
| 能前進（progress） | 臨界區沒人時，想進去的人不會被無故擋在外面 |
| 等待有上限（bounded waiting） | 不會有人永遠排不到 |
最常用的工具是 mutex（互斥鎖）：進入臨界區前 pthread_mutex_lock，離開時 pthread_mutex_unlock。別人持有鎖時，呼叫 lock 的執行緒會被核心放到等待狀態，不會佔用 CPU。
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_lock(&lock);
counter++;
pthread_mutex_unlock(&lock);
注意 mutex 沒有禁止切換：持有鎖的執行緒還是可能在 counter++ 中間被換下來。差別在於別人就算輪到了，也進不了臨界區。
鎖本身怎麼做到「不會兩個人同時拿到」，是下一課的內容。
為什麼這種錯誤很難抓
加上 mutex 之後，同一支程式在真正的 Linux 上跑三次（每個執行緒 30 萬次，因為鎖比較花時間）：
第 1 次：counter = 600000
第 2 次：counter = 600000
第 3 次：counter = 600000
在真正的 Linux 上實際執行的結果（Compiler Explorer 的 Linux x86-64 環境，gcc 13.3，2026-11-03）。
有鎖就正確了。但沒有鎖的版本並不是每次都錯得這麼明顯。如果兩個執行緒沒有同時開始，第一個可能在第二個建立之前就做完了，測試就會得到完全正確的答案。圈數少、核心少、機器不忙的時候，錯誤可能一直不出現。
所以：
- 跑過一次是對的，不能證明沒有競爭條件。 錯誤取決於時機，可能要到正式環境、流量變大才出現。
- 加
printf除錯可能讓錯誤消失。 輸出會改變時機，這類錯誤有時被叫做 Heisenbug（一觀察就變）。 - 要從程式碼判斷：有沒有共用資料？有沒有人會寫入？存取的時候有沒有用同一把鎖保護？
工具可以幫忙：gcc 和 clang 的 ThreadSanitizer（編譯時加
-fsanitize=thread）會在執行時偵測沒有保護的共用存取。它只能抓到這次執行有走到的路徑，所以仍然不能取代對程式碼的判斷。
用程式模擬兩種交錯
用 Python 把剛才的三個指令寫出來。order 是執行順序，例如 'AABBAB' 代表 A、A、B、B、A、B。注意 reg 是每個執行緒各一個，counter 只有一個。
實作：算出所有交錯的結果
A、B 各有 3 個指令，全部的先後順序有幾種？其中幾種會遺失更新？補完程式，算出每種結果出現幾次。
combinations(range(6), 3) 會列出「A 的 3 個指令放在 6 個位置裡的哪幾個」的所有選法，每一種選法就是一種交錯。
確認一下
兩個執行緒各做一次 counter++，counter 從 0 開始。下面哪一種順序的結果是 1？（A1 是 A 的 load、A2 是 add、A3 是 store）
一支沒有用鎖的多執行緒程式，在你的電腦上測試 100 次都正確。可以得到什麼結論？
只有一顆 CPU 核心時，還會發生遺失更新嗎？
有 mutex 保護 counter++ 時，持有鎖的執行緒可能在 load 和 store 之間被換下來嗎？
下面哪一段程式需要保護？
重點整理
counter++是 load、add、store 三個動作，切換可能發生在任何兩個動作之間。- 結果取決於執行順序的錯誤叫競爭條件；遺失更新是最典型的一種。不需要多核心，一顆核心加上切換就會發生。
- 存取共用資料、不能交錯的程式段是臨界區。用 mutex 保護時，切換還是會發生，只是別人進不來。
- 測試通過不能證明沒有競爭條件，要從程式碼判斷：共用、有寫入、沒有同一把鎖保護。
下一課打開鎖的內部：硬體提供什麼指令，自旋鎖和 mutex 有什麼差別。