排他制御（ロック・セマフォ・ミューテックス）

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：競合状態とクリティカルセクション　|　関連：デッドロック・並行性のパターン

要点（BLUF）

競合（競合状態とクリティカルセクション）を防ぐには、クリティカルセクションに相互排他を課す。その道具がロック（ミューテックス）・セマフォ。
ロック自体の取得が競合してはいけないので、土台にアトミック命令（test-and-set / compare-and-swap）がハードで用意されている。
待ち方が2系統：スピンロック（取れるまでCPUを回し続ける／短い待ち向け）とブロッキング（OSに登録して眠る／長い待ち向け）。セマフォは「同時にN個まで」を数える一般化。

概念 ── 守る道具の全体像

クリティカルセクションを「同時に1つだけ」にするには、入口で印を立て、出口で外す仕組みが要ります。これがロック。

ミューテックス（mutex）：ロックの基本形。lock() で取得（取れなければ待つ）、unlock() で解放。所有者の概念があり、取った者だけが外せる。
セマフォ（semaphore）：内部にカウンタを持ち、「同時にN個まで通す」資源管理に使う。N=1のセマフォ（バイナリセマフォ）はミューテックスに近い。
スピンロック：取れるまでループで待ち続ける（CPUを手放さない）軽量ロック。

flowchart TB
    subgraph MX["ミューテックス（N=1：1人だけ）"]
      m["lock -> 区間 -> unlock"]
    end
    subgraph SE["セマフォ（N個まで）"]
      s["acquire（カウンタ--）-> 資源 -> release（カウンタ++）"]
    end

仕組み① ── アトミック命令が土台

ここに鶏と卵の問題があります。「ロックを取る」操作自体が「フラグを読んで、空いていれば立てる」という read-modify-write で、これが競合したら（競合状態とクリティカルセクション）ロックの意味がありません。

解決はソフトでなくハードにあります。CPUは「読みと書きを不可分に行う命令」を提供します。

test-and-set：あるビットを読み、同時に1にセットする（読みと書きが1命令で割り込まれない）。
compare-and-swap (CAS)：「いまの値が期待値と一致したら新値に置き換える」を不可分に行う。

これらは1命令でCPUがバスをロックして実行するので、途中で他コアが割り込めません。このハードの不可分性の上に、すべての高級な同期（ミューテックス・セマフォ・ロックフリーデータ構造）が積み上がります。「最終的な正しさはハードが保証する」のがポイントです。

仕組み② ── スピン vs ブロック

ロックが取れないとき、待ち方に2系統あります。

flowchart TB
    want["ロックを取りたい"] --> avail{"空いている?"}
    avail -->|"Yes"| got["取得して区間へ"]
    avail -->|"No (スピン)"| spin["ループで再試行（CPUを回し続ける）"] --> avail
    avail -->|"No (ブロック)"| sleep["待機列に入り眠る（CPUを手放す）"]
    sleep -->|"解放時に起こされる"| got

スピンロック：CPUを手放さずループ。待ちが極短いときに有利（眠って起きるコストより速い）。マルチコアで「別コアがすぐ手放す」前提。シングルコアで長く回すと、ロック保持者にCPUが回らず最悪。
ブロッキング（ミューテックス）：取れなければOSの待機列に入りスリープ（プロセスとスレッドの待機状態）。CPUを別の仕事に回せる。代わりに眠る/起こす（文脈切り替え）のコスト。待ちが長いときに有利。

要するに「待ち時間 < 文脈切り替えコスト」ならスピン、それ以上ならブロック。実用のロックは短時間スピンしてから眠るハイブリッドが多い。

具体例 ── ロックで競合を消す

競合状態とクリティカルセクションの壊れたカウンタを、ロックで囲むだけで直ります（[[#対応ラボ]] の同じ 04-01_race_and_lock.py）。

lock = threading.Lock()
def add_safe():
    global counter2
    for _ in range(N_ITERS):
        with lock:               # ここがクリティカルセクション（1スレッドのみ）
            tmp = counter2
            counter2 = tmp + 1

実行結果（実機）:

== ロック有り ==
期待値 16000 / 実際 16000 / 一致: True

with lock: の中を「同時に1つ」に制限したので、read-modify-writeが割り込まれず、更新喪失が消えました。

仕組みの直観 ── なぜこの設計か

ハードにアトミック命令を置く理由：ソフトだけでは「ロックを取る競合」を断ち切れない（無限後退）。どこかでハードが不可分性を提供しないと土台が立たない。
セマフォがカウンタを持つ理由：相互排他は「N=1の資源管理」の特殊形。一般化して「N個の同種資源（接続プール・バッファ枠）」を数で管理できる（並行性のパターンの有界バッファ）。
スピンとブロックを分ける理由：待ち時間の長短で最適な戦略が逆。短いのに眠れば切替コストで損、長いのに回せばCPUを無駄に焼く。状況依存だから両方用意する。

⚠️ よくある誤解・落とし穴

「ロックすれば安心」→ ロックの取り方を誤るとデッドロック（デッドロック）。粒度が粗いと並列性が死ぬ（性能の評価とアムダールの法則の逐次部分が増える）。
「スピンロックは速いから常に良い」→ 長い待ちや過剰なコアでCPUを浪費する。保持時間が短い場合限定。
「セマフォ＝ミューテックス」→ ミューテックスは所有者がいて取った者だけが解放。セマフォは誰でもrelease可能でカウントを数える。用途が違う。
「volatile/atomicにすれば同期不要」→ 単一変数の可視性は得ても、複数操作の不可分性は別問題。クリティカルセクションには依然ロックが要る。

対応ラボ

cs-foundations-study/labs/04-01_race_and_lock.py（ロック有り側を実行し、結果が常に正しくなることを確認済み）。