アトミックセマンティクス

アトミック セマンティクスは、並列マシンまたは連携して動作するコンピュータ ネットワーク内の複数のプロセッサによって共有されるデータ レジスタによって提供される一種の保証です。アトミック セマンティクスは非常に強力です。アトミック レジスタは、同時実行や障害が発生した場合でも強力な保証を提供します。

読み取り/書き込みレジスタ R は値を格納し、2 つの基本操作 (読み取りと書き込み (v)) によってアクセスされます。読み取りは R に格納されている値を返し、書き込み (v) は R に格納されている値を v に変更します。レジスタは、次の 2 つのプロパティを満たす場合、アトミックと呼ばれます。

1) 読み取りまたは書き込み操作の各呼び出し op:

•時間的に単一のポイント τ(​​op) で実行されたかのように表示されなければなりません。

•τ(op) は次のように機能します: τb(op) ≤ τ(op) ≤ τe(op): ここで、τb(op) と τe(op) は操作 op の開始時刻と終了時刻を示します。

・op1≠op2の場合、τ(op1)≠τ(op2)

2) 各読み取り操作は、読み取り前の最後の書き込み操作によって書き込まれた値を、すべての操作が τ 値によって順序付けられたシーケンスで返します。

アトミック/線形化可能なレジスタ:

終了: ノードが正しい場合、遅かれ早かれ各読み取りおよび書き込み操作が完了します。

安全性プロパティ(読み取り、書き込み、失敗した操作の線形化ポイント):

読み取り操作: 呼び出しと応答時間の間のある時点ですべてのノードで発生したように見えます。

書き込み操作: 読み取り操作と同様に、呼び出しと応答時間の間のある時点ですべてのノードで発生したように見えます。

失敗した操作 (アトミックという用語はこの概念に由来します): すべてのノードで操作が完了したか、またはどのノードでも操作が発生しなかったように見えます。

例: アトミック レジスタは、シーケンシャル セーフ レジスタに線形化可能なレジスタであることがわかっています。

次の図は、各操作の線形化ポイントを配置する場所を示しています。

アトミック レジスタは、単一のライターと複数のリーダー (SWMR)、単一のライターと単一のリーダー (SWSR)、または複数のライターと複数のリーダー (MWMR) を持つ変数に対して定義できます。以下は、3 つのプロセス (P1、P2、P3) によってアクセスされる、マルチリーダー マルチライター アトミック レジスタの例です。R. read() → v は、対応する読み取り操作がレジスタの値である v を返すことを意味することに注意してください。したがって、レジスタ R の次の実行は、アトミック レジスタの定義を満たすことができます: R.write(1)、R.read()→1、R.write(3)、R.write(2)、R.read()→2、R.read()→2。

• 正規の意味論
• 安全なセマンティクス

• アトミック セマンティクスは、Lamport の「プロセス間通信について」Distributed Computing 1, 2 (1986)、77–101 で正式に定義されています。(SRC Research Report 8 にも掲載されています)。