Deadlock detection

• システムがDeadlock状態にあるかどうかの検知をする

分散システムにおけるDeadlock detection

• 分散システム$S=P_1,P_2,...,P_n$があるとする。$P_i$: プロセス
• Wait-for graph $G=(\Pi ,E)$: プロセス間の待ち状況を表現した有向グラフ
  • ここで、$\Pi =P_1,P_2,...,P_n$
  • 有向枝$(P,Q)\in E$はプロセス$P$がプロセス$Q$を待っていることを示す
  • dependent set $D(P_i)$: $P_i$が待っているプロセスの集合
  • 例:
    • $D(P)=Q,D(Q)=R,D(R)=P,D(S)=R$
• Deadlock状態: Wait-for graph$G$が有向閉路$Q_1,Q_2,...,Q_k$を含むとすると、$Q_1$は$Q_2$を、$Q_2$は$Q_3$を…$Q_k$は$Q_1$を待つことになり、deadlock
  • 要は有向閉路があったらオシマイ(kekeho)
  • Deadlock detectionにおいては、有向閉路の存在があるかどうかチェックすればOK Deadlock detection algorithm 1
• 仮定
  1. 分散システム$S$はある別のシステム$S^{\ast }$上で稼働していると仮定。そのうえで、$P_i\in \Pi$を管理する、システム$S^{\ast }$上のプロセス$P_i^{\ast }$は$D(P_i)$を把握しているとする
  2. $P_i^{\ast }\in S^{\ast }$は、$P_j\in S^{\ast }(j\ne i)$とメッセージ交換が可能
  3. プロセスも通信リンクも故障しないことを仮定
  4. 各プロセスの持つ入力情報が変化しないStatic problemとして捉える。少なくともアルゴリズム実行中に、$D(P_i)$が変化しないことを仮定
• initiator $P_1^{\ast }$: Deadlock detection algorithmを開始したいプロセス
• 擬似コード
  • $P_i^{\ast }$がinitiatorの場合:
  1. for all $j=2,3,...,n$ do Send($P_j^{\ast }$, Request)
  2. for all $j=2,3,...,n$ do Receive($P_j^{\ast }$, $D_j$)
  3. Wait-for graph$G$を、$D(P_1)$と$D(P_j)(j=2,3,...,n)$から構築
  4. $G$に対し、有向閉路発見アルゴリズムを適用
  • $P_i^{\ast }$がinitiatorではない場合:
  1. Receive($P_1^{\ast }$, M);
  2. if M = Request then Send($P_1^{\ast }$, $D(P_i)$)
• 定理
  1. このアルゴリズムの始動時にシステムがデッドロック状態にあるならば、それを検知する
     • デッドロック状態が勝手に解消されることはないので、Asynchronous Systemを仮定してもこれは言える(kekeho)
  2. Asynchronous Systemを仮定する。このアルゴリズムはデッドロックを誤検知、すなわちPhantom deadlockを検知することがある。
     • 非同期システムにおいては、デッドロックがある⇒検知されるは真でも、その逆は成り立たない(検知されたからといって、本当にデッドロックが起きているとは限らない)
     • 各プロセス$P_i^{\ast }$がレスポンスを返すタイミングはバラバラなので、バラバラな時間における依存関係が重ね合わさってしまう
  3. Synchronous Systemを仮定する。このアルゴリズムがデッドロックを検知したときは、実際にシステムはデッドロック状態にある。Phantom deadlockを検知しない。
• 実際の分散システムは、Dynamic problemとして捉えるほうが適切