排他制御とデッドロック

なぜ排他制御が要る？──競合状態（レースコンディション）

複数の処理が同じメモリを共有していると、実行の順番（タイミング）次第で結果が変わってしまう ことがあります。これが競合状態（レースコンディション）です。

典型例が「カウンタを 1 増やす」だけの操作。コード上は1行でも、CPUの中では 読む → 足す → 書く の3ステップに分かれます。

counter++ は実際にはこの3手:
  1. counter の値をレジスタに読む  (read)
  2. レジスタの値に 1 を足す        (modify)
  3. 結果を counter に書き戻す       (write)

スレッドAとBが両方 counter++（初期値0）を実行すると、運が悪いとこう絡みます。

時刻  スレッドA            スレッドB            counter
 t1   read(0)                                   0
 t2                        read(0)              0   ← Aの加算前を読んでしまう
 t3   add → 1                                   0
 t4                        add → 1              0
 t5   write(1)                                  1
 t6                        write(1)             1   ← 2回足したのに1!

2回足したのに結果は 1。これを 更新の喪失（lost update） と呼びます。怖いのは、たいてい正しく動いてしまい、ごく稀にしか壊れない こと。テストをすり抜け、本番の高負荷時だけ再現する——並行バグが「再現しないバグ」の代表格なのはこのためです。

クリティカルセクションとロック

競合が起きる「共有データを触る危険な区間」を クリティカルセクション と呼びます。ここを 同時に1つの処理しか実行できない（相互排他＝mutual exclusion） ようにすれば、競合は防げます。

そのための最も基本的な道具が ロック です。クリティカルセクションに入る前に鍵を取得（lock / acquire）し、出るときに返す（unlock / release）。鍵が取られている間、他の処理は待たされます。

lock(mtx)          // 鍵を取る（誰かが持っていたら待つ）
  counter = counter + 1   // ← クリティカルセクション（1人だけ）
unlock(mtx)        // 鍵を返す（待っている誰かが入れる）

こうすれば先ほどの「read → add → write」が 割り込まれずにひとまとまりで実行 され、更新の喪失が起きません。

ミューテックスとセマフォ

排他制御の代表的な部品が ミューテックス（mutex） と セマフォ（semaphore） です。名前が似ていて混同されがちですが、役割が違います。

• ミューテックス：鍵は1本。「同時に1つだけ」を保証する（相互排他＝mutual exclusion の略）。基本的に ロックした本人が解放する（所有者の概念がある）。
• セマフォ：内部に カウンタ を持ち、「同時にN個まで」を許す仕組み。acquire で1減らし（0なら待つ）、release で1増やす。所有者の縛りはなく、ある処理が acquire、別の処理が release してもよい。

カウンタ上限を 1 にしたセマフォ（バイナリセマフォ）はミューテックスに似ますが、「所有者が解放する」という制約がない点が異なります。用途も、ミューテックスが 資源の保護（クリティカルセクションを守る）なのに対し、セマフォは 資源の個数管理 や 処理の順序づけ（シグナル通知） に向きます。

アトミック操作：ロックを使わない選択肢

ロックを取らずに競合を防ぐ手もあります。CPUが提供する アトミック操作 の利用です。アトミック（atomic＝それ以上分割できない）とは、「読む→変える→書く」が他から割り込まれない1つの不可分な操作 として実行されること。

代表が CAS（Compare-And-Swap / 比較交換）。「今の値が期待どおりなら新しい値に書き換える。違っていたら何もしない」を1命令でやります。

CAS(addr, expected, new):
  もし *addr == expected なら *addr = new として成功
  そうでなければ失敗（誰かが先に書き換えた）
→ これら全体が割り込まれない（アトミック）

CAS を「成功するまで再試行」する形にすると、ロックなしで（lock-free）安全なカウンタやキュー が作れます。ロック待ちで眠らせる必要がなく、デッドロックも原理的に起きにくいのが利点。一方で正しく書くのは難しく、ABA問題（値がA→B→Aと戻ると「変わっていない」と誤認する）などの落とし穴もあります。

デッドロック：守りすぎて全員が固まる

ロックで安全にしたつもりが、今度は 互いに相手の鍵を待ち合って、誰も先に進めなくなる ことがあります。これが デッドロック（deadlock） です。

古典的なのが「ロックを取る順番の食い違い」。送金処理で、口座AとBを両方ロックしたいとします。

スレッド1: lock(A) → （Bを取りたい）→ lock(B)
スレッド2: lock(B) → （Aを取りたい）→ lock(A)

t1: スレッド1が A を確保
t2: スレッド2が B を確保
t3: スレッド1は B を待つ（2が持っている）
t4: スレッド2は A を待つ（1が持っている）
→ 互いに永久に待つ＝デッドロック

デッドロック成立の4条件（Coffman条件）

デッドロックは、次の 4つが同時に成り立つとき に発生します。逆に言えば、どれか1つでも崩せば防げます。

実務で一番効くのは 「循環待ち」を崩す こと。ロックに グローバルな取得順序（例：口座IDの小さい方から取る）を決め、全員がその順で取る ようにすれば、輪が閉じず先の送金例も解消します。

ルール: ID が小さい口座から先にロックする
スレッド1（A→B送金）: lock(min(A,B)) → lock(max(A,B))
スレッド2（B→A送金）: lock(min(A,B)) → lock(max(A,B))
→ 両者とも同じ順で取るので、循環待ちが起きない

デッドロックと紛らわしい状態

「進まない」系の障害はデッドロックだけではありません。区別できると原因の切り分けが速くなります。

まとめ