分散処理を勉強した記録～その31～

この記事は、
「分散処理システム」著：真鍋義文　森北出版株式会社
を参考にしています。

今回は「相互排除問題を解く自己安定アルゴリズム」についてです。
プロセスがP0～P4まで5つ存在し、
各プロセスはパラメータSiを持つものとします。

ここで、
P0の遷移可能条件は

$$S_{0} == S_{4}$$

P1～P4の遷移可能条件は

$$S_{i} != S_{i-1}$$

となります。
P0は、S4とS0の値を比較します。よって、
3 != 1　となり、
遷移不可能です。

P1はS1とS0の値を比較するので、
1 == 1　となり、遷移不可能です。

同様に、P2～P4の値を評価すると、
P2～P4は遷移可能です。

今回はCデーモンを採用するので、
実際に遷移するのは1つだけです。
そのため、P3の値を変化させます。

P1～P4に代入する値は、

$$S_{i} = S_{i-1}$$

となります。

P3の値S3にS2を代入し、
S3は「3」になります。

同様に、P0とP1～P4の遷移条件を評価していきます。
P0については、S4とS0の値が同じなら遷移可能です。
4 != 1　なので、P0は遷移不可能です。

P1は、S0とS1の値が異なる場合に遷移可能です。
1 == 1　なので、P1は遷移不可能です。

P2～P4についても同じように評価すると、
P2とP4が遷移可能です。

今回は、P2の値を変化させます。
S2にS1を代入するので、「1」になります。

P0については、S4とS0の値が同じなら遷移可能です。
4 != 1　なので、P0は遷移不可能です。

P1は、S0とS1の値が異なる場合に遷移可能です。
1 == 1　なので、P1は遷移不可能です。

P2～P4についても同じように評価すると、
P3とP4が遷移可能です。

今回は、P3の値を変化させます。
S3にS2を代入するので、「1」になります。

P0については、S4とS0の値が同じなら遷移可能です。
4 != 1　なので、P0は遷移不可能です。

P1は、S0とS1の値が異なる場合に遷移可能です。
1 == 1　なので、P1は遷移不可能です。

P2～P4についても同じように評価すると、
P4が遷移可能です。

P4の値を変化させます。
S4にS3を代入するので、「1」になります。

P0については、S4とS0の値が同じなら遷移可能です。
1 == 1　なので、P0は遷移可能です。

P1は、S0とS1の値が異なる場合に遷移可能です。
1 == 1　なので、P1は遷移不可能です。

P2～P4についても同じように評価すると、すべて遷移不可能です。

P0に代入する値は、

$$(S_{0} + 1) mod K$$

となります。
Kはプロセス数より大きい値より大きければ何でも構いません。
ここではプロセス数は5なので、6とします。
S0は1なので、
(1 + 1) mod 6 = 2
になります。

P0については、S4とS0の値が同じなら遷移可能です。
1 != 4　なので、P0は遷移不可能です。

P1は、S0とS1の値が異なる場合に遷移可能です。
1 == 2　なので、P1は遷移可能です。

P2～P4についても同じように評価すると、すべて遷移不可能です。

STEP4以降、遷移可能なプロセスは1つだけになっていたかと思います。
なので、このアルゴリズムによって相互排除が実現されています。

今回はここまでです。ありがとうございました。