分散処理本第39回に参加

恒例の分散本(Distributed Computing: Principles, Algorithms, and Systems)を読む勉強会です。

分散システムでのデッドロック検知はサイト間での検知を如何にとるか、と言うのがポイントだと思います。 今回勉強した2種類のアルゴリズムではサイト間でメッセージを送ってデッドロックを検知します

Distributed Computing: Principles, Algorithms, and Systems

10.7  Chandy–Misra–Haas algorithm for the AND model

Andモデルでのデッドロック検出は単純で、サイクルを検出できれば良い。tripletというメッセージをWFGの依存先の各ノードがサイト外である場合に送る。

• triple(i,j,k)の形式は以下に示す通り

  • i:デッドロック検出を開始したノード
  • j:kに依存しているノード(かつkとは別サイト)
  • k:jが依存しているノード(かつjとは別サイト)

• 送信するprobe:triplet(pi, pj, pk)

• 依存関係の配列:dependent_K(i)

引用元:http://www.lnse.org/vol3/205-X0012.pdf

以下がアルゴリズム

Algorithm 10.1 より引用

ポイントは以下の通り

• サイクルの検出開始地点(Fig1の図で言うとP1がi=kのprobeを受け取った時点でデッドロックの検出が成功する。
  • 上図(fig1)の例でだと(1,5,1)のprobeがi=kに相当する
• 検出開始ノードから送るprobeの内容とprobeを受け取ったノードが依存先にprobeを送る内容は同一

参考リンク:

• 元になってる論文6のDistributed deadlock detection, ACM Transactions on Computer Systems:https://www.cs.utexas.edu/users/misra/scannedPdf.dir/DistrDeadlockDetection.pdf
• wikipedia:https://en.wikipedia.org/wiki/Chandy-Misra-Haas_algorithm_resource_model

10.8  Chandy–Misra–Haas algorithm for the OR model

• 基本的な考え方
  • ORモデルの場合は一つのサイクルの検出でデッドロック検知とならない。
  • ORモデルの定義として、複数のリソースに依存している場合、依存先のリソース全てでデッドロックが発生して初めてデッドロックとなる
  • このため、WFGの各ノードは依存先のノード件数をローカル変数numでもつ
  • 依存先のデッドロック検出(後述のreply受診時)の度に、numをデクリメントする。
  • num＝0のノードはその先で全てデッドロックが起こっていると言うことなのでreply(i,j,k)を自分の依存元に返す

A->Aのデッドロックが最初に発生した時

アルゴリズム

Algorithm 10.2 Chandy–Misra–Haas algorithm for the OR model より抜粋

最終的に上図のAはBからreply(A,B,A),つまりi=k=Aを受け取ってデッドロックの検知が完了する。

参考リンク:

• 図の引用元:http://www.cs.fsu.edu/~xyuan/cop5611/lecture10.html

読書会では「10.9 Kshemkalyani–Singhal algorithm for the P-out-of-Q model」まで突入したが、予習ができてないので内容がよくわからなかった。 また、10.9をやりきっていないのでそちらは次回の予習で調べます。

次回は「10.9.2 The algorithm」から