排他制御
排他制御(はいたせいぎょ)とは、コンピュータ・プログラムの実行において、複数のプロセスが利用出来る共有資源に対し、複数のプロセスからの同時アクセスにより競合が発生する場合に、あるプロセスに資源を独占的に利用させている間は、他のプロセスが利用できないようにする事で整合性を保つ処理の事をいう。相互排除または相互排他(mutual exclusion)ともいう。最大k個のプロセスが共有資源にアクセスして良い場合を k-相互排除という。
換言すれば1つのクリティカルセクションに複数のプロセス(またはスレッド)が同時に入ることを防ぐことである。クリティカルセクションとは、プロセスが共有メモリなどの共有資源にアクセスしている期間を指す。排他制御の問題は1965年、エドガー・ダイクストラが並行プログラミング制御における問題の解法に付いて扱った論文で扱ったのが最初である。
排他制御の重要性を示す例として、片方向連結リストがある(右図)。
シングルプロセッサシステムでは、あるプロセスがクリティカルセクションにあるとき割り込みを禁止するというのが最も単純な排他制御である。その間、いかなる割り込みハンドラも動作できない(それによって実質的にプリエンプションを防ぐ)。この方式は効果的だが、同時に様々な問題もはらんでいる。クリティカルセクションが長い場合、クロック割り込みが処理されないためにシステム時刻が徐々に遅れていくという事態が発生しうる。また、クリティカルセクション内でプロセスが停止すると、他のプロセスに制御を渡せなくなり、結果としてシステム全体が停止することになる。μITRONなどでは、タスク切り替え(プリエンプションとディスパッチ)を禁止するという操作もある。より上品な方式としてビジーウェイトで相互排他する方式もある。
ビジーウェイトはシングルプロセッサでもマルチプロセッサでも有効である。共有メモリと不可分なテスト・アンド・セット命令を使うことで、排他制御を実現する。プロセスは共有メモリ上の特定位置について値を調べて新たな値をセットするという操作を不可分に実施でき、それによって一度に1つのプロセスだけがフラグをセットできることを保証する。