排他制御（はいたせいぎょ）とは、コンピュータ・プログラムの実行において、複数のプロセスが利用出来る共有資源に対し、複数のプロセスからの同時アクセスにより競合が発生する場合に、あるプロセスに資源を独占的に利用させている間は、他のプロセスが利用できないようにする事で整合性を保つ処理の事をいう。相互排除または相互排他（mutual exclusion）ともいう。最大k個のプロセスが共有資源にアクセスして良い場合を k-相互排除という。

換言すれば1つのクリティカルセクションに複数のプロセス（またはスレッド）が同時に入ることを防ぐことである。クリティカルセクションとは、プロセスが共有メモリなどの共有資源にアクセスしている期間を指す。排他制御の問題は1965年、エドガー・ダイクストラが並行プログラミング制御における問題の解法に付いて扱った論文で扱ったのが最初である[1][2]。

排他制御の重要性を示す例として、片方向連結リストがある（右図）。このような連結リストからノードを削除するには、1つ前のノードにある、次のノードを指すポインタを、削除したいノードの、次のノードを指すように書き換える（例えば、ノード i を削除するには、ノード i-1 のnextポインタをノード i+1 を指すよう書き換える）。このとき、その連結リストを複数プロセスが共有しているなら、2つのプロセスがそれぞれ別のノードを削除しようとして次のような問題を生じる可能性がある。

2つのプロセスはそれぞれノード i と i+1 を同時に削除しようとする。どちらのノードも連結リストの途中にあり、先頭でも最後尾でもないとする。

ノード i-1 のnextポインタはノード i+1 を指すよう書き換えられ、ノード i のnextポインタはノード i+2 を指すよう書き換えられる。

両方の削除処理が完了した状態を見ると、ノード i-1 がノード i+1 を指すよう書き換えられたために、ノード i+1 は連結リストに残ってしまう。

この問題は排他制御を施して複数の状態更新処理が同時に行われないようにすれば解決する。
排他制御の実施

排他制御を実施する手段はハードウェアによるものとソフトウェアによるものがある。
ハードウェアによる方式

シングルプロセッサシステムでは、あるプロセスがクリティカルセクションにあるとき割り込みを禁止するというのが最も単純な排他制御である。その間、いかなる割り込みハンドラも動作できない（それによって実質的にプリエンプションを防ぐ）。この方式は効果的だが、同時に様々な問題もはらんでいる。クリティカルセクションが長い場合、クロック割り込みが処理されないためにシステム時刻が徐々に遅れていくという事態が発生しうる。また、クリティカルセクション内でプロセスが停止すると、他のプロセスに制御を渡せなくなり、結果としてシステム全体が停止することになる。μITRONなどでは、タスク切り替え（プリエンプションとディスパッチ）を禁止するという操作もある。より上品な方式としてビジーウェイトで相互排他する方式もある。

ビジーウェイトはシングルプロセッサでもマルチプロセッサでも有効である。共有メモリと不可分なテスト・アンド・セット命令を使うことで、排他制御を実現する。プロセスは共有メモリ上の特定位置について値を調べて新たな値をセットするという操作を不可分に実施でき、それによって一度に1つのプロセスだけがフラグをセットできることを保証する。フラグをセットできなかったプロセスは別の処理を行って後で再試行するか、プロセッサを他のプロセスに明け渡して後で再試行するか、フラグをセットできるまでループして再試行を繰り返すといった動作が可能である。プリエンプションは可能なので、この方式ではプロセスがフラグ（ロック）を保持したまま停止してもシステム全体は機能し続ける。

不可分操作命令は他にもいくつかの実装があり、どれもデータ構造の排他制御に使える。よく見られるのはコンペア・アンド・スワップ (CAS) である。CAS命令を使えば wait free と呼ばれる排他制御を任意の共有データに実施できる。そのためには連結リストを作り、各ノードが実行したい操作を表すようにする。CAS命令はその連結リストに新しいノードを挿入する際に使用する。ノードの挿入はCAS命令を使えば一度に1つのプロセスしか成功しない。失敗したプロセスはノード追加処理が成功するまで試行し続ける。各プロセスはこのデータ構造のローカルなコピーを保持でき、連結リストを走査でき、リストのローカルコピー上の各操作を実行できる。
ソフトウェアによる方式

ハードウェアサポートを必要とする方式とは別に、ビジーウェイトを使ってソフトウェアのみで排他制御を実現する方式も存在する。例えば、次のようなものがある。

デッカーのアルゴリズム

ピーターソンのアルゴリズム

ランポートのパン屋のアルゴリズム[3]

Szymanskiのアルゴリズム（en）

Taubenfeld の Black-White Bakery Algorithm[2]

これらのアルゴリズムはアウト・オブ・オーダー実行が働くプラットフォーム上では動作できない(但し、メモリバリアを実現する機械語命令を持っているCPUプラットフォームの場合は除く)。アルゴリズム実施中、メモリ操作はプログラミングした通りに行われなければならない[4]。

OSのマルチスレッドライブラリが同期機構を提供しているなら、それを使う方が望ましい。ハードウェアによる方式が利用可能ならばそれを使って実装されているだろうし、そうでないならばソフトウェアによる方式を利用しているだろう。たとえばOSのライブラリを使い、スレッドが他者が既に獲得しているロックを獲得しようとしたとき、OSはそのスレッドを中断させてコンテキストスイッチし動作可能な他のスレッドを動作させたり、動作可能な他のスレッドがなければプロセッサを省電力状態にしたりといったことをする可能性がある。したがって、ほとんどの現代の排他制御技法はキューイングとコンテキストスイッチを使いレイテンシとビジーウェイト時間を削減しようとする。しかし、スレッドを中断させて再開させるのにかかる時間がスレッドがロックを獲得できるまでの待ち時間より長い場合に限り、スピンロックの方が適しているといえる。