排他制御
とは、コンピュータ・プログラムの実行において、複数のプロセスが利用出来る共有資源に対し、複数のプロセスからの同時アクセスにより競合が発生する場合に、あるプロセスに資源を独占的に利用させている間は、他のプロセスが利用できないようにする事で整合性を保つ処理の事をいう。相互排除または相互排他（）ともいう。最大k個のプロセスが共有資源にアクセスして良い場合を k-相互排除という。
換言すれば1つのクリティカルセクションに複数のプロセス（またはスレッド）が同時に入ることを防ぐことである。クリティカルセクションとは、プロセスが共有メモリなどの共有資源にアクセスしている期間を指す。排他制御の問題は1965年、エドガー・ダイクストラが並行プログラミング制御における問題の解法に付いて扱った論文で扱ったのが最初である。
排他制御の重要性を示す例として、片方向連結リストがある（右図）。このような連結リストからノードを削除するには、1つ前のノードにある、次のノードを指すポインタを、削除したいノードの、次のノードを指すように書き換える（例えば、ノード "i" を削除するには、ノード "i-1" のnextポインタをノード "i+1" を指すよう書き換える）。このとき、その連結リストを複数プロセスが共有しているなら、2つのプロセスがそれぞれ別のノードを削除しようとして次のような問題を生じる可能性がある。
この問題は排他制御を施して複数の状態更新処理が同時に行われないようにすれば解決する。