鎖：自旋鎖與 mutex

鎖自己也是一個變數

上一課用 pthread_mutex_lock 修好了競爭條件。但鎖本身也只是記憶體裡的一個值，兩個執行緒同時來拿，它怎麼保證只給一個人？

最直覺的寫法是自己放一個變數當門牌：看到 flag 是 0 就進去，進去之前把它改成 1。

while (flag == 1) { }   // 有人在裡面就等
flag = 1;               // 輪到我，把門關上
// …臨界區…
flag = 0;               // 把門打開

這一課會把這段程式弄壞，再一步一步換成真正可靠的做法。

這一課的 C 語法：&a 是變數 a 的位址，pthread_create(&a, …) 要把新執行緒的編號寫進 a，所以傳位址給它。void * 是「什麼型別都可以指的指標」，執行緒函數的參數一律是這個型別；(long)arg、(void *)1 是強制轉型，這裡只是拿指標的位置順便傳一個數字。while (…) { } 的大括號裡是空的：條件成立就一直重新檢查。想多練指標可以看 C++ 軌。

Peterson 演算法：只用讀寫也做得到

剛才的第三個任務也是找這種錯誤的實用技巧：懷疑某個空隙有問題，就在那裡暫時加一點延遲，讓錯誤更容易重現。這只能幫你找到錯誤，不能拿來修。

只用普通的讀取和寫入，有辦法寫出正確的鎖嗎？有。G. L. Peterson 在 1981 年發表的兩執行緒版本只要兩個變數：

interested[me] = 1;   // 我想進去
turn = other;         // 但如果你也想，你先請
while (interested[other] == 1 && turn == other) { }   // 你想進去，而且輪到你：我等
// …臨界區…
interested[me] = 0;   // 我出來了

如果兩個人同時想進去，兩人都會寫 turn，後寫的那個人把機會讓給了對方，所以只有一個人會等。如果對方根本不想進去，interested[other] 是 0，直接進去，不會被擋在外面。

在真實硬體上，光是對的順序還不夠

教學核心的記憶體是順序一致的：指令照程式寫的順序發生，寫入之後別人馬上看得到。所以上面的 Peterson 跑 200 次都對。

真實的多核心 CPU 不是這樣。x86-64 的核心會把寫入先放在自己的寫入緩衝區（store buffer），後面的讀取可以先做。也就是說，interested[me] = 1 還沒讓別人看見，這個核心已經讀了 interested[other]；兩邊同時這樣做，兩邊都讀到 0，就一起進去了。結果和你剛才對調兩行很像：對方檢查的時候，還看不到我想進去。差別是這次程式順序完全正確，是硬體造成的。

同一個演算法放到真正的 Linux 上，每個執行緒進出 300 萬次。__sync_synchronize() 是記憶體屏障（memory barrier）：前面的寫入做完，才可以做後面的讀取。

第 1 次：
should be  6000000
no fence   5999999
with fence 6000000

第 2 次：
should be  6000000
no fence   6000000
with fence 6000000

第 3 次：
should be  6000000
no fence   6000000
with fence 6000000

第 4 次：
should be  6000000
no fence   5999999
with fence 6000000

第 5 次：
should be  6000000
no fence   6000000
with fence 6000000

在真正的 Linux 上實際執行的結果（Compiler Explorer 的 Linux x86-64 環境，gcc 13.3，2026-11-04）。

六百萬次裡只少一次，而且不是每次都發生，比上一課的 counter++ 難抓得多。加了屏障的那一行在這幾次都正確；這只是這幾次的結果，真正的保證來自處理器規格。

所以 Peterson 演算法現在主要用來理解問題。實務上不要自己用普通變數寫同步，改用硬體提供的原子指令，或直接用函式庫的鎖，它們都已經包含需要的屏障。

test-and-set：把檢查和設定合成一個動作

剛才的問題都出在「檢查」和「設定」是兩步。硬體的解法是提供一個原子指令，一步做完兩件事，中間不會有別的核心或執行緒插進來。

gcc 內建的 __sync_lock_test_and_set(&x, 1) 就是這種指令：把 x 改成 1，回傳它原本的值。

while (__sync_lock_test_and_set(&flag, 1)) { }   // 回傳 1 就繼續試
// …臨界區…
__sync_lock_release(&flag);                      // 把 flag 改回 0

這就是自旋鎖（spinlock）：拿不到就原地一直重試。在 x86 上，這類操作對應 xchg 這種帶鎖定語意的指令，同時也有屏障的效果。

等待的人一直在佔用 CPU，這叫忙等（busy waiting）。如果持有鎖的人很快就放手，等一下比較划算；如果對方很久才放，就是白白燒 CPU。mutex 的做法相反：拿不到就請核心讓自己睡著，放手的人負責叫醒。

忙等與阻塞，誰比較划算

在教學核心用同一段臨界區，一顆 CPU、輪轉排程，實際跑出來的數字：

自旋鎖版本的 test-and-set 呼叫了 600 次，只拿到 10 次鎖；mutex 版本等鎖的人睡了 9 次；原子操作沒有鎖，但只適用於「加一個數字」這種事。

但結論不是「自旋鎖一定比較差」。下面是真正的 Linux，兩顆 CPU，兩個執行緒各加 100 萬次，臨界區只有一行：

第 1 次：
no lock  counter =  1323779     16 ms
spinlock counter =  2000000     38 ms
mutex    counter =  2000000    112 ms
atomic   counter =  2000000     18 ms

第 2 次：
no lock  counter =  1801310      9 ms
spinlock counter =  2000000     48 ms
mutex    counter =  2000000     65 ms
atomic   counter =  2000000     18 ms

第 3 次：
no lock  counter =  1916527      6 ms
spinlock counter =  2000000     44 ms
mutex    counter =  2000000    112 ms
atomic   counter =  2000000     18 ms

在真正的 Linux 上實際執行的結果（Compiler Explorer 的 Linux x86-64 環境，gcc 13.3，2026-11-04）。

這裡自旋鎖比 mutex 快，因為有第二顆 CPU：持有鎖的人正在跑，很快就放手，等一下就好；mutex 在搶鎖時要進核心睡覺、再被叫醒，這段成本反而比較高。no lock 的答案是錯的，快也沒有用。

• 自旋鎖：適合多核心、臨界區極短、不會在裡面睡覺；不適合單核心、臨界區長、持有時可能被換下來。
• mutex：一般情況的預設選擇；不適合不能睡覺的地方（例如中斷處理）。
• 原子操作：適合單一變數的加減、旗標、計數器；要同時更新好幾個變數並保持一致時就不夠用。

Linux 核心內部兩種都用：在不能睡覺的地方用自旋鎖。一般應用程式用 pthread_mutex 就好。

mutex 怎麼做到不用每次都進核心

如果每次 lock、unlock 都要做系統呼叫，mutex 會很慢。Linux 的做法是 futex（fast user-space mutex）：大部分情況不進核心，只有真的要睡覺時才進去。

lock：
  用原子指令把鎖從 0 改成 1
  成功 → 拿到了，完全沒有進核心（快路徑）
  失敗 → 標記「有人在等」，呼叫 futex(FUTEX_WAIT) 請核心讓我睡（慢路徑）

unlock：
  用原子指令把鎖改回 0
  如果有人在等 → 呼叫 futex(FUTEX_WAKE) 叫醒一個

FUTEX_WAIT 有一個重要的細節：核心會再檢查一次那個值是不是你以為的那個值，檢查和睡著是一個不可分割的動作。如果在你決定要睡、還沒睡著的空隙裡，對方已經放手了，檢查就會失敗，你不會睡下去等一個永遠不會來的通知。這個空隙造成的問題叫喚醒遺失，下一課會親手排出來。

在 os-lab 上，系統呼叫面板可以看到 lock 和 unlock。教學核心把搶不到鎖的情況簡化成直接等待，真實的 glibc 細節更多，但快路徑、慢路徑的想法是一樣的。

鎖的粒度也是取捨。整個帳務系統一把大鎖：簡單，不容易寫錯，但所有人都要排隊。每個帳戶一把鎖：不同帳戶可以同時處理，但轉帳要同時拿兩把，下下一課會看到這樣容易出事。

持有鎖的時候做慢的事，代價也會變大。在教學核心實測：兩個執行緒各 sleep(1)，如果 sleep 放在鎖裡面，虛擬時間約 2 秒；放到鎖外面，約 1 秒。只鎖真正需要保護的那幾行。

這兩個錯誤怎麼避免

重複上鎖：POSIX 規定一般型別（PTHREAD_MUTEX_NORMAL）的 mutex 重複上鎖會死結，預設型別則是未定義行為，不能依賴它的結果。常見的整理方式是把函數分成兩種：對外的 deposit() 負責上鎖，內部的 deposit_locked() 假設呼叫者已經持有鎖，兩種都命名清楚。

忘記解鎖：通常發生在提早 return 或錯誤處理的分支。C 程式常把解鎖集中在函數結尾，所有分支都跳到那裡；C++ 的 std::lock_guard 則在離開範圍時自動解鎖，這也是 C++ 軌 會教的慣用法。

這兩個錯誤和競爭條件有一樣的麻煩：你剛才隨機跑時可以看到，修好之前也有幾次是正常結束的。只測一次不夠。

重點整理

• 用普通變數當鎖會出錯：檢查和設定是兩步，中間可能換人。
• Peterson 演算法只靠讀寫就能做到互斥，但真實多核心 CPU 會重排寫入與讀取，需要記憶體屏障。自己不要這樣寫同步。
• 硬體的原子指令（test-and-set）把檢查和設定合成一步，可以做出自旋鎖。
• 自旋鎖等待時佔用 CPU，適合多核心、極短的臨界區；mutex 等待時睡著，是一般情況的預設選擇。Linux 的 futex 讓沒人搶的時候完全不用進核心。
• 單一變數的簡單更新可以用原子操作；要一起更新好幾個變數就要用鎖。
• 忘記解鎖、重複上鎖都會讓程式卡住，提早 return 的分支要特別檢查。只鎖真正需要的那幾行。

想再深入，可以讀免費公開的教科書 OSTEP 第 28 章 Locks。

鎖解決的是「不要同時進去」。下一課的問題不一樣：我要等到某個條件成立才繼續，這時候該怎麼等？