全面分析作業系統中同步原語

這篇文章帶給大家的內容是關於全面分析作業系統中同步原語，有一定的參考價值，有需要的朋友可以參考一下，希望對你有幫助。

競態條件

在一般的作業系統中，不同的進程可能會分享一塊公共的儲存區域，例如記憶體或硬碟上的文件，這些行程都允許在這些區域上進行讀寫。
作業系統有一些職責，來協調這些使用公共區域的進程之間以正確的方式進行想要的操作。這些進程之間需要通信，需要互相溝通，有商有量，才能確保一個進程的動作不會影響到另一個進程正常的動作，進而導致進程運行後得不到期望的結果。在作業系統概念中，通常用 IPC（Inter Process Communication，即進程間通訊）這個名詞來代表多個進程之間的通訊。
為了解釋什麼是競態條件（race condition），我們引入一個簡單的例子來說明：
一個檔案中保存了一個數字n，進程A 和進程B 都想要去讀取這個檔案的數字，並把這個數字加1 後，又存回檔案。假設 n 的初始值是 0，在我們理想的情況下，進程 A 和進程 B 運行後，檔案中 n 的值應該是 2，但實際上可能會發生 n 的值為 1。我們可以考慮一下，每個行程做這件事時，需要經過什麼步驟：

1. 讀取檔案裡n 的值

2. 令n = n 1

3. 把新的n 值存回檔案。

在進一步解釋競態條件之前，必須先回顧作業系統概念中的幾個知識點：

1. 進程是可以並發運行的，即使只有一個CPU 的時候）

2. 作業系統的時鐘中斷會引起進程運行的重新調度，

3. 除了時鐘中斷，來自其它設備的中斷也會引起進程運行的重新調度

假設進程A 在運行完步驟1 和2，但還沒開始運行步驟3 時，發生了一個時鐘中斷，這時候作業系統通過調度，讓進程B 開始運行，進程B 運行步驟1 時，發現n 的值為0，於是它運行步驟2 和3，最終會把n = 1 儲存到檔案中。之後進程 A 繼續運行時，由於它不知道在它運行步驟 3 之前，進程 B 已經修改了檔案裡的值，所以進程 A 也會把 n = 1 寫回檔案中。這就是問題所在，進程 A 在運作的過程中，會有別的行程去操作它所操作的資料。

唯一能讓 n = 2 的方法，只能期望進程 A 和進程 B 依序分別完整地運行完所有步驟。
我們可以為競態條件下一個定義了

兩個或多個行程讀寫某些共享數據，而最後的結果取決於進程運行的準確時序，稱為競態條件。

在上述的文字中，我們使用行程作為物件來討論競態條件，實際上對於執行緒也同樣適用，這裡的執行緒包含但不限於核心執行緒、使用者執行緒。因為在作業系統中，進程其實是靠執行緒來運行程式的。更甚至，在 Java 語言的執行緒安全性中，競態條件這個概念也同樣適用。 （參考《Java 並發程式設計實戰》第二章）

互斥與臨界區

如何避免race condition，我們需要以某種手段，確保當一個行程在使用一個共享變量或文件時，其它的進程不能做同樣的操作，換言之，我們需要「互斥」。
以上述例子作為例子，我們可以把步驟1 - 3 這段程序片段定義為臨界區，臨界區意味著這個區域是敏感的，因為一旦進程運行到這個區域，那麼意味著會對公共數據區域或檔案進行操作，也意味著有可能有其它進程也正運行到了臨界區。如果能夠採用適當的方式，使得這兩個流程不會同時處於臨界區，那麼就能避免競態條件。
也就是，我們需要想想怎麼樣做到「互斥」。

互斥的方案

互斥的本質就是阻止多個行程同時進入臨界區

屏蔽中斷

先前提到的範例中，流程 B 之所以能夠進入臨界區，是因為進程 A 在臨界區中受到了中斷。如果我們讓進程A 在進入臨界區後，立即對所有中斷進行屏蔽，離開臨界區後，才回應中斷，那麼即使發生中斷，那麼CPU 也不會切換到其它進程，因此此時進程A 可以放心地修改文件內容，不用擔心其它的進程會幹擾它的工作。
然而，這個設想是美好，事實上它並不可行。第一個，如果有多個CPU，那麼進程A 無法對其它CPU 屏蔽中斷，它只能屏蔽正在調度它的CPU，因此由其它CPU 調度的進程，依然可以進入臨界區；第二，關於權力的問題，是否可以把屏蔽中斷的權力交給使用者流程？如果這個行程屏蔽中斷後再也不回應中斷了， 那麼一個行程就有可能掛住整個作業系統。

鎖定變數

也許可以透過設定一個鎖定標誌位，將其初始值設為0 ，當一個行程想進入臨界區時，先檢查鎖定的值是否為0，如果為0，則設為1，然後進入臨界區，退出臨界區後把鎖的值改為0；若檢查時鎖的值已經為1，那麼代表其他進程已經在臨界區中了，於是進程進行循環等待，並持續偵測鎖的值，直到它變成0。
但這種方式也存在著競態條件，原因是，當一個進程讀出鎖的值為0時，在它將其值設為1之前，另一個進程被調度起來，它也讀到鎖的值為0，這樣就出現了兩個行程同時都在臨界區的情況。

嚴格輪換法

鎖定變數之所以出問題，其實是因為將鎖定變數由0改為1這個動作，是由想要取得鎖的進程去執行的。如果我們把這個動作改為由已經獲得鎖的進程去執行，那就不存在競態條件了。
先設定一個變數turn，代表目前允許誰取得鎖，假設有兩個行程，行程A 的邏輯如下所示：

        while (turn != 0){// 如果还没轮到自己获取锁，则进入循环等待
        }
        do_critical_region();// 执行临界区的程序
        turn = 1;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
        do_non_critical_region();// 执行非临界区的程序

行程B 的邏輯如下所示：

        while (turn != 1) {// 如果还没轮到自己获取锁，则进入循环等待
        }
        do_critical_region();// 执行临界区的程序
        turn = 0;// 由获得锁的一方将锁变量修改为其它值，允许其它进程获得锁
        do_non_critical_region();// 执行非临界区的程序

但這裡需要考慮到一個事情，假設進程A 的do_non_critical_region() 需要執行很長時間，即進程A 的非臨界區的邏輯需要執行較長時間，而進程B 的非臨界區的邏輯很快就執行完，顯然，進程A 進入臨界區的頻率會比進程B 小一點，理想的情況下，進程B 應該多進入臨界區幾次。但由於進程B 在執行非臨界區邏輯前會把turn 設為0，等它很快地把非臨界區的邏輯執行完後，回來檢查turn 的值時，發現turn 的值一直都不是1，turn的值需要進程A 把它設為1，而進程A 此時卻正在進行著漫長的非臨界區邏輯程式碼，所以導致進程B 無法進入臨界區。
這就說明，在一個行程比另一個行程慢很多的情況下，嚴格輪換法並不是一個好辦法。

Peterson 演算法

嚴格輪換法的問題就出在嚴格兩個字上，即多個進程之間是輪流進入臨界區的，根本原因是想要獲得鎖的進程需要依賴其它程序對於鎖變數的修改，而其它程序都要先經過非臨界區邏輯的執行才會去修改鎖變數。
嚴格輪換法中的turn 變數不僅用來表示當前該輪到誰獲取鎖，而且它的值未改變之前，都意味著它依然阻止了其它進程進入臨界區，恰恰好，一個進程總是要經過非臨界區的邏輯後才會去改變turn的值。
因此，我們可以用兩個變數來表示，一個變數表示當前應該輪到誰獲得鎖，另一個變數表示當前進程已經離開了臨界區，這種方法實際上叫做Peterson 演算法，是由荷蘭數學家T.Dekker 提出來的。

    static final int N = 2;
    int turn = 0;
    boolean[] interested = new boolean[N];

    void enter_region(int process) {
        int other = 1 - process;
        interested[process] = true;
        turn = process;
        while(turn == process && !interested[other]) {
        }
    }

    void exit_region(int process) {
        interested[process] = false;
    }

進程在需要進入臨界區時，先呼叫 enter_region，離開臨界區後，呼叫 exit_region。 Peterson 演算法使得進程在離開臨界區後，立刻消除了自己對臨界區的“興趣”，因此其它進程完全可以根據 turn 的值，來判斷自己是否可以合法進入臨界區。

TSL 指令

回顧我們之前提到的「鎖定變數」這種方法，它的一個致命的缺點是對狀態變數進行改變的時候，如從0 改為1 或從1改為0 時，是可以被中斷打斷的，因此存在競態條件。
之後我們在鎖變數的基礎上，提出如果鎖變數的修改不是由想要取得進入臨界區的程序來修改，而是由已經進入臨界區後想要離開臨界區的程序來修改，就可以避免競態條件，進而引發嚴格輪換法，以及從嚴格輪換法基礎改進的Peterson 演算法。這些方法都是從軟體的方式去考慮的。實際上，可以在硬體 CPU 的支援下，保證鎖變數的改變不被打斷，使鎖變數成為一種很好的解決進程互斥的方法。
目前大多數的電腦的CPU，都支援TSL 指令，其全稱為Test and Set Lock，它將一個記憶體的變數（字）讀取暫存器RX 中，然後再在該記憶體位址上存一個非零值，讀取操作和寫入操作從硬體層面保證是不可打斷的，也就是說是原子性的。它採用的方式是在執行 TSL 指令時鎖住記憶體匯流排，禁止其它 CPU 在 TSL 指令結束之前存取記憶體。這也是我們常說的 CAS （Compare And Set)。
當需要把鎖定變數從0 改為1 時，先把記憶體的值複製到暫存器，並將記憶體的值設為1，然後檢查暫存器的值是否為0，則操作成功，如果非0 ，則重複偵測，知道暫存器的值變成0，如果暫存器的值變成0 ，表示另一個程序離開了臨界區。當進程離開臨界區時，需要把記憶體中該變數的值設為 0。

忙著等待

上述提到的Peterson 演算法，以及TSL 方法，實際上它們都有一個特點，那就是在等待進入臨界區的時候，它們採用的是忙碌等待的方式，我們也常常稱之為自旋。它的缺點是浪費 CPU 的時間片，並且會導致優先反轉的問題。

考慮一台電腦有兩個進程， H 優先權較高，L 優先權較低。調度規則規定，只要 H 處於就緒狀態，就可以運作。在某一時刻，L 處於臨界區內，此時 H 處於就緒態，準備運作。但 H 需要進行忙等待，而 L 由於優先順序低，沒法得到調度，因此也無法離開臨界區，所以 H 將會永遠忙等待，而 L 總無法離開臨界區。這種情況稱之為優先權反轉問題（priority inversion problem）

處理進程的阻塞與喚醒

作業系統提供了一些原語，sleep 和wakeup 。

核心提供給核外呼叫的過程或函數成為原語（primitive），原語在執行過程中不允許中斷。

sleep 是一個將調用進程阻塞的系統調用，直到另外一個進程調用 wakeup 方法，將被阻塞的進程作為參數，將其喚醒。阻塞與忙等待最大的差別在於，進程被阻塞後CPU將不會分配時間片給它，而忙等待則是一直在空轉，消耗 CPU 的時間片。

信號量

首先需要明白的一點是，信號量的出現是為了解決什麼問題，由於一個進程的阻塞和喚醒是在不同的進程中造成的，比如說進程A 呼叫了sleep() 會進入阻塞，而進程B 呼叫wakeup（A）會把進程A 喚醒。因為是在不同的進程中進行的，所以也存在著被中斷的問題。加入進程A 根據邏輯，需要呼叫sleep() 進入阻塞狀態，然而，就在它呼叫sleep 方法之前，由於時鐘中斷，進程B 開始運行了，根據邏輯，它調用了wakeup() 方法喚醒進程A，可是由於進程A 還未進入阻塞狀態，因此這個wakeup 訊號就遺失了，等待進程A 從之前中斷的位置開始繼續運行時並進入阻塞後，可能再也沒有進程去喚醒它了。
因此，進程的阻塞和喚醒，應該需要額外引進一個變數來記錄，這個變數記錄了喚醒的次數，每次被喚醒，變數的值加1。有了這個變量，即使wakeup操作先於sleep操作，但wakeup操作會被記錄到變量中，當進程進行sleep時，因為已經有其它進程喚醒過了，此時認為這個進程不需要進入阻塞狀態。
這個變量，在作業系統概念中，則被稱為信號量（semaphore），由 Dijkstra 在 1965 年提出的一種方法。
對信號量有兩種操作， down 和 up。
down 操作其實對應sleep，它會先偵測信號量的值是否大於0，若大於0，則減1，進程此時無須阻塞，相當於消耗掉了一次wakeup；若信號量為0 ，進程則會進入阻塞狀態。
而up 操作對應著wakeup，進行up 操作後，如果發現有進程阻塞在這個信號量上，那麼系統會選擇其中一個進程將其喚醒，此時信號量的值不需要變化，但被阻塞的進程已經少了一個；如果up 操作時沒有進程阻塞在信號量上，那麼它會將信號量的值加1。
有些地方會把 down 和 up 運算稱為 PV 運算，這是因為在 Dijkstra 的論文中，使用的是 P 和 V 分別來代表 down 和 up。
信號量的 down 和 up 操作，是作業系統支援的原語，它們是具有原子性的操作，不會出現被中斷的情況。

互斥量

互斥量（mutex）其實是信號量的一種特例，它的值只有0 和1，當我們不需要用到信號量的計數能力時，我們可以使用互斥量，實際上也意味著臨界區值同一時間只允許一個進程進入，而信號量是允許多個進程同時進入臨界區的。

以上是全面分析作業系統中同步原語的詳細內容。更多資訊請關注PHP中文網其他相關文章！