TL;DR
複数のプロセスやスレッドが共有資源を使うとき、ある時点で 1 つだけが使えるようにして整合性を保つ仕組み。相互排除とも呼ぶ。同じクリティカルセクションに、複数の主体が同時に入らないようにすることである。
なぜ必要か
Wikipedia は、片方向連結リストの例を挙げている。2 つのノードを同時に削除すると、一方の削除が失われてノードが残ることがある。排他制御で状態の更新が同時に走らないようにすれば、この問題を防げる。
仕組み
Wikipedia によると、実現方法には次のようなものがある。
- ハードウェアによる方法: 割り込みの禁止や、test-and-set、compare-and-swap などのアトミック操作を使ったビジーウェイト
- ソフトウェアによる方法: デッカー、ピーターソン、ランポートのパン屋のアルゴリズム
- 高度な同期プリミティブ: ロック、スピンロック、mutex、セマフォ、モニタ、メッセージパッシング
ソフトウェアによるアルゴリズムは、アウトオブオーダー実行のある環境では動かないことがあるので、OS の同期機構を使うほうが望ましい。
例
Monitor pattern は、スレッド間の排他制御と条件待ちをカプセル化したデザインパターンである。セマフォは、アクセスを任意の数 N まで許し、N = 1 なら mutex と同じ働きをする。
注意点
Wikipedia は、排他制御で気をつける問題として次を挙げている。
- デッドロック: 複数のプロセスが互いの解放を待ち続け、処理が止まる
- ライブロック: 処理は動いているのに、どの主体も資源を取得できない
- フェアネス: 資源を求める主体が、いつかは利用できること