排他制御

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

排他制御を行う場合にはアトミック性が重要となる。プロセスがある資源を占有しようとする時には、以下の操作を行う必要があるが、これらの途中で他のプロセスに実行が移行すると整合性を保つ事が出来ない。

資源が他のプロセスによって占有されていない事を確認する。
資源を占有する。

アトミック性を確保するために後述するような各種の実装方法が利用される。

クリティカルセクションでは、排他制御を必要とする。

実装方法

排他制御の実装方式としては、以下のようなものが利用される。

留意すべき現象と性質

デッドロック

詳細は「デッドロック」を参照

排他制御によりロックされた資源に、複数のユーザからアクセス要求が出された時に、お互いに資源が解放されるのをブロック状態で待つという状況が発生する。この様な状態に至ると、どのユーザも資源獲得の処理が進まず資源が確保出来ない為停止状態となる。この様な状態をデッドロックという。

例えば、蛇と蛙と蛞蝓（ナメクジ）の三すくみの状況にあたる。

また、食事する哲学者の問題が典型的な例として挙げられる。円卓に5人の哲学者が着席し食事をするのであるが、箸が合計5本しかなく、1本ずつ哲学者の間に置かれている。それぞれの哲学者は2本の箸を利用出来るのであるが、1本は左側の人と共有しており、もう1本は右側の人と共有している。料理を食べるときには、まず左の箸を獲得し、次に右の箸を獲得して、両方が揃えば料理を一口食べる。一口食べ終わったら、箸を元の場所に置き、思索にふけるという事を繰り返すとする。ここで、たまたまタイミングが悪く、全ての哲学者が料理を食べようとして、同時に左の箸を取ったとすると、次にどの哲学者も右の箸を取ることが出来ない。右の箸を取れるまで左の箸を戻さずに待つ戦略であれば、どの哲学者も永遠に待ち続けることになる。

ライブロック（Livelock）

デッドロックと同様、排他制御によりロックされた資源に、複数のユーザからアクセス要求が出されたときに、お互いに資源が解放されるのをビジー状態で待つという状況が発生する。デッドロックでは個々のユーザにおける資源獲得のための処理が進行しないのに対し、ライブロックでは資源獲得の処理が進行しているにも関わらず、どのユーザも資源が獲得出来ない状況である。

例えば、狭い道を歩いていて対面した歩行者2名が、お互いに相手が避けようとした方向に動いてしまい、避けられ無いという事が有る。次に、逆の方向に避けようして避けられない。このような状況が続いて、何時まで経ってもすれ違うことが出来ないという状況にあたる。

食事をする哲学者の問題において、箸が揃わなかった場合に獲得した箸を一旦戻す戦略に変更しても、タイミングが悪ければ、一斉に左の箸を取っては元に戻すことを繰り返し続ける事になる。(リソーススタベーション参照)

フェアネス（公平性、Fairness）

「共有資源を利用したいユーザが、いつかは共有資源を利用できる」という、排他制御アルゴリズムが満たすべき性質。フェアネスが満たされない場合の例であるが、駅の切符売り場に3台の券売機があって、各券売機に行列が出来ているとき、並んだ行列の進みが遅い場合に他の行列の後尾に並びなおす戦略を採用すると、運が悪ければ何時まで経っても券を購入できないということが起こりうる。

k-バイパス（k-Bypass）

共有資源へのアクセス要求を出したユーザが、後から要求を出した最大k個のユーザによって、先に資源を使われてしまう可能性があるということを表す、フェアネスの度合いを計る指標である。

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。