先來先服務排程演算法 (FCFS)

---

在多道程式設計中，需要對CPU進行排程，以便能夠在更短的時間內或同時執行多個任務。透過CPU排程，決定就緒佇列中哪個程序應該分配到CPU。因此，存在許多CPU排程演算法來排程CPU。先來先服務 (FCFS) 排程是其中一種CPU排程演算法。

先來先服務 (FCFS) 排程演算法 (FIRST-COME, FIRST-SERVED)

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

FCFS 排程的現實生活例子

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

FCFS 排程數學示例

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

• 到達時間 (AT) - 到達時間是指程序到達就緒佇列的時間。

• 突發時間 (BT) 或程序的CPU時間 - 突發時間是特定程序完成執行所需的時間單位。

• 完成時間 (CT) - 完成時間是指程序終止的時間。

• 週轉時間 (TAT) - 從到達時間到完成時間的總時間稱為週轉時間。TAT可以寫成：

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

• 等待時間 (WT) - 等待時間是指程序在等待分配CPU時，前一個程序正在CPU上執行的時間。WT可以寫成：

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

• 響應時間 (RT) - 響應時間是指CPU第一次分配給特定程序的時間。

  在非搶佔式排程中，等待時間和響應時間通常相同。

• 甘特圖 - 甘特圖是一種視覺化工具，有助於在專案中排程和管理特定任務。它在解決排程問題時使用，用於概念化程序如何在不同演算法中被分配。

問題 1

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

程序 ID	到達時間	突發時間
P1	2	2
P2	5	6
P3	0	4
P4	0	7
P5	7	4

解答

甘特圖

對於這個問題，CT、TAT、WT、RT顯示在下表中：

程序 ID	到達時間	突發時間	CT	TAT=CT-AT	WT=TAT-BT	RT
P1	2	2	13	13-2= 11	11-2= 9	9
P2	5	6	19	19-5= 14	14-6= 8	8
P3	0	4	4	4-0= 4	4-4= 0	0
P4	0	7	11	11-0= 11	11-7= 4	4
P5	7	4	23	23-7= 16	16-4= 12	12

平均等待時間 = (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)、平均週轉時間和平均等待時間。

程序 ID	到達時間	突發時間
P1	2	2
P2	0	1
P3	2	3
P4	3	5
P5	4	5

解答

甘特圖：

對於這個問題，CT、TAT、WT、RT顯示在下表中：

程序 ID	到達時間	突發時間	CT	TAT=CT-AT	WT=TAT-BT	RT
P1	2	2	4	4-2= 2	2-2= 0	0
P2	0	1	1	1-0= 1	1-1= 0	0
P3	2	3	7	7-2= 5	5-3= 2	2
P4	3	5	12	12-3= 9	9-5= 4	4
P5	4	5	17	17-4= 13	13-5= 8	8

平均等待時間 = (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中的車隊效應。