CPU 排程

護航效應(convoy effect)

想像單線道上一輛慢吞吞的卡車擋在前頭:一排快車堆在後面無法超車,全被迫以卡車的速度爬行。排程中的護航效應正是如此——在先到先服務下,佇列最前面一個長而 CPU 密集的行程握著 CPU,許多短行程在它後面擠成一團,全卡著等這個慢郎中做完。

讓它比聽起來更糟的機制是這樣。假設一個大運算和好幾個快速的 I/O 密集工作在 FCFS 下共用 CPU。大工作搶到 CPU 並跑了很久。小工作們等著,接著各拿到一小段 CPU 爆發、迅速跑去做 I/O。與此同時,大工作從它自己的 I/O 回來後,可能又搶到它們前面,於是模式重演:小工作不斷在大工作後面集結。CPU 與 I/O 裝置最終都使用不足,因為所有人都被同步到那個慢行程上。

為什麼重要:護航效應是反對單純 FCFS 的頭號論據,也是先佔與偏好短工作的動機。輪轉排程藉由迫使長工作在一段配量後讓出而打破它;最短工作優先則藉由不讓長工作先跑而避免它。認出這個模式——短任務被一個握著共享資源的長者卡住——在 CPU 排程之外也會出現,例如並行程式中一個遲遲不放鎖的持鎖者。

一個 100 毫秒的 CPU 密集工作排在最前面;後面是十個各需 1 毫秒 CPU 的 I/O 密集工作。在 FCFS 下,每個短工作都要等約 100 毫秒才輪到它那 1 毫秒——它們被護航在巨人後面。改用配量 10 毫秒的輪轉,每個短工作反而在前幾段配量內就能執行。

FIFO 佇列最前面一個長工作,把它後面的所有人都拖慢到它的速度。

護航效應並非由長工作「長」所造成——而是由 FCFS 不先佔、讓它執行到完成所造成。加入先佔(輪轉)後,護航隊就散了。