共有レジスタ

分散コンピューティングでは、共有メモリシステムとメッセージパッシングシステムは、広く研究されているプロセス間通信の 2 つの方法です。共有メモリシステムでは、プロセスは共有データ構造にアクセスして通信します。共有(読み取り/書き込み)レジスタ(単にレジスタと呼ばれることもあります) は、値を格納し、レジスタに格納されている値を返す読み取りと、格納されている値を更新する書き込みという 2 つの操作を実行する、基本的なタイプの共有データ構造です。その他のタイプの共有データ構造には、読み取り、変更、書き込み、テストと設定、比較とスワップなどがあります。同時にアクセスされるメモリの場所は、レジスタと呼ばれることがあります。

分類

レジスタは、同時アクセス時に満たす一貫性条件、格納可能な値の範囲、読み取りまたは書き込み操作でアクセスできるプロセスの数に応じて分類することができ、合計24種類のレジスタがあります。^[1]

読み取りと書き込みが同時に発生すると、読み取りによって返される値が一意に決定されない場合があります。Lamportは、安全レジスタ、通常レジスタ、アトミックレジスタの3 種類のレジスタを定義しました。 ^[1]安全レジスタの読み取り操作は、書き込み操作と同時であれば任意の値を返すことができ、読み取り操作が書き込みと重複していない場合は、最新の書き込み操作によって書き込まれた値を返します。通常レジスタは、読み取り操作が最新の完了した書き込み操作または重複する書き込み操作によって書き込まれた値を返すことができるという点で、安全レジスタと異なります。アトミックレジスタは、線形化可能であるというより強い条件を満たしています。

レジスタは、読み取りまたは書き込み操作でアクセスできるプロセスの数によって特徴付けられます。単一書き込み (SW) レジスタは 1 つのプロセスによってのみ書き込むことができ、複数書き込み (MW) レジスタは複数のプロセスによって書き込むことができます。同様に、単一読み取り (SR) レジスタは 1 つのプロセスによってのみ読み取ることができ、複数読み取り (MR) レジスタは複数のプロセスによって読み取ることができます。SWSR レジスタの場合、書き込みプロセスと読み取りプロセスが同じである必要はありません。

建設

下の図は、非同期メッセージパッシングシステムにおけるSWSRレジスタの実装から、SWスナップショットオブジェクトを使用したMWMRレジスタの実装までの構築を段階的に示しています。この種の構築は、シミュレーションまたはエミュレーションと呼ばれることもあります。^{[2]各段階（ステージ3を除く）では、右側のオブジェクト型は、左側のより単純なオブジェクト型によって実装できます。各段階（ステージ3を除く）の構築を以下に簡単に示します。}スナップショットオブジェクトの構築の詳細について説明している記事があります。

{\ce {{\operatorname {メッセージパッシング} \atop (MP)~System}->[][{\text{ステージ 1}}]SWSR~atomic->[][{\text{ステージ 2}}]SWMR->[][{\text{ステージ 3}}]SW~snapshot->[][{\text{ステージ 4}}]MWMR}}

共有レジスター建設段階

実装が線形化可能であると判断されるのは、実行ごとに次の 2 つの特性を満たす線形化順序が存在する場合です。

操作が線形化の順序で順次実行されると、同時実行の場合と同じ結果が返されます。
操作 op1 が操作 op2 の開始前に終了する場合、線形化では op1 が op2 の前に来ます。

メッセージパッシングシステムにおけるアトミックSWSRレジスタの実装

SWSR アトミック (線形化可能) レジスタは、プロセスがクラッシュする可能性がある場合でも、非同期メッセージパッシングシステムに実装できます。プロセスが受信者にメッセージを配信したり、ローカル命令を実行したりするのに時間制限はありません。つまり、プロセスは、応答が遅いプロセスと単にクラッシュしたプロセスを区別できません。

^{Attiya、Bar-Noy、Dolev [3]}による実装では、 $n > 2 f が$ 必要です。ここで、 $n$ はシステム内のプロセスの総数、 $f は$ 実行中にクラッシュする可能性のあるプロセスの最大数です。アルゴリズムは次のとおりです。

操作の線形化順序は、writeを発生順に線形化し、その値を返すwriteの後にread を挿入することです。実装が線形化可能であることを確認できます。特に op1 がwriteで op2 がreadであり、read がwriteの直後である場合に、プロパティ 2 を確認できます。これは、背理法によって示せます。read がwrite を参照しないと仮定すると、実装によれば、 n プロセス間でサイズ $($ $n$ $-$ $f$ $)$ の 2 つの互いに素なセットが存在する必要があります。したがって、 $2 * ($ $n$ $-$ $f$ $) \leq$ $nとなり、$ $n$ $\leq 2$ $f$ となり、これは $n$ $> 2$ $f$ という事実と矛盾します。したがって、read は、そのwriteによって書き込まれた値を少なくとも 1 つ読み取る必要があります。

SWSRレジスタからSWMRレジスタを実装する

SWMR レジスタは 1 つのプロセスによってのみ書き込むことができますが、複数のプロセスによって読み取ることができます。

SWMR レジスタを読み取ることができるプロセスの数を n とします。 $R i$ 、 $0 < i \leq n$ は、 SWMR レジスタのリーダーを指します。 $w は、$ SWMR の単一の書き込み者とします。右の図は、 $n (n + 1)$ 個のSWSR レジスタの配列を使用した SWMR レジスタの構築を示しています。配列を $A$ で示します。各 SWSR レジスタ $A[i, j]は、$ $0 <$ $i$ $\leq$ $n$ の場合に $R i$ によって書き込み可能であり、 $i$ $=$ $n$ $+ 1$ の場合に $w$ によって書き込み可能です。各 SWSR レジスタ $A[$ $i$ $,$ $j$ $]は、$ $R$ $j$ によって読み取り可能です。読み取りと書き込みの実装を以下に示します。

操作の t 値は、書き込まれる t の値であり、操作は t 値によって線形化されます。書き込みと読み取りのt 値が同じ場合は、書き込みを読み取りの前に順序付けます。複数の読み取りが同じ t 値を持つ場合は、開始時間で順序付けます。

SWスナップショットオブジェクトからMWMRレジスタを実装する

サイズ n の SW スナップショットオブジェクトを使用して、MWMR レジスタを構築できます。

線形化の順序は次のとおりです。書き込み操作を t 値で順序付けします。複数の書き込みが同じ t 値を持つ場合は、小さいプロセス ID を先頭にして操作を順序付けします。書き込みの直後に読み取りを挿入し、その読み取りによって値が返されるときはプロセス ID で決着をつけ、それでも決着がつかない場合は開始時間で決着をつけます。

参照

参考文献

^ ab Kshemkalyani, Ajay D.; Singhal, Mukesh (2008).分散コンピューティング：原理、アルゴリズム、システム。ケンブリッジ：ケンブリッジ大学出版局。pp. 435–437。ISBN 9780521876346。
^ Attiya, Hagit; Welch, Jennifer (2004 年 3 月 25 日)。分散コンピューティング: 基礎、シミュレーション、高度なトピック。John Wiley & Sons, Inc. ISBN 978-0-471-45324-6。
^ Attiya, Hagit; Bar-Noy, Amotz; Dolev, Danny (1990)。「メッセージパッシングシステムにおけるメモリの堅牢な共有」。分散コンピューティングの原理に関する第 9 回 ACM シンポジウムの議事録。第 9 巻 PODC '90。pp. 363–375。doi : 10.1145/ 93385.93441。ISBN 089791404X. S2CID 1233774。

[DCFSA-1] Kshemkalyani, Ajay D.; Singhal, Mukesh (2008).分散コンピューティング：原理、アルゴリズム、システム。ケンブリッジ：ケンブリッジ大学出版局。pp. 435–437。ISBN 9780521876346。

[2] Attiya, Hagit; Welch, Jennifer (2004 年 3 月 25 日)。分散コンピューティング: 基礎、シミュレーション、高度なトピック。John Wiley & Sons, Inc. ISBN 978-0-471-45324-6。

[3] Attiya, Hagit; Bar-Noy, Amotz; Dolev, Danny (1990)。「メッセージパッシングシステムにおけるメモリの堅牢な共有」。分散コンピューティングの原理に関する第 9 回 ACM シンポジウムの議事録。第 9 巻 PODC '90。pp. 363–375。doi : 10.1145/ 93385.93441。ISBN 089791404X. S2CID 1233774。