💨

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

2 min read

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

今回は「相互排除問題を解く自己安定アルゴリズム」についてです。
プロセスが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つだけになっていたかと思います。
なので、このアルゴリズムによって相互排除が実現されています。

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

Discussion

ログインするとコメントできます