作業系統調度演算法：短作業優先（SJF）詳解

定義

短作業優先排程：從就緒佇列中選擇**預估執行時間（突發時間）最短**的行程/作業，分配 CPU 執行。

兩種模式

範例推演（非搶佔）

行程  到達時間  突發時間
P1    0         6
P2    1         4
P3    2         2
P4    3         3

執行順序：
t=0: P1 開始 (唯一就緒)
t=6: P1 結束，就緒佇列 {P2(4), P3(2), P4(3)} → 選 P3 (最短 2)
t=8: P3 結束，就緒 {P2(4), P4(3)} → 選 P4 (3)
t=11: P4 結束，執行 P2 (4)
t=15: 全結束

等待時間：P1=0, P2=10, P3=6, P4=8 → 平均 = 6.0
（若 FCFS：P1=0, P2=5, P3=8, P4=10 → 平均 = 5.75，此例 FCFS 較好，但 SJF 平均表現優於 FCFS）

關鍵挑戰

1. 預估執行時間： 實際系統無法知曉真實突發時間，常用**指數平均法**預估：
   τ(n+1) = α * T(n) + (1-α) * τ(n)，α ∈ [0,1]（典型 0.5），T(n) 為上次實際執行時間，τ(n) 為上次預估值。
2. 飢餓問題： 長作業可能永遠不被排程。解決：老化——隨等待時間增加動態提升優先權（priority = base + wait_time * factor）。
3. 搶佔開銷： SRTF 需頻繁上下文切換，實際系統常折衷用**多級回饋佇列（MLFQ）**近似 SJF 行為。

現代系統中的應用

• Linux CFS (Completely Fair Scheduler) 採用**虛擬執行時間**排序，近似 SJF 精神（短任務得高優先權）。
• 雲端批次作業排程（Kubernetes Batch, Spark, Flink）常用 SJF/最短剩餘時間優先，減少作業完成時間（JCT）。
• 資料庫查詢優化器：估算執行成本，優先執行低成本查詢。

總結

SJF 是**平均等待時間理論最優**的排程演算法（非搶佔式對所有到達時間相同時；搶佔式 SRTF 對任意到達時間）。實際部署需解決**執行時間預估、飢餓防護、搶佔開銷**三大工程問題，常以 MLFQ、CFS 等近似實現取代純 SJF。