Wait-for graph とは

コンピュータサイエンスの待ちグラフは、オペレーティングシステムやリレーショナルデータベースシステムのデッドロック検出に使用される有向グラフです。
コンピュータサイエンスでは、複数のプロセスの同時操作とリソースのロックを可能にし、デッドロックを回避または防止するメカニズムを提供しないシステムは、デッドロックを検出するメカニズムと、デッドロックから回復するためのアルゴリズムをサポートする必要があります。
そのようなデッドロック検出アルゴリズムの1つは、待機中のグラフを使用して、プロセスが現在ブロックしている他のプロセスを追跡します。待機中のグラフでは、プロセスはノードとして表され、プロセス P i {\displaystyle P_{i}} から P j {\displaystyle P_{j}} へのエッジは、 P j {\displaystyle P_{j}} P i {\displaystyle P_{i}} が必要とするリソースを保持していることを意味し P j {\displaystyle P_{j}} そのリソースに対するロックを解除します。プロセスが1つ以上のリソースが利用可能になるのを待っている場合(単純なケース)、複数のエッジは、異なるリソースの結合的(または)または分離的な(または)集合、またはコレクションからの一定数の同等のリソースを表すことができる。結び付きの場合、グラフサイクルはデッドロックの可能性を暗示しますが、論理和の場合、ノットはデッドロックの可能性を示します。最後のケースでデッドロックの可能性を検出するための単純なアルゴリズムはありません。 (Srinavasan、Rajaram 2011)
グラフの待機方式は、各リソースタイプの複数のインスタンスを持つリソース割り当てシステムには適用できません。