??進(jìn)程的調(diào)度方式有兩種：非剝奪調(diào)度方式（非搶占式）和剝奪調(diào)度方式（搶占方式）。
??非搶占式：只允許進(jìn)程主動(dòng)放棄處理機(jī)宙暇。如進(jìn)程運(yùn)行結(jié)束输枯、異常結(jié)束或主動(dòng)請(qǐng)求I/O阻塞。在運(yùn)行的過(guò)程中即使有更緊迫的任務(wù)到達(dá)占贫，當(dāng)前進(jìn)程依然會(huì)繼續(xù)使用處理機(jī)桃熄，直到該進(jìn)程終止或主動(dòng)要求進(jìn)入阻塞態(tài)。
??搶占式：當(dāng)一個(gè)進(jìn)程正在處理機(jī)上執(zhí)行時(shí)型奥，如果有一個(gè)更重要更緊迫的進(jìn)程需要處理機(jī)瞳收，則立即暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分配給更重要更緊迫的那個(gè)進(jìn)程厢汹。
??下面介紹適用于早期操作系統(tǒng)幾種進(jìn)程調(diào)度的算法

1 先來(lái)先服務(wù)算法（FCFS,First Come First Service）

??先來(lái)先服務(wù)（FCFS）：按照到達(dá)的先后順序調(diào)度螟深，事實(shí)上就是等待時(shí)間越久的越優(yōu)先得到服務(wù)。
??下面表示按照先來(lái)先服務(wù)算法的執(zhí)行順序

??計(jì)算進(jìn)程的幾個(gè)衡量指標(biāo)：

周轉(zhuǎn)時(shí)間 = 完成時(shí)間 – 到達(dá)時(shí)間????P1=7-0=7???? P2=11-2=9????P3=12-4=8????P4=16-5=11
帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/運(yùn)行時(shí)間????P1=7/7=1?
???P2=9/4=2.25????P3=8/1=8????P4=11/4=2.75
等待時(shí)間=周轉(zhuǎn)時(shí)間 - 運(yùn)行時(shí)間 ????P1=7-7=0???? P2=9-4=5????P3=8-1=7????P4=11-4=7
平均周轉(zhuǎn)時(shí)間=(7+9+8+11)/4=8.75
平均帶權(quán)周轉(zhuǎn)時(shí)間=(1+2.25+8+2.75)/4=3.5
平均等待時(shí)間=(0+5+7+7)/4=4.75

2 短作業(yè)優(yōu)先算法（SJF,Shortest Job First）

??短作業(yè)優(yōu)先算法是非搶占式的算法烫葬，但是也有搶占式的版本——最短剩余時(shí)間優(yōu)先算法（STRN,Shortest Remaining Time Next）界弧。
??用于進(jìn)程的調(diào)度算法稱為短進(jìn)程優(yōu)先調(diào)度算法（SPF,Shortest Process First）。

?? 2.1非搶占式的短作業(yè)優(yōu)先調(diào)度算法

??短作業(yè)/進(jìn)程優(yōu)先調(diào)度算法：每次調(diào)度時(shí)選擇當(dāng)前已到達(dá)且運(yùn)行時(shí)間最短的作業(yè)/進(jìn)程.搭综。

??因?yàn)檫M(jìn)程1最先達(dá)到垢箕，此時(shí)沒(méi)有其他線程，所以進(jìn)程1先被服務(wù)兑巾。當(dāng)進(jìn)程1運(yùn)行完后条获，進(jìn)程2和3已經(jīng)到達(dá)，此時(shí)進(jìn)程3需要的運(yùn)行時(shí)間比進(jìn)程2少蒋歌，所以進(jìn)程3先被服務(wù)…
??計(jì)算進(jìn)程的幾個(gè)衡量指標(biāo)：

周轉(zhuǎn)時(shí)間 = 完成時(shí)間 – 到達(dá)時(shí)間???? P1=7-0=7 ???? P2=12-2=10 ???? P3=8-4=4???? P4=16-5=11
帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/運(yùn)行時(shí)間???? P1=7/7=1 ???? P2=10/4=2.5???? P3=4/1=4???? P4=11/4=2.75
等待時(shí)間=周轉(zhuǎn)時(shí)間 - 運(yùn)行時(shí)間???? P1=7-7=0 ???? P2=10-4=6????P3=4-1=3???? P4=11-4=7
平均周轉(zhuǎn)時(shí)間=(7+10+4+11)/4=8 8.75
平均帶權(quán)周轉(zhuǎn)時(shí)間=(1+2.5+4+2.75)/4=2.56 ??????3.5（先來(lái)先服務(wù)的平均帶權(quán)周轉(zhuǎn)時(shí)間）
平均等待時(shí)間=(0+6+3+7)/4=4

?? 2.2 搶占式的短作業(yè)優(yōu)先調(diào)度算法——最短剩余時(shí)間優(yōu)先算法

??最短剩余時(shí)間優(yōu)先算法：每當(dāng)有進(jìn)程加入就緒隊(duì)列改變時(shí)就需要調(diào)度帅掘，如果新到達(dá)的進(jìn)程的所需的運(yùn)行時(shí)間比當(dāng)前運(yùn)行的進(jìn)程剩余時(shí)間更短，則由新進(jìn)程搶占處理機(jī)堂油，當(dāng)前運(yùn)行進(jìn)程重新回到就緒隊(duì)列修档。此外，當(dāng)一個(gè)進(jìn)程完成時(shí)也需要調(diào)度府框。

當(dāng)有新的進(jìn)程達(dá)到就緒隊(duì)列和存在進(jìn)程完成時(shí)萍悴，需要調(diào)度，Pn(m)表示當(dāng)>前Pn進(jìn)程的剩余時(shí)間寓免，加粗表示當(dāng)前調(diào)度下獲取處理機(jī)的進(jìn)程：
0時(shí)刻（P1到達(dá)）：P₁(7)
2時(shí)刻（P2到達(dá)）：P₁(5)癣诱、P₂(4)
4時(shí)刻（P3到達(dá)）：P₁(5)、P₂(2)袜香、P₃(1)
5時(shí)刻（P3完成且P4剛好達(dá)到）：P₁(5)撕予、P₂(2)、P₄(4)
7時(shí)刻（P2完成）：P₁(5) 蜈首、P₄(4)
11時(shí)刻（P4完成）：P₁(5)
16時(shí)刻（P1完成）
周轉(zhuǎn)時(shí)間 = 到達(dá)時(shí)間 – 運(yùn)行時(shí)間 ????P1 = 16-0=16 ????P2=7-2=5 ????P3=5-4=1???? P4=11-5=6
帶權(quán)周轉(zhuǎn)時(shí)間 = 周轉(zhuǎn)時(shí)間/運(yùn)行時(shí)間???? P1=16/7=2.28???? P2=5/4-1.25 ????P3=1/1=1 ????P4=6/4=1.5
等待時(shí)間 = 周轉(zhuǎn)時(shí)間 – 運(yùn)行時(shí)間 ????P1=16-7=9 ????P2=5-4=1????P3=1-1=0 ????P4=6-4=2
平均周轉(zhuǎn)時(shí)間=(16+6+1+6)/4=7
平均帶權(quán)周轉(zhuǎn)時(shí)間=(2.28+1.25+1+1.5)/4=1.50
平均等待時(shí)間=(9+1+0+2)/4=3

通過(guò)比較上面三組的平均周轉(zhuǎn)時(shí)間实抡、平均帶權(quán)周轉(zhuǎn)時(shí)間和平均等待時(shí)間可以看出，短作業(yè)優(yōu)先算法可以減少進(jìn)程的等待時(shí)間欢策，對(duì)短作業(yè)有利吆寨。

3 高響應(yīng)比優(yōu)先（HRRN,Highest Response Ratio Next）算法

??高響應(yīng)比優(yōu)先算法：非搶占式的調(diào)度算法，只有當(dāng)前運(yùn)行的進(jìn)程主動(dòng)放棄CPU時(shí)（正常/異常完成踩寇、或主動(dòng)阻塞）啄清，才需要進(jìn)行調(diào)度，調(diào)度時(shí)計(jì)算所有就緒進(jìn)程的相應(yīng)比俺孙，選響應(yīng)比最高的進(jìn)程上處理機(jī)辣卒。

??響應(yīng)比 = （等待時(shí)間 + 運(yùn)行時(shí)間）/ 運(yùn)行時(shí)間

0時(shí)刻：只有P1到達(dá)就緒隊(duì)列，P1上處理機(jī)睛榄。
7時(shí)刻（P1主動(dòng)放棄CPU）：就緒隊(duì)列中有P2荣茫、P3和P4，它們的響應(yīng)比分別為P2=(5+4)/4=2.25 P3=(3+1)/1=4 P4=(2+4)/4=1.5场靴，所以P3上處理機(jī)啡莉。
8時(shí)刻（P3完成）：P2=(6+4)/4=2.5 P4=(3+4)/4=1.75
12時(shí)刻（P2完成）：就緒隊(duì)列中只剩下P4。

4 三種調(diào)度算法的比較

??上面的三種調(diào)度算法一般適用于早期的批處理系統(tǒng)泞边，沒(méi)有考慮響應(yīng)時(shí)間也不區(qū)分任務(wù)的緊急程度该押。因此對(duì)用戶來(lái)說(shuō)交互性差。

??本文完

??如發(fā)現(xiàn)錯(cuò)誤阵谚，請(qǐng)指正２侠瘛！梢什！