彼得森演算法在程序同步中的應用

---

協調併發執行的程序的操作是程序同步的核心關注點，這是計算機科學中的一個基本問題。互斥問題是程序同步的一個關鍵組成部分，彼得森演算法為此提供了一個著名的解決方案。這個互斥演算法由 Gary Peterson 於 1981 年提出，是簡單易懂且流行的演算法之一。本文將深入探討彼得森演算法，包括其描述、正確性證明、優缺點、與其他演算法的比較、應用以及結論。

彼得森演算法

• 將 turn 設定為 0 或 1，指示哪個程序可以首先進入其臨界區。

• 無限迴圈 -

• 將 flag[i] 設定為 true，表示程序 i 想要進入其臨界區。

• 將 turn 設定為 j，另一個程序的索引。

• 當 flag[j] 為 true 且 turn 等於 j 時，等待。

• 進入臨界區。

• 將 flag[i] 設定為 false，表示程序 i 已完成其臨界區。

• 剩餘部分。

演算法描述

互斥問題有一個基於軟體的解決方案，稱為彼得森演算法，它旨在確保只有一個程序在任何時候都存在於其臨界區。該演算法的基礎是兩個共享變數，一個 flag 陣列和一個 turn 變數。flag 陣列為每個程序分配一個標誌，包含布林值，表示程序是否對訪問其臨界區感興趣。turn 變數是一個數字，指示在發生衝突時哪個程序應該先執行。

每次程序想要進入或退出其臨界區時，都會呼叫演算法的兩個方法 lock() 和 unlock()。lock() 方法的實現如下 -

void lock(int i) {
   flag[i] = true;
   turn = j; //j is the other process
   while (flag[j] && turn == j);
}

unlock() 方法更容易使用 -

void unlock(int i) {
   flag[i] = false;
} 

lock() 方法首先將呼叫程序的標誌設定為 true，表示呼叫程序對訪問其臨界區感興趣。如果兩個程序同時想要訪問其臨界區，則它將 turn 變數設定為另一個程序的索引 (j)，表示另一個程序應該先執行。然後，該函式進入一個忙等待迴圈，其中它反覆檢查另一個程序的標誌是否為 true，以及現在是否輪到它進入臨界區。如果其中一個條件不滿足，則迴圈繼續。當兩個條件都滿足時，迴圈結束，並且呼叫過程繼續執行其臨界部分。

呼叫程序可以使用 unlock() 方法簡單地將其標誌更改為 false，從而退出其臨界區，並且不再對進入臨界區感興趣。

語法

int turn = 0;          // shared variable
bool flag[2] = {false, false}; // shared variable

Process 0:
while (true) {
   flag[0] = true;
   turn = 1;
   while (flag[1] && turn == 1) {} // busy wait
   // critical section
   flag[0] = false;
   // remainder section
}

Process 1:
while (true) {
   flag[1] = true;
   turn = 0;
   while (flag[0] && turn == 0) {} // busy wait
   // critical section
   flag[1] = false;
   // remainder section
}

正確性證明

彼得森演算法對互斥問題提供了一個有效的解決方案，它滿足以下條件 -

互斥

在任何時間點，只有一個程序可以處於其臨界區。

進展

如果當前沒有程序在其臨界區，並且任意數量的程序想要進入，則其中一個程序最終將進入其臨界區。

有界等待

對其他程序阻止一個程序訪問其臨界區的頻率有限制。

正確性證明使用不變式，即在演算法執行之前、期間和之後都成立的屬性。證明包含以下不變式 -

• 如果一個程序想要訪問其臨界區，則該程序的標誌為 true。

• 如果一個程序不想進入其臨界區，則該程序的標誌為 false。

• 如果一個程序在其臨界區，則該程序的 turn 變數將等於其索引。

這些不變式可用於證明互斥屬性是有效的，因為如果兩個程序嘗試同時進入其臨界區，則忙等待迴圈要求至少一個程序等待另一個程序完成執行。進展屬性是有效的，因為 turn 變數保證至少有一個程序始終能夠進入其臨界區，因此即使沒有程序在其臨界區並且一個或多個程序想要進入，最終其中一個程序將會成功。有界等待屬性是有效的，因為忙等待迴圈確保每個程序最終都會獲得進入其臨界區的輪次，即使其他程序也對進入臨界區感興趣。

不同方法

彼得森演算法是程序同步中解決臨界區問題的一種常用方法。它用於確保一次只有一個程序可以訪問共享資源。彼得森演算法有多種變體，它們在實現方式上有所不同，但都遵循相同的核心思想。

以下是三種常見的彼得森演算法實現方法 -

方法 1：使用標誌

在這種方法中，每個程序都有一個布林標誌，指示它是否想要訪問共享資源。演算法的工作原理如下 -

boolean flag[2] = {false, false};
int turn = 0;

/* Process 0 */
flag[0] = true;
turn = 1;
while (flag[1] && turn == 1);
/* critical section */
flag[0] = false;

/* Process 1 */
flag[1] = true;
turn = 0;
while (flag[0] && turn == 0);
/* critical section */
flag[1] = false;

這種方法使用一個名為 flag 的布林變數陣列來指示程序是否想要訪問臨界區。整數變數 turn 確定哪個程序首先進入臨界區。該演算法確保如果一個程序想要進入，則另一個程序必須等到 turn 被傳遞，從而防止兩個程序同時進入臨界區。

方法 2：僅使用 turn 變數

在這種方法中，只有一個變數用於確定哪個程序可以訪問臨界區，即 turn。演算法的工作原理如下 -

int turn = 0;

/* Process 0 */
turn = 1;
while (turn == 1);
/* critical section */
turn = 1;

/* Process 1 */
turn = 0;
while (turn == 0);
/* critical section */
turn = 0;

在此實現中，變數 turn 用於選擇哪個程序可以訪問臨界區。如果 turn 等於程序 ID，則程序可以訪問臨界區。如果 turn 不等於程序 ID，則程序必須等待輪到它。

方法 3：使用鎖變數

這種方法使用一個鎖變數來指示臨界區是否已鎖定。演算法的工作原理如下 -

boolean lock = false;

/* Process 0 */
while (lock);
lock = true;
/* critical section */
lock = false;

/* Process 1 */
while (lock);
lock = true;
/* critical section */
lock = false;

在此實現中，變數 lock 表示臨界區的鎖定狀態。如果 lock 等於 true，則臨界區已鎖定，程序必須等待直到它變為 false。如果 lock 等於 false，則程序可以訪問臨界區並將其鎖定。當程序完成臨界區後，它透過將 lock 設定為 false 來解鎖它。

應用

彼得森演算法被應用於計算機科學的多個領域，特別是作業系統和分散式系統。該演算法可用於確保程式碼關鍵部分的互斥，例如檔案系統操作、網路連線和共享記憶體訪問。在分散式系統中，例如具有分散式資料庫和訊息佇列的系統，該演算法也可用於協調對共享資源的訪問。

結論

總之，彼得森演算法是解決互斥問題的一種著名且仍在使用的演算法。該演算法簡單易懂，使其成為小型系統的一個理想選擇。該演算法也有一些缺點，包括容易發生忙等待以及依賴共享變數。儘管存在這些缺點，但彼得森演算法在計算機科學中仍然有許多應用，特別是在作業系統和分散式系統中。總的來說，彼得森演算法是程序同步發展中的一個重要里程碑，並且在現代計算系統中仍然是一種有效的確保互斥的方法。