sjf

SJF算法是以進入系統的作業所要求的CPU時間為標準，是指對短作業或者短進程優先調度的算法，將每個進程與其估計運行時間進行關聯選取估計計算時間最短的作業投入運行。

基本介紹

• 外文名：sjf
• 定義：最短作業優先算法
• 全名：SJF算法
• 屬性：算法

算法優缺點

最短作業優先算法SJF

SJF(Shortest Job First )

SJF算法的優缺點：

算法易於實現。但效率不高，主要弱點是忽視了作業等待時間;會出現飢餓現象。

SJF算法與FCFS算法的比較：

SJF的平均作業waiting time比FCFS要小，故它的調度性能比FCFS好。

SJF調度算法的問題：

實現SJF調度算法需要知道作業所需運行時間，否則調度就沒有依據，要精確知道一個作業的運行時間是辦不到的。

SJF是一種Non-preemptive（非搶占式）調度。

與SJF類似的一種preemptive 版本的調度叫shortest－remaining－time－first。

SJF是一種優先調度（priority scheduling），優先的是inverse of 預測的下一個中央處理器突發時間。

SJF調度算法是被證明了的最佳調度算法，這是因為對於給定的一組進程，SJF算法的平均周轉時間最小。通過將短進程移到長進程之前，短進程等待時間的減少大於長進程等特時間的增加，因此，平均等特時間減少了。

例如，有一組進程p1、p2、p3和p4，在0時刻到達，運行時間依次為6ms8ms.7ms.3ms.採用SF調度就能得到如圖1所示的調度結果，因此，平均周轉時間為w=(3+9+16+24)/4=13ms.如果使用FCFS調度方案，那么，平均周轉時間w=(6+14+21+24)4=16.25ms.

圖1

SJF調度算法

從上面的例子可以看出，SJF算法能有效地降低作業的平均等待時間，提高系統吞吐量。但是也存在一些不容忽視的缺點。

(1)長作業(進程)有可能被餓死。在有短作業(進程)持續不斷存在的情況下，由於調度程式總是優先調度那些(即使是後進來的)短作業(進程)，將導致長作業(進程)長期得不到調度而餓死

(2)缺少剝奪機制，不適用於分時系統或互動式事務處理環境。

(3)無法準確知道作業進程)的確切執行時間，致使該算法不一定能真正做到短作業優先調度。