競合状態とクリティカルセクション

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

📎 前提：プロセスとスレッド　|　関連：排他制御（ロック・セマフォ・ミューテックス）・CPUと命令実行

要点（BLUF）

**競合状態（race condition）**とは、複数の実行が共有データに同時アクセスし、実行順序（タイミング）次第で結果が変わってしまう状態。
原因は counter += 1 のようなread-modify-write が不可分でないこと。読んでから書くまでの間に他スレッドが割り込むと、更新が失われる。
共有データを触る危険な区間がクリティカルセクション。ここを「同時に1つの実行だけ」に制限すれば（相互排他）競合は消える。

概念 ── 「順番が決まっていない」が諸悪の根源

1つのスレッドだけなら、コードは書いた順に動き結果は決定的です。ところが複数スレッドが同じメモリを共有し（プロセスとスレッド）、OSが任意のタイミングで切り替える（CPUスケジューリング）と、命令のインターリーブ（混ざり方）が不定になります。

ほとんどの混ざり方は無害ですが、特定の混ざり方だけ結果が壊れる。これが競合状態。やっかいなのは、大半の実行では正しく動き、稀にしか壊れないこと。だから「手元では再現しないバグ」になりがちです。

仕組み ── なぜ `counter += 1` が壊れるか

counter += 1 は1行ですが、CPU（CPUと命令実行）では3つの操作に分かれます。

読み出し：counterの現在値をレジスタへ（例：5）
加算：レジスタで +1（→6）
書き戻し：レジスタの値をcounterへ（→6）

2つのスレッドがこれをインターリーブすると：

sequenceDiagram
    participant A as スレッドA
    participant M as counter（共有）
    participant B as スレッドB
    Note over M: counter = 5
    A->>M: 読み出し -> 5 を取得
    B->>M: 読み出し -> 5 を取得（Aの書き戻し前！）
    A->>M: 6 を書き戻す
    B->>M: 6 を書き戻す（Aの+1が消える）
    Note over M: counter = 6（本当は7のはず）

AとBが両方+1したのに、結果は+1ぶんしか増えない。更新が失われた（lost update）。

実機で確かめます（[[#対応ラボ]] の 04-01_race_and_lock.py。読み書きを明示的に分け、間にプリエンプション点を置いて忠実に再現）。

counter = 0
def add_unsafe():
    global counter
    for _ in range(N_ITERS):
        tmp = counter        # (1) 読み出し
        time.sleep(0)        # ここでOSが他スレッドへ切替うる
        counter = tmp + 1    # (3) 書き戻し（古いtmpだと更新が消える）

実行結果（実機・8スレッド×2000回。値は実行ごとに変動）:

== ロック無し ==
期待値 16000 / 実際 2199 / 失われた更新 13801

8スレッドが合計16000回インクリメントしたのに、結果は2199。1万件以上の更新が消えた。これが競合状態の破壊力です。

補足：CPythonのGILにより、素朴な counter += 1 は偶然壊れないことがあります。競合の本質は「読み出しと書き戻しの間に割り込みうる」点なので、ラボでは読み書きを分け切替点を明示しています。

概念 ── クリティカルセクション

共有データを読み書きする危険な区間を クリティカルセクションと呼びます。上の例なら「読み出し〜書き戻し」の3操作。

競合を防ぐ要件は、この区間に**相互排他（mutual exclusion）**を課すこと：どの瞬間も、クリティカルセクションに入っている実行は高々1つ。誰かが入っていれば他は入口で待つ。

flowchart LR
    enter["入口（他がいれば待つ）"] --> cs["クリティカルセクション（共有データを操作・1スレッドのみ）"]
    cs --> exit["出口（次の待機者を通す）"]

正しい相互排他には次の性質が要ります。

相互排他：同時に2つ以上が入らない（安全性）。
進行：誰も入っていないなら、入りたい者が入れる（デッドロックしない）。
有限待機：いつかは入れる（飢餓しない）。

この区間をどう守るかが排他制御（ロック・セマフォ・ミューテックス）の道具立てです。

仕組みの直観 ── なぜこの設計か（なぜ難しいのか）

共有メモリの代償：スレッドが軽量・高速なのは共有のおかげ（プロセスとスレッド）。その同じ共有が、同期しなければ競合を生む。性能と安全のトレードオフ。
不可分性が鍵：壊れるのは「途中で割り込めるから」。だから守り方は「途中で割り込めなくする＝不可分（atomic）にする」。これがロックやアトミック命令の存在理由。
非決定性ゆえにテストで見つけにくい：壊れる混ざり方は稀。だから「動いた＝正しい」が通用しない。設計段階で共有とクリティカルセクションを洗い出すしかない。

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

「1行のコードは不可分」→ 高級言語の1行はCPUの複数命令。x += 1 も list.append も中で分割される。
「読むだけなら安全」→ 他が書き換え中の中途半端な値を読む危険がある（特に複数フィールドの構造体）。
「めったに起きないから大丈夫」→ 稀なだけで必ず起きる。本番の高負荷で顕在化する典型。
「GILがあるPythonは競合しない」→ I/Oや明示的なyield、複数バイトコードにまたがる操作で競合する。GILは万能ではない。

対応ラボ

cs-foundations-study/labs/04-01_race_and_lock.py（実行して更新喪失とロックによる解消を確認済み）。

確認できること：lost update、クリティカルセクションをロックで守ると正しくなること