CPU同步機制漫談

張銀奎 [email protected]

更快是計算機世界的一個永恒主題。要做到更快有兩個方向：一是提高串行執行的速度，二是并行計算（Parallel Computing）。并行計算又可分為同一CPU内部多個流水線間的并行、同一個系統内多個CPU間的并行、和同一個網絡中多個計算機系統間的并行。

當并行運作的多個任務彼此無關，互不依賴時，整個系統的性能是最高的。但在現實的并行計算中，這是不可能的。至少同一組内的多個任務之間是存在依賴關系的，它們需要交流資訊，報告彼此的計算結果；調整進度，確定各個任務都有條不紊的進行；協調資源，確定共享資料的一緻性和安全性和最終結果的正确性。這樣便産生了并行計算中的一個基本問題，那就是同步（Synchronization）。并行計算的特征決定了同步是它的一個必然問題。

為了易于了解，我們看一個從銀行賬戶中存款和提款的簡單例子，清單1給出的是賬戶類CAccount的Withdraw和Deposit方法的C++代碼。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

BOOL CAccount::Withdraw(double dblNumber) {          BOOL bRet=TRUE;          if(GetBalance()>=dblNumber)          {                    // Send out money now, we use sleep to simulate                    Sleep(rand());                    m_dblBalance-=dblNumber;          }          else          {                    bRet = FALSE;          }          Log(TASK_WITHDRAW,dblNumber,bRet);          return bRet; } void CAccount::Deposit(double dblNumber) {          m_dblBalance+=dblNumber;          Log(TASK_DEPOSIT,dblNumber,TRUE); }

以上方法很容易了解，參數dblNumber是要支出或存入的金額，第4行檢查帳戶餘額是否足夠本次提取，第7行執行支付操作，我們調用Sleep函數延遲一段時間來模拟這個操作，第8行修改賬戶餘額。

圖1是使用以上類的TaskSync程式的界面和一次執行記錄。點選Deposit和Withdraw按鈕會觸發建立新的線程來調用CAccount類的Deposit和Withdraw 方法。編輯框中的數字既是存入和支出的金額，又是要建立的線程數，因為我們讓每個線程都固定的存入或取出1元錢。

在編輯框中各輸入10後，随機的反複點選Deposit和Withdraw按鈕，持續一段時間後，我們會發現餘額變成了負數。

圖1 TaskSync程式

觀察清單1中的代碼，隻有在確定餘額不小于參數dblNumber時（第4行）才會執行取款動作，然後遞減餘額（m_dblBalance）。也就是說這個賬戶是不應該出現負數餘額的（不可透支）。那麼，是什麼原因導緻餘額變為負數呢？以下是幾種猜想：

1.          在某個（些）線程執行取款動作的過程中（第7行），其它線程又修改了餘額值。盡管第4行作判斷時賬戶中還有足夠的餘額，但是在執行遞減操作時，其它線程（提款機）可能已經把餘額遞減為0了，于是再次遞減便出現了負數。

2.          在某個（些）線程更新m_dblBalance變量時，也就是執行遞減操作（第8行）時，其它線程又修改了它的值。清單2列出了m_dblBalance-=dblNumber語句所對應的彙編代碼。可見盡管C++是一條語句，但是編譯出的彙編語句還是有很多條的。第1行（清單2）是将this指針存入EAX寄存器，第2行是将m_dblBalance（this+8）從記憶體加載到FPU（符點處理單元）寄存器棧中，第3行是執行減法運算，ebp+8指向的是參數dblNumber，第4行是将this指針存入ECX寄存器，第5行是将計算結果存回記憶體中的m_dblBalance成員變量。因為第3行的減法計算是對加載在CPU寄存器中的值做減法，第5行再将這個值存回記憶體，那麼如果在某個線程執行2、3條指令的間隙，其它線程修改了m_dblBalance，那麼這個線程使用的仍然是舊的資料，而且第5行會将錯誤的結果寫入到記憶體中。

3.          在32位x86系統中，m_dblBalance變量在記憶體中的長度是8個位元組（QWORD）。這意味着存取這個變量時需要讀寫8個位元組。如果，兩個線程恰好都要讀寫這8個位元組，那麼有可能某個線程讀到的内容是另一個線程寫了一半的資料，或者某個線程寫了8個位元組的前半部分，另一個線程寫了後半部分。

清單2 m_dblBalance-=dblNumber語句所對應的彙編代碼

1 2 3 4 5

004013B5   mov         eax,dword ptr [ebp-4] 004013B8   fld         qword ptr [eax+8] 004013BB   fsub        qword ptr [ebp+8] 004013BE   mov         ecx,dword ptr [ebp-4] 004013C1   fstp        qword ptr [ecx+8]

可以說，以上三種猜想都是合理的。猜想1的可能性最大，因為判斷條件和遞減操作之間的時間較大，在此期間，餘額值被其它線程修改的機率很高。猜想2也是可能的，因為在Windows這樣的搶先式（preemptive）多任務作業系統中，作業系統可能在某個線程執行完清單2中的第2條指令後将其挂起，然後去執行其它線程。這意味着，因為線程切換，即使系統中隻有一個普通的CPU（非Hyper Threading等），那麼猜想1和猜想2所描述的情況仍然可能發生。

下面看一下猜想3，對于單CPU系統，因為CPU總是在指令邊界（instruction boundary）來确認中斷和進行線程切換，而且存取m_dblBalance變量都是使用一個指令來完成的，是以這種情況是不會發生的，也就是說CPU不會在一條指令還沒執行完時将某個線程挂起。對于多CPU系統，是可能發生的（見下文），因為多個CPU可能并行執行清單2中的遞減操作，也就是所謂的并發（concurrency）情況。

事實上，以上三種情況也是并行計算中經常遇到的三個典型問題。為了解決這些問題，作業系統通常會提供各種同步機制，供自身和應用軟體使用。比如Windows作業系統提供了很多種用于線程同步的核心對象，以滿足不同的需要，比如關鍵區（critical section），事件對象（event），互斥對象（semaphore）和spinlock等等。此外，作為計算機系統執行核心的CPU也内建了很多 同步支援。下面以IA32 CPU為例略作介紹。

首先我們介紹一下CPU一級的原子操作（atomic operations）。所謂原子操作，就是CPU會保證整個操作被完整執行，不會被打斷成幾個部分多次執行。例如，IA32 CPU會保證以下操作（列出的不是全部）都是原子的：

n         讀寫一個位元組。

n         讀寫與16位位址邊界對齊的字（WORD）。

n         讀寫與32位位址邊界對齊的雙字（DWORD）。

n         讀寫與64位位址邊界對齊的四字（QWORD）（從奔騰開始）。

歸納一下，讀寫一個位元組永遠是安全的，讀寫按其長度做記憶體對齊的資料通常也是安全的。讀寫記憶體對齊的資料也有利于提高效率，這也是編譯器在編譯時會自動做記憶體對齊的原因。回到我們剛才讨論的猜想3，m_dblBalance是8位元組長的，從調試器中可以看到它的位址是0x12fed0，這個位址可以被8整除，符合64位（二進制）對齊标準。是以如果是在奔騰及其之後的CPU上執行，那麼讀寫m_dblBalance是安全的（不必擔心不完全的讀寫）。如果在CAccount類的定義前加上pack(1)編譯指令（compiler directive），并在m_dblBalance成員前加上一個一位元組的字元變量，那麼m_dblBalance的位址變成了0x12fecd，不再64位對齊了。

#pragma pack(1)

class CAccount 

{

protected:

char n;

double m_dblBalance;

…

對于沒有對齊的16位，32位和64位資料，CPU是否能以原子方式讀寫就要視情況而定了，如果它們是位于同一個cache line中的，那麼P6系列及其後的IA32 CPU仍會保證原子讀寫。如果是分散在多個cache line中的，那麼奔騰4和至強（Xeon）CPU仍有可能支援其原子讀寫，但是通路這樣的未對齊資料會影響系統的性能。

下面我們再來看一下總線鎖定。為了保證某些關鍵的記憶體操作不被打斷，IA32 CPU設計了所謂的總線鎖定機制。當位于前端總線上的某個CPU需要執行關鍵操作時，它可以設定（assert） 它的#LOCK信号（管腳）。當一個CPU輸出了#LOCK信号，其它CPU的總線使用請求便會暫時堵塞，直到發出#LOCK信号的CPU完成操作并撤銷#LOCK信号。例如，CPU在執行以下操作時，會使用總線鎖定機制：

n         設定TSS（任務狀态段）的Busy标志。設定Busy标志，是任務切換的一個關鍵步驟，使用鎖定機制可以防止多個CPU都切換到某個任務。

n         更新段描述符。

n         更新頁目錄和頁表表項。

n         确認（acknowledge）中斷。

除了以上預設的操作外，軟體也可以通過在指令前增加LOCK字首來顯式的（explicitly）強制使用總線鎖定。例如，可以在以下指令前增加LOCK字首：

n         位測試和修改指令BTS、BTR和BTC。

n         資料交換指令，如XCHG、XADD、CMPEXCHG和CMPEXCHG8B。

n         以下單操作符算術或邏輯指令：INC、DEC、NOT和NEG。

n         以下雙操作符算術或邏輯指令：ADD、ADC、SUB、SBB、AND、OR和XOR。

Windows作業系統所提供的用于同步通路共享變量的Interlocked Variable Access API就是使用LOCK方法實作的。例如，以下就是InterlockedIncrement API的彙編代碼：

kernel32!InterlockedIncrement:

7c809766 8b4c2404        mov     ecx,dword ptr [esp+4]

7c80976a b801000000      mov     eax,1

7c80976f f00fc101        lock xadd dword ptr [ecx],eax

7c809773 40              inc     eax

7c809774 c20400          ret     4

可以看到，XADD指令前被加上了LOCK字首。類似的InterlockedExchange API是使用帶有LOCK字首的cmpxchg指令。以下是kernel32.dll和ntdll.dll輸出的所有Interlocked API。

0:001> x kernel32!Interlocked*

7c80978e kernel32!InterlockedExchange = <no type information>

7c8097b6 kernel32!InterlockedExchangeAdd = <no type information>

7c80977a kernel32!InterlockedDecrement = <no type information>

7c8097a2 kernel32!InterlockedCompareExchange = <no type information>

7c809766 kernel32!InterlockedIncrement = <no type information>

0:001> x ntdll!Interlocked*

7c902f55 ntdll!InterlockedPushListSList = <no type information>

7c902f06 ntdll!InterlockedPopEntrySList = <no type information>

7c902f2f ntdll!InterlockedPushEntrySList = <no type information>

除了前面的三種猜想，還有一種可能導緻資料不同步，那就是因為處理器的亂序執行（out-of-order execution）和内部緩存（cache）而導緻的資料不一緻。為了發揮CPU内多條執行流水線（execution pipeline）的效率，CPU可能把一段代碼分成幾段同時放到幾個流水線中執行；另外，為了減少存取記憶體的次數，少占用前端總線，處理器會對某些寫操作進行緩存。比如，一個函數先向位址A寫入1，而後又寫為2，…….，那麼CPU可以延遲中間步驟中的各次寫操作，隻需要把最終的結果更新到記憶體，這就是所謂的寫合并（Write Combining）。但如果系統中有多個處理器，那麼另一個處理器就有可能使用過時的資料。為了解決諸如此類的問題，IA32 CPU配備了SFENSE 、LFENCE和MFENCE三條指令，分别代表Store Fence（寫屏障）、Load Fence（讀屏障）和Memory Fence。SFENCE用來保證該指令之前（程式順序）的寫操作一定早于它之後的所有寫操作而落實完成（complete）、公之于衆（通知其它處理器和寫入記憶體）。換句話來說，SFENCE指令之前的寫操作是不可能穿越SFENCE而早于其後的寫操作而完成的。類似的，LFENCE是用來強制讀操作的順序的，MFENCE可以同時強制讀寫操作的順序。因為這三條指令的作用都是為了顯式定義記憶體存取順序，是以它們又被稱為記憶體定序（memory ordering）指令。

因為SFENCE指令是Pentium III CPU引入的，而LFENCE和MFENCE是奔騰4和至強引入的，是以這幾條指令在Windows XP或之前的系統中還較少使用。

DDK for Windows Server 2003定義了KeMemoryBarrier API，在3790版本DDK的ntddk.h中可以看到其x86實作如下：

FORCEINLINE VOID KeMemoryBarrier ( VOID )

{

    LONG Barrier;

    __asm {  xchg Barrier, eax  }

}

可見使用的是自動鎖定的XCHG指令。而在支援Vista的5744及更高版本的DDK中，其定義為：

FORCEINLINE VOID KeMemoryBarrier ( VOID )

{

    FastFence();

    LFENCE_ACQUIRE();

    return;

}

其中FastFence被定義為編譯器的intrinsics（内建函數）：

#define FastFence __faststorefence

所謂intrinsics，就是定義在編譯器内部的函數片斷，很類似于擴充關鍵字，當編譯器看到程式調用這些函數時，會自動産生合适的代碼，也有些intrinsics隻是以函數調用的形式向編譯器傳送資訊，并不産生代碼，如KeMemoryBarrierWithoutFence便是告訴編譯器調整記憶體操作順序時不能跨越這個位置。類似的定義還有：

#define LoadFence _mm_lfence

#define MemoryFence _mm_mfence

#define StoreFence _mm_sfence

在最新的Vista SDK（SDK 6.0）的頭檔案中也包含以上定義，隻不過使用者态的API名字叫MemoryBarrier()。可見最新的Windows DDK和SDK都已經提供了充分的記憶體定序支援。

本文結合一個簡單的例子讨論了多任務系統中的同步問題，重點介紹了原子操作，總線鎖定和記憶體定序這三種實作同步的重要機制。更多内容請閱讀參考文獻中所列出的資源。

參考文獻：

1, IA-32 Intel (C) Architecture Developer’s Manual Volume 2& 3 Intel Corporation

2, Compiler Intrinsics MSDN

3, Multiprocessor Considerations for Kernel-Mode Drivers Microsoft Corporation

4, Memory Barriers Wrap-up Steve Dispensa