作業系統 - 優先順序排程演算法

---

---

優先順序排程是一種 CPU 排程策略，它根據分配給程序的優先順序來決定就緒佇列中哪個程序應該接下來執行。它通常用於系統中，其中程序的執行是分批進行的。

優先順序排程

在實施了優先順序排程策略的系統中，每個程序都分配了一個優先順序值。一些系統遵循優先順序值越低，優先順序越高的方案；而其他系統則遵循優先順序值越高，優先順序越高的方案。優先順序值最高的程序被選中執行。

優先順序排程有兩種變體：

非搶佔式優先順序排程

在非搶佔式版本中，一旦一個程序被分配給 CPU，它就會一直執行到完成。在這裡，當一個程序完成執行或當一個新程序到達一個空的準備佇列時，排程程式被呼叫。排程程式選擇優先順序最高的程序進行執行。

搶佔式優先順序排程

在搶佔式版本中，如果一個高優先順序程序在低優先順序程序執行期間進入系統，則會發生程序切換，其中正在執行的程序被換出，而新到達的高優先順序程序開始執行。因此，排程程式在系統中出現新程序或現有程序完成執行時被呼叫。

優先順序值也可以分為兩種形式：

• 靜態優先順序：在這個系統中，一旦一個優先順序值被分配給一個程序，它就會保持不變，直到該程序離開系統。
• 動態優先順序：在這裡，優先順序值根據程序的性質或程序在系統中的等待時間而變化。

優先順序排程的特點

• 優先順序最高的程序被分配給 CPU。
• 使用靜態優先順序的非搶佔式優先順序排程通常用於批處理程序。
• 使用動態優先順序的搶佔式優先順序排程用於大多數作業系統。
• 如果兩個程序具有相同的最高優先順序，則排程程式會根據先來先服務的原則在它們之間進行仲裁。
• 由於大多數系統都有一些高優先順序的系統程序，因此優先順序排程得到了廣泛的應用，通常與其他排程演算法結合使用。

我們可以透過以下示例瞭解優先順序排程演算法的工作原理：

非搶佔式優先順序排程的示例

示例 1

假設我們有一組四個程序，它們以 P1、P2、P3 和 P4 的順序同時到達。程序的突發時間（以毫秒為單位）和優先順序由下表給出：

考慮到優先順序值越低，優先順序越高，讓我們對其執行非搶佔式優先順序排程。我們將繪製甘特圖並找到平均週轉時間和平均等待時間。

甘特圖

程序 P2 具有最高優先順序，因此它首先執行。然後我們發現 P1 和 P4 的優先順序值都為 2。由於 P1 先到達，因此 CPU 分配給 P1，然後分配給 P4。最後執行 P3。因此，執行順序為 P2、P1、P4、P3，如下所示

讓我們根據上圖計算平均週轉時間和平均等待時間。

平均週轉時間

= 每個程序週轉時間之和 / 程序數

= ( TAT_P1 + TAT_P2 + TAT_P3 + TAT_P4) / 4

= ( 16 + 10 + 26 + 22) / 4 = 18.5 毫秒

平均等待時間

= 每個程序等待時間之和 / 程序數

= ( WT_P1 + WT_P2 + WT_P3 + WT_P4) / 4

= ( 10 + 0 + 22 + 16) / 4 = 10.5 毫秒

示例 2

在這個例子中，我們考慮一個程序到達時間不同的情況。假設我們有一組四個程序，它們的到達時間、CPU 突發時間和優先順序如下：

讓我們繪製甘特圖，並使用非搶佔式優先順序排程找到平均週轉時間和平均等待時間，並將較低的優先順序值視為較高的優先順序。

甘特圖

在 0 毫秒時，只有 P1 存在，因此它被分配給 CPU。P1 在 6 毫秒時完成執行，此時 P2 和 P3 已到達。P2 具有更高的優先順序，因此被分配給 CPU。P2 在 10 毫秒時完成執行。到那時，P4 已到達，其優先順序值為 1，因此它被分配給 CPU。P4 完成執行後，P3 被分配給 CPU。因此，執行順序為 P1、P2、P4、P3，如下所示的甘特圖：

讓我們計算每個程序的週轉時間，然後計算平均值。

程序的週轉時間 = 完成時間 - 到達時間

TAT_P1 = CT_P1 - AT_P1 = 6 - 0 = 6 毫秒

TAT_P2 = CT_P2 - AT_P2 = 16 - 4 = 12 毫秒

TAT_P3 = CT_P3 - AT_P3 = 23 - 4 = 19 毫秒

TAT_P4 = CT_P4 - AT_P4 = 19 - 8 = 11 毫秒

平均週轉時間

= 每個程序週轉時間之和 / 程序數

= ( 6 + 12+ 19 + 11) / 4 = 12 毫秒

等待時間由每個程序在就緒佇列中等待的時間給出。對於非搶佔式排程演算法，每個程序的等待時間可以簡單地計算如下：

任何程序的等待時間 = CPU 接納時間 - 到達時間

WT_P1 = 0 - 0 = 0 毫秒

WT_P2 = 6 - 4 = 2 毫秒

WT_P3 = 19 - 4 = 15 毫秒

WT_P4 = 16 - 8 = 8 毫秒

平均等待時間

= 每個程序等待時間之和 / 程序數

= (WT_P1 + WT_P2 + WT_P3 + WT_P4) / 4

= ( 0 + 2 +15 + 8) / 4 = 6.25 毫秒

搶佔式優先順序排程的示例

在搶佔式優先順序排程中，如果到達的程序優先順序高於正在執行的程序，則高優先順序程序會搶佔低優先順序程序。讓我們考慮以下一組程序，其到達時間、突發時間和優先順序在下表中給出：

甘特圖

在 0 毫秒時，P1 是唯一的程序，因此它開始執行。在 4 毫秒時，P2 和 P3 到達。由於 P2 的優先順序高於 P1，因此 P2 搶佔 P1。在 10 毫秒時，P4 到達，其優先順序高於 P2，因此搶佔 P2。P4 在 14 毫秒時完成執行並離開。系統中的程序為 P1、P2 和 P3，其中 P2 具有最高優先順序，因此被分配給 CPU。在 18 毫秒時，P2 完成執行，因此係統中的程序為 P1 和 P3。由於這兩個程序的優先順序相同，因此排程程式使用先來先服務的機制選擇 P1。當 P1 完成執行時，最後執行 P3。以下甘特圖顯示了執行順序：

從甘特圖中，我們計算平均週轉時間和平均等待時間。

平均週轉時間

= 每個程序週轉時間之和 / 程序數

= (TAT_P1 + TAT_P2 + TAT_P3 + TAT_P4) / 4

= ((22-0) + (18-4) + (25-4) + (14-10)) / 4 = 15.25 毫秒

平均等待時間

= 每個程序等待時間之和 / 程序數

= (WT_P1 + WT_P2 + WT_P3 + WT_P4) / 4

= (14 + 4 + 18 +0) / 4 = 7 毫秒

優先順序排程的優點

• 實現簡單，因為排程程式不需要進行任何預先計算。
• 一旦 CPU 定義了程序的相對相關性（優先順序），執行順序就很容易預測。
• 高優先順序程序幾乎立即得到服務。
• 優先順序排程在具有各種程序（每個程序都有自己的需求）的系統中特別有用。

優先順序排程的缺點

• 在靜態優先順序系統中，低優先順序程序可能需要無限期地等待，因為系統忙於執行高優先順序程序。這會導致停滯。
• 動態優先順序解決了停滯問題。但是，根據系統動態更新優先順序值的附加邏輯需要額外的 CPU 週期，從而增加了系統負載。
• 在非搶佔式優先順序排程中，一個大型程序通常會讓較短的程序等待很長時間。
• 在搶佔式優先順序排程中，低優先順序程序可能會被間歇性出現的高優先順序程序反覆搶佔，從而導致頻繁的上下文切換。

結論

優先順序排程演算法為更復雜的排程方法（如多級佇列排程）鋪平了道路。為程序分配優先順序可以幫助 CPU 首先完成其重要工作，並將剩餘時間留給後臺程序。可以根據程序的突發時間、程序型別、等待時間等為程序分配優先順序，從而融合其他基本排程演算法的優點。