逐次一貫性

ウィキペディア

逐次一貫性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/08/04 07:57 UTC 版)

逐次一貫性（ちくじいっかんせい、英語: sequential consistency）、順次整合性（じゅんじせいごうせい）、逐次整合性（ちくじせいごうせい）は並行プログラミングにおける一貫性モデルの一種である。「どのような実行結果も、すべてのプロセッサがある順序で逐次的に実行した結果と等しく、かつ、個々のプロセッサの処理順序がプログラムで指定された通りであること」と定義されている^[1]。

この記述を理解するためには、同一プロセッサ（またはスレッド）内でのプログラムの実行順序はプログラムの順序と同じであるが、プロセッサ（またはスレッド）間でのプログラムの実行順序は未定義であることを理解する必要がある。以下の例では

 プロセッサー 1:     <-- A1 run --> <-- B1 run -->        <-- C1 run -->
 プロセッサー 2:       <-- A2 run --> <-- B2 run -->
 時間 --------------------------------------------------------------------->

A1、B1、C1の実行順序は維持される。つまりA1はB1の前、B1はC1の前に実行される。A2とB2についても同様である。しかしプロセッサ間の実行順序は未定義であるため、B2がC1の前または後に実行される可能性がある（物理的にはB2がC1の前に実行されるかもしれないが、B2の効果がC1の効果の後に現れるかもしれない。）

概念的には、単一のグローバルメモリと、任意のプロセッサを任意の時間ステップでメモリに接続する「スイッチ」が存在する。各プロセッサはプログラム順にメモリ操作を行い、スイッチはすべてのメモリ操作間のグローバルな直列化を行う。

• 

同じメモリー部分（ページ、仮想オブジェクト、セル等）に対する書き込み操作がすべてのノードにおいて同じ順序で観測されるならば、たとえその順序が実際に操作が行われた時間順序とは異なっていたとしても、そのシステムでは逐次一貫性が保証される。

逐次一貫性は厳密な一貫性(英語: strict consistency)（これはすべての操作が発行された順序で実行されることを求める。ただし、分散並列システムでは大域的な時間を決定することができないので、実現不能である。）よりも緩やかな一貫性モデルである。

関連項目

• 並列処理
• 並行プログラミング
• 一貫性モデル
• 不可分操作
• 直列化可能性
• 一貫性モデル (ソフトウェア)
• 線形化可能性
• リリース一貫性

脚注

[脚注の使い方]

1. ^ Leslie Lamport, "How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs", IEEE Trans. Comput. C-28,9 (Sept. 1979), 690-691.

ウィキペディア小見出し辞書

逐次一貫性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/29 18:38 UTC 版)

「一貫性モデル (ソフトウェア)」の記事における「逐次一貫性」の解説

詳細は「逐次一貫性」を参照 逐次一貫性（整合性）モデルは、ランポート(1979)によって提唱された。厳密な一貫性モデルよりも弱いメモリモデルである。変数への書き込みは瞬時に確認される必要はないが、異なるプロセッサによる変数への書き込みは、すべてのプロセッサで同じ順序で確認されなければならない。ランポート(1979)の定義によると、「任意の実行結果が、すべてのプロセッサの操作が何らかの順序で実行された場合と同じであり、個々のプロセッサの操作が、そのプログラムで指定された順序でこの順序に現れる」場合に、逐次整合性が満たされる。 各プロセッサ内のプログラムの順序と、プロセッサ間の操作の順序は維持されるべきである。プロセッサ間の実行の順序を維持するためには、すべての操作が他のすべてのプロセッサに対して瞬間的または不可分的に実行されているように見えなければならない。情報を瞬時に送信することは物理的に不可能なので、これらの操作は完了したように見えればよいのです。例えば、単一のグローバル共有バスを利用したシステムでは、バスラインに情報がポストされると、すべてのプロセッサが同じ瞬間にその情報を見ることが保証される。そのため、バスラインに情報を渡すことで、すべてのプロセッサに対して実行が完了し、実行されたように見える。キャッシュレス・アーキテクチャや、インターコネクト・ネットワークが瞬間的ではないキャッシュ・アーキテクチャでは、プロセッサとメモリの間にスロー・パスが含まれることがある。このような遅い経路では、あるメモリが他のメモリよりも早くブロードキャストデータを受け取るため、シーケンシャルな不整合が生じる可能性がある。 逐次一貫性は、非決定的な結果をもたらすことがある。これは、プロセッサ間の逐次操作の順序が、プログラムの異なる実行時に異なる可能性があるためです。すべてのメモリ操作は、プログラムの順番通りに行われる必要があります。 線形化可能性（不可分整合性とも呼ばれる）は、逐次一貫性にリアルタイム制約を加えたものと定義できる。

逐次（シーケンシャル）一貫性

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/29 18:38 UTC 版)

「一貫性モデル (ソフトウェア)」の記事における「逐次（シーケンシャル）一貫性」の解説

データ中心の一貫性（整合性）モデルの目的はプロセスが並行して更新を行う可能性のあるデータストアに一貫したビューを提供することである。重要なデータ中心一貫性モデルの1つに、Lamport (1979) によって定義された逐次一貫性がある。Tanenbaum et al(2007)は、逐次一貫性を以下の条件で定義している。 任意の実行結果は，データストア上のすべてのプロセスによる（読み書きの）操作が何らかの順序で実行され，個々のプロセスの操作がそのプログラムで指定された順序でこの順序に現れる場合と同じである。 Adve and Gharachorloo, 1996は，逐次整合性を実現するための要件として，プログラムの順序と書き込みの不可分性の2つを定義している． プログラムオーダー：各プロセスがメモリ要求をプログラムの順番で発行することを保証する。 書き込み不可分性：書き込みの不可分性は、メモリ要求が単一のFIFOキューの順序に基づいて処理される。 逐次整合性では、時間や最新の書き込み操作という概念はない。すべてのプロセスで同じように、いくつかの操作のインターリーブがある。あるプロセスは、すべてのプロセスの書き込み操作を見ることができるが、自分の読み取り操作を見ることができるだけである。 線形化可能性(不可分メモリ)は、各操作の開始時刻と終了時刻を考慮することにより、実時間制約のある逐次一貫性として定義できる。各操作の開始時刻と終了時刻の間に点を置くことにより、各操作が線形化可能な順序で行われ、逐次的な一貫性が保証される場合、実行は線形化可能である。