競争條件，臨界區，忙等待的互斥

一、競争條件和臨界區

在同一個應用程式中運作多個線程本身并不會引起問題。當多個線程通路相同的資源時才會出現問題。比如多個線程通路同一塊記憶體區域（變量、數組、或對象）、系統（資料庫、 web 服務等）或檔案。事實上，隻有一個或多個線程改寫這些資源時才會出現問題。多個線程隻讀取而不會改變這些相同的資源時是安全的。

兩個線程通路同一個資源而且與線程通路資源時的順序有關的這樣一種情形就叫競争條件。 導緻競争條件發生的代碼片段就叫臨界區。在臨界區中可以通過恰當的線程同步來消除競争條件。

當兩個線程競争同一資源時，如果對資源的通路順序敏感，就稱存在競争條件。導緻競争條件發生的代碼稱作臨界區。

對共享記憶體進行通路的程式片段稱作臨界區。

對于一個好的實作互斥的解決方案，需要滿足以下4個條件：

1) 任何兩個程序不能同時處于其臨界區。

2) 不應對CPU的速度和數量做任何假設。

3) 臨界區外運作的程序不得阻塞其他程序。

4) 不得使程序無限期等待進入臨界區。

二、忙等待的互斥

競争條件：兩個或多個程序讀取某些共享資料，最後的結果取決于程序運作的精确時序，成為競争條件。

互斥：當一個程序在使用一個共享變量或檔案時，其他程序不能做同樣的操作。

臨界區：對共享記憶體進行通路的程式片段成為臨界區。

實作互斥，避免競争條件的方法：

1 屏蔽中斷

在單處理器系統中，最簡單的方法是使每個程序在剛剛進入臨界區後立即屏蔽所有中斷，并在就要離開之前再打開中斷。屏蔽中斷後，時鐘中斷也被屏蔽。CPU隻有發生時鐘中斷或其他中斷時才會進行程序切換，這樣，在屏蔽中斷之後CPU将不會被切換到其他程序。于是，一旦某個程序屏蔽中斷之後，它就可以檢查和修改共享記憶體，而不必擔心其他程序介入。

這個方案并不好，因為把屏蔽中斷的權力交給使用者程序是不明智的。設想一下，若一個程序屏蔽中斷後不再打開中斷，其結果将會如何？整個系統可能會是以終止。而且，如果系統是多處理器（有兩個或可能更多的處理器），則屏蔽中斷僅僅對執行disable指令的那個CPU有效。其他CPU仍将繼續運作，并可以通路共享記憶體。

另一方面，對核心來說，當它在更新變量或清單的幾條指令期間将中斷屏蔽是很友善的。當就緒程序隊列之類的資料狀态不一緻時發生中斷，則将導緻競争條件。是以結論是：屏蔽中斷對于作業系統本身而言是一項很有用的技術，但對于使用者程序則不是一種合适的通用互斥機制。

2 鎖變量

設想有一個共享（鎖）變量，其初始值為0。當一個程序想進入其臨界區時，它首先測試這把鎖。如果該鎖的值為0，則該程序将其設定為1并進入臨界區。若這把鎖的值已經為1，則該程序将等待直到其值變為0。于是，0就表示臨界區内沒有程序，1表示已經有某個程序進入臨界區。

但是仍存在問題，當程序a把鎖變量設為1之前恰好又有程序b進入臨界區，臨界區将有2個程序。（假設一個程序讀出鎖變量的值并發現它為0，而恰好在它将其值設定為1之前，另一個程序被排程運作，将該鎖變量設定為1。當第一個程序再次能運作時，它同樣也将該鎖設定為1，則此時同時有兩個程序進入臨界區中）

可能讀者會想，先讀出鎖變量，緊接着在改變其值之前再檢查一遍它的值，這樣便可以解決問題。但這實際上無濟于事，如果第二個程序恰好在第一個程序完成第二次檢查之後修改了鎖變量的值，則同樣還會發生競争條件。

3 嚴格輪換法 

忙等待：連續測試一個變量直到某個值出現為止，稱為忙等待。

自旋鎖：用于忙等待的鎖成為自旋鎖。

原理：

整型變量turn，初始值為0，用于記錄輪到哪個程序進入臨界區，并檢查或更新共享記憶體。開始時，程序0檢查turn，發現其值為0，于是進入臨界區。程序1也發現其值為0，是以在一個等待循環中不停地測試turn，看其值何時變為1（忙等待）。由于這種方式浪費CPU時間，是以通常應該避免。

while(true){//程序0
    while(turn!=0);  //循環
    critical_region();  
    turn=1;  
    noncritical_region();  
}  
/  
while(true){//程序1 
    while(turn!=1);  //循環
    critical_region();  
    turn=0;  
    noncritical_region();  
}  
           

 圖2-23 臨界區問題的一種解法（在兩種情況下請注意分号終止了while語句）：a) 程序0；b) 程序1

整型變量turn初始為0，程序0進入臨界區，程序1忙等待，直到程序0離開臨界區，并将turn設為1，然後程序1進入臨界區，當程序1也離開臨界區時，又把turn設為0，接着程序0再次進入臨界區，以此類推。由于這種方法需要兩者交替進行，如果程序0退出臨界區時，turn設為1，但是程序1一直在處理非臨界區的工作，程序0隻有一直忙等待，直到程序1将turn設為0。這說明，在一個程序比另一個程序慢很多的情況下，輪流進入臨界區不是好方法。隻有在有理由認為等待時間是非常短的情形下，才使用忙等待。

這種情況違反了前面叙述的條件3：程序0被一個臨界區之外的程序阻塞。再回到前面假脫機目錄的問題，如果我們現在将臨界區與讀寫假脫機目錄相聯系，則程序0有可能因為程序1在做其他事情而被禁止列印另一個檔案。

實際上，該方案要求兩個程序嚴格地輪流進入它們的臨界區，如假脫機檔案等。任何一個程序都不可能在一輪中列印兩個檔案。盡管該算法的确避免了所有的競争條件，但由于它違反了條件3，是以不能作為一個很好的備選方案。

4、peterson解法

看這個方案是如何工作的。一開始，沒有任何程序處于臨界區中，現在程序0調用enter_ region。它通過設定其數組元素和将turn置為0來辨別它希望進入臨界區。由于程序1并不想進入臨界區，是以enter_region 很快便傳回。如果程序1現在調用enter_region，程序1将在此處挂起直到 interested[0]變成FALSE，該事件隻有在程序0調用 leave_region退出臨界區時才會發生。

開始時臨界區中無程序，假設程序0想進入臨界區，程序1不想進入臨界區，則程序0調用enter_region()後直接進入臨界區，現在程序1想進入臨界區，它要在此處挂起并等到程序0調用leave_region()離開臨界區後才能進入臨界區。如果兩個程序同時想進入臨界區并調用enter_region()，都把自己的程序号存入turn，則後存入的程序号會覆寫前寫入的turn，則前進入的程序會進入臨界區。 後進入的程序忙等待直到前一個程序退出臨界區。 假設程序1是後存入的，則turn為1。當兩個程序都運作到while語句時，程序0将循環0次并進入臨界區，而程序1則将不停地循環且不能進入臨界區，直到程序0退出臨界區為止。

圖2-24   完成互斥的Peterson解法

5 TSL指令（測試并加鎖）

某些計算機中，特别是那些設計為多處理器的計算機，都有下面一條指令：

1. TSL RX, LOCK 

稱為測試并加鎖（Test and Set Lock），它将一個記憶體字lock讀到寄存器RX中，然後在該記憶體位址上存一個非零值。讀字和寫字操作保證是不可分割的，即該指令結束之前其他處理器均不允許通路該記憶體字。執行TSL指令的CPU将鎖住記憶體總線，以禁止其他CPU在本指令結束之前通路記憶體。

鎖住存儲總線不同于屏蔽中斷。屏蔽中斷，然後在讀記憶體字之後跟着寫操作并不能阻止總線上的第二個處理器在讀操作和寫操作之間通路該記憶體字。事實上，在處理器1上屏蔽中斷對處理器2根本沒有任何影響。讓處理器2遠離記憶體直到處理器1完成的惟一方法就是鎖住總線，這需要一個特殊的硬體設施（基本上，一根總線就可以確定總線由鎖住它的處理器使用，而其他的處理器不能用）。

為了使用TSL指令，要使用一個共享變量lock來協調對共享記憶體的通路。當lock 為0時，任何程序都可以使用TSL指令将其設定為1，并讀寫共享記憶體。當操作結束時，程序用一條普通的move指令将lock的值重新設定為0。

這條指令如何防止兩個程序同時進入臨界區呢？解決方案如圖2-25所示。假定（但很典型）存在如下共4條指令的彙編語言子程式。第一條指令将lock 原來的值複制到寄存器中并将lock 設定為1，随後這個原來的值與0相比較。如果它非零，則說明以前已被加鎖，則程式将回到開始并再次測試。經過或長或短的一段時間後，該值将變為0（目前處于臨界區中的程序退出臨界區時），于是過程傳回，此時已加鎖。要清除這個鎖非常簡單，程式隻需将0存入lock即可，不需要特殊的同步指令。

圖2-25   用TSL指令進入和離開臨界區

現在有一種很明确的解法了。程序在進入臨界區之前先調用enter_region，這将導緻忙等待，直到鎖空閑為止，随後它獲得該鎖并傳回。在程序從臨界區傳回時它調用 leave_region，這将把lock設定為0。與基于臨界區問題的所有解法一樣，程序必須在正确的時間調用enter_region和 leave_region，解法才能奏效。如果一個程序有欺詐行為，則互斥将會失敗。

一個可替代TSL的指令是XCHG，它原子性地交換了兩個位置的内容，例如，一個寄存器與一個存儲器字。代碼如圖2-26所示，而且就像可以看到的那樣，它本質上與TSL的解決辦法一樣。所有的Intel x86 CPU在低層同步中使用XCHG指令。

1. enter_region:  
2. MOVE REGISTER,#1    | 在寄存器中放一個1  
3. XCHG REGISTER,LOCK  | 交換寄存器與鎖變量的内容  
4. CMP REGISTER,#0 |鎖是零嗎？  
5. JNE enter_region    | 若不是零，說明鎖已被設定，是以循環  
6. RET | 傳回調用者，進入臨界區  
7. leave_region:  
8. MOVE LOCK,#0    | 在鎖中存入0  
9. RET | 傳回調用者 

圖2-26   用XCHG指令進入和離開臨界區

一個可替代TSL指令的是XCHG指令，原子性的交換兩個位置的内容。本質上和TSL解法一樣。

peterson，TSL或XCHG都是正确的，但是它們都有忙等待的缺點：

1 浪費cpu時間

2 優先級反轉問題：例如H程序優先級高，L程序優先級低 ，假設L處于臨界區中，H這時轉到就緒态想進入臨界區，H需要忙等待直到L退出臨界區，但是H就緒時L不能排程，L由于不能排程無法退出臨界區，是以H永遠等待下去。