最高響應比優先 (HRRN) 排程演算法

---

---

CPU 排程演算法是在多程式設計環境中決定就緒佇列中哪個程序應該接下來執行的策略。有多種排程策略，其中最高響應比優先 (HRRN) 排程演算法旨在提供最優的排程解決方案之一。

最高響應比優先 (HRRN) 排程演算法

HRRN 演算法是一種非搶佔式排程策略，它根據一個稱為響應比的引數選擇下一個要執行的程序。響應比的計算公式如下：

$$\mathrm{響應比 = \frac{(等待時間 + 服務時間)}{服務時間}}$$

這裡，W 是程序到現在的等待時間，S 是程序的突發時間。

當多個程序準備執行時，排程程式計算每個程序的響應比，並將 CPU 分配給具有最高值的程序。由於 HRRN 是一種非搶佔式演算法，一旦程序獲得 CPU 訪問權，它就會執行到完成，然後另一個程序才能獲得 CPU 訪問權。

HRRN 排程的特點

• HRRN 演算法是最優演算法，因為它根據程序的響應比選擇要執行的程序。
• HRRN 既優先考慮較短的程序，也優先考慮在就緒佇列中等待時間較長的程序。
• 它被設想為最短作業優先演算法的改進，解決了 SJF 演算法的飢餓問題。
• 由於它是非搶佔式的，因此當程序完成執行或當新的程序到達空閒的就緒佇列時，排程程式就會被呼叫。
• 它不需要頻繁的上下文切換。這有助於 CPU 主要專注於程序的執行。

HRRN 演算法的工作原理

• 最初當 CPU 空閒時，當一個或多個新程序到達就緒佇列時，排程程式就會被呼叫。首先讓具有最短突發時間的程序進入。
• 當正在執行的程序完成執行後，計算就緒佇列中每個程序的響應比。將具有最高響應比的程序分配給 CPU。
• 重複執行步驟 2，直到就緒佇列中沒有程序。

HRRN 排程演算法示例

我們可以透過以下示例來了解 HRRN 排程演算法的工作原理。

讓我們考慮一個系統，該系統有四個程序同時到達，順序為 P1、P2、P3 和 P4。每個程序的突發時間（以毫秒為單位）由下表給出：

4

10

P3

4

4

P4

8

5

讓我們對它進行 HRRN 排程。我們將繪製甘特圖並找到平均週轉時間和平均等待時間。

甘特圖生成

要生成甘特圖，我們將找到排程程式每次被呼叫時的響應比。

在時間 = 0 毫秒時

系統中的程序：P1。

8

由於 P1 是唯一程序，因此它立即被排程。它在時間 = 6 毫秒時執行完成。

到此時間的甘特圖是：

在時間 = 6 毫秒時

程序 P1 完成執行並離開系統。

系統中的程序：P2 和 P3，它們都在時間 = 4 毫秒到達。

P2 的響應比 = (W + S) / S = (2 + 10) / 10 = 1.2

8

P3 的響應比 = (W + S) / S = (2 + 4) / 4 = 1.5

由於 P3 的響應比更高，因此將 P3 分配給 CPU。

在時間 = 10 毫秒時

程序 P3 完成執行並離開系統。

系統中的程序：P2（在時間 = 4 毫秒到達）和 P4（在時間 = 8 毫秒到達）。

P2 的響應比 = (W + S) / S = (6 + 10) / 10 = 1.6

P4 的響應比 = (W + S) / S = (2 + 5) / 5 = 1.4

由於 P2 的響應比更高，因此將 P2 分配給 CPU。

在時間 = 20 毫秒時

程序 P2 完成執行並離開系統。

系統中唯一的程序是 P4，因此它立即被排程。

因此，最終的甘特圖是：

由此我們將計算每個程序的週轉時間和等待時間及其平均值。

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

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

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

TAT_P3 = CT_P3 - AT_P3 = 10 - 4 = 6 毫秒

TAT_P4 = CT_P4 - AT_P4 = 25 - 8 = 17 毫秒

平均週轉時間

= 各程序週轉時間之和 / 程序數

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

= (6 + 16 + 6 + 17) / 4 = 11.25 毫秒

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

任何程序的等待時間 = CPU 進入時間 - 到達時間

WT_P1 = 0 - 0 = 0 毫秒

• WT_P2 = 10 - 4 = 6 毫秒
• WT_P3 = 6 - 4 = 2 毫秒
• WT_P4 = 20 - 8 = 12 毫秒
• 平均等待時間

= 各程序等待時間之和 / 程序數

• = (WT_P1 + WT_P2 + WT_P3 + WT_P4) / 4
• = (0 + 6 + 2 + 12) / 4 = 5 毫秒
• HRRN 排程的優點

HRRN 演算法是最優演算法之一。

它更喜歡較短的程序，因此具有最短作業優先排程演算法的所有優點。