CPU 排程

先到先服務排程(first-come, first-served)

/ FCFS /

這就是銀行排隊那種公平:誰先排到就先服務誰,一路到底,不准插隊。先到先服務(FCFS)排程對行程做的正是這件事——就緒佇列是一個單純的先進先出(FIFO)清單,CPU 嚴格依行程變為就緒的順序交給它們。

它的運作方式:當一個行程變為就緒時,它加入佇列尾端;排程器總是挑佇列最前面的行程,讓它一路執行到它那段 CPU 爆發結束才換下一個。FCFS 是非先佔式的——一個行程一旦開始,就保有 CPU 直到它阻塞或完成。它是能想到最簡單的排程器:實作極其容易,而且顯然不會有飢餓,因為每個工作終究會排到最前面。

不過它的缺點很嚴重。由於工作一旦開始就執行到完成,排在最前面的一個長工作會讓它後面每個短工作都等上那整段長時間——這就是護航效應,它能毀掉平均等待時間與反應時間。FCFS 對互動使用也表現不佳,因為一個 CPU 密集的工作能霸著處理器,而快速的 I/O 密集工作在它後面堆積。在通用系統中它很少單獨使用,但常作為更精巧排程器內部的「平手裁決」規則。

幾個工作幾乎同時抵達:依序為 P1 需 24 毫秒、P2 需 3 毫秒、P3 需 3 毫秒。FCFS 給出的等待時間是 0、24、27,平均 17 毫秒。若兩個短工作先跑,平均會低得多——FCFS 完全任憑抵達順序擺佈。

FCFS 公平且不會飢餓,但排在最前面的一個長工作會懲罰它後面的所有人。

FCFS 不會飢餓,卻有公平性問題:它在「順序」上公平,但在「等待時間」上極不公平,因為一個短工作可能在長工作後面等上遠超過它自身長度的時間。

又稱
FCFSFIFO scheduling先進先出排程