**論文:
Priority Inheritance Protocols: An Approach to Real-Time Synchronization**

**大綱:**
為了確保多個程序在運行共享資源時，不會發生數據或條件競爭，保護數據的完整性和一致性，會使用 Synchronization Primitives （同步原始物件）；但是使用這個工具可能會產生 Priority Inversion (優先權反轉)，造成高優先權的任務被低優先權的任務 Blocking (鎖死)。
此論文主要在解決此一問題，提出了兩種方法 Priority Inheritance Protocols(PIP) 和 Priority Ceiling Protocols(PCP)。

**Synchronization Primitives（同步原始物件）**
是在計算機科學中用於管理多個進程或線程之間對共享資源的訪問的基本工具。這些原始物件用於確保多個並發執行的程序片段在訪問共享資源（如數據結構或設備）時，不會發生數據競爭或條件競爭，從而保護數據的完整性和一致性。

主要的同步原始物件包括：

1. 信號量（Semaphores）：
用於控制多個線程對共享資源的訪問，透過計數器來管理資源。
2. 互斥鎖（Mutexes）：
確保資源獨佔訪問，防止同時多個線程操作同一資源。
3. 監視器（Monitors）：
封裝資源及其訪問方法，保證方法間的互斥執行。
4. 條件變量（Condition Variables）：
允許線程在特定條件未滿足時等待，並在條件變化時被喚醒。
5. 屏障（Barriers）：
用於多個線程間的同步點，確保所有線程都達到某一點後才能繼續執行。
6. 讀寫鎖（Read/Write Locks）：
允許多重讀取或單一寫入操作，適用於讀多寫少的情況，提升效率。

---

# **優先權繼承協議（Priority Inheritance Protocol）**
是一種在多任務操作系統中解決優先權倒置問題的同步機制。優先權倒置是指一個低優先級任務因持有資源而阻塞了一個或多個高優先級任務的情況。
所以優先權繼承協議的是把低優先級任務的優先權提升到高優先級，藉此來加快任務完成，防止阻塞太久。


這裡是優先權繼承協議的基本運作流程：

**1. 起始狀態**
多個任務（Task）運行，其中包括至少一個高優先級任務和一個低優先級任務。
這些任務共享資源，例如數據或硬件。
**2. 資源的佔用**
低優先級任務獲得對共享資源的控制（例如，通過獲取互斥鎖）。
**3. 高優先級任務請求資源**
高優先級任務試圖訪問已被低優先級任務持有的共享資源，從而發起對該資源的請求。
由於資源已被低優先級任務鎖定，高優先級任務不能繼續執行，進入等待狀態。
**4. 優先權繼承**
在這一步驟中，當一個高優先級任務試圖訪問由一個低優先級任務持有的資源時（例如，一個被低優先級任務鎖定的互斥鎖），高優先級任務將無法獲得該資源並進入阻塞狀態。根據優先權繼承協議，發生這種情況時，低優先級任務會暫時繼承阻塞其的最高優先級任務的優先權。
運作流程如下：

繼承觸發：當低優先級任務持有資源並且高優先級任務因為該資源而被阻塞時，
低優先級任務的優先級會被臨時提升至最高的那個阻塞它的任務的優先級。

執行加速：這種優先級的提升有助於確保持有資源的任務能夠在其他同原始優先級的任務之前執行，
從而更快地完成其工作並釋放資源，減少高優先級任務的等待時間。

**5. 資源釋放和優先權恢復**
當低優先級任務完成其對資源的使用後，會進行兩個重要的操作：釋放資源和恢復其原始優先級。
運作流程如下：

釋放資源：低優先級任務完成其操作後，會解鎖或釋放其持有的資源。
這使得其他正在等待這些資源的任務（特別是之前被阻塞的高優先級任務）可以繼續其操作。

優先權恢復：一旦資源被釋放，低優先級任務會自動恢復其原始的優先級。
這是必要的，因為其任務完成了，不再需要保持高優先級。

通知和喚醒：釋放資源的同時，系統會檢查是否有任何其他任務因該資源被阻塞，
並根據優先級喚醒這些任務繼續執行。

**6. 高優先級任務繼續執行**
高優先級任務隨後獲得對共享資源的訪問權，繼續其中斷的操作。
重要特點

減少阻塞時間：優先權繼承協議減少了高優先級任務的等待時間，
因為它通過提升低優先級任務的優先級，使其能夠更快地完成並釋放資源。

避免死鎖：協議確保即使在多個任務競爭相同資源的情況下，也不會發生死鎖。
優先權繼承協議是一個重要的同步機制，特別是在實時操作系統中，
它幫助系統維持任務的執行順序和效率，並確保高優先級任務可以及時執行。

---

# **優先權天花板協議（Priority Ceiling Protocol）**
是另一種用於解決多任務環境中優先權倒置和死鎖問題的同步機制。這個協議不僅解決了優先權倒置問題，還進一步防止了因資源共享導致的 Deadlock (死鎖)。

**Deadlock (死鎖):**
假設有多個任務，互相擁有對方的共享資源並等待對方釋放資源，從而導致任務無法進行下去的情況稱為死鎖。

死鎖的發生需要滿足以下四個條件：

1.互斥條件（Mutual Exclusion）：
資源不能被多個進程同時共享，即在某一時刻，只能有一個進程可以使用特定的資源。

2.持有並等待條件（Hold and Wait）：
一個進程已經至少持有一個資源，並且正在等待獲得其他被其他進程持有的資源。

3.不可剝奪條件（No Preemption）：
已經分配給進程的資源在該進程使用完成之前，不能被其他進程強制剝奪。

4.循環等待條件（Circular Wait）：
發生死鎖時，必然存在一個進程-資源的循環等待鏈，
進程集合{P1, P2, ..., Pn}中的每個進程Pi都在等待一個由P(i+1)持有的資源
（最後一個進程Pn等待由P1持有的資源）。


**基本概念：**
優先權天花板協議賦予每個鎖（或其他同步物件）一個所謂的「優先權天花板」，這是所有可能獲得該鎖的任務中最高的靜態優先級。這個值在系統啟動時確定，並在系統運行期間保持不變。

協議運作流程：
**1. 設定優先權天花板**
系統初始化時，為每個資源（如互斥鎖）設定一個優先權天花板，該天花板是所有可能請求該資源的任務中最高的優先級。
**2. 資源請求規則**
當一個任務試圖獲得一個鎖時，系統首先檢查該任務的當前優先級是否高於當前所有已鎖定資源的優先權天花板。
如果是，任務可以鎖定該資源。
如果不是，任務則被阻塞，直到該資源變得可用（即沒有其他較低優先級的任務持有該資源）。
**3. 執行和阻塞**
如果任務獲得資源，它將執行相關操作。在持有資源期間，任務的優先級被提升到該資源的優先權天花板，以防止更高優先級的任務介入並導致死鎖。
任務完成操作後，資源被釋放，並恢復任務的原始優先級。
**4. 資源釋放**
當任務釋放資源時，它會將控制權交還給系統，系統則根據優先級決定下一個可以獲得該資源的任務。

**特點和優點：**
減少死鎖風險：通過確保在持有任何資源之前，任務的優先級必須高於所有當前鎖定資源的優先權天花板，協議有效地防止了死鎖的發生。
減少優先權倒置時間：只有當高優先級任務因無法獲得鎖而阻塞時，最多只會被一個低優先級任務的單一持鎖區塊所阻塞。
實現簡單：優先權天花板的設定是靜態的，易於管理和預測。

---

Shah, L., Kumar, R., & Lehoczky, J. P. (1990). Priority Inheritance Protocols: An Approach to Real-Time Synchronization. IEEE Transactions on Computers, 39(9), 1175-1185.

**P(J0)>P(J1)>P(J2)
P(J1)=P(S1)=P(S2)**

**1. t0 時間點：**
J2 啟動並開始執行，鎖定了S2。
**2. t1 時間點：**
J1 啟動並搶占了 J2。
**3. t2 時間點：**
J1 試圖進入其關鍵區段以執行對 S1 的操作，但由於 J1 的優先級不高於持有 S2 鎖的優先權天花板，因此運行系統暫停了 J1 而未鎖定 S1。此時，J2 繼承了 J1 的優先級並恢復執行。
***這邊避免了潛在 J1 與 J2 死鎖的可能性。***
**4. t3 時間點：**
J2 仍在其關鍵區段中。
高優先級的 J0 啟動並搶占了 J2。
J0 嘗試鎖定 S0，由於 J0 的優先級高於持有 S2 的鎖的優先權天花板，因此 J0 獲得了 S0 的鎖並繼續其關鍵區段執行。
**5. t4 時間點：**
J0 完成其關鍵區段的執行並完成所有執行，J2 因此恢復執行並鎖定了 S1 並且J1 被 J2 阻塞。
**6. t5 時間點：**
J2 釋放了 S1。
**7. t6 時間點：**
J2 釋放了 S2 並恢復其原始優先級。
被 J2 阻塞的 J1，由於具有更高的優先級，搶占了 J2，恢復執行，並鎖定了 S2 和 S1，進行其嵌套的關鍵區段操作。
**8. t7 時間點：**
J1 完成所有操作，包括解鎖 S1 和 S2，並結束其非關鍵區段的代碼執行。
J2 隨後恢復執行。
**9. t8 時間點：**
J2 完成執行。

Shah, L., Kumar, R., & Lehoczky, J. P. (1990). Priority Inheritance Protocols: An Approach to Real-Time Synchronization. IEEE Transactions on Computers, 39(9), 1175-1185.

**1. t0 時間點：**
J2 開始執行並鎖定 S2。
**2. t1 時間點：**
J1 啟動，搶占 J2 並開始執行。
**3. t2 時間點：**
當 J1 嘗試訪問已由 J2 鎖定的 S2 時，J1 被阻塞。
J2 因此繼承 J1 的優先級 P1 並繼續其關鍵區段的執行。
**4. t3 時間點：**
J2 成功進入其關鍵區段，鎖定 S1，此時並沒有其他工作對 S 進行訪問。
**5. t4 時間點：**
高優先級的 J0 啟動，搶占了在 S1 上的 J2 並開始執行非關鍵區段代碼。
**6. t5 時間點：**
J0 嘗試進入其關鍵區段並鎖定 S0，但因為 S1 的優先權天花板阻塞了 J0，由於 J0 的優先級不高於 S1 的優先權天花板 PO，J0 被 J2 阻塞。
此時，J2 恢復執行其關鍵區段，繼承了 J0 的優先級 Po。
(這邊有一個新型的阻塞)
**7. t6 時間點：**
J2 完成其關鍵區段，解鎖 S1，返回之前繼承的優先級 P1，J0 被喚醒。
J0 搶占 J2，因其優先級 PO 高於 S2 的優先權天花板 P1，鎖定並執行其關鍵區段 S0，最後解鎖 S0 與鎖定及解鎖 S1。
**8. t7 時間點：**
J0 完成執行，J2 進行關鍵區段並繼承優先權 P1。
**9. t8 時間點：**
J2 完成執行並解鎖 S2 恢復其原始優先級 P2，J1 被喚醒。
此時，J1 搶佔 J2，並且執行 S2 的鎖定。隨後，J1 解鎖 S2 並執行它的非關鍵部分代碼。
**10. t9 時間點：**
J1 完成執行與最後的操作。
**11. t10 時間點：**
J2 恢復執行直到完成。

---
優先權天花板協議 (PCP) 確實引入了一種額外的阻塞類型，稱為天花板阻塞。這種新的阻塞類型對於管理更複雜的優先權倒置場景以及**防止潛在的死鎖或連鎖阻塞**情況至關重要。

天花板阻塞：
當一個作業嘗試鎖定一個信號量但由於信號量的優先權天花板低於作業的當前優先級而被阻止時，就會發生天花板阻塞。這是為了防止更高優先級的作業被持有資源的低優先級作業阻塞，從而減少潛在的死鎖情況。

悲觀協議：**PCP 被視為一種悲觀協議，因為它可能導致“不必要的”阻塞情況**，其中作業被阻塞不是因為它需要的資源正在使用中，而是因為系統在防止潛在的未來死鎖。這種方法可以改善最壞情況的性能，但在死鎖不太可能發生的情況下可能導致效率低下。

這兩種協議的主要差異：

1. 防止優先權倒置的策略
優先權繼承協議（PIP）：
當一個高優先級任務被一個持有資源的低優先級任務阻塞時，該低優先級任務暫時繼承阻塞它的最高優先級任務的優先權。這種繼承只在有高優先級任務被阻塞的情況下觸發。
優先權天花板協議（PCP）：
每個資源（如互斥鎖）被賦予一個固定的優先權天花板，這是所有可能請求該資源的任務中最高的優先級。任務在試圖鎖定資源前，必須具有高於當前所有已鎖定資源的天花板的優先級。這不僅防止了優先權倒置，也防止了死鎖的發生。
2. 資源鎖定和釋放
PIP：
任務可以隨時鎖定它需要的資源，如果該資源已被另一個低優先級任務鎖定，則進行優先權繼承。
PCP：
任務在鎖定資源之前必須滿足更嚴格的條件，即其優先級必須高於所有已鎖定資源的優先權天花板。這減少了死鎖的可能性並且減少了由多個低優先級任務阻塞高優先級任務的情況。
3. 處理死鎖的能力
PIP：
主要解決優先權倒置問題，但它不提供防止死鎖的機制。如果不進一步管理資源的鎖定順序，死鎖仍然可能發生。
PCP：
通過優先權天花板的使用，有效預防了死鎖。因為任務在獲得資源前必須滿足嚴格的優先級檢查，這減少了因資源分配不當導致的死鎖風險。
4. 適用場景
PIP：
適用於優先級數目較少且系統中任務相對固定的環境。因為它比較簡單，但需要注意死鎖風險。
PCP：
適合在複雜的實時系統中使用，特別是在任務和資源都比較多且動態變化的環境中。由於其提供了更全面的解決方案，能夠更好地應對各種競爭條件。
總之，雖然兩種協議都旨在解決多任務環境中的優先權倒置問題，但優先權天花板協議提供了更嚴格的控制，以防止死鎖並減少因資源競爭引起的問題。相比之下，優先權繼承協議操作更簡單，但需要額外的機制來防止死鎖。

---
# **未來展望**
優先權天花板協議是一種有效的實時同步協議，因為它可以防止死鎖，將阻塞減少到最多一個關鍵區段，並且實現起來簡單。然而，這仍是一個次優協議，因為它可能導致可以通過協議的增強來避免的作業阻塞。儘管對可能的增強進行正式處理超出了本文的範圍，我們還是希望提出一些可能的增強想法，以激發對這個主題的更多研究。

例如，我們可以定義一個信號量的優先權底線，類似於其優先權天花板，作為可能訪問它的最低優先級作業的優先級。然後，如果作業J的優先級高於S的優先權天花板，或者以下條件成立，則J可以鎖定信號量S。如果J的優先級等於S的優先權天花板且S的優先權底線大於被搶占的最高優先級作業，也可以授予對S的鎖定。這最後一個條件，稱為優先權底線條件，確保被搶占的作業或更高優先級的作業不會訪問S。這保證了避免了死鎖和鏈接。這種協議稱為**優先限制協議**。優先限制協議消除了第四例中Jc在t5時間點遇到的天花板阻塞。此外，這種協議需要的資訊與優先權天花板協議相同，並且可以同樣容易地實施。然而，優先限制協議並不改善最壞情況的行為，因此不提高排程能力。

通過以下條件取代優先權底線條件，也有可能增強優先限制協議。如果作業J的優先級等於S的優先級，且沒有被搶占的低優先級作業訪問信號量S，則也可以允許作業J鎖定信號量S。這條件同樣保證避免了死鎖和鏈接。這種協議稱為**作業衝突協議**，優於優先權天花板和優先限制協議。然而，作業衝突協議仍然是一個次優協議。開發一個最佳的優先權繼承協議並將其與優先權天花板協議在性能和實施複雜性方面進行比較，將是一個有趣的練習。

---

# **總結**

在實時計算機系統中，具有嚴格截止時間的作業排程是一個重要的研究領域。
在本文中，我們研究了**優先權驅動的搶佔式排程背景下的同步問題**。展示了直接應用**常用的同步原始物件可能導致無控制的優先權倒置**，這是一種高優先級的作業被低優先級作業間接搶佔且時間不定的情況。
為了解決這個問題，我們研究了兩種屬於優先權繼承協議類的協議，分別是基本優先權繼承協議和優先權天花板協議，並將其應用於單處理器的背景中。
我們證明了這兩種協議均能解決無控制的優先權倒置問題。特別是，優先權天花板協議防止了死鎖並將阻塞減少到最多一個關鍵區段。
我們還推導出了一組充分條件，根據這些條件，使用此協議的一組週期性任務可以由速率單調算法進行排程。最後，我們概述了此協議的實施考慮和可能的擴展。