Chandy–Misra–Haasアルゴリズムのリソースモデル

Chandy –Misra–Haasアルゴリズムのリソースモデルは、分散システムにおけるデッドロックをチェックします。これは、K. Mani Chandy、Jayadev Misra、およびLaura M. Haasによって開発されました。

単一のシステム（コントローラ）で実行されるn 個のプロセスP ₁、P ₂、P ₃、P ₄、P _5、 ... 、P _nを考えます。 P ₁がP ₂に依存し、P ₂がP ₃に依存し_、 ...およびP _{n−1 がP n}に依存する場合、 P ₁はP nに局所的に依存します。つまり、${\displaystyle P_{1}\rightarrow P_{2}\rightarrow P_{3}\rightarrow \ldots \rightarrow P_{n}}$、 それから${\displaystyle P_{1}}$ローカルに依存している${\displaystyle P_{n}}$P _{1 が}局所的に自身に依存していると言われるのは、 P _nに局所的に依存し、かつP _{n が}P ₁に依存している場合である。${\displaystyle P_{1}\rightarrow P_{2}\rightarrow P_{3}\rightarrow \ldots \rightarrow P_{n}\rightarrow P_{1}}$、 それから${\displaystyle P_{1}}$局所的に自己依存している。

このアルゴリズムは、probe(i,j,k) と呼ばれるメッセージを使用して、プロセスP _jのコントローラからプロセスP _kのコントローラにメッセージを転送します。このメッセージは、デッドロックが発生したかどうかを判断するために、プロセスP _iによって開始されたメッセージを指定します。各プロセスP _{j は}、依存するプロセスに関する情報を含むブール配列dependentを保持します。初期状態では、各配列の値はすべて「false」です。

擬似コードでは、アルゴリズムは次のように動作します。^{[ 1 ]}

P jがローカルに自身に 依存している場合はデッドロックを宣言する 。 そうでない場合はすべてのP j、P kに対して、 (i) P iは局所的にP jに依存します。 （ii）P jは ' P kを待っており、 （iii）P jとP kは異なるコントローラ上にある。 プローブ(i, j, k)をP kのホームサイトに送信する。

 (i) P kがアイドル状態またはブロックされている場合 （ii）従属変数k（i）=偽、 (iii) P k がP j へのすべての要求に応答していない場合は、 「依存関係」を開始し、 「k」 (i) = true; k == i の場合はP iがデッドロック状態である ことを宣言し、そうでない場合はすべてのP a、P bに対して、 (i) P kは局所的にP aに依存する。 （ii）P aは ' P bを待っており、 （iii）P a、P bは異なるコントローラ上にある。 プローブ(i、a、b)をP bのホームサイトに送信する。

P _{1 は}デッドロック検出を開始します。C _{1 は}、P _{2 が}P ₃に依存していることを示すプローブを送信します。C 2_はメッセージを受信すると、 P ₃がアイドル状態かどうかを確認します。P ₃はローカルにP ₄に依存しているためアイドル状態であり、依存₃ (2)をTrue に更新します。

上記のように、C _{2 は}C ₃にプローブを送信し、C _{3 は}C ₁にプローブを送信します。C 1 では、 P 1_はアイドル状態であるため、依存関係_{1 (1)を}True に更新します。したがって、デッドロックが宣言されます。

仮に${\displaystyle n}$コントローラーと${\displaystyle m}$プロセス、最大${\displaystyle m(n-1)/2}$デッドロックを検出するにはメッセージの交換が必要であり、遅延は${\displaystyle O(n)}$メッセージ。^{[ 2 ]}