技術文章 » 號誌及其使用和實現(超詳細)

號誌及其使用和實現(超詳細)

2020-07-16 10:04:35
互斥鎖，我們剛剛討論過了，通常認為是最簡單的同步工具。本節將會討論一個更棒的工具，它的功能類似於互斥鎖，但是它能提供更為高階的方法，以便進程能夠同步活動。

一個號誌 S 是個整型變數，它除了初始化外只能通過兩個標準原子操作：wait () 和 signal() 來存取：
  • 操作 wait() 最初稱為 P（荷蘭語proberen，測試）；
  • 操作 signal() 最初稱為 V（荷蘭語verhogen，增加）；

可按如下來定義wait ():
wait(S){
    while (S <= 0)
        ;// busy wait
    S--；
}
可按如下來定義signal()：
signal(S) {
    S++;
}
在 wait() 和 signal() 操作中，號誌整數值的修改應不可分割地執行。也就是說，當一個進程修改號誌值時，沒有其他進程能夠同時修改同一號誌的值。另外，對於 wait(S)，S 整數值的測試（S < 0）和修改（S--）也不能被中斷。

首先，我們看看如何使用號誌。

號誌的使用

作業系統通常區分計數號誌與二進位制號誌。計數號誌的值不受限制，而二進位制號誌的值只能為 0 或 1。因此，二進位制號誌類似於互斥鎖。事實上，在沒有提供互斥鎖的系統上，可以使用二進位制號誌來提供互斥。

計數號誌可以用於控制存取具有多個範例的某種資源。號誌的初值為可用資源數量。當進程需要使用資源時，需要對該號誌執行 wait() 操作（減少號誌的計數)。當進程釋放資源時，需要對該號誌執行 signal() 操作（增加號誌的計數）。當號誌的計數為 0 時，所有資源都在使用中。之後，需要使用資源的進程將會阻塞，直到計數大於 0。

我們也可以使用號誌來解決各種同步問題。例如，現有兩個並行執行的進程：P1 有語句 S1 而 P2 有語句 S2。假設要求只有在 S1 執行後才能執行 S2。我們可以輕鬆實現這一要求：讓 P1 和 P2 共用同一號誌 synch，並且初始化為 0。

在進程 P1 中，插入語句：

S1;
signal (synch);

在進程 P2 中，插入語句：

wait (synch);
S2;

因為 synch 初始化為 0，只有在 P1 呼叫 signal(synch) ，即 S1 語句執行之後，P2 才會執行 S2。

號誌的實現

回想一下，互斥鎖實現具有忙等待。剛才描述的號誌操作 wait() 和 signal()，也有同樣問題。

為了克服忙等待需要，可以這樣修改號誌操作 wait() 和 signal() 的定義：當一個進程執行操作 wait() 並且發現號誌值不為正時，它必須等待。然而，該進程不是忙等待而是阻塞自己。阻塞操作將一個進程放到與號誌相關的等待佇列中，並且將該進程狀態切換成等待狀態。然後，控制轉到 CPU 排程程式，以便選擇執行另一個進程。

等待號誌 S 而阻塞的進程，在其他進程執行操作 signal() 後，應被重新執行。進程的重新執行是通過操作 wakeup() 來進行的，它將進程從等待狀態改為就緒狀態。然而，進程被新增到就緒佇列。（取決於 CPU 排程演算法，CPU 可能會也可能不會從正在執行的進程切換到新的就緒進程。）

為了實現這樣定義的號誌，我們按如下定義號誌：
typedef struct {
    int value;
    struct process *list;
} semaphore;
每個號誌都有一個整數 value 和一個進程連結串列 list。當一個進程必須等待號誌時，就被新增到進程連結串列。操作 signal() 從等待、進程連結串列上取走一個進程，並加以喚醒。

現在，號誌操作 wait() 可以定義如下：
wait(semaphore *S) {
    S->value--;
    if (S->value < 0) {
        add this process to S->list;
        block();
    }
}
而號誌操作 signal() 可定義如下：
signal(semaphore *S) {
    S->value++;
    if (S->value <= 0) {
        remove a process P from S->list;
        wakeup(P);
    }
}
操作 block() 掛起呼叫它的進程。操作 wakeup(P) 重新啟動阻塞進程 P 的執行。這兩個操作都是由作業系統作為基本系統呼叫來提供的。

注意，這樣實現的號誌的值可以是負數，而在具有忙等待的號誌經典定義下，號誌的值不能為負。如果號誌的值為負，那麼它的絕對值就是等待它的進程數。出現這種情況源於，在實現操作 wait() 時互換了遞減和測試的順序。

通過每個過程控制塊 PCB 的一個連結欄位，等待進程的連結串列可以輕鬆實現。每個號誌包括一個整數和一個 PCB 連結串列指標。向連結串列中增加和刪除進程以便確保有限等待的一種方法採用 FIFO 佇列，這裡的號誌包括佇列的首指標和尾指標。然而，一般來說，連結串列可以使用任何排隊策略。號誌的正確使用不依賴於號誌連結串列的特定排隊策略。

關鍵的是，號誌操作應原子執行。我們應保證：對同一號誌，沒有兩個進程可以同時執行操作 wait() 和 signal()。這是一個臨界區問題。

對於單處理器環境，在執行操作 wait() 和 signal() 時，可以簡單禁止中斷。這種方案在單處理器環境下能工作，這是因為一旦中斷被禁用，不同進程指令不會交織在一起。只有當前執行進程一直執行，直到中斷 被重新啟用並且排程程式重新獲得控制。

對於多處理器環境，每個處理器的中斷都應被禁止；否則，在不同處理器上不同的執行進程可能會以任意不同方式一起交織執行。每個處理器中斷的禁止會很困難，也會嚴重影響效能。因此，SMP 系統應提供其他加鎖技術，如 compare_and__swap() 或自旋鎖，以確保 wait() 與 signal() 原子執行。

重要的是，對於這裡定義的操作 wait() 和 signal()，我們並沒有完全取消忙等待。我們只是將忙等待從進入區移到臨界區。此外，我們將忙等待限制在操作 wait() 和 signal() 的臨界區內，這些區比較短（如經合理編碼，它們不會超過 10 條指令）。因此，臨界區幾乎不被占用，忙等待很少發生，而且所需時間很短。對於應用程式，存在一種完全不同的情況，即臨界區可能很長（數分鐘或數小時）或幾乎總是被佔用。在這種情況下，忙等待極為低效。

死鎖與飢餓

具有等待佇列的號誌實現可能導致這樣的情況：兩個或多個進程無限等待一個事件，而該事件只能由這些等待進程之一來產生。當出現這樣的狀態時，這些進程就為死鎖。

為了說明起見，假設有一個系統，它有兩個進程 P0 和 P1，每個存取共用號誌 S 和 Q，這兩個號誌的初值均為 1:
P0 P1
wait(S);  wait(Q);
wait(Q);   wait(S);
signal(S); signal(Q);
signal(Q); signal(S);

假設 P0 執行 wait(S)，接著 P1 執行 wait(Q)。當 P0 執行 wait(Q) 時，它必須等待直到 P1 執行 signal(Q)。類似地，當 P1 執行 wait(S) 時，它必須等待直到 P0 執行 signal(S)。由於這兩個操作 signal() 都不能執行，這樣 P0 和 P1 就死鎖了。

我們說一組進程處於死鎖狀態：組內的每個進程都等待一個事件，而該事件只可能由組內的另一個進程產生。這裡主要關心的事件是資源的獲取和釋放。然而，其他型別的事件也能導致死鎖。

與死鎖相關的另一個問題是無限阻塞或飢餓，即進程無限等待號誌。如果對與號誌有關的連結串列按 LIFO 順序來增加和刪除進程，那麼可能發生無限阻塞。

優先順序的反轉

如果一個較高優先順序的進程需要讀取或修改核心資料，而且這個核心資料當前正被較低優先順序的進程存取（這種串聯方式可涉及更多進程），那麼就會出現一個排程挑戰。由於核心資料通常是用鎖保護的，較高優先順序的進程將不得不等待較低優先順序的進程用完資源。如果較低優先順序的進程被較高優先順序的進程搶占，那麼情況變得更加複雜。

比如，假設有三個進程 L、M 和 H，它們的優先順序順序為 L<M<H。假定進程 H 需要資源 R，而 R 目前正在被進程 L 存取。通常，進程 H 將等待 L 用完資源 R。但是，現在假設進程 M 進入可執行狀態，從而搶佔進程 L。間接地，具有較低優先順序的進程 M，影響了進程 H 應等待多久，才會使得進程 L 釋放資源 R。

這個問題稱為優先順序反轉。它只出現在具有兩個以上優先順序的系統中，因此一個解決方案是只有兩個優先順序。然而，這對於大多數通用作業系統是不夠的。通常，這些系統在解決問題時採用優先順序繼承協定。

根據這個協定，所有正在存取資源的進程獲得需要存取它的更高優先順序進程的優先順序，直到它們用完了有關資源為止。當它們用完時，它們的優先順序恢復到原始值。在上面的範例中，優先順序繼承協定將允許進程 L 臨時繼承進程 H 的優先順序，從而防止進程 M 搶占執行。當進程 L 用完資源 R 時，它將放棄繼承的進程 H 的優先順序，以採用原來的優先順序。因為資源 R 現在可用，進程 H（而不是進程 M）會接下來執行。