内存一致性模型指南
Memory Consistency Models: A Tutorial（內存一致性模型指南）
The cause of, and solution to, all your multicore performance problems.
計算機科學里有幾個比較困難的問題：緩存失效、命名、off-by-one errors。除此之外還有事件排序問題，以一定的順序觀察事件是一件很具有挑戰性的事情。
內存一致性模型用來描述事件排序，定義多個并行線程之間如何以一定的順序觀察共享內存的狀態變化。有很多討論內存一致性的資料，但是大多數要么是幻燈片要么出自《A Primer on Memory Consistency and Cache Coherence》這本書。我的目標就是就是盡量闡述為什么對于多處理器系統而言內存一致性為什么會如此重要。更詳細的問題可以查看其他更優秀的資料。
Making threads agree
一致性模型用來表示多個線程如何看待這個世界。考慮如下程序片段：
為了搞清楚這個程序的輸出，我們必須考慮事件的執行順序。憑感覺來說這個程序有兩種執行路徑：
- (1) → (2) → (3) → (4): 輸出01.
- (3) → (4) → (1) → (2): 輸出01.
還有兩種交叉執行的可能： - (1) → (3) → (2) → (4): 輸出11.
- (1) → (3) → (4) → (2): 輸出11.
- 其他執行順序也是相同的輸出。
Things that shouldn’t happen（不應該發生的事情）
直覺上來講，這個程序不會輸出00。為了讓(2)輸出0，(2)必須在(3)之前執行，我們可以畫一條箭頭從(2)指向(3)。
一條從x指向y的箭頭表明，x先于y執行。同樣地，為了(4)輸出0，(4)必須先于(1)執行。如下圖：
最后，每個線程的執行路徑按照程序指定的順序執行——(1) 先于 (2)，(3) 先于 (4)。最后得到下圖：
如果我們從(1)開始執行，然后順著箭頭的方向執行的話，到 (2), 然后 (3), 再然后 (4), 最后又到了 (1)！這個圖表示(1)先于(1)執行。除非物理學有重大研究突破，否則，這是不可能的！
因為這個執行路徑需要時間扭曲，所以我們可以得出結論，這個程序不可能輸出00.我們使用反證法來進行論證：假設這個程序可以輸出00，那么我們剛才列出的排列規則一定會遵守，但是通過這個規則我們得出（1）先于(1)執行。所以，假設是錯誤的。
Sequential consistency: an intuitive model of parallelism（順序一致性：一個直觀的并行模型）
架構師和語言設計者希望我們上面列舉的規則對于軟件開發人員來說是通俗易懂的。核心思想就是在單個主內存的計算機系統中并行執行多個線程，這些線程的執行事件一定是有序進行的。如果兩個事件同時訪問主存的話，那么這兩個事件不可能同時執行。
這個規則沒有規定全局的事件到底以什么樣的順序執行，但是規定了在一個線程內，事件肯定是按照程序指定的順序（program order）執行，這肯定是程序員期望的，因為不可能在不檢查鑰匙之前就直接發送導彈。
所以，一個共享內存和程序順序（program order）共同定義了順序一致性。定義順序一致性是Leslie Lamport在2013.1年獲得圖靈獎的眾多成就之一（盡管Lamport剛開始是研究多核系統，但是之后他的工作方向變成了分布式系統，在當前的分布式系統場景中的sequential consistency與架構師所期望的sequential consistency模型不太一樣，甚至可能還要弱一點。架構師期望的sequential consistency可能是分布式系統中現在使用的“linearizability”模型）。
順序一致性是內存模型的第一個例子。內存一致性模型（通常叫做內存模型）定義了多線程在多核心處理器上執行時，事件被允許執行的順序。比如上面的程序，順序一致性模型禁止輸出00結果，但是允許出現01和11兩個結果。
內存模型是硬件和軟件之間的契約。硬件只會按照內存模型允許的順序重新排列事件，相應地，軟件也會考慮所有事件可以執行的可能性。
The problem with sequential consistency（順序一致性的一些問題）
理解順序一致性的一個更好的方法就是轉換器（switch）。每一個時鐘周期，轉換器選擇一個線程執行，然后執行線程的下一個事件。這個實例保持了順序一致性的兩個原則：事件只訪問了一個主內存，并且都是按照程序規定的順序訪問。
這個模型非常的低效。我們在同一個時刻只能執行一條指令，所以我們不能發揮多線程帶來的并行優勢。更糟糕的是，我們只能等待一條指令執行完成并且修改的數據對其他線程都可見之后才可以執行下一條指令。
Coherence（緩存一致性）
有些時候，等待是非常有必要的。考慮如下場景，兩個線程想要往A變量寫入數據，并且第三個線程打算讀取這個變量：
如果我們不規定只有一個主存并且允許(1) 和 (2) 并行執行，我們無法確定(3)能讀取到什么數據。一個主存可以保證兩個寫事件只能有一個成功。如果沒有這個前提的話，(1) 和 (2)同時發生，我們能同時看到1和2。
Coherence保證對一個內存位置的所有寫操作，在所有線程看來順序都是一樣的。但是不能規定哪個事件先執行（(1)先執行或者(2)先執行），但是可以保證同一時刻所有的線程看到的寫事件都是一個。
Relaxed memory models
不考慮一致性（Coherence）的話，完全不用限制只有一個內存。考慮如下程序：
事件(2)沒必要等待事件(1)完成。這兩個事件沒有任何交集，所以他倆可以并行執行。事件(1)比較慢，因為是一個寫操作。在一個主存的情況下，我們只能在(1)寫完后并且其他線程都可以看到后，才能執行(2)。在現代CPU系統中，由于緩存的存在導致這是一個非常耗時的操作。
兩個CPU唯一共享的內存就是L3級緩存，這一級緩存的操作大概需要90個時鐘周期。
Total store ordering (TSO)
我們可以把事件(1)放入一個store buffer中，從而不必等待（1）的操作對所有線程都可見再去執行后面的事件。事件(2)在(1)被放入store buffer之后可以立即執行，不用等待事件(1)把數據寫入L3。因為store buffer是在CPU核心里，所以訪問速度非常快。之后的某個時間段，緩存系統會把事件(1)的操作結果反映到緩存上，之后其他線程就可以看到這個數據。
Store buffering非常nice，因為他保留了單個線程的一些特點。考慮如下程序：
為了保證單個線程執行這個程序時的特性，(2)必須能讀取到（1）寫入的值。(1)還沒有把數據寫入內存，只是放在了CPU1的store buffer里，所以如果（2）直接去內存讀取的話，可能會讀到之前的數據。但是因為(1)和(2)都在一個CPU上運行，所以(2)可以直接去store buffer檢索，如果找到有更新相同內存的事件的話，直接讀取就可以。所以，即使使用了store buffer，這個程序的輸出也是1。
允許store buffering存在的內存模型叫做total store ordering (TSO)。TSO與順序一致性模型一樣，唯一的區別就是，TSO使用了store buffer來減少寫的時延從而提高程序的運行速度。
The catch（缺點）
Store buffer聽起來像是一個很棒的性能優化，但這里有一個問題:TSO允許順序一致性不允許的行為。換句話說，運行在TSO上的程序會表現出讓開發者感覺很詫異的行為。
讓我們回顧上面的一個程序，但是這次這個程序運行在一個有store buffer的計算機上。首先我們執行(1)然后執行(3)，這兩個都會把數據放入store buffer而不是寫入主存：
接下來我們在CPU1上執行(2)，事件(2)先去CPU1的store buffer中查找是否有變量B的值，因為store buffer中沒有B的值，所以事件(2)去內存里讀取到了B=0這個值。最后我們在CPU2上執行(4)，同樣在CPU2的store buffer中沒有找到A的值，然后去主存獲取到了A=0這個值。在未來某個時刻，緩存系統會把store buffer中的值同步到內存里。
在TSO模型里，程序會打印00.這個值在SC（Sequential consistency）模型中是不會出現的。所以store buffer會造成一些開發者不希望看到的行為。
一些計算機體系結構會為了提升性能而采取一些讓開發者感覺很奇怪的優化方法嗎？當然！事實證明現代的體系架構都會有個一個store buffer，并且也會有一個和TSO一樣弱的內存模型。
X86架構使用了和TSO非常接近的內存模型。Intel（x86的設計者）和AMD（x86-64的設計者）都使用了類似上面的簡單程序代碼對內存模型進行了描述。但是對于比較復雜的系統，很難用測試用例來描述系統的表現行為。Cambridge大學的研究人員花費了大量精力來形式化x86-TSO模型，該模型規定了x86’s TSO的實現所具有的某些特性（還描述了與store buffering不一樣的地方）。
Getting weaker
盡管x86放棄了順序一致性，但是就這個架構能允許的瘋狂表現而言，x86是一個表現非常好的架構。其他的架構實現了更弱的內存模型，這就意味著會出現更多意想不到的行為。SPARC架構允許開發人員在系統運行過程中選擇不同的內存模型。
現在智能手機中普遍使用的ARM架構就采用了比TSO還弱的內存模型。ARM內存模型本質上是一種弱排序（weak ordering），它所能提供的保證更少。弱排序（weak ordering）幾乎可以對任何操作進行重排序以便進行硬件優化，但是，這對于軟件開發者來說是一個噩夢。
Escaping through barriers（內存屏障解決一切）
幸運的是，現代架構都有同步操作，在需要的時候可以通過同步操作控制這些弱化的內存模型。最常用的同步操作就是內存屏障（barrier 或者 fence）。內存屏障指令之前的所有內存操作完成之后才可以執行后續的操作。也就是說，內存屏障指令使得程序運行的某個時刻讓系統的內存模型變成了順序一致性模型。
當然我們會通過使用store buffer或者其他優化方式盡量減少內存屏障的使用。內存屏障是一個非常耗時的操作，一次操作大概需要幾百個時鐘周期，必須謹慎使用，并且與一些定義不清楚的內存模型結合使用的時候，很容易出錯。有一些比較有用的基礎指令，比如CAS（atomic compare-and-swap），但是我們建議盡量少使用這種比較底層的同步指令。使用一些專用的同步庫可能會比較方便。
Languages need memory models too
硬件可能會重排序內存操作指令，編譯器也經常對指令進行重排序。考慮如下程序代碼：
X = 0 for i in range(100):X = 1print X這個程序會打印長度為100的字符串（1111…）。在循環里為X賦值顯得比較冗余，因為沒有其他地方對X進行修改。編譯器在進行代碼編譯的時候會把代碼優化成下面這樣：
X = 1 for i in range(100):print X這兩段代碼完全一樣， 因為他們的輸出是一樣的。
考慮有另個線程也在運行我們的程序，并且為X進行了賦值：
X = 0
當這兩個線程同時執行的時候，第一個程序的輸出就會變成11101111…，因為第二次循環會把X設置成1。第二個程序的輸出也會變成11100000…，因為循環里的賦值代碼被優化到循環外面。
對于這兩個程序片段來說，第一個程序片段不會輸出11100000…，第二個程序片段也不會輸出11101111…。這就意味著，在并行場景中，編譯器優化不能再得到兩個一樣的代碼。
這個示例說明在語言層面也需要內存模型。編譯器把一些內存訪問指令進行了重排序。為了保持明確的代碼執行結果，編程語言需要內存模型來控制編譯器如何對代碼指令進行重排序。在語言設計領域，內存模型變得越來越普遍，比如最新版本的C++和Java都有明確的內存模型定義。
Computers are broken!
這些重排序看著比較凌亂，我們是沒有辦法完全搞明白這些重排序。另一方面，如果我們回顧一下自己的編程經驗，那么內存一致性可能并不常見(除非是一個底層內核黑客)。
我這里提到的每個例子都涉及到數據競爭。數據競爭是指對同一個內存位置的兩次訪問，其中至少一次是寫操作，并且沒有使用同步操作保證執行順序。如果沒有數據競爭（race-free）的話，那么指令重排序就沒有太大問題，因為所有的不確定的重排序操作都會被同步指令禁止。但是這并不意味著沒有數據競爭的程序就是確定性的，因為每次多線程執行的時候，都會只有一個線程贏得這次競爭。
實際上，編程語言比如C++或者Java都為data-race-free的程序提供了稱為sequential consistency（順序一致性）的一致性模型。這個模型保證如果程序沒有數據競爭的話，編譯器會在必要的地方插入內存屏障來保障順序一致性。如果程序有數據競爭的話，編程語言便不會提供這些保障，編譯器可以按照它們的意愿進行重排序。所以，帶有數據競爭的程序非常的容易有bug，并且編程語言也不會為這種程序提供太強的一致性保證。如果程序有數據競爭的話，開發者應該了解如果處理這些數據競爭，并且有義務去處理這些內存重排序問題。
Use a synchronization library
我們應該使用同步工具，同步工具會幫我們解決這些討厭的重排序問題。操作系統也進行了大量優化，會在特定平臺上進行必要的同步。經過簡單的討論，現在我們已經了解了當這些庫和內核處理同步問題時，底層到底發生了什么。
如果想更多的了解更多的內存模型，Morgan & Claypool有關于一致性模型和緩存一致性更好的資料。
總結
- 上一篇： poi excel文档生成与读取
- 下一篇： python中configparser详