內存一致性模型

內存一致性模型描述的讀操作和寫操作這些操作可能的執行順序中那些是正確的。在假定沒有流水線的情況下（即單個處理器內指令的執行是按順序執行的），設系統內共有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) 指的是程序在執行的歷史中在存在可線性化點P的執行模型，這意味着一個操作將在程序的調用和返回之間的某個點P起作用。這裏“起作用”的意思是被系統中併發運行的所有其他線程所感知。線性一致性最重要的性質就是其“局部性”（Local property, 或可組合性 - Compositional），即數個線性一致單對象歷史的組合也是線性一致的。線性一致性的非阻塞性(Non-blocking property)：線程P對完全操作(total function)的調用永遠不會阻塞。

原子一致性(Atomic consistancy)：讀操作未能立即讀到此前最近一次寫操作的結果，但多讀幾次還是獲得了正確結果。所有對數據的修改操作都是原子的，不會產生競態衝突。

順序一致性（Sequential consistency ）:（併發程序在多處理器上的）任何一次執行結果都相同，就像所有處理器的操作按照某個順序執行，各個微處理器的操作按照其程序指定的順序進行。換句話説，所有的處理器以相同的順序看到所有的修改。讀操作未必能及時得到此前其他處理器對同一數據的寫更新。但是各處理器讀到的該數據的不同值的順序是一致的。

緩存一致性（Cache coherence，或cache coherency），又譯為緩存連貫性、緩存同調，是指保留在高速緩存中的共享資源，保持數據一致性的機制。在一個系統中，當許多不同的設備共享一個共同存儲器資源，在高速緩存中的數據不一致，就會產生問題。這個問題在有數個CPU的多處理機系統中特別容易出現。緩存一致性可以分為三個層級：在進行每個寫入運算時都立刻採取措施保證數據一致性；每個獨立的運算，假如它造成數據值的改變，所有進程都可以看到一致的改變結果；在每次運算之後，不同的進程可能會看到不同的值。

處理器一致性（Processor consistency）/PRAM一致性（PRAM consistency，P指pipeline）：在一個處理器上完成的所有寫操作，將會被以它實際發生的順序通知給所有其它的處理器；但是在不同處理器上完成的寫操作也許會被其它處理器以不同於實際執行的順序所看到。這反映了網絡中不同節點的延遲可能是不相同的。對於雙處理器，處理器一致性與順序一致性是等價的。