最短作業優先 (SJF) 排程演算法

---

---

CPU排程策略是一種選擇一個處於等待狀態的程序並將其分配給CPU以便執行的過程。存在多種排程演算法。在本節中，我們將學習最短作業優先 (SJF) 排程演算法。

SJF（最短作業優先）排程演算法

在最短作業優先排程演算法中，程序按其CPU突發時間的升序進行排程，即CPU分配給執行時間最短的程序。

SJF 排程演算法的變體

SJF 排程演算法有兩個變體：

非搶佔式 SJF 排程

在非搶佔式版本中，一旦一個程序被分配給CPU，它就會一直執行到完成。在此，當一個程序完成執行或當一個或多個新程序到達空的準備佇列時，就會呼叫短期排程程式。

搶佔式 SJF 排程

這是 SJF 排程的搶佔式版本，也稱為最短剩餘時間優先 (SRTF) 排程演算法。在這裡，如果在較長程序執行期間，較短程序進入準備佇列，則會發生程序切換，即將正在執行的程序交換到準備佇列，而新到達的較短程序開始執行。因此，短期排程程式在系統中到達新的程序或現有程序完成執行時被呼叫。

SJF 演算法的特性

• SJF 將 CPU 分配給執行時間最短的程序。
• 如果兩個或多個程序具有相同的突發時間，則根據先到先服務原則在這幾個程序之間進行仲裁。
• 存在搶佔式和非搶佔式版本。
• 它最大限度地減少了程序的平均等待時間。
• 如果短程序持續進入系統，則可能會導致長程序飢餓。

我們可以透過以下示例瞭解這兩種排程策略的工作原理。

非搶佔式 SJF 演算法示例

示例 1

假設我們有一組四個程序同時到達，順序為 P1、P2、P3 和 P4。每個程序的突發時間（毫秒）如下表所示：

P3

4

P4

8

讓我們繪製甘特圖，並使用非搶佔式 SJF 演算法找到平均週轉時間和平均等待時間。

使用 SJF 的程序集的甘特圖

程序 P3 的突發時間最短，因此它首先執行。然後我們發現 P1 和 P4 的突發時間相同，均為 8ms。由於 P1 先到達，因此 CPU 分配給 P1，然後分配給 P4。最後執行 P2。因此，執行順序為 P3、P1、P4、P2，如下面的甘特圖所示：

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

平均週轉時間

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

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

= (12 + 36 + 4 + 20) / 4 = 18 ms

平均等待時間

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

P3

示例 2

在前面的示例中，我們假設所有程序同時到達，這在實踐中是不可能的。在這裡，我們考慮程序在不同時間到達的情況。假設我們有一組四個程序，其到達時間和 CPU 突發時間如下：

到達時間

CPU 突發時間

甘特圖

在繪製甘特圖時，我們將考慮在呼叫排程程式時系統中到達了哪些程序。在 0ms 時，只有 P1 存在，因此它被分配給 CPU。P1 在 6ms 完成執行，此時 P2 和 P3 已到達，但 P4 尚未到達。P3 被分配給 CPU，因為在當前程序中它具有最短的突發時間。P3 在 10ms 完成執行。到那時，P4 已到達，因此在程序 P2 和 P4 上執行 SJF 演算法。因此，我們發現執行順序為 P1、P3、P4、P2，如下面的甘特圖所示：

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

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

讓我們繪製甘特圖，並使用非搶佔式 SJF 演算法找到平均週轉時間和平均等待時間。

TAT_P1 = CT_P1 - AT_P1 = 6 - 0 = 6 ms

TAT_P2 = CT_P2 - AT_P2 = 23 - 4 = 19 ms

TAT_P3 = CT_P3 - AT_P3 = 10 - 4 = 6 ms

TAT_P4 = CT_P4 - AT_P4 = 13 - 8 = 5 ms

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

= (6 + 19 + 6 + 5) / 4 = 9 ms

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

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

平均週轉時間

WT_P1 = 0 - 0 = 0 ms

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

WT_P2 = 13 - 4 = 9 ms

WT_P3 = 6 - 4 = 2 ms

WT_P4 = 10 - 8 = 2 ms

示例 2

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

= (0 + 9 + 2 + 2) / 4 = 3.25 ms

搶佔式 SJF (SRTF) 演算法示例

讓我們繪製甘特圖，並使用非搶佔式 SJF 演算法找到平均週轉時間和平均等待時間。

TAT_P1 = CT_P1 - AT_P1 = 6 - 0 = 6 ms

程序 P3 的突發時間最短，因此它首先執行。然後我們發現 P1 和 P4 的突發時間相同，均為 8ms。由於 P1 先到達，因此 CPU 分配給 P1，然後分配給 P4。最後執行 P2。因此，執行順序為 P3、P1、P4、P2，如下面的甘特圖所示：

現在讓我們對以下程序執行搶佔式 SJF (SRTN) 排程，繪製甘特圖並找到平均週轉時間和平均等待時間。

平均週轉時間

WT_P1 = 0 - 0 = 0 ms

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

由於這是一個搶佔式排程演算法，因此當程序到達和完成執行時都會呼叫排程程式。排程程式計算系統中每個程序的剩餘完成時間，並選擇剩餘執行時間最短的程序。

最初，只有 P1 到達，因此它被分配給 CPU。在 4ms 時，P2 和 P3 到達。排程程式計算程序 P1、P2 和 P3 的剩餘時間為 4ms、10ms 和 3ms。由於 P3 的時間最短，因此 P1 被 P3 搶佔。P3 在 7ms 完成執行，並呼叫排程程式。在系統中的程序中，P1 的時間最短，因此它繼續執行。在 10ms 時，P4 到達，排程程式再次計算每個程序的剩餘時間。由於 P1 的剩餘時間最短，因此不發生程序切換，P1 繼續執行。以類似的方式，其餘程序完成執行。

• 根據甘特圖，我們計算平均週轉時間和平均等待時間。
• = ((11 - 0) + (25 - 4) + (7 - 4) + (15 - 10)) / 4 = 10 ms
• = (3 + 11 + 0 + 1) / 4 = 3.75 ms

SJF 演算法的優點

• 與 FCFS 排程相比，在搶佔式和非搶佔式方法中，SJF 的平均等待時間都大大減少。
• SJF 在相當程度上優化了週轉時間。
• 如果精確估計每個程序的執行時間，它可以保證最大吞吐量。

SJF 演算法的缺點

如果存在具有較短突發時間的程序流，則系統中的較長程序可能會無限期地等待在準備佇列中，從而導致飢餓。