作業系統排程演算法

---

---

程序排程器根據特定的排程演算法，將不同的程序分配給CPU。本章將討論六種常用的程序排程演算法：

• 先來先服務 (FCFS) 排程
• 最短作業優先 (SJN) 排程
• 優先順序排程
• 最短剩餘時間優先
• 輪詢 (RR) 排程
• 多級佇列排程

這些演算法是非搶佔式或搶佔式的。非搶佔式演算法的設計使得一旦一個程序進入執行狀態，它就不能被搶佔，直到它完成分配的時間，而搶佔式排程是基於優先順序的，當高優先順序的程序進入就緒狀態時，排程程式可以隨時搶佔低優先順序的執行程序。

先來先服務 (FCFS)

• 作業按先來先服務的順序執行。
• 這是一種非搶佔式、可搶佔的排程演算法。
• 易於理解和實現。
• 其實現基於 FIFO 佇列。
• 效能較差，因為平均等待時間較長。

每個程序的**等待時間**如下：

平均等待時間：(0+4+6+13) / 4 = 5.75

最短作業優先 (SJN)

• 這也被稱為**最短作業優先**，或 SJF。

• 這是一種非搶佔式、可搶佔的排程演算法。

• 最小化等待時間的最佳方法。

• 易於在批處理系統中實現，其中所需的 CPU 時間是預先知道的。

• 無法在互動式系統中實現，因為所需的 CPU 時間是未知的。

• 處理器應該預先知道程序需要多長時間。

已知：程序表及其到達時間、執行時間

每個程序的**等待時間**如下：

平均等待時間：(0 + 4 + 12 + 5)/4 = 21 / 4 = 5.25

基於優先順序的排程

• 優先順序排程是一種非搶佔式演算法，也是批處理系統中最常見的排程演算法之一。

• 每個程序都分配一個優先順序。優先順序最高的程序首先執行，依此類推。

• 具有相同優先順序的程序按先來先服務的順序執行。

• 優先順序可以根據記憶體需求、時間需求或任何其他資源需求來決定。

已知：程序表及其到達時間、執行時間和優先順序。這裡我們認為 1 是最低優先順序。

每個程序的**等待時間**如下：

平均等待時間：(0 + 10 + 12 + 2)/4 = 24 / 4 = 6

最短剩餘時間優先

• 最短剩餘時間 (SRT) 是 SJN 演算法的搶佔式版本。

• 處理器分配給最接近完成的作業，但它可以被一個具有更短完成時間的新就緒作業搶佔。

• 無法在互動式系統中實現，因為所需的 CPU 時間是未知的。

• 它通常用於需要優先處理短作業的批處理環境。

輪詢排程

• 輪詢是一種搶佔式程序排程演算法。

• 每個程序都被提供一個固定的執行時間，這被稱為**時間片**。

• 一旦一個程序執行了一定的時間段，它就會被搶佔，然後其他程序執行一定的時間段。

• 上下文切換用於儲存被搶佔程序的狀態。

每個程序的**等待時間**如下：

平均等待時間：(9+2+12+11) / 4 = 8.5

多級佇列排程

多級佇列不是一個獨立的排程演算法。它們利用其他現有的演算法對具有共同特徵的作業進行分組和排程。

• 為具有共同特徵的程序維護多個佇列。
• 每個佇列可以有自己的排程演算法。
• 為每個佇列分配優先順序。

例如，CPU 密集型作業可以安排在一個佇列中，所有 I/O 密集型作業安排在另一個佇列中。然後，程序排程程式交替地從每個佇列中選擇作業，並根據分配給該佇列的演算法將它們分配給 CPU。