共有レジスタ

Type of shared data structure

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

分類

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

共有レジスタ分類
一貫性条件	ドメイン	書く	読む
安全な通常の原子	2進整数	シングルライターマルチライター	単一読者複数読者

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

レジスタは、読み取りまたは書き込み操作でアクセスできるプロセスの数によって特徴付けられます。シングルライター（SW）レジスタは1つのプロセスのみが書き込み可能で、マルチライター（MW）レジスタは複数のプロセスが書き込み可能です。同様に、シングルリーダー（SR）レジスタは1つのプロセスのみが読み取り可能で、マルチリーダー（MR）レジスタは複数のプロセスが読み取り可能です。SWSRレジスタの場合、書き込みプロセスと読み取りプロセスは必ずしも同じである必要はありません。

建設

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

{\ce {{\operatorname {Message-passing}  \atop (MP)\ System}->[][{\text{Stage 1}}]SWSR\ atomic->[][{\text{Stage 2}}]SWMR->[][{\text{Stage 3}}]SW\ snapshot->[][{\text{Stage 4}}]MWMR}}

共有レジスタ建設段階

実装は、すべての実行に対して次の 2 つのプロパティを満たす線形化順序が存在する場合、線形化可能です。

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

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

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

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

ライター

リーダー

書く(動詞)
  t++
  (v,t)をすべてのプロセスに送信する
  (nf) 確認応答を受け取るまで待つ

読む（）
  すべてのプロセスに読み取り要求を送信する
  彼らからの返答を待つ
  tが最大のvを選択する

操作の線形化の順序は次のとおりです。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 つのプロセスによってのみ書き込むことができますが、複数のプロセスによって読み取ることができます。

SWSRレジスタを使用したSWMRレジスタの実装
読者作家	⁠ ⁠ $R_{1}$	⁠ ⁠ $R_{2}$	⋯	⁠ ⁠ $R_{n}$
⁠ ⁠ $R_{1}$	A[1,1]	A[1,2]	...	A[1,n]
⁠ ⁠ $R_{2}$	A[2,1]	A[2,2]	...	A[2,n]
⋮	...	...	...	...
⁠ ⁠ $R_{n}$	A[n,1]	A[n,2]	...	A[n,n]
$わ$	A[n+1,1]	A[n+1,2]	...	A[n+1,n]

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$ によって読み取り可能です。読み取りと書き込みの実装を以下に示します。

ライター

w: 書き込み(v)

j = i..n の場合
    t++
    A[n+1,j]に(v,t)を書き込む
終わりのために

読者

$R i$ : 読み取り()

k = 1..(n+1) の場合
    (V[k],T[k]) <- A[k,i]を読み込む
終わりのために
すべてのlに対してT[k] >= T[l]となるkをとる
r <- V[k]
t <- T[k]
j=1..nの場合
    A[i,j]に(r,t)を書き込む
終わりのために
rを返す

操作のt値とは、書き込むtの値であり、操作はt値によって線形化されます。writeとreadのt値が同じ場合は、writeをreadより先に実行します。複数のreadが同じt値を持つ場合は、開始時刻順に実行します。

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

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

ライター	読者
P _i : WRITE(v)	P _i : READ()
((v1, t1), ..., (vn, tn)) <- V.SCAN() t = max(t1, ..., tn) + 1 とします。 V.UPDATE(i, (v, t))	V.スキャンスキャンの結果、最大のタイムスタンプを持つ値を返します (同点の場合は、最も大きいタイムスタンプの右端のペアを使用します)

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

参照

参考文献

^ ab Kshemkalyani, Ajay D.; Singhal, Mukesh (2008). 『分散コンピューティング：原理、アルゴリズム、システム』ケンブリッジ：ケンブリッジ大学出版局. pp. 435–437. ISBN 9780521876346。
^ アティヤ・ハギット、ウェルチ・ジェニファー（2004年3月25日）『分散コンピューティング：基礎、シミュレーション、そして高度なトピックス』John Wiley & Sons, Inc. ISBN 978-0-471-45324-6。
^ Attiya, Hagit; Bar-Noy, Amotz; Dolev, Danny (1990). 「メッセージパッシングシステムにおけるメモリの堅牢な共有」.第9回ACMシンポジウム「分散コンピューティングの原理」の議事録. Vol. 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] アティヤ・ハギット、ウェルチ・ジェニファー（2004年3月25日）『分散コンピューティング：基礎、シミュレーション、そして高度なトピックス』John Wiley & Sons, Inc. ISBN 978-0-471-45324-6。

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