前川のアルゴリズム

前川アルゴリズムは、分散システムにおける相互排除アルゴリズムです。このアルゴリズムの基礎は、クォーラムに似たアプローチであり、任意の1つのサイトは他のサイトのサブセットからのみ許可を求める必要があります。

アルゴリズム

用語

• サイトとは、前川のアルゴリズムを実行するあらゆるコンピューティングデバイスである。
• クリティカルセクションに入る要求の1つに対して:
  • 要求元サイトとは、クリティカル セクションに入ることを要求しているサイトです。
  • 受信サイトとは、要求サイトからの要求を受信する他のすべてのサイトです。
• tsは、論理クロックに従ったシステムのローカルタイムスタンプを指します。

アルゴリズム

リクエストサイト:

• 要求元サイトは、クォーラム セット内のすべてのサイトにメッセージを送信します。${\displaystyle P_{i}}$ ${\displaystyle {\text{request}}(ts,i)}$ ${\displaystyle R_{i}}$

受取場所：

• メッセージを受信すると、受信サイトは次の処理を実行します。 ${\displaystyle {\text{request}}(ts,i)}$ ${\displaystyle P_{j}}$
  • site に未処理のメッセージ (つまり、解放されていないメッセージ)がない場合、 site はsite にメッセージを送信します。${\displaystyle P_{j}}$ ${\displaystyle {\text{grant}}}$ ${\displaystyle {\text{grant}}}$ ${\displaystyle P_{j}}$ ${\displaystyle {\text{grant}}(j)}$ ${\displaystyle P_{i}}$
  • サイトに、要求よりも優先度の高いプロセスに関する未処理のメッセージがある場合、サイトはサイトにメッセージを送信し、サイトはサイトからの要求をキューに入れます。${\displaystyle P_{j}}$ ${\displaystyle {\text{grant}}}$ ${\displaystyle P_{j}}$ ${\displaystyle {\text{失敗}}(j)}$ ${\displaystyle P_{i}}$ ${\displaystyle P_{j}}$ ${\displaystyle P_{i}}$
  • サイト に、要求よりも優先度の低いプロセスとの未処理のメッセージがある場合、 サイト は、現在 サイト によってクリティカル セクションへのアクセスを許可されているプロセスにメッセージを送信します。（つまり、未処理のメッセージがあるサイトです。）${\displaystyle P_{j}}$ ${\displaystyle {\text{grant}}}$ ${\displaystyle P_{j}}$ ${\displaystyle {\text{問い合わせ}}(j)}$ ${\displaystyle P_{j}}$ ${\displaystyle {\text{grant}}}$
• メッセージを受信すると、サイトは次の処理を実行します。 ${\displaystyle {\text{問い合わせ}}(j)}$ ${\displaystyle P_{k}}$
  • サイトが他のサイトからメッセージを受信した場合、または他のサイトに yield を送信したが新しいメッセージを受信して​​いない場合に限り、サイトにメッセージを送信します。${\displaystyle {\text{収量}}(k)}$ ${\displaystyle P_{j}}$ ${\displaystyle P_{k}}$ ${\displaystyle {\text{失敗}}}$ ${\displaystyle P_{k}}$ ${\displaystyle {\text{grant}}}$
• メッセージを受信すると、サイトは次の処理を実行します。 ${\displaystyle {\text{収量}}(k)}$ ${\displaystyle P_{j}}$
  • リクエストキューの先頭にあるリクエストにメッセージを送信します。先頭にあるリクエストは最も優先度が高いことに注意してください。${\displaystyle {\text{grant}}(j)}$
  • リクエスト キューに配置します。${\displaystyle P_{k}}$
• メッセージを受信すると、サイトは次の処理を実行します。 ${\displaystyle {\text{リリース}}(i)}$ ${\displaystyle P_{j}}$
  • リクエスト キューから削除します。${\displaystyle P_{i}}$
  • リクエスト キューの先頭にあるリクエストにメッセージを送信します。${\displaystyle {\text{grant}}(j)}$

クリティカルセクション:

• サイトは、 内のすべてのサイトからメッセージを受信すると、クリティカル セクションに入ります。${\displaystyle P_{i}}$ ${\displaystyle {\text{grant}}}$ ${\displaystyle R_{i}}$
• クリティカル セクションを終了すると、内のすべてのサイトにメッセージを送信します。${\displaystyle P_{i}}$ ${\displaystyle {\text{リリース}}(i)}$ ${\displaystyle R_{i}}$

クォーラム セット ( )${\displaystyle R_{x}}$ :
クォーラム セットは次のプロパティに従う必要があります。

1. ${\displaystyle \forall i\,\forall j\,[R_{i}\bigcap R_{j}\neq \emptyset ]}$
2. ${\displaystyle \forall i\,[P_{i}\in R_{i}]}$
3. ${\displaystyle \forall i\,[|R_{i}|=K]}$
4. サイトはリクエストセットに正確に含まれています${\displaystyle P_{i}}$ ${\displaystyle K}$

したがって：${\displaystyle |R_{i}|\geq {\sqrt {N-1}}}$

パフォーマンス

• ネットワークメッセージの数;${\displaystyle 3{\sqrt {N}}}$ ${\displaystyle 6{\sqrt {N}}}$
• 同期遅延: 2 メッセージ伝播遅延
• 保護対策を講じないとアルゴリズムがデッドロックする可能性があります。^{[1] [2]}

参照

• ランポートのベーカリーアルゴリズム
• ランポートの分散相互排除アルゴリズム
• リカート・アグラワラアルゴリズム
• レイモンドのアルゴリズム

参考文献

1. 「前川の相互排除アルゴリズム：投票アプローチ」。
2. 「分散相互排除」（PDF） .

• M. Maekawa、「分散システムにおける相互排除のための√Nアルゴリズム」、ACM

コンピュータシステムに関する取引、第3巻、第2号、pp.145-159、1985年。

• 前川守、アーサー・E・オルデホフト、ロドニー・R・オルデホフト (1987). 『オペレーティングシステム：高度な概念』 Benjamin/Cummings Publishing Company, Inc.
• B. サンダース (1987). 分散型相互排除アルゴリズムの情報構造. ACM Transactions on Computer Systems, Vol. 3, No. 2, pp. 145–59.