並發中的一些基本概念

來自專欄 分散式計算

背景

在多核多線程的並發編程中，我們經常會碰到一些概念，比如說out of order execution， memory consistency， cache coherence， memory model等，這裡我對這些概念做一些簡單的總結和介紹。

為什麼會有亂序執行

亂序執行（out of order execution）的來源通常有2種，一種是來自編譯器，一種來自CPU。之所以會發生亂序，簡單點來講就是為了更高的執行效率。編譯器通過亂序可以生成更優化的代碼，CPU亂序可以更好的利用硬體。比如說，當需要載入的數據不在cache中，CPU可以跳過等待載入的過程，繼續後面其他的寫入數據或者載入數據。

Memory Consistency

Memory Consistency通常指的是CPU執行代碼時所要遵循的一些限制。前面我們講過CPU在執行代碼時又可能會發生亂序，如果CPU的亂序沒有任何的限制，那我們根本無法編寫多線程程序，因為我們根本沒有辦法預測代碼以何種方式執行。而memory consistency則對CPU的亂序做了某些限制，從而讓我們能推理程序可能的執行結果。這裡我們以sequential consistency為例來說明。關於sequantial consistency的定義網上有很多說明，這個我不在贅述，簡單講就是2點：

1. 所有的指令執行順序符合某種全序
2. 在這個全序中每個線程的指令符合program order

有了這2點保證，下面的代碼段就不會出現r1=0 and r2=0 的結果：

thread 1: a = 4;r1 = b;thread 2:b = 7;r2 = a;

Sequential consistency是一個比較強的內存模型，現實中的CPU基本上沒有遵循這個模型的，因為這個模型上能做的優化太少。通常來說，CPU在提供一定的內存模型之外，還會提供一定的指令來允許指定程序的執行順序，這樣的指令通常稱為memory barrier或者memory fence。

cache coherence

cache coherence對於程序來說是不可見的。cache的引入主要是為了解決CPU和內存之間速度不匹配的問題。由於訪問內存速度較慢，CPU的直接操作數據的對象就變成了cache而不是內存。這就帶來一些問題，因為每個core會有自己私有的cache，當core 1改變了數據寫入cache而沒有寫入內存，core 2中的cache就會有過期數據，如果不做任何處理，cache的引入就會導致錯誤。cache coherence protocol就是為不同cache之間的數據的一致性而設計的，有了它的存在cache只會影響程序執行速度而不是正確性。

Memory Model

這裡的memory model指的是編程語言的memory model。我們所使用的高級編程語言如java, c++, c等都有一個abstract machine model，編程語言的memory model就是用來指定程序的合法的執行順序。對於java來說，memory model就是用來指定虛擬機執行程序的時候哪些優化是合法的。對於c/c++這樣的語言來說，memory model會限制編譯器生成程序的時候所做的優化，以及在目標平台上應該結合目標平台提供的memory consistency和指令來實現。

Memory Barrier

Memory Barrier是編程語言memory model的一部分，沒有一個統一的標準來規定memory barrier的種類，但是通常情況下會有如下幾種：

1. load load
2. store store
3. load store
4. store load
5. data dependency
6. full barrier

這幾種barrier的具體含義很容易查到，這裡我就不再敘述。當我們在使用memory barrier推理程序的正確性的時候，有幾點需要注意：

1. memory barrier必須成對使用才有效果。比如說如下示例：

a = 1;store store barrierb = 2;

r1 = b; r2 = a;

在這個示例中2段程序分別由不同的線程執行，對於第二段程序，當r1 = 2時，r2讀到的值不一定是1，要想達到想要的效果，必須在2次讀取之間加入一個load load barrier。

2. 盡量使用memory barrier提供的語義保證來推理程序的執行邏輯，而不要嘗試將其對應到相應平台的指令來推理。這個道理同樣適用於memory model里所提供的語義。 網路上有很多關於memory model和memory barrier的資料，但一個常見的錯誤是在推理程序執行邏輯的時候喜歡使用具體的指令集而不是形式化的memory model所提供的語義。當然了解一些硬體平台的指令和memory model對你理解編程語言的memory model會有幫助，但還是應該使用形式化的memory model來推理程序的正確性≥

推薦閱讀：