同步中的臨界區

---

---

什麼是臨界區？

臨界區指的是程序中一段程式碼，這段程式碼會改變任何共享資源的值或狀態。共享資源指的是共享記憶體變數、公共表、共享檔案、共享裝置或任何其他系統資源。

這段程式碼被稱為“臨界區”，因為如果多個程序同時嘗試操作共享資源，則由於一種稱為競爭條件的現象，結果將不一致。

臨界區問題

臨界區問題在於設計一種協議，使得當一個程序正在執行其臨界區時，不允許其他程序同時執行其臨界區，從而避免發生競爭條件。

為了實現這種合作，每個程序都必須請求進入其臨界區的許可。程序進行此操作的程式碼段稱為入口段。如果程序獲得許可，則它進入臨界區，在臨界區中，它更新共享資源的值。

臨界區之後，程序透過退出段，在退出段中，它放棄對共享資源的控制並將其告知系統中的其他程序。然後，程序繼續執行其剩餘語句。下圖顯示了具有臨界區的程序的一般結構。

臨界區問題解決方案的要求

任何針對臨界區問題的解決方案都需要滿足以下三個要求：

1. 互斥

互斥意味著任何時候只有一個程序可以在臨界區內。如果其他程序需要執行其臨界區，則必須等待臨界區空閒。

2. 程序推進

當沒有任何程序當前在其臨界區中，而某些程序想要進入其臨界區時，只有不在其剩餘段中的程序才能參與決定哪個程序可以接下來進入其臨界區，並且此決定不能無限期推遲。程序推進確保程序之間有公平的仲裁，以便程序繼續執行。

3. 有界等待

有界等待意味著每個程序必須有有限的等待時間。它不應該無限期地等待訪問臨界區。它為當一個程序請求其臨界區的許可時其他程序可以訪問臨界區的次數設定了一個界限。

解決臨界區問題的演算法和方法

為了解決臨界區問題，已經開發了許多演算法和方法。一些最常見的解決方案列在下面。

1. Peterson 演算法

Peterson 演算法是一種經典的基於軟體的方法，用於確保併發程序之間的互斥。它使兩個程序能夠訪問共享資源而不會發生衝突，依靠共享記憶體進行通訊。該演算法使用兩個共享變數，即 flag 用於指示一個程序對進入臨界區的興趣，turn 用於確定如果兩個程序都感興趣時的優先順序。

2. 測試並設定

此方法使用一個共享布林變數，稱為“鎖”，其中 lock = true 表示一個程序在其臨界區中。每個程序的入口段都有一個原子函式“測試並設定”，它檢查 lock 的值。如果 lock 為 true，則等待。否則，它將 lock 設定為 true 並進入臨界區。在退出段中，lock 重置為 false。

3. 訊號量

訊號量是一種高階同步工具。它使用兩個原子操作，“wait()”和“signal()”。wait() 指令用於在入口段中獲取對臨界區的訪問許可權，而 signal() 操作用於釋放對共享資源的控制。訊號量可以分為兩種型別：二進位制訊號量和計數訊號量。

4. 比較並交換

此方法類似於“測試並設定”方法。它使用一個共享布林變數，其值使用“比較並交換”指令進行測試和設定。只有當傳遞給它的值與某個值匹配時，鎖才設定為 true。

5. 互斥鎖

互斥一詞源於互斥。它使用鎖，這些鎖分別在入口段和退出段中使用原子函式“acquire()”和“release()”進行操作。一次只有一個程序可以獲取鎖，因此一次只有一個程序可以訪問臨界區。

作業系統核心中解決臨界區問題的方法

與使用者程序一樣，許多核心程序也併發執行，它們可能嘗試更新核心資料結構的值。核心資料是共享資料結構，包括程序列表、記憶體分配、開啟檔案列表、中斷處理等。嘗試更新這些值會導致出現許多競爭條件情況的可能性很高。作業系統競爭條件比使用者程序中發生的競爭條件更關鍵，可能會導致系統崩潰。因此，核心開發者需要細緻的設計策略來避免核心競爭條件。

作業系統中的核心大致分為搶佔式和非搶佔式兩種。讓我們來看看在兩者中解決競爭條件的一般方法。

非搶佔式核心

非搶佔式核心本質上沒有競爭條件。在這裡，在核心模式下執行的程序不會被任何其他程序搶佔。它將繼續執行，直到它退出、阻塞或自願放棄 CPU 的控制權。由於任何給定時間只有一個程序在核心中處於活動狀態，因此非搶佔式核心不容易在核心資料結構上出現競爭條件。

搶佔式核心

在搶佔式核心中，正在執行的核心程序可能會中途停止，另一個程序可能會開始執行。這可能會破壞核心資料結構的值。搶佔式核心對於即時系統至關重要，因為它們具有更高的響應能力和吞吐量，因此不能被非搶佔式核心取代。因此，它們需要採取足夠的措施來處理核心臨界區。

一個常見的解決方案是使用自旋鎖程式碼。當核心程序持有自旋鎖時，相應處理器的搶佔或中斷將被暫時停用。程序執行其臨界區程式碼，然後釋放自旋鎖。一旦自旋鎖被釋放，中斷將再次啟用。由於停用中斷可能會產生許多不利後果，因此目標是透過任何程序來最小化持有自旋鎖的時間。