分散処理本読書会で度々話題になっているknotについて簡単にまとめました。

分散処理本でknotの出典としている論文「Some Deadlock Properties of Computer Systems」をknotの説明の箇所より少し後まで読み終えたため、knotについてわかったこと、つまりcycleとの違いやなぜ定義する必要があるのかなどを書きたいと思います。

cycleについて
knotについて
違いは何か
なぜ分けて定義する必要があるのか。
- ケース1.and modelではknotを検出する必要はない。cycleだけで十分
- ケース2.or modelではcycleだけだと不十分でありknotを示す必要がある
参考文献

cycleについて

参考にしている論文の定義を借ります。

定義:サイクルは開始ノードと終了ノードが同じになるようなpathのことです*1

例えば下記の図はc→d→cというcycleが存在しています。これを論文の表記を借りて(c,d,c)と書きます。

f:id:yuyubu:20181112010842p:plain — 図の出典:参考文献2のHOLTの論文

knotについて

定義:knotは集合K内の到達可能なノードの厳密な集合のことです。*2

集合Kがknotである場合、Kの要素は以下の特性を持ちます。

集合内の要素は互いにK内のどの要素にも到達可能である
Kに含まれない要素には到達できない

例えば上記に掲載したHOLT論文のFig3の図で言えばcとdはc,d以外への到達を可能にするエッジを持っていません。こちらも論文の表記を借りて{c,d}と書きます。

違いは何か

knotはノードの集合の定義、cycleはエッジの集合(path)の定義です。

knotを構成しているノードの組み合わせから作成できるcycleのパスが必ずあります。
逆にcycleを構成しているエッジのノードの集合は常にknotになっているわけではありません。

Holtの論文ではcとdはcycleを構成し、かつknotになっています。cycleでありながら、knotでは無い図はHoltの論文には掲載されていません。そのような図は分散処理本こと"Distributed Computing: Principles, Algorithms, and Systems"には掲載されています。

f:id:yuyubu:20181112011538p:plain — 図の出典:参考文献1の分散処理本

こちらの図では(P11,P21,P24,P54,P11)のサイクルが存在していますが、サイクルを構成しているノードの集合{P11,P21,P24,P54}はknotではありません。なぜなら(P11,P32)のエッジが存在しており、ノードP11は集合{P11,P21,P24,P54}以外のノードP32へ到達可能だからです。

定義している集合の要素の種類(ノード/エッジ)が違っていますが、あえていうなら、cycleよりknotの方が厳しい条件を備えているというべきでしょう。(cycleの方がゆるい)

なぜ分けて定義する必要があるのか。

ノード(プロセス)が複数のノードに同時に依存している場合、その依存の種類によってデッドロックの判定方法は変わります。あるケースではcycleを検出するだけではデッドロックの検出条件として不十分だからです。

ケース1.and modelではknotを検出する必要はない。cycleだけで十分

and modelは依存している複数のプロセスを 全て完了する必要がある とするモデル。デッドロック検出を行うにはサイクルを示せば良い。分散処理本figure 10.1の図ではP11→P21→P24→P54→P11のサイクルが存在しているためデッドロックが発生している。

具体的に書くと、P11の要素はP32とP21の要素両方の終了を待つ必要があるが、P21はP11とサイクルを構成しているため、P21とP11は永遠の完了しない、これはデッドロックである。

ケース2.or modelではcycleだけだと不十分でありknotを示す必要がある

or modelは依存している複数のプロセスに対して、 どれか1つだけの完了を必要 とするモデル。デッドロック検出を行うにはcycleだけでは不十分でknotを示す必要がある。例えば分散処理本figure 10.1の図では

P11→P21→P24→P54→P11のサイクルが存在しているが、これはknotではないのでこのWait-for-graphではデッドロックは発生していない。

具体的に書くと、P11の要素はP32とP21の要素どちらかの終了を待つ必要があるが、P21はP11とサイクルを構成しているが、P32が完了するればP21の完了を待つ必要がないため、これはデッドロックではない。

f:id:yuyubu:20181112013934p:plain — 分散処理本のWFGに加筆

分散処理本掲載の図のWFGでは赤矢印で示した順P33→P32→P11→P54→P24→P21→P44で処理を完了させることができる。*3

念の為ですが、knotは必ずcycleを構成するのでknotがあればand modelでもデッドロックが発生している事になる。

参考文献

1:Ajay D. Kshemkalyani and Mukesh Singhal(2011)Distributed Computing: Principles, Algorithms, and Systems
2:RICHARD C. HOLT (1972)Some Deadlock Properties of Computer Systems