セマフォとミューテックスの古典的同期問題

セマフォの原理：カウンタと待ち行列

セマフォ（semaphore）は Dijkstra が 1965 年に提案した同期プリミティブで、本質は 整数カウンタと、それを操作する2つのアトミックな操作 だけです。

• wait（P 操作、acquire、down とも）：カウンタを 1 減らす。減らした結果が負なら、呼び出したスレッドをブロックして待ち行列に入れる。
• signal（V 操作、release、up とも）：カウンタを 1 増やす。待っているスレッドがいれば 1 つ起こす。

wait(S):
  S.count -= 1
  if S.count < 0:
    このスレッドを S の待ち行列に入れてブロック
signal(S):
  S.count += 1
  if S.count <= 0:        // まだ待っている者がいる
    待ち行列から1つ取り出して起こす

ここで重要なのは、カウンタの符号が状態を表す こと。値が正なら「あと何個 wait を通せるか」を、負なら「何個のスレッドが待たされているか」を表します。count -= 1 と判定が 不可分（アトミック） に行われる点が肝で、これを保証するために実装内部ではスピンロックや割り込み禁止で短いクリティカルセクションを守ります。

待ち行列を FIFO にすれば、起こす順序が公平になりスターベーション（飢餓）を避けられます。逆に「ただ起こす」だけの実装だと、毎回同じスレッドが先に走って一部が永久に待たされうる——強いセマフォ（FIFO 保証）と弱いセマフォ の区別はここにあります。

生産者消費者問題（有界バッファ）

固定長 N のリングバッファに、生産者が要素を入れ、消費者が取り出す。守るべき不変条件は2つ——満杯のときに入れない／空のときに取り出さない、そして インデックス更新の競合を防ぐ ことです。これを 2つの計数セマフォと1つの相互排他 で表します。

empty = セマフォ(N)   // 空き枠の数
full  = セマフォ(0)   // 詰まっている要素の数
mutex = セマフォ(1)   // バッファ操作の相互排他

生産者:                        消費者:
  wait(empty)   // 空きを確保     wait(full)    // 要素を確保
  wait(mutex)                     wait(mutex)
    バッファに入れる                バッファから取る
  signal(mutex)                   signal(mutex)
  signal(full)  // 要素+1          signal(empty) // 空き+1

empty と full の 和は常に N に保たれ、片方の wait が他方の signal で必ず釣り合います。これが「満杯／空」を正しくブロックする仕組みです。

読者書込者問題

共有データに対し、読者は同時に何人でも許すが、書込者は1人だけ・読者とも排他 したい。読み取りが多い場面で並行性を上げる定式化です。素朴な解（第一読者問題）はこうです。

rw_mutex   = セマフォ(1)   // 書込みの排他（読者集団 vs 書込者）
read_mutex = セマフォ(1)   // readers カウンタの保護
readers    = 0

読者:                                書込者:
  wait(read_mutex)                     wait(rw_mutex)
    readers += 1                         書き込む
    if readers == 1: wait(rw_mutex)    signal(rw_mutex)
  signal(read_mutex)
    読む
  wait(read_mutex)
    readers -= 1
    if readers == 0: signal(rw_mutex)
  signal(read_mutex)

ポイントは 最初の読者が rw_mutex を取り、最後の読者が返す こと。読者がいる間は書込者が締め出されます。ただしこの解は読者を優先するため、読者が途切れないと 書込者が永久に待つ（writer starvation）。実務の RW ロックは、待機中の書込者がいたら新規読者をブロックする「書込者優先」や、到着順に処理する公平版で飢餓を防ぎます。

食事する哲学者問題

円卓に N 人の哲学者、隣り合う2人の間に1本ずつフォーク。食べるには 左右2本 が要る。全員が同時に左フォークを取ると、各自が右を待ち続けて 循環待ちのデッドロック に陥る——これが本質です。

最も明快なのが 資源順序付け。最後の1人だけ取得順が逆になるため輪が閉じず、デッドロックが原理的に起きません。

左フォーク = i, 右フォーク = (i+1) mod N とすると
  哲学者 i: lo = min(左,右), hi = max(左,右)
  wait(fork[lo]); wait(fork[hi])   // 全員が「小さい番号から」
    食べる
  signal(fork[hi]); signal(fork[lo])

ミューテックスとの本質的な違い：所有権

二値セマフォとミューテックスは「同時に1つだけ」を実現する点で似ますが、所有権（ownership） の有無が決定的に違います。

所有権があることで生まれる最大の利点が 優先度継承 です。低優先度スレッドがミューテックスを握ったまま高優先度スレッドにプリエンプトされ、中優先度が割り込んで進めなくなる——これが優先度逆転。所有者が一意に決まるミューテックスなら「握っている低優先度スレッドを一時的に昇格させる」対処ができますが、所有者の概念がないセマフォではそもそも誰を昇格すべきか定まりません。詳細は 優先度逆転と優先度継承 を参照してください。

Linux では、ユーザー空間の高速な相互排他は futex を土台に実装され、競合がない限りシステムコールを発行せずアトミック命令だけで完結します。カーネル内部の各種ロックは カーネルのロック機構 に、ロックを使わない選択肢は ロックフリーとCAS にまとめてあります。

まとめ