デッドロックの回避・検知

恐竜本7章です。6章では非同期処理の同期に使えるロックオブジェクトの種類に関する解説が述べられていました。本章ではそういうロックオブジェクトを不適切に使った場合に生じるデッドロックの発生条件、回避手法、検知手法に関して述べられています。正直このスライドが上位互換です。

デッドロック発生の必要条件

  • 排他制御であること(mutex)
  • プロセスがリソースを握ったまま別のリソースが空くのを待っていること(hold and wait)
  • リソースの専有が途中で中断されないこと(no preemption)
  • 待ちの関係が循環していること(circular wait)
    • P1がP2の握っているリソースを待ち、P2がP3のリソースを待ち、P3がP1のリソースを待つなど

これらのANDが必要条件なので、どれかが崩れるとデッドロックは発生しない。

　リソースの専有・待ちの状態をきれいに表す手法としてsystem resource-allocation graphがある。これは有向グラフであり、プロセスとリソースがノードとなる。プロセスPがリソースRを待っているときP→Rの向きに辺を記入する(request edge)。また、RがPに割り当てられているときR→Pの向きに辺を引く(assignment edge)。リソースが1種類につき1個しか存在しない場合は、このグラフが閉路を持っているときデッドロックである。一方で、1種類につき複数個のインスタンスが存在するリソースの場合、閉路があってもデッドロックではない場合がある。どちらにせよ閉路がなければデッドロックではないことは言える。

OSによるデッドロックへの対処

　OSがプロセスのデッドロックに対処する方法は3パターンある。

  • デッドロックを防止する
  • デッドロックを回避する
  • デッドロックが生じたら検知してデッドロックを解消する
  • デッドロックを無視し、手動回復の手段だけ与える

UNIXやWindowsではデッドロックを無視する方法をとっている。デッドロックの回避や検知はオーバーヘッドがあり、かつデッドロックは頻繁に起こるわけでもないので、無視のほうがコスパが良いという考え方になっている。

デッドロックの防止

　デッドロックの防止は、デッドロック発生必要条件のうち少なくとも1つを破るようルールを作る対処法である。

　「排他制御であること」を破る方法としてはすべてを共有可能なリソースとして扱うことが考えられる。しかし、本質的に共有できないリソースもあるので現実的ではない。

　「プロセスがリソースを握ったまま他のリソース解放を待つ」を破る方法としては、プロセスの実行前にすべてのリソースを割り当ててから実行する、新規リソースは現在リソースを保持していないときだけ割り当てる、などの方法がある。いずれにしても必要ないタイミングでリソースを保持したり、後で必要になるとわかっているのに一旦解放して再取得するなど、無駄が多い。更に、人気のあるリソースを待っているプロセスは、いつまでもそのリソースが空かず実行できないというスターベーションが生じる可能性がある。

　「リソースの専有が途中で中断されないこと」を破る方法としては、リソース要求をプロセスが発したときすぐに割り当てられない場合は、そのリソースが持っているリソースを一回全部解放するという物が考えられる。もしくは、既に別プロセスが持っているリソースを無理やり解放して要求したプロセスに与えるという方法がある。この方法はCPUレジスタやメモリの割当などすぐに復帰できるようなリソースには使えるが、プリンターのような一旦中断して後で復帰することができないリソースには使えない。

　「待ちの関係が循環していること」を破る方法としては、リソースの獲得順を決められた順序に矯正することが挙げられる。例えば、リソースに番号を振って、その番号が昇順になるようにするという方法である。この方法はOSではなく、アプリケーション側が実装する。OSの仕組みで防げていないので、アプリケーションプログラマーの不注意でデッドロックは起こりうる。なお、見た目で順序を正しくできているように見えてもそうなっていない場合がある。

def transaction(From:Account,To:Account,amount:float):
    lock1=getLock(From)
    lock2=getLock(To)
    wait(lock1)
    wait(lock2)
    withdraw(From,amount)
    deposit(To,amount)
    signal(lock1)
    signal(lock2)

上記のような関数について、transaction(A,B,10)とtransaction(B,A,10)を並列処理で呼び出した場合タイミングによってはデッドロックとなりうる。

デッドロックの回避

　デッドロックの回避ではシステムの状態がsafe stateを保つようにリソース割り当てを行う。safe stateとは、safe sequenceが存在するような状態である。safe sequenceとは、プロセスを実行する順番であり、次のように定義される。プロセス実行順P1,P2,…,Pnを考える。プロセスは実行中リソースを解放しないが、自分が終了したときリソースを全部解放する。あるプロセスPiは自分以前のプロセスP1,P2,…,Pi-1が解放したリソースを全部使える。P1,P2,…,PnがPnまでデッドロックに陥らず完了できるとき、safe sequenceという。safe sequenceが存在しない、すなわち、どういう順序でプロセスを実行してもいずれデッドロックになる状態をunsafeという。

　リソースが各種類1個しか存在しない場合は、resource allocation graphを用いてデッドロック回避ができる。単純なresource allocation graphに加え、プロセスから将来的に要求するかもしれないリソースに向かってclaim edgeという辺を引く。プロセスからのリソース要求に応じるとclaim edge含めて閉路を生じる、という場合unsafe stateとなる。unsafe stateになる場合要求に応じないか待たす。

　リソースが各種類複数個存在する場合は銀行家のアルゴリズムが使える。銀行家のアルゴリズムではデータ構造として

  • 各リソースの現在使用可能な数(available)
  • 各プロセスが要求する各リソースの最大個数(max)
  • 現在それぞれのプロセスに割り当てているリソース数(allocation)

を使用する。なお、現在プロセスが追加で必要とする最大リソース数needはneed=max-allocationで計算できる。

　現在の状態がsafe stateであるか否かは、safe sequenceが存在するか否かをチェックすることで判定できる。safe sequenceの洗い出しは総当たりで行う。このアルゴリズムの計算量はO(mn^2)である1。ただしmはリソースの種類数、nはプロセス数である。

　あるリソース割り当てに即座に応答すべきかどうかは、その割当に応答した場合の状態がsafe stateかどうかを前述のアルゴリズムを使って判定すれば良い。

デッドロックの検出

　リソースの個数が各種類で1個の場合、resource-allocation graphから各プロセスだけを抽出してプロセス間の待ちを表現したwait-for graphを作って閉路を確認すれば良い。ただし、この確認は定期的に実行し続けることとなる。

　リソースの個数が複数個ある場合、銀行家のアルゴリズムの変種を実行する。通常の銀行家のアルゴリズムでは各プロセスがこれから要求しうる最大のリソース要求数をneedとして用いたが、検出においては現在各プロセスが要求しているリソース数を用いる。表記としてもneedではなくrequestを用いる。これは、各プロセスは現在の要求数以上にリソースを要求しない、ということを暗黙的に仮定していることと同義。

　検出も計算時間というリソースを食うので、実行頻度などは考えなければならない。

デッドロックからの復帰

　結論としては、汎用的な賢い方法は無い。

　まず、デッドロックに加わっているプロセスを殺すことが考えられる。どのプロセスを殺すか、もしくは全部殺すかを選定しなければならない。プロセスの優先度、どれくらいそのプロセスが実行されてきたか、どれくらいそのプロセスがリソースを保持しているか、あと何個のリソースをそのプロセスが必要としているか、インタラクティブかバッチか、などを加味する。

　次に、リソースを解放することが考えられる。どのリソースを解放するか、解放されたリソースを保持していたプロセスをどうリソース獲得前の状態に戻すか、スターベーションは大丈夫か、などを考える必要がある。

  1. なんでこうなるかの説明は書かれていませんでした。各ステップで実行可能なプロセスが1個しか存在しない場合は、どのプロセスが現在実行可能かを検査するループ数がO(n)、全プロセスを消化するまでn回ループするのでO(n^2)のループ回数となります。リソース種類数がmなので各検査でO(m)の計算量が発生すると考えると全体の計算量はO(mn^2)となります。一方で、あるステップで複数個のプロセスが実行可能であることもあると思います。その場合、どのプロセスをまず実行するかの自由度があるので、ループ回数は増えるはずです。あるシーケンスがsafeかどうかはシーケンスの最後までシミュレートしなくてもわかる事が多いはずなので、すべての順列を最後まで見なくて良く、O(mn!)とはならなそうということはわかるのですが…

コメント

タイトルとURLをコピーしました