11 Priority Ceiling Protocol 非 Ceiling-Priority Protocol

admin

Priority Ceiling Protocol（優先級天花板協議）是一種用於實時操作系統中的資源同步協議，其主要目的是解決優先級反轉（Priority inversion）和死鎖（Deadlock）問題。優先級天花板協議主要針對具有固定優先級的任務，並且假設所有任務對資源的使用情況都是事先已知的。

在優先級天花板協議中：

• Π(R)：表示資源R的優先級天花板。這是所有需要該資源的任務中具有最高優先級的那個任務的優先級。 Priority ceiling of resource R.The highest priority of all tasks that require R.
• Π^(t)：表示在某個時間點t的當前系統優先級天花板。這是在該時間點正在使用的所有資源中具有最高優先級天花板的資源的優先級。
  

優先級天花板協議的基本原則如下：

在任務需要鎖定資源時，首先檢查任務的優先級是否高於當前系統優先級天花板。如果高於天花板，則允許任務鎖定資源；否則，任務必須等待。
當某個任務鎖定資源時，將系統優先級天花板提升至該資源的優先級天花板。
當任務解鎖資源時，降低系統優先級天花板，恢復到未鎖定該資源時的狀態。
通過這種方法，優先級天花板協議可以在任務鎖定資源時減少高優先級任務被低優先級任務阻塞的情況，從而避免優先級反轉問題。此外，由於資源鎖定的有序性，這種協議還可以防止死鎖問題的發生。

There are three types of blockings in PCP

• 直接阻塞（Direct Blocking）：當高優先級的任務需要鎖定的資源被低優先級的任務持有時，就會發生直接阻塞。在這種情況下，高優先級的任務必須等待低優先級的任務釋放資源。
  
• 優先級繼承阻塞（Priority-Inheritance Blocking）：這種阻塞發生在一個低優先級的任務持有一個資源，並且一個高優先級的任務需要該資源，但低優先級的任務被另一個中間優先級的任務預占的情況。在這種情況下，低優先級的任務會繼承高優先級任務的優先級，直到它釋放資源。
  
• 迴避阻塞（Avoidance Blocking）：這是優先級天花板協議中特有的一種阻塞。當一個任務試圖鎖定一個資源，但該任務的優先級低於當前系統的優先級天花板時，該任務會被阻塞。這是為了避免可能導致死鎖或優先級反轉的情況。
  

Theorem: any job governed by PCP can be blocked for at most the duration of one critical section.
在 Priority Ceiling Protocol（優先級天花板協議）中，任何工作在最壞情況下只能被阻塞一次，而且阻塞的時間長度最多是一個臨界區域的執行時間。

為什麼呢？這是由 Priority Ceiling Protocol 的工作方式決定的：

在此協議中，每個共享資源都有一個所謂的 "priority ceiling"，這是所有需要該資源的任務中的最高優先級。

當一個任務持有一個資源時，系統的優先級天花板就會被設定為當前持有資源的任務的優先級天花板和該資源的優先級天花板之間的最大值。

如果一個任務嘗試鎖定一個資源，但該任務的優先級低於當前的系統優先級天花板，那麼該任務就會被阻塞。這意味著只有當沒有其他任務持有任何其需要的資源時，該任務才能獲得資源。

因此，由於這種協議，一個任務最多只能被阻塞一次，並且阻塞的時間長度最多只能是一個臨界區域（持有資源的區段）的執行時間，因為一旦該區段完成，資源將被釋放，並且可以被阻塞的任務獲得。

No transitive blocking
"Transitive blocking"是指一種情況，其中一個高優先級的任務因為另一個低優先級的任務正在等待一個由第三個任務佔用的資源，而被間接阻塞。這種阻塞是"轉移性"的，因為它通過一個中介任務從佔用資源的任務轉移到等待資源的任務。

在 Priority Ceiling Protocol（優先級天花板協議）中，不會出現轉移性阻塞，這是由該協議的工作方式確保的。當一個任務獲得一個資源的鎖定時，系統的優先級天花板會提高到該資源的優先級天花板（即，所有可能需要該資源的任務的最高優先級）。這意味著只有當沒有任務持有資源時，高優先級的任務才能運行。

因此，如果一個低優先級的任務正在等待一個由另一個任務佔用的資源，那麼任何比這兩個任務優先級更高的任務都不會被阻塞，因為系統的優先級天花板會阻止它們運行。這就消除了轉移性阻塞的可能性。