SJF短作業(yè)優(yōu)先算法

算法思想： 追求更少的平均時間，最少的平均周轉(zhuǎn)時間，最少的平均平均帶權(quán)周轉(zhuǎn)時間
算法規(guī)則： 最短的作業(yè)/進程優(yōu)先得到服務(wù)（所謂“最短”，是指要求服務(wù)時間最短）
用于作業(yè)/進程調(diào)度： 即可用于作業(yè)調(diào)度，也可用于進程調(diào)度。用于進程調(diào)度時稱為“短進程優(yōu)先（SPF，Shortest Process First）算法”
是否可搶占？： SJF和SPF都是非搶占式的算法。但是也有搶占式的版本----最短剩余時間優(yōu)先算法。（SRTN,Shortest Remaining Time Next）
優(yōu)點： "最短的"平均等待時間、平均周轉(zhuǎn)時間
缺點： 不公平。對短作業(yè)有利，對長作業(yè)不利。可能產(chǎn)生==饑餓現(xiàn)象。==另外，進程/作業(yè)的運行時間都是由用戶提供的，并不一定真實，不一定能做到真正的短作業(yè)優(yōu)先。
饑餓： 會導(dǎo)致饑餓

例題
例題：各進程到達就緒隊列的時間、需要的運行時間如下所示，使用非搶占式的短作業(yè)優(yōu)先調(diào)度算法，計算各進程的等待時間、平均等待時間、周轉(zhuǎn)時間、平均周轉(zhuǎn)時間、帶權(quán)周轉(zhuǎn)時間、平均帶權(quán)周轉(zhuǎn)時間

進程到達時間運行時間

p1	0	7
p2	2	4
p3	4	1
p1	5	4

短作業(yè)/進程優(yōu)先調(diào)度算法：每次調(diào)度選擇當前已到達且運行時間最短的作業(yè)/進程。
經(jīng)過簡單的分析之后，可以知道調(diào)度順序為p1–>p3–>p2–>p4

下面我們來用最短剩余時間來考慮：

進程到達時間運行時間

p1	0	7
p2	2	4
p3	4	1
p1	5	4

最短剩余時間優(yōu)先算法：每當有進程加入就緒隊列改變時就需要調(diào)度，如果新到達的進程剩余時間比當前運行的進程剩余時間更短，則由新進程搶占處理機，當前運行進程重新回到就緒隊列。另外,當一個進程完成時也需要調(diào)度。

需要注意的是，當有新進程到達時就緒隊列就會改變，就要按照上述規(guī)則就行檢查。以下p_n(m)表示當前p_n進程剩余時間為m。每個時刻的情況如下
(我們用黃色表示這個時刻剩余時間最短的進程)

• 0時刻（p1到達）：p₁(7)
• 2時刻（p2到達）：p₁(5) 、 p₂(4)
• 4時刻（p3到達）：p₁(5)、p₂（2）、p₃(1)
• 5時刻(p3完成且p4剛好到達)：p₁(5)、p₂（2）、p₄(4)
• 7時刻（p2完成）：p₁(5)、=p₄(4)
• 11時刻（p4完成）：p₁(5)
• 16時刻（p1完成）：結(jié)束

周轉(zhuǎn)時間=完成時間-到達時間
帶權(quán)周轉(zhuǎn)時間=周轉(zhuǎn)時間 / 運行時間
等待時間=周轉(zhuǎn)時間- 運行時間

周轉(zhuǎn)時間	p1=16-0=16	p2=7-2=5	p3=5-4=1	p4=11-5=6
帶權(quán)周轉(zhuǎn)時間	p1=16/7=2.28	p2=5/4=1.25	p3=1/1=1	p4=6/4=1.5
等待轉(zhuǎn)時間	p1=16-7=9	p2=5-4=1	p3=1-1=0	p4=6-4=2

平均周轉(zhuǎn)時間=（16+5+1+6）/4=7
平均帶權(quán)周轉(zhuǎn)時間=(2.28+1.25+1+1.5)/4=1.5
平均等待時間=(9+1+0+2)/4=3

總結(jié)

以上是生活随笔為你收集整理的SJF调度算法（操作系统）短作业优先和最短剩余时间优先的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。