|
排他制御（はいたせいぎょ）とは、コンピュータ・プログラムの実行において、複数のプロセスが利用出来る共有資源に対し、複数のプロセスからの同時アクセスにより競合が発生する場合に、あるプロセスに資源を独占的に利用させている間は、他のプロセスが利用できないようにする事で整合性を保つ処理の事をいう。相互排除または相互排他（）ともいう。最大k個のプロセスが共有資源にアクセスして良い場合を k-相互排除という。 換言すれば1つのクリティカルセクションに複数のプロセス（またはスレッド）が同時に入ることを防ぐことである。クリティカルセクションとは、プロセスが共有メモリなどの共有資源にアクセスしている期間を指す。排他制御の問題は1965年、エドガー・ダイクストラが ''Solution of a problem in concurrent programming control''（並行プログラミング制御における問題の解法）と題した論文で扱ったのが最初である〔E. W. Dijkstra. Solution of a problem in concurrent programming control . Communications of the ACM, 8(9), page 569, September, 1965.〕〔Taubenfeld. The Black-White Bakery Algorithm . In Proc. Distributed Computing, 18th international conference, DISC 2004. Vol 18, 56-70, 2004〕。 排他制御の重要性を示す例として、片方向連結リストがある（右図）。このような連結リストからノードを削除するには、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'' は連結リストに残ってしまう。 この問題は排他制御を施して複数の状態更新処理が同時に行われないようにすれば解決する。 == 排他制御の実施 == 排他制御を実施する手段はハードウェアによるものとソフトウェアによるものがある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「排他制御」の詳細全文を読む スポンサード リンク
|