排他制御とデッドロック 入門 - ミューテックス・セマフォから食事する哲学者まで

複数のスレッドが同じ変数を触るコードは、単体テストでは通るのに本番でごくまれに壊れる、という厄介な挙動を見せます。原因の多くは共有状態の同期の不足です。この記事では、なぜ排他制御が必要なのか（レースコンディション）から始めて、ミューテックス・セマフォ・条件変数といった同期の道具、そして排他制御が招く新たな問題であるデッドロックまでを、古典的な定義と各言語の公式APIを一次ソースに整理します。プロセスとスレッドの基礎は姉妹編の並行処理と並列処理 入門で扱ったので、本記事はその一段先、複数の実行主体が同じメモリを触るときの話に集中します。

なぜ排他制御が必要か（レースコンディション）

レースコンディション（競合状態）とは、複数のスレッドが共有データに同時にアクセスし、その結果が実行の順序（タイミング）に依存して変わってしまう状態を指します。典型例が「カウンタを1増やす」だけの処理です。

# 悪い例: 2スレッドで各10万回インクリメントしても、合計は20万にならない
import threading
 
counter = 0
 
def worker():
    global counter
    for _ in range(100_000):
        counter += 1  # 読み取り・加算・書き戻しの3ステップ
 
t1 = threading.Thread(target=worker)
t2 = threading.Thread(target=worker)
t1.start(); t2.start()
t1.join(); t2.join()
print(counter)  # 200000 にならないことがある

counter += 1は一見1つの操作に見えますが、実際には「現在値を読む」「1を足す」「書き戻す」の3段階に分かれます。スレッドAが値を読んだ直後、書き戻す前にスレッドBが同じ古い値を読むと、片方の加算が上書きされて消えます。この「複数ステップに分かれた操作が途中で割り込まれる」ことが競合の本質です。途中で割り込まれず全体が一気に完了する性質をアトミック（不可分）と呼び、レースコンディションはアトミックであるべき操作がそうでないときに起こります。

クリティカルセクションと相互排他

共有リソースにアクセスするコード領域、つまり「同時に1つのスレッドしか実行してはいけない区間」をクリティカルセクション（危険領域）と呼びます。先の例ではcounter += 1がそれにあたります。

このクリティカルセクションに「同時に入れるのは1スレッドだけ」という制約を課すのが相互排他（mutual exclusion）です。正しい相互排他の仕組みが満たすべき性質は、古典的に次の3つとされています。

• 相互排他（mutual exclusion）: 同時にクリティカルセクションに入れるのは高々1スレッド
• 進行（progress）: 誰もクリティカルセクションにいないなら、入りたいスレッドは有限時間で入れる（無関係なスレッドに邪魔されない）
• 有限待ち（bounded waiting）: あるスレッドが待たされる回数に上限がある（永久に追い抜かれ続けない）

ソフトウェアだけでこれを実現する試みが歴史的に研究されました。2プロセス向けの最初の正しい解が1965年のDekker（デッカー）のアルゴリズム、それを簡潔にしたのが1981年のG. L. PetersonによるPetersonのアルゴリズムです。いずれも共有フラグとturn変数だけで相互排他を実現しますが、現代のCPUはメモリの読み書き順序を入れ替える（リオーダリング）ため、そのままでは正しく動きません。実務ではこうした低レベルの正しさはOSやライブラリが提供するプリミティブに任せ、私たちはミューテックスやセマフォを使います。

ミューテックス

ミューテックス（mutex, mutual exclusionの略）は、相互排他を実現する最も基本的な道具です。「ロックを取る（lock / acquire）」と「ロックを返す（unlock / release）」の2操作を持ち、あるスレッドがロックを保持している間、他のスレッドは同じミューテックスをロックできず待たされます。鍵付きの部屋の鍵が1本だけあるイメージで、鍵を持つ人だけが部屋（クリティカルセクション）に入れます。

先ほどのカウンタをミューテックスで直します。

# 良い例: ロックで囲めば結果は必ず 200000
import threading
 
counter = 0
lock = threading.Lock()
 
def worker():
    global counter
    for _ in range(100_000):
        with lock:          # ここから
            counter += 1    # クリティカルセクション
        # with を抜けると自動で解放
 

C++ではstd::mutexを直接lock/unlockするのではなく、RAII（スコープを抜けると自動解放）のラッパーを使うのが定石です。例外が飛んでもロックが確実に解放されるためです。

#include <mutex>
 
std::mutex mtx;
long counter = 0;
 
void worker() {
    for (int i = 0; i < 100000; ++i) {
        std::lock_guard<std::mutex> guard(mtx);  // ロック取得
        ++counter;
    }  // guard のスコープを抜けると自動で unlock
}

std::lock_guard<std::mutex>のような型引数つきの表記はコード内で扱い、文章中では必ずインラインコードにします。GoやJavaにも同様の仕組みがあります。Goはsync.Mutexとdefer、JavaはsynchronizedブロックやReentrantLockです。

// Go: sync.Mutex と defer Unlock がイディオム
var (
    mu      sync.Mutex
    counter int
)
 
func worker() {
    for i := 0; i < 100000; i++ {
        mu.Lock()
        counter++
        mu.Unlock() // 短い区間なので defer を使わず即解放
    }
}

ミューテックスに関わる用語をいくつか押さえておきます。再入可能（reentrant / recursive）ミューテックスは、同じスレッドが同じロックを二重に取ってもデッドロックしないものです。JavaのsynchronizedやReentrantLockは再入可能ですが、C++のstd::mutexは非再入で、同じスレッドが二重ロックすると未定義動作になります（再入したいならstd::recursive_mutex）。また、ロックの所有権という考え方があり、多くのミューテックスは「ロックを取ったスレッドだけが解放できる」という規約を持ちます。

セマフォ（生産者消費者問題）

セマフォ（semaphore）はEdsger Dijkstraが1960年代のTHEオペレーティングシステムの設計過程で導入した、より一般的な同期プリミティブです。内部にカウンタを持ち、2つの操作で増減させます。

• P操作（wait / acquire）: カウンタを1減らす。0未満になるなら、正になるまでブロックして待つ
• V操作（signal / release）: カウンタを1増やす。待っているスレッドがいれば1つ起こす

PとVはオランダ語に由来し、DijkstraはVをverhogen（増やす）、Pをprolaag（probeer te verlagen＝「減らそうと試みる」の短縮）と説明しています。カウンタは「利用可能なリソースの残数」を表すと考えると直感的です。

セマフォは初期値によって2つの使い方に分かれます。

バイナリセマフォはミューテックスに似ていますが、決定的な違いがあります。ミューテックスは「ロックしたスレッドだけが解放できる」所有権を持つのに対し、セマフォには所有者がなく、あるスレッドがP操作した後、別のスレッドがV操作してよい点です。この非対称性がセマフォを「スレッド間のシグナル（合図）」として使える理由です。

計数セマフォの代表的な応用が生産者消費者問題（producer-consumer problem）です。生産者がデータをバッファに入れ、消費者が取り出す構図で、バッファが満杯なら生産者は待ち、空なら消費者は待つ必要があります。これを「空き枠の数」と「詰まっているデータの数」という2つのセマフォで表現します。

# 生産者消費者: 有限バッファをセマフォ2つ + ミューテックスで守る
import threading, collections
 
buf = collections.deque()
CAPACITY = 5
empty = threading.Semaphore(CAPACITY)  # 空き枠の数（初期値=容量）
full  = threading.Semaphore(0)         # 詰まっているデータ数（初期値=0）
mutex = threading.Lock()               # buf 自体の保護
 
def producer(item):
    empty.acquire()          # 空き枠を1つ確保（満杯なら待つ）
    with mutex:
        buf.append(item)
    full.release()           # データが1つ増えた合図
 
def consumer():
    full.acquire()           # データを1つ確保（空なら待つ）
    with mutex:
        item = buf.popleft()
    empty.release()          # 空き枠が1つ増えた合図
    return item

emptyとfullはリソースの数を数え、mutexはバッファ操作そのものの短い相互排他を担う、という役割分担がポイントです。

条件変数・スピンロック

セマフォの他にも、待ち合わせのための道具があります。

条件変数（condition variable）は「ある条件が成立するまで待つ」ための仕組みで、必ずミューテックスとセットで使います。waitはミューテックスを解放して眠り、他スレッドのnotify（signal）で起こされると再びロックを取り直します。重要な注意点として、waitはwhileループの中で条件を再チェックしなければなりません。偽装的に起こされる「見せかけの起床（spurious wakeup）」や、起こされてからロックを取り直すまでに条件が再び崩れる可能性があるためです。

# 条件変数: バッファが空でなくなるまで待つ（while で再チェック）
import threading, collections
 
cv = threading.Condition()
buf = collections.deque()
 
def consumer():
    with cv:
        while not buf:          # if ではなく while
            cv.wait()           # ロックを解放して待つ
        return buf.popleft()
 
def producer(item):
    with cv:
        buf.append(item)
        cv.notify()             # 待っている消費者を1つ起こす

スピンロック（spinlock）は、ロックが取れるまでスレッドを眠らせず、ループでひたすら再試行し続ける（ビジーウェイト）タイプのロックです。眠って起こす（コンテキストスイッチ）コストを省けるため、ロックを保持する時間がごく短い場合やマルチコアでのカーネル内処理では有利です。一方、待ち時間が長いとCPUを無駄に食い続けるため、シングルコアや長い待ちには不向きです。「待ちが極めて短いと分かっているならスピン、長引くなら眠らせる（ミューテックス）」が基本的な使い分けです。

デッドロックとは（4条件）

排他制御はレースを防ぎますが、新たな問題を生みます。デッドロック（deadlock）は、複数のスレッドが互いに相手の持つロックの解放を待ち合い、全員が永久に進めなくなる状態です。

最小の例は「2つのロックを逆順に取る」ことです。スレッドAがロック1を持ってロック2を待ち、スレッドBがロック2を持ってロック1を待つと、両者は永遠に待ち続けます。

// 悪い例: A は m1->m2、B は m2->m1 の順で取るとデッドロックしうる
var m1, m2 sync.Mutex
 
func threadA() {
    m1.Lock()
    m2.Lock() // B が m2 を持っていたら永久に待つ
    // ...
    m2.Unlock(); m1.Unlock()
}
 
func threadB() {
    m2.Lock()
    m1.Lock() // A が m1 を持っていたら永久に待つ
    // ...
    m1.Unlock(); m2.Unlock()
}

デッドロックが成立する必要条件を、Edward Coffmanらが1971年の論文「System Deadlocks」で整理しました。次の4条件（Coffmanの条件）がすべて同時に成り立つときにのみデッドロックが起こりえます。逆に言えば、どれか1つでも崩せばデッドロックは原理的に発生しません。

この「4条件のどれかを崩す」という視点が、後述する予防策の設計指針になります。

食事する哲学者の問題

デッドロックを説明する古典が、Dijkstraが1965年ごろに定式化し（当初は「食事する五人組」）、後にTony Hoareが哲学者と箸の形にした食事する哲学者の問題（dining philosophers problem）です。

円卓に5人の哲学者が座り、各人の左右に1本ずつ、計5本の箸（フォーク）があります。哲学者は「考える」と「食べる」を繰り返し、食べるには左右2本の箸が必要です。素朴に「まず左の箸を取り、次に右の箸を取る」というルールにすると、全員が同時に左の箸を取った瞬間、全員が右の箸（＝隣の人が持つ左の箸）を待ち続け、循環待機が完成してデッドロックします。

この問題はCoffmanの4条件を体感するのに最適で、代表的な解法はそれぞれどの条件を崩しているかで理解できます。

• 資源順序付け: 箸に番号を振り、必ず小さい番号から取る。1人だけ取る順が逆転するので循環待機を崩す（後述のロック順序統一と同じ発想）
• 同時に食べる人数の制限: 計数セマフォで「席に着けるのは同時に4人まで」とし、保持と待機による全員の飽和を防ぐ
• 両方の箸をアトミックに取る: 2本同時に取れないなら1本も取らない（保持と待機を崩す）

デッドロックへの3つの対処（予防・回避・検出）

デッドロックへの対処は、大きく3つの戦略に分かれます。

予防は最も実務的で、たとえば「ロックを取る順序を全体で統一する」（循環待機を崩す）や「必要なロックを一括で取る」（保持と待機を崩す）が該当します。

回避の代表がDijkstraの銀行家のアルゴリズム（banker's algorithm）です。銀行が貸し倒れを避けるように、各プロセスが必要とするリソースの最大量を事前に申告させ、あるリソース要求を許可すると「安全状態（safe state）」を保てるかを毎回シミュレートします。安全状態とは「全プロセスを何らかの順序で最後まで完了させられる割り当てが存在する」状態で、そうでない要求は保留します。理論的には美しいものの、最大需要の事前申告や毎回のチェックが重く、汎用OSではほとんど使われません。

検出と回復は、リソース割り当てグラフのサイクルを定期的に探し、見つかったらどれかのスレッドを中断（ロールバック）して輪を断ち切ります。データベースはこの戦略を採り、デッドロックを検出すると片方のトランザクションを犠牲者（victim）として自動的にロールバックします。詳しくはデータベーストランザクションとACID・分離レベル 入門で扱っています。

ライブロックとスターベーション

デッドロックの近縁として、混同しやすい2つの状態があります。

ライブロック（livelock）は、スレッドが停止こそしていないものの、互いに譲り合い続けて実質的に何も進まない状態です。狭い廊下で2人がすれ違おうとして、同じ方向に同時に避け続けてぶつかり続けるイメージです。デッドロックの回避策として「一定時間取れなければ全ロックを手放してリトライ」を素朴に入れると、両者が同時に手放して同時にリトライし、これを繰り返してライブロックになることがあります。対策は待ち時間にランダムなゆらぎ（ジッタ）を入れる、優先順位に差をつけるなどです。

スターベーション（starvation, 飢餓）は、特定のスレッドが必要なリソースをいつまでも得られず進めない状態です。優先度の高いスレッドに割り込まれ続ける、あるいはロックの獲得が不公平で常に他者に追い抜かれる、といったときに起こります。対策は先に触れた「有限待ち」を保証する公平な（fair）ロックで、JavaのReentrantLockは公平モードを選べます（ただし公平性を上げるとスループットは下がる傾向があります）。

実務での回避策

理論を踏まえ、日々のコードで効く回避策をまとめます。

ロック順序を統一するのが最も費用対効果の高い予防策です。プログラム全体で「複数のロックを取るときは必ず同じ順序（例: アドレス順やID順）で取る」と決めれば、循環待機が原理的に起きません。先のGoの悪い例は、両スレッドがm1 -> m2の順に統一するだけで直ります。C++には複数ミューテックスをデッドロックなく一括ロックするstd::scoped_lock（内部でstd::lockのデッドロック回避アルゴリズムを使う）があり、渡す順序に依存せず安全に取れます。

// 良い例: scoped_lock なら渡す順序に関係なくデッドロックしない
#include <mutex>
 
std::mutex m1, m2;
 
void transfer() {
    std::scoped_lock lock(m1, m2);  // 両方をアトミックに取得
    // ... 両方を保持した処理 ...
}  // スコープを抜けると両方まとめて解放

その他の実務的な指針です。

• タイムアウトつきロック: 無限に待たず、一定時間で諦めてリトライやエラーにする（横取り不可を実質的に緩める）。JavaのtryLock(timeout)、Goではcontextとの組み合わせなど
• ロック粒度の設計: 粗いロック（1本で全体を守る）は単純だが並行度が落ち、細かいロック（データごとに分ける）は並行度が上がるがデッドロックの余地が増える。まず粗く作り、競合が測定できてから必要な箇所だけ細かくするのが安全
• クリティカルセクションを短く: ロック中にI/Oや重い計算、他のロック取得をしない。持つ時間が短いほど競合もデッドロックも起きにくい
• 共有そのものを減らす: 各スレッドにローカルな状態を持たせ、最後に集約する、あるいはメッセージパッシング（Goのchannelなど）で「メモリを共有して通信するのではなく、通信してメモリを共有する」設計にする
• lock-free / atomic: カウンタのような単純な操作は、ロックの代わりにアトミック命令（CAS: compare-and-swap）で実装できます。ロックを一切使わないロックフリーなデータ構造はデッドロックとは無縁ですが、正しく書くのは難しく、ABA問題などの落とし穴があります。まずは正しいロックを使い、計測でボトルネックと分かってから検討する対象です

そして、書いたコードが本当にレースフリーかは目視では確認しきれません。動的解析ツールを使います。Goはgo test -raceやgo run -raceでレースディテクタ（ThreadSanitizerベース）を有効にでき、実行中に検出したデータ競合を報告します。C/C++やRustでもThreadSanitizer（-fsanitize=thread）が使えます。CIに組み込んでおくと、まれにしか再現しない競合を早期に捕まえられます。

# Go: レースディテクタつきでテスト。競合があれば WARNING: DATA RACE を出す
go test -race ./...

まとめ

排他制御は「レースコンディションを防ぐ」ために不可欠ですが、その手段であるロックは「デッドロック」という新たな失敗モードを持ち込みます。要点を整理します。

• レースコンディションは、アトミックであるべき操作が途中で割り込まれて起こる。クリティカルセクションを相互排他で守る
• ミューテックスは所有権つきの相互排他、セマフォは所有権のないカウンタでリソース数管理やシグナルに使う。条件変数はwhileで条件を再チェックしながら待つ
• デッドロックはCoffmanの4条件（相互排他・保持と待機・横取り不可・循環待機）がすべて揃うと起こる。どれか1つ崩せば防げる
• 対処は予防・回避（銀行家のアルゴリズム）・検出の3系統。実務ではロック順序の統一を軸に、タイムアウト・粒度設計・共有削減・レースディテクタを組み合わせる
• 停止しないが進まないライブロックと、特定スレッドが得られないスターベーションも意識する

土台となるプロセスとスレッド、並行と並列の違いは並行処理と並列処理 入門で、ロックが実際に運用される具体例はデータベーストランザクションとACID・分離レベル 入門で、メモリ管理の観点は仮想メモリとページングの仕組みで補完できます。