內存一致性模型

記憶體一致性模型描述的是程序在執行過程中記憶體操作正確性的問題。記憶體操作包括讀操作和寫操作，每一操作又可以用兩個時間點界定：發出（Invoke）和響應（Response）。在假定沒有流水線的情況下（即單個處理器內指令的執行是按順序執行的），設系統內共有N個處理器，每個處理器可發出$s_{n}(0<n\leq N)$個記憶體操作（讀或寫），那麼總共有：${\frac {(\sum _{n=1}^{n=N}s_{n})!}{\prod _{n=1}^{n=N}s_{n}!}}$種可能的執行順序。記憶體一致性模型描述的就是這些操作可能的執行順序中哪些是正確的。

內存一致性模型的研究歷史和分類

按照傳統馮諾依曼體系結構的計算模型來看，讀操作應當返回最近的寫操作所寫入的結果，但是這裡「最近」的含義是比較模糊的。因此必須將概念嚴格化，於是產生了線性一致性（或稱做嚴格一致性Strict consistency、原子一致性Atomic consistency）的概念。但是線性一致性太難實現了，因為這裡需要一個全局同步的時鐘，於是Leslie Lamport提出了順序一致性（Sequential consistency）的概念，這裡全局的時鐘變得不再需要，轉而需要的是各個處理器局部的時鐘，相應的，Maurice Herlihy和Nir Shavit等人後來又提出了靜態一致性（Quiescent consistency）的概念。

然而，即使是順序一致性在實際系統中也是很少使用的，主要是它嚴格限制了程序的優化執行，強行的使程序在本地處理器上按程序順序（program order）執行在大多數情況下是沒有必要的。於是在後來的研究中陸續提出了面向硬體的內存模型（Hardware-centric memory model），其中包含了弱序一致性模型（WO, Weak-order model），處理器一致性模型（PC, Processor-consistency model），鬆弛一致性模型（RC, Release consistency model）以及一系列相關的派生模型，如TSO一致性模型（Total store ordering），PSO一致性模型（Partial Store Ordering）等。使用前面的這些模型對於程式設計師來說無疑是非常困惑的，因為這要求程式設計師在編寫程序時必須考慮到各種硬體體系結構所對應的不同內存模型，於是後來的研究進一步提出了面向程式設計師的內存模型（Programmer-centric model）的概念，主要包括SCNF模型（Sequntial consistency nomal form）和PL模型（Properly-Labeled Model）等等。

內存一致性模型列表

• 線性一致性（Linearizability）或嚴格一致性（Strict consistency）：任何對一個內存位置X的讀操作，將返回最近一次對該內存位置的寫操作所寫入的值。
• 原子一致性(Atomic consistency)：讀操作未能立即讀到此前最近一次寫操作的結果，但多讀幾次還是獲得了正確結果。所有對數據的修改操作都是原子的，不會產生競態衝突。
• 順序一致性（Sequential consistency ）:（並發程序在多處理器上的）任何一次執行結果都相同，就像所有處理器的操作按照某個順序執行，各個微處理器的操作按照其程序指定的順序進行。換句話說，所有的處理器以相同的順序看到所有的修改。讀操作未必能及時得到此前其他處理器對同一數據的寫更新。但是各處理器讀到的該數據的不同值的順序是一致的。
• 緩存一致性（Cache Coherence）
• 靜態一致性（Quiescent consistency）
• 處理器一致性（Processor consistency）/PRAM一致性（PRAM consistency，P指pipeline）：在一個處理器上完成的所有寫操作，將會被以它實際發生的順序通知給所有其它的處理器；但是在不同處理器上完成的寫操作也許會被其它處理器以不同於實際執行的順序所看到。這反映了網絡中不同節點的延遲可能是不相同的。對於雙處理器，處理器一致性與順序一致性是等價的。
• 釋放一致性（Release consistency ）：在對一個共享變量進行普通訪問之前，進程在之前所有的獲得鎖而進行的操作必須成功的完成。在釋放一個鎖操作之前，進程之前的讀和寫操作必須已經完成。獲得和釋放鎖的操作必須符合「FIFO一致性」。「釋放一致性」僅僅關注被鎖住的共享內存內存變量，僅僅只需要將對被鎖住的共享變量的修改通知給其它的處理器。C#的VolatileWrite函數即實現了釋放一致性語義。
• 因果一致性（Causal consistency ）
• TSO一致性（Total store ordering）
• PSO一致性（Partial store ordering）
• 弱序一致性（Weak-ordering consistency）
• 最終一致性（Eventual consistency）

相關話題

• 任務並行
• 面向硬體的內存模型
• 面向程式設計師的內存模型

參考文獻

1. Designing Memory Consistency Models For Shared-Memory Multiprocessors,Computer Sciences Technical Report #1198,University of Wisconsin-Madison December 1993,Sarita V. Adve
2. Distributed Computing,Principles, Algorithms, and Systems. Ajay D. Kshemkalyani University of Illinois at Chicago, Chicago and Mukesh Singhal University of Kentucky, Lexington

外部連結

存儲一致性總結 （頁面存檔備份，存於網際網路檔案館）