作業系統 - 先來先服務排程演算法

---

---

在多道程式設計環境中，排程是由 CPU 執行的，用於決定下一個要執行的程序。這允許多個 CPU 程序同時存在，同時最佳化系統資源的使用以及執行時間。排程策略定義了一個從就緒佇列中等待執行的程序中選擇一個程序的過程。有各種各樣的排程策略，其中最基本的一種是先來先服務 (FCFS) 排程演算法。

FCFS 排程

FCFS 被認為是最簡單的 CPU 排程演算法。在 FCFS 演算法中，最先請求 CPU 的程序首先被分配到 CPU。FCFS 演算法的實現是透過 FIFO（先進先出）佇列管理的。FCFS 排程是非搶佔式的。非搶佔式意味著，一旦 CPU 被分配給一個程序，該程序就會一直佔用 CPU，直到它執行完工作或任務並釋放 CPU，或者透過請求 I/O 來釋放 CPU。

FCFS 演算法的主要特點

• FCFS 是一種非搶佔式排程演算法。
• 最先到達就緒佇列的程序首先被分配執行。
• 實現簡單，因為它不涉及任何複雜的演算法。
• 它不需要任何關於程序的先驗知識。此外，如果程序的執行時行為動態變化，對 FCFS 排程演算法沒有影響。
• 雖然這保證了公平的排程，但它可能導致單個程序的等待時間過長。

FCFS 排程的現實生活例子

作為 FCFS 排程的現實生活例子，可以觀察到購物中心的收銀臺系統。排在隊伍中第一個人先結賬，然後下一個人才有機會結賬付款，依此類推。如果沒有給 VIP 客戶優先權，那麼結賬系統將按此進行（這意味著排在隊伍中的第一人（第一個任務）將首先結賬，並在完成（執行）第一個客戶的付款後，收銀員（CPU）將關注其他客戶（單獨的任務），因為他們都在排隊）。由於 FCFS 是非搶佔式的，因此不會優先考慮隨機的重要任務。

FCFS 排程數學示例

在 CPU 排程問題中，解決問題時會使用一些術語，因此出於概念目的，這些術語將如下討論 -

• 到達時間 (AT) - 到達時間是指程序到達就緒佇列的時間。
• 突發時間 (BT) 或程序的 CPU 時間 - 突發時間是指特定程序完成執行所需的單位時間。
• 完成時間 (CT) - 完成時間是指程序終止的時間。
• 週轉時間 (TAT) - 從到達時間到完成時間的總時間稱為週轉時間。TAT 可以寫成，
• 等待時間 (WT) - 等待時間是指程序在等待分配時，前一個程序正在 CPU 中執行的時間。WT 寫成，

週轉時間 (TAT) = 完成時間 (CT) - 到達時間 (AT) 或 TAT = 突發時間 (BT) + 等待時間 (WT)

等待時間 (WT) = 週轉時間 (TAT) - 突發時間 (BT)

• 響應時間 (RT) - 響應時間是指 CPU 首次分配給特定程序的時間。
• 在非搶佔式排程的情況下，等待時間和響應時間通常相同。
• 甘特圖 - 甘特圖是一種視覺化工具，有助於專案中特定任務的排程和管理。在解決排程問題時使用它，瞭解程序如何在不同演算法中被分配。

問題 1

考慮下表，找到完成時間 (CT)、週轉時間 (TAT)、等待時間 (WT)、響應時間 (RT)、平均週轉時間和平均等待時間。

解決方案

甘特圖

對於此問題，CT、TAT、WT、RT 顯示在下表中 -

平均等待時間 = (9+8+0+4+12)/5 = 33/5 = 6.6 時間單位（時間單位可以視為毫秒）

平均週轉時間 = (11+14+4+11+16)/5 = 56/5 = 11.2 時間單位（時間單位可以視為毫秒）

問題 2

考慮下表，找到完成時間 (CT)、週轉時間 (TAT)、等待時間 (WT)、響應時間 (RT)、平均週轉時間和平均等待時間。

解決方案

甘特圖 -

對於此問題，CT、TAT、WT、RT 顯示在下表中 -

平均等待時間 = (0+0+2+4+8)/5 = 14/5 = 2.8 時間單位（時間單位可以視為毫秒）

平均週轉時間 = (2+1+5+9+13)/5 = 30/5 = 6 時間單位（時間單位可以視為毫秒）

*在空閒（非活動）CPU 期間，沒有程序被安排終止，因此在此期間它會保持一段時間空閒。

FCFS 排程的優點

• 它易於實現，因為它不包含任何複雜的方式。
• 每個任務都應同時執行，因為它遵循 FIFO 佇列。
• FCFS 不會優先考慮任何隨機的重要任務，因此它是一種公平的排程。

FCFS 排程的缺點

• FCFS 會導致車隊效應，這意味著如果突發時間較長的程序首先到達就緒佇列，那麼突發時間較短的程序可能會被阻塞，並且如果突發時間較長的任務永遠佔用時間，則突發時間較短的程序可能無法獲得 CPU。
• 如果突發時間長的程序首先排隊，那麼其他突發時間短的程序必須等待很長時間，因此它對於分時系統來說不是很好。
• 由於它是不可搶佔的，因此它不會在完全完成任務執行之前釋放 CPU。

*車隊效應和飢餓聽起來很相似，但略有不同，因此建議不要將這兩個術語視為相同的詞。

結論

儘管 FCFS 易於實現和理解，但 FCFS 不適合互動式系統，並且在現代作業系統中未使用。可以使用其他 CPU 排程搶佔式演算法（如“輪轉排程”）來防止 FCFS 中的車隊效應。