不可分操作
(厳密な一貫性 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/12/18 23:40 UTC 版)
|
この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。（2023年1月）
|
不可分操作（ふかぶんそうさ）あるいはアトミック操作 (英: atomic operation) とは、情報工学においていくつかの操作を組み合わせたもので、システムの他の部分から見てそれらがひとつの操作に見えるものをいう。
条件
不可分操作は、以下の2つの条件を満たさなければならない。
- 全操作が完了するまで、他のプロセスはその途中の状態を観測できない。
- 一部操作が失敗したら組合せ全体が失敗し、システムの状態は不可分操作を行う前の状態に戻る。
システムの他の部分から見て、操作の組合せが一度に成功したか失敗したように見える。途中の状態にアクセスすることはできない。このため不可分操作あるいはアトミック操作（= 原子操作）と呼ぶのである。
マルチプロセッサでなくとも、この実装は重要である。制御の流れが変更される可能性がある限り、不可分性がなければシステムが不正な状態になってしまう可能性がある。
単純な例
例えば、プロセスがあるメモリ位置の内容をインクリメントしているとする。その処理の流れは以下のようになる:
- プロセスがその位置の値を読み込む。
- 同じプロセスがその値に 1 を加算する。
- 同じプロセスがそのメモリ位置に加算結果を書き込む。
ここで、2つのプロセスが一箇所の共有メモリ上の位置の内容をインクリメントすると仮定する:
- 1番目のプロセスがその位置の値を読み込む。
- 1番目のプロセスがその値に 1 を加算する。
ここで、1番目のプロセスが加算結果を書き戻す前にサスペンドされ、2番目のプロセスが走行し始めたとする:
- 2番目のプロセスがその位置の値を読み込む。読み込まれた値は1番目のプロセスが先に読み込んだのと同じ値。
- 2番目のプロセスがその値に 1 を加算する。
- 2番目のプロセスが加算結果を書き戻す。
ここで、2番目のプロセスがサスペンドされ、1番目のプロセスが再度走行する:
- 1番目のプロセスが自身の持つ加算結果を書き戻すが、それは2番目のプロセスの処理を反映していない。
これは些細な例である。実際のシステムでは、操作はより複雑で、微妙なエラーとなって現われるかもしれない。例えば、64ビットの値をメモリから読む操作は32ビットのリードを2回行うことで実現されている場合がある。プロセスが最初の32ビットをリード後、次の32ビットをリードする前に値が変更されるかもしれない。結果として得られた64ビット値は変更前とも変更後とも異なる無意味な値となる。
さらに、このような結果はプロセスの動作する順番に依存しており、デバッグしようとしても検出が難しい。
CPUアーキテクチャによる違いとロック
カウンタのインクリメント/デクリメントは、RISCアーキテクチャの場合、上記の例のようにリードとライトが別々の命令で行われるために、そのままでは不可分操作にできない。しかし、x86アーキテクチャのようなCISCでは、インクリメントやデクリメントを1命令で実行する命令が存在するため、それだけで不可分性が成立する。必要最小限の不可分操作は、結局テスト・アンド・セットのような指定されたメモリアドレスへのリードとライトを不可分に行う操作となる。しかし、RISCアーキテクチャは 1命令で複数回のメモリアクセスを行わないのが基本思想であるため、直接テスト・アンド・セット命令を実装することはできない（テスト・アンド・セットを命令として実装する場合、バスをロックしてリードとライトを行って他のバスマスタがメモリアクセスを途中で発行できないようにしている）。そのためにコンペア・アンド・スワップやLoad-Link/Store-Conditionalといった不可分操作が使われるようになった。
上記の例は「クリティカルセクション」のまわりでロックを獲得することで解決するように見える。しかし、ロックもハードウェアのサポート無しでは単なるメモリ上のデータでしかない。スピンロックなどのアルゴリズムをソフトウェアだけで実装することは可能だが、効率的ではない。そのために、上述のテスト・アンド・セットなどの不可分操作が最近のプロセッサで実装されており、そういった機能でロックを実装する。
関連項目
厳密な一貫性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/29 18:38 UTC 版)
「一貫性モデル (ソフトウェア)」の記事における「厳密な一貫性」の解説
詳細は「厳密な一貫性」を参照 厳密な一貫性は、最も強力な一貫性モデルである。このモデルでは、任意のプロセッサによる変数への書き込みは、すべてのプロセッサによって瞬時に確認される必要がある。 厳密モデルの図と非厳密モデルの図は、時間の制約である「瞬間」を表している。これは、あたかもグローバルクロックが存在し、すべての書き込みがそのクロック期間の終わりまでにすべてのプロセッサのキャッシュに反映されなければならないように理解することができる。次の操作は、次のクロック期間にのみ行われなければならない。 シーケンス厳密なモデル非厳密なモデルP1P2P1P21W(x)1 W(x)1 2 R(x)1 R(x)0 3 R(x)1 これは最も厳格なモデルである。このモデルでは、プログラマーが期待した結果が毎回返ってくる。よって決定論的なモデルである。瞬間的なメッセージ交換は不可能なので、実用的な関連性は思考実験と形式論に限られる。また、同時書き込みが不可能であることを前提としているため、同じデータアイテムへの同時書き込みにおける衝突解決の問題にも役立たない。
※この「厳密な一貫性」の解説は、「一貫性モデル (ソフトウェア)」の解説の一部です。
「厳密な一貫性」を含む「一貫性モデル (ソフトウェア)」の記事については、「一貫性モデル (ソフトウェア)」の概要を参照ください。
- 厳密な一貫性のページへのリンク
