一個系列 之二

按照上一篇中的計劃，這一篇應當從實踐的角度分析如何在Lock Free Code中注意Out Of Order問題帶來的影響。但是不想這一段時間出了這么多的事情，包括.NET的內存模型實現上出了Bug讓人們更加關注這部分的問題。那么這篇就對前幾篇小小隨筆做一個全面的解釋，改正文章里出現的理解錯誤，或容易被理解錯誤的地方。

按照上一篇中的計劃，這一篇應當從實踐的角度分析如何在Lock Free Code中注意Out Of Order問題帶來的影響。但是不想這一段時間出了這么多的事情，包括.NET的內存模型實現上出了Bug讓人們更加關注這部分的問題。那么這篇就對前幾篇小小隨筆做一個全面的解釋，改正文章里出現的理解錯誤，或容易被理解錯誤的地方。

 

首先附上前幾篇文章的鏈接：

 

一個系列：之一

"Loads are not reorderd with other loads" is a FACT!!

"Loads are not reorderd with other loads" is a FACT!! 續：不要指望 volatile

"Loads are not reorderd with other loads" is a FACT!! 再續：.NET MM IS BROKEN

選擇虛擬機環境介入多線程編程是一個好的選擇

 

一開始我們就開始提內存模型，實際上，關于內存模型的問題對于底層代碼編寫人員顯得格外重要（把話說明確一點，就是內存模型對于寫無鎖代碼的程序員非常重要！）而對于使用高級同步結構的同志就不那么明顯了。關于內存模型我們在文章中強調的問題始終是：你的代碼并不一定向你想象的那樣在執行。實際上這不是全部，我忘記了一個地方就是內存模型不是一個層次就能夠決定的。

 

一、內存一致性模型

 

想要正確的編寫共享內存平臺下的并行程序的話，需要了解在多個處理器上，內存的讀寫操作是以一種什么樣的方式來執行的。這種對多處理器下內存的讀寫行為進行的描述，稱為稱為內存一致性模型。也就是我們關注的所謂“內存模型”。（參見： Hans-J. Boehm，Threads Cannot be Implemented as a Library，Internet Systems and Storage Laboratory，HP Laboratories Palo Alto，November 12, 2004）

 

內存一致性模型為多處理器共享內存系統中的內存系統對程序開發者的影響提供了一種正式的描述。化解了開發者的期望與實際系統行為之間的差異。為了保證有效性，內存一致性模型往往對于可返回的共享內存數據添加了一些限制。直觀的比如，一個“讀”操作應當返回最后一次對應位置“寫”操作所寫入的數據。在單處理器系統中，“最后一次”是對于程序順序而言的，即，在程序中內存操作指令出現的順序。但是在多處理器系統中，這個概念不再適用。例如，對于上述程序來說，對于data的讀與寫并不是以程序順序進行衡量的，因為他們分別在兩個不同的處理器上執行。然而，直接將單一處理器的模式應用到多處理器系統中卻是可行的。這中模型稱為順序一致性模型。不準確的說，順序一致性模型就是使內存的訪問必須一個一個的執行，并且對于其中的任一個處理器而言，都是按照程序指定的順序進行執行的。這樣對于上述程序來說，就可以保證，每次讀到的data均是P1寫入時的data。（參見：Sarita Adve，Phd: Designing Memory Consistency Models for Shared-Memory Multiprocessors，University of Wisconsin-Madison Technical Report #1198, December 1993）

 

順序的內存一致性模型為我們提供了一種簡單的并且直觀的程序模型。但是，這種模型實際上阻止了硬件或者編譯器對程序代碼進行的大部分優化操作。為此，人們提出了很多松弛的（relaxed）內存模型，給予處理器權利對內存的操作進行適當的調整。例如Alpha處理器，PowerPC處理器以及我們現在使用的x86, x64系列的處理器等等。這些內存模型各不相同，為跨平臺的應用帶來了很多障礙。

 

內存一致性模型是聯系程序開發人員與系統的接口。他會影響共享內存應用程序 的開發（開發人員必須使用這些約定來保證其程序的正確性）。需要指出的是，內存一致性模型會在某些程度上影響系統的性能，因為他部分的限制了硬件或者軟件的優化機制。并且，即使在有內存一致性模型的情況下，不同系統之間由于內存一致性模型的不同也會給程序的移植工作帶來困難。

 

注：以上所述的內容說明了，內存一致性模型的繁雜使得開發跨平臺的并行程序難度加大，因此，如果希望實現跨平臺就需要一定程度上統一內存模型，當然，這會帶來一定的性能沖擊。

 

注：以下將要說明的就是我們前一階段文章忽略了的問題。就是內存一致性模型并不僅僅是CPU決定的，而是系統的各個層面上的組合。

 

內存一致性模型需要在各種的程序與系統的各個層次上定義內存訪問的行為。在機器碼與的層次上，其定義將影響硬件的設計者以及機器碼開發人員；而在高級語言層次上，其定義將影響高級語言開發人員以及編譯器開發人員和硬件設計人員。因此以上所謂的可編程性，性能以及可移植性在各種層次上都需要進行考慮。

 

注：因此所謂的語言的，編譯器的內存模型說的就是語言層次上的。例如，目前C++對內存一致性模型的描述非常弱，因此我們在編程的時候就非常依賴編譯器的內存一致性模型（當然造成的結果也就是程序的正確性對編譯器的依賴）。

 

因此，內存一致性模型不但會從程序的角度影響并行程序開發人員，而且從系統設計人員的角度看影響了并行系統的方方面面（處理器，內存系統，互聯，編譯器以及程序語言）。如果能夠在不同的實際平臺上保證一定的寬松的（Relaxed）內存一致性模型。就可以在保持性能的同時從很大程度上保證多線程程序庫的通用性與正確性。

[END:內存一致性模型]

 

可見，所謂統一內存模型的.NET Framework，其內存模型并不僅僅由CLI的實現者決定，而是CLI的實現者，編譯器，內存系統以及處理器共同作用而形成的。即我們在第一篇文章中提到的：話說你某一天編寫了一段代碼-->你在編譯器上進行編譯發現很順利(但是在編譯的過程中可能你的代碼順序已經被改變了，這種改變應該屬于執行順序改變)-->你試圖運行目標代碼(目標文件中的代碼的順序應該是程序順序)-->你的代碼開始被執行（但是執行過程中CPU對內存操作進行了亂序，這屬于執行順序的改變）

 

那么有了內存一致性模型，我們對內存操作的規則就有了一個大概的了解。那么有沒有什么辦法來對內存訪問的順序進行限制呢？有！那就是內存柵障！這里我們重提這個部分就是因為以前的文章對這一部分的說明相當容易讓人誤解。這回來一個徹底了斷。

 

二、內存柵障

 

如果運行平臺的共享內存模型是確定的，則遵照這個模型編寫的多線程程序庫可以在支持這個運行平臺的任何底層平臺上正確的運行。但是，有時算法（尤其是無鎖算法）需要我們自己實現某一種特定的內存操作的語義以保證算法的正確性。這時我們就需要顯式的使用一些指令來控制內存操作指令的順序以及其可見性定義。這種指令稱為內存柵障（內存柵欄）。

 

我們剛才提到了。內存一致性模型需要在各種的程序與系統的各個層次上定義內存訪問的行為。在機器碼與的層次上，其定義將影響硬件的設計者以及機器碼開發人員；而在高級語言層次上，其定義將影響高級語言開發人員以及編譯器開發人員和硬件設計人員。即，內存操作的亂序在各個層次都是存在的。這里，所謂的程序的執行順序有三種：

 

（1）程序順序：指在特定CPU上運行的，執行內存操作的代碼的順序。這指的是編譯好的程序二進制鏡像中的指令的順序。編譯器并不一定嚴格按照程序的順序進行二進制代碼的編排。編譯器可以按照既定的規則，在執行代碼優化的時候打亂指令的執行順序，也就是上面說的程序順序。并且，編譯器可以根據程序的特定行為進行性能優化，這種優化可能改變算法的形式與算法的執行復雜度。（例如將switch轉化為表驅動序列）
（2）執行順序：指在CPU上執行的獨立的內存相關的代碼執行的順序。執行順序和程序順序可能不同，這種不同是編譯器和CPU優化造成的結果。CPU在執行期（Runtime）根據自己的內存模型（跟編譯器無關）打亂已經編譯好了的指令的順序，以達到程序的優化和最大限度的資源利用。

（3）感知順序：指特定的CPU感知到他自身的或者其他CPU對內存進行操作的順序。感知順序和執行順序可能還不一樣。這是由于緩存優化或者內存優化系統造成的。

（參見：Memory Ordering in Modern Microprocessors）

而最終的共享內存模型的表現形式是由這三種“順序”共同決定的。即從源代碼到最終執行進行了至少三個層次上的代碼順序調整，分別是由編譯器和CPU完成的。我們上面提到，這種代碼執行順序的改變雖然在單線程程序中不會引發副作用，但是在多線程程序中，這種作用是不能夠被忽略的，甚至可能造成完全錯誤的結果。因此，在多線程程序中，我們有時需要人為的限制內存執行的順序。而這種限制是通過不同層次的內存柵障完成的。

注：在以前我們沒有提到不同層次的內存柵障而實際上，如果您在使用Visual Studio 2005/2008，您就會發現API中出現了_ReadBarrier, _WriteBarrier, _ReadWriteBarrier等等，看看MSDN得知這是內存柵障，可是這是什么層次上的內存柵障呢？

 

嚴格意義上來講，內存柵障僅僅應用于硬件層次而并非軟件。即，內存柵障并不是對于編譯器而言的。但是由于編譯器更改代碼順序的現象確實存在，因此又引入了編譯器內存柵障的概念。以下給出其定義：

• 編譯器內存柵障指，編譯器保證在內存柵障兩側的代碼不會跨越內存柵障，但是不能夠阻止CPU改變代碼的執行順序。
• 內存柵障指，一系列強制促使CPU按照一定順序，在其兩側按照一致性規則執行內存指令的指令。

 以Visual C++ 8.0/9.0編譯器為例。編譯器規則中規定，Visual C++編譯器有權利對聲明為volatile的變量的操作調整其順序以達到優化的效果，因此，在Platform SDK中引入了編譯器內存柵障——_ReadBarrier()，_WriteBarrier()，_ReadWriteBarrier()。恰當的使用這些函數可以確保在多線程模式下，代碼的執行順序不會因為編譯器優化的原因而更改。否則，優化之后的程序行為可能會被改變。可見，這種優化僅僅是對于編譯器一級而言的。而并不保證執行過程。

 

所以，在"Loads are not reorderd with other loads" is a FACT!! 再續：.NET MM IS BROKEN ，才有了這樣的代碼：

 

 

為什么在InterlockedExchange中還需要load_with_acquire呢？原文中的注釋欠考慮了，實際上是因為阻止編譯器對 voltaile進行優化的原因。而如果編譯器保證volatile不會進行順序調整，例如Intel編譯器也就不用再來一次load_with_acquire了。讀者可能要問了，那么如果_ReadWriteBarrier僅僅是編譯器一級的，那么執行順序不就變化了嗎？厄，單純對于這個load是不會的，因為這個代碼是IA-32下的，CPU已經保證了load的語義，只要編譯器不擅自改變就OK了。

 

而真正的內存柵障是硬件一級的。是采用了CPU提供的某些特定的指令。例如，在Microsoft Platform SDK中，MemoryBarrier宏即該類型的內存柵障。其定義如下（在x86，x64，IA64平臺下）：

 

 

通過以上說明可見，如果希望得到正確的內存操作順序，就需要在程序中恰當的使用軟件的或者真正的內存柵障。內存柵障使用過度，會造成程序性能比較嚴重的下降（因為CPU的內存操作順序優化和Cache優化不能發揮作用）；而使用不當則會造成非常隱蔽而難以調試的錯誤。

 

[END:內存柵障]

 

三、Cache的一致性

 

在“之一”中，有一句話：“CPU 1操作了內存單元1進而操作了內存單元2，但是另一個CPU先看到了內存單元2的改變而后又看到了內存單元1的改變”需要指出的是：這個在大多數處理器中都是不存在的，大多數處理器保證了這種順序的可見性與操作順序是一致的。（對于Intel處理器，參見：Intel 64 and IA-32 Architectures Software Developer's Manual，Volume 3A: System Programming Guide，10.4）

 

在大多數有關多線程的文章中，都會提到由于內存的優化，以至于可見性...需要澄清的是，這種可見性的差異在大多數情況下都不是Cache造成的。應該說是Memory Optimization造成的還不錯。因為正因為為了避免Cache的不一致，才有了Cache一致性協議的研究。才有了Intel關于我的Cache采用了四種狀態云云，實際上就是所謂的采用了總線監聽協議。

 

我們在"Loads are not reorderd with other loads" is a FACT!! 系列文章中，通過了一個例子說明.NET MM是有問題的，但是如果Cache都沒問題，那么到底是什么造成的這個問題呢？答案是，Store Buffer！！我們先來看看Cache的工作：

 

如果CPU發現系統內存的操作數是可以被緩存的（并非所有的內存單元都是可以被緩存的），CPU便將一個Cache Line全部讀到恰當的緩存中L1，L2或者L3（如果有的話）。該操作稱為Cache Line Fill。如果CPU發現需要的操作數已經存在在Cache中，則CPU直接從緩存中而不是內存中讀取操作數，這種情況稱之為Cache Hit。

當CPU試圖向可緩存的系統內存寫入操作數時，其首先檢查Cache中是否已經緩存了該操作數。如果一個有效地（Valid）Cache Line的確存在在緩存中，CPU（根據當前寫操作數的策略）可以將操作數寫入Cache中而不是系統內存中。這種操作稱之為Write Hit。反之，如果緩存中并不包含該操作數的地址，則CPU執行一次Cache Line Fill操作，并將操作數寫入緩存，同時（根據當前寫操作數的策略）可以將操作數寫回系統內存。如果真的要將操作數寫回內存，則其首先寫回存儲緩沖區（Store Buffer），然后等待總線空閑，并從存儲緩沖區（Store Buffer）回寫到內存中。（參見：Intel 64 and IA-32 Architectures Software Developer's Manual，Volume 3A: System Programming Guide，10.2）

 

好了，現在我們知道Store Buffer是什么東西了。如果沒有Store Buffer那么我們必須等待總線空閑再將操作數寫回內存，但是現在，即使總線不是空閑的Cache回寫的操作也能立即返回！但是，當一個Store臨時的處于Store Buffer時，他滿足了自身處理器的Load操作但是不能滿足其他處理器的Load操作。也就是，此時如果其他CPU需要Load這個地址，則他不能看到新的值！這不是因為Cache不一致造成的，但是現象好像是Cache不一致造成的！（參見：Intel 64 Architecture Memory Ordering White Paper，2.4）

 

因此，我們說，如果要修正這個錯誤就要Flush Store Buffer，而不是Flush Cache！而如何Flush Store Buffer呢？列舉如下：

 

當一個CPU異常或者中斷產生的時候；
當一個順序執行指令執行的時候；
當一個I/O指令執行的時候；
當一個LOCK操作執行的時候；
當一個BINIT操作執行的時候；
當使用LFENCE限制操作的調整的時候；
當使用MFENCE限制操作調整的時候；

（參見：Intel 64 and IA-32 Architectures Software Developer's Manual，Volume 3A: System Programming Guide，10.10）

 

而我們知道，System.Threading.Thread.MemoryBarrer()實際上就是一個xchg（對于IA-32），屬于一個LOCK操作，因此具有Flush Store Buffer的功能！因此我們說System.Threading.Thread.MemoryBarrer()可以修正這個錯誤，但是原因并不是Cache，而是Store Buffer!

 

至此，對于上述文章的說明與修正可以到一個段落了。與大家共同學習:-)