2.2_5 調度算法

文章目錄

2.2_5 調度算法
一、適用于早期的批處理系統
- （一）先來先服務（FCFS，First Come First Serve）
- （二）短作業優先（SJF，Shortest Job First）
- （三）高響應比優先（HRRN，Highest Response Ratio Next）
總結
二、適用于交互式系統
- （一）時間片輪轉（RR，Round-Robin）
- （二）優先級調度算法
- （三）多級反饋隊列調度算法
總結
三、多級隊列調度算法

2.2_5 調度算法

注意：各種調度算法的學習思路如下。

1.算法思想

2.算法規則

3.這種調度算法是用于作業調度還是進程調度？

4.搶占式 or 非搶占式？

5.優點 or 缺點？

6.是否會導致饑餓

饑餓：指某進程/作業長期得不到服務。

一、適用于早期的批處理系統

（一）先來先服務（FCFS，First Come First Serve）

FCFS

1.算法思想

??主要從“公平”的角度考慮。（類似于我們生活中排隊買東西的例子）

2.算法規則

??按照作業/進程到達的先后順序進行服務

3.用于作業/進程調度

??用于作業調度時，考慮的是哪個作業先到達后備隊列；用于進程調度時，考慮的是哪個進程先到達就緒隊列。

4.是否可搶占？

??非搶占式的算法

5.優缺點

??優點：公平、算法實現簡單

??缺點：排在長作業（進程）后面的短作業需要等待很長時間，帶權周轉時間很大，對短作業來說用戶體驗不好。即，FCFS算法對長作業有利，對短作業不利。

6.是否會導致饑餓

??不會。

例子

??各進程到達就緒隊列的時間、需要的運行時間如下表所示。使用先來先服務調度算法，計算各進程的等待時間、平均等待時間、周轉時間、平均周轉時間、帶權周轉時間、平均帶權周轉時間。

進程	到達時間	運行時間
P1	0	7
P2	2	4
P3	4	1
P4	5	4

??先來先服務算法：按照到達的先后順序調度，事實上就是等待時間越久的越優先得到服務。

??因此，調度順序為：P1 —> P2 —> P3 —> P4。

答：

??1.周轉時間 = 完成時間 - 到達時間

P1=7-0=7；P2=11-2=9；P3=12-4=8；P4=16-5=11

??2.帶權周轉時間 = 周轉時間 / 運行時間

P1=7/7=1；P2=9/4=2.25；P3=8/1=8；P4=11/4=2.75

注意：帶權周轉時間就是周轉時間是實際運行時間的多少倍。而P3這個進程的帶權周轉時間是8，也就意味著P3這個用戶的體驗其實是非常糟糕的。

??3.等待時間 = 周轉時間 - 運行時間

注：對本題而言，可以這樣計算等待時間。原因在于，本題中的進程都是純計算型（即：只需要CPU）的進程，一個進程到達后要么在等待、要么在運行。如果是又有計算、又有I/O操作的進程，其等待時間就是周轉時間 - 運行時間 - I/O操作的時間。

P1=7-7=0；P2=9-4=5；P3=8-1=7；P4=11-4=7

??4.平均周轉時間 = (7+9+8+11) / 4 = 8.75

??5.平均帶權周轉時間 = (1+2.25+8+2.75) / 4 = 3.5

??6.平均等待時間 = (0+5+7+7) / 4 = 4.75

（二）短作業優先（SJF，Shortest Job First）

SJF

1.算法思想

??追求最少的平均等待時間，最少的平均周轉時間，最少的平均帶權周轉時間。

2.算法規則

??最短的作業/進程優先得到服務（所謂“最短”，是指要求服務時間最短）

3.用于作業/進程調度

??既可用于作業調度，也可用于進程調度。

??但用于進程調度時，名稱要換一下，稱為“短進程優先（SPF，Shortest Process First）算法”。

4.是否可搶占？

??SJF和SPF是非搶占式的算法。

??但是也有搶占式的版本——最短剩余時間優先算法（SRTN，Shortest Remaining Time Next）。

5.優缺點

??優點：“最短的”平均等待時間、平均周轉時間

??缺點：不公平。對短作業有利，對長作業不利。可能產生饑餓現象。另外，作業/進程的運行時間是由用戶提供的，并不一定真實，不一定能做到真正的短作業優先。

6.是否會導致饑餓

??會。如果源源不斷地有短作業/進程到來，可能使長作業/進程長時間得不到服務，產生“饑餓”現象。如果一直得不到服務，則稱為“餓死”。

例子1

??各進程到達就緒隊列的時間、需要的運行時間如下表所示。使用非搶占式的短作業優先調度算法，計算各進程的等待時間、平均等待時間、周轉時間、平均周轉時間、帶權周轉時間、平均帶權周轉時間。

注：嚴格來說，用于進程調度，它的算法名稱應該叫做“短進程優先調度算法（SPF）”，不用在意這個細節，算法本質都是一樣的。

進程	到達時間	運行時間
P1	0	7
P2	2	4
P3	4	1
P4	5	4

??短作業/進程優先調度算法：每次調度時選擇當前已到達且運行時間最短的作業/進程。

??因此，調度順序為：P1 —> P3 —> P2 —> P4。

答：

??1.周轉時間 = 完成時間 - 到達時間

P1=7-0=7；P3=8-4=4；P2=12-2=10；P4=16-5=11

??2.帶權周轉時間 = 周轉時間 / 運行時間

P1=7/7=1；P3=4/1=4；P2=10/4=2.5；P4=11/4=2.75

??3.等待時間 = 周轉時間 - 運行時間

P1=7-7=0；P3=4-1=3；P2=10-4=6；P4=11-4=7

??4.平均周轉時間 = (7+4+10+11) / 4 = 8

??5.平均帶權周轉時間 = (1+4+2.5+2.75) / 4 = 2.56

??6.平均等待時間 = (0+3+6+7) / 4 = 4

注意：對比FCFS算法的結果，顯然SPF算法的平均等待/周轉/帶權周轉時間都要更低。

例子2

??各進程到達就緒隊列的時間、需要的運行時間如下表所示。使用搶占式的短作業優先調度算法，計算各進程的等待時間、平均等待時間、周轉時間、平均周轉時間、帶權周轉時間、平均帶權周轉時間。

注：搶占式的短作業優先算法又稱“最短剩余時間優先算法”（SRTN）

進程	到達時間	運行時間
P1	0	7
P2	2	4
P3	4	1
P4	5	4

??最短剩余時間優先算法：每當有進程加入就緒隊列改變時就需要調度，如果新到達的進程剩余時間比當前運行的進程剩余時間更短，則由新進程搶占處理機，當前運行進程重新回到就緒隊列。另外，當一個進程完成時也需要調度（即：一個進程主動放棄處理機的時候）。

??需要注意的是，當有新進程到達時就緒隊列就會改變，就要按照上述規則進行檢查。

??以下Pn(m)表示當前Pn進程剩余時間為m。各個時刻的情況如下：

??0時刻（P1到達）：P1(7)

??2時刻（P2到達）：P1(5)、P2(4)

??4時刻（P3到達）：P1(5)、P2(2)、P3(1)

??5時刻（P3完成且P4剛好到達）：P1(5)、P2(2)、P4(4)

??7時刻（P2完成）：P1(5)、P4(4)

??11時刻（P4完成）：P1(5)

答：

??1.周轉時間 = 完成時間 - 到達時間

P1=16-0=16；P2=7-2=5；P3=5-4=1；P4=11-5=6

??2.帶權周轉時間 = 周轉時間 / 運行時間

P1=16/7=2.28；P2=5/4=1.25；P3=1/1=1；P4=6/4=1.5

??3.等待時間 = 周轉時間 - 運行時間

P1=16-7=9；P2=5-4=1；P3=1-1=0；P4=6-4=2

??4.平均周轉時間 = (16+5+1+6)/4 = 7

??5.平均帶權周轉時間 = (2.28+1.25+1+1.5)/4 = 1.50

??6.平均等待時間 = (9+1+0+2)/4 = 3

注意：對比非搶占式的短作業優先算法，顯然搶占式的這幾個指標又要更低

??對于“短作業優先”，注意幾個小細節：

??1.如果題目中未特別說明，所提到的“短作業/進程優先算法”默認是非搶占式的。

??2.很多書上都會說“SJF調度算法的平均等待時間、平均周轉時間最少”。

??嚴格來說，這個表述是錯誤的、不嚴謹的。之前的例子已經表明，最短剩余時間優先算法得到的平均等待時間、平均周轉時間還要更少。

??因此，嚴謹來說，應該說“搶占式的短作業/進程優先調度算法（最短剩余時間算法，SRNT算法）的平均等待時間、平均周轉時間最少”。

??或者加上前提條件（從而削弱搶占式的優勢），說：“在所有進程同時可運行時（或：在所有進程都幾乎同時到達時），采用SJF調度算法的平均等待時間、平均周轉時間最少”。

??3.雖然嚴格來說，SJF的平均等待時間、平均周轉時間并不一定最少，但相比于其他算法，SJF依然可以獲得較少的平均等待時間、平均周轉時間。

??4.如果選擇題中遇到“SJF算法的平均等待時間、平均周轉時間最少”的選項，那最好先判斷其他選項是不是有很明顯的錯誤，靈活做出判斷。

（三）高響應比優先（HRRN，Highest Response Ratio Next）

??對FCFS和SJF兩種算法的思考：

??1.FCFS算法是在每次調度的時候選擇一個等待時間最長的作業（進程）為其服務。但是沒有考慮到作業的運行時間，因此導致了對短作業不友好的問題。

??2.SJF算法是選擇一個執行時間最短的作業為其服務。但是又完全不考慮各個作業的等待時間，因此導致了對長作業不友好的問題，甚至還會造成饑餓問題。

??那么，能不能設計一個算法，既考慮到各個作業的等待時間，也能兼顧運行時間呢？——高響應比優先算法。

1.算法思想

??要綜合考慮作業/進程的等待時間和要求服務的時間。

2.算法規則

??在每次調度時先計算各個作業/進程的響應比，選擇響應比最高的作業/進程為其服務。
$響應比=\frac{等待時間+要求服務時間}{要求服務時間}$

注：由公式可見，響應比≥1。

3.用于作業/進程調度

??既可以用于作業調度，也可用于進程調度。

4.是否可搶占？

??非搶占式的算法。因此只有當前運行的作業/進程主動放棄處理機時，才需要調度，才需要計算響應比。

5.優缺點

??綜合考慮了等待時間和運行時間（要求服務時間）。

??等待時間相同時，要求服務時間短的優先（SJF的優點）。

??要求服務時間相同時，等待時間長的優先（FCFS的優點）。

??對于長作業來說，隨著等待時間越來越久，其響應比也會越來越大，從而避免了長作業饑餓的問題。

6.是否會導致饑餓

??不會。

例子

??各進程到達就緒隊列的時間、需要的運行時間如下表所示。使用高響應比優先調度算法，計算各進程的等待時間、平均等待時間、周轉時間、平均周轉時間、帶權周轉時間、平均帶權周轉時間。

進程	到達時間	運行時間
P1	0	7
P2	2	4
P3	4	1
P4	5	4

??高響應比優先算法：非搶占式的調度算法，只有當前運行的進程主動放棄CPU時（正常/異常完成，或主動阻塞），才需要進行調度，調度時計算所有就緒進程的響應比，選響應比最高的進程上處理機。
$響應比=\frac{等待時間+要求服務時間}{要求服務時間}$

答：

??0時刻：只有P1到達就緒隊列，P1上處理機

??7時刻（P1主動放棄CPU）：就緒隊列中有P2(響應比=(5+4)/4=2.25)、P3((3+1)/1=4)、P4((2+4)/4=1.5)

注意：從嚴格的計算結果來比較，沒問題。但也可以從公式理解的方面去考慮，而不必計算出具體結果。如，在7時刻想要比較P2和P4的響應比，應該注意到，P2和P4要求服務的時間一樣，但P2此時等待時間長，因此必然是P2的響應比更大。

??8時刻（P3完成）：P2(2.5)、 P4(1.75)

??12時刻（P2完成）：就緒隊列中只剩下P4

總結

注意：這幾種算法主要關心對用戶的公平性、平均周轉時間、平均等待時間等評價系統整體性能的指標，但是不關心“響應時間”，也并不區分任務的緊急程度，因此對用戶來說，交互性很糟糕。因此這三種算法一般適合用于早期的批處理系統。當然，FCFS算法也常結合其他的算法使用，在現在也扮演著很重要的角色。

早期的計算機CPU也比較昂貴，因此主要注重的是系統整體性能表現，并不注重用戶感受，也是情有可原的。

??而適合用于交互式系統的調度算法將在后面介紹。

二、適用于交互式系統

（一）時間片輪轉（RR，Round-Robin）

1.算法思想

??公平地、輪流地為各個進程服務，讓每個進程在一定時間間隔內都可以得到響應。

??其實是伴隨著分時操作系統出現的一種思想。

2.算法規則

??按照各進程到達就緒隊列的順序，輪流讓各個進程執行一個時間片（如100ms）。若進程未在一個時間片內執行完，則剝奪處理機，將進程重新放到就緒隊列隊尾重新排隊。

??時間片的長短，具體看系統，有的系統長、有的系統短，甚至有的系統的時間片長短是動態調整的。

3.用于作業/進程調度

??用于進程調度。

??因為所謂“時間片”，指的是處理機的時間片，而一個作業只有被放入內存并建立相關PCB后，只有作為進程，它才有可能被分配處理機的時間片。

4.是否可搶占

??若進程未能在時間片內運行完，將被強行剝奪處理機使用權，因此時間片輪轉調度算法屬于搶占式的算法。由時鐘裝置發出時鐘中斷來通知CPU時間片已到。

5.優缺點

??優點：公平；響應快，適用于分時操作系統。

??缺點：由于高頻率的進程切換，因此有一定開銷；不區分任務的緊急程度。

6.是否會導致饑餓

??不會。

7.補充

??時間片太大或太小，分別會造成影響。時間片太大，會使進程響應時間過長；時間片太小，會使進程切換的開銷占比過大。

例子

??各進程到達就緒隊列的時間、需要的運行時間如下表所示。使用時間片輪轉調度算法，分析時間片大小分別是2、5時的進程運行情況。

??注意：“時間片輪轉”常用于分時操作系統，更注重“響應時間”，因而此處不計算周轉時間等指標。

進程	到達時間	運行時間
P1	0	5
P2	2	4
P3	4	1
P4	5	6

答1：

??時間片大小為2時。

??注：以下括號內表示當前時刻就緒隊列中的進程，以及進程的剩余時間。用箭頭表示隊列，左邊是隊頭、右邊是隊尾

??0時刻（P1(5)）：0時刻只有P1到達就緒隊列，讓P1上處理機運行一個時間片。

??2時刻（P2(4) —> P1(3)）：2時刻P2到達就緒隊列，P1運行完一個時間片，被剝奪處理機，重新放到隊尾。

??此時P2排在隊頭，因此讓P2上處理機。

??注意：2時刻，P1下處理機，同一時刻新進程P2到達，如果在題目中遇到這種情況，默認新到達的進程先進入就緒隊列。

??4時刻（P1(3) —> P3(1) —> P2(2)）：4時刻，P3到達，先插到就緒隊尾，緊接著，P2下處理機也插到隊尾。

??5時刻（P3(1) —> P2(2) —> P4(6)）：5時刻，P4到達插到就緒隊尾（注意：由于P1的時間片還沒用完，因此暫時不調度。另外，此時P1處于運行態，并不在就緒隊列中）

??說明：

??1.之所以討論5時刻時的情況，是因為在這一時刻，P4進程到達了。

??2.但是在5時刻，P1只運行了1單位的時間，時間片還沒有用完。因此P1還處于執行狀態，并不會被剝奪處理機，因此P1并不會出現在就緒隊列當中。

??3.接下來P1會把自己的時間片執行完，即6時刻的時候，再繼續討論。

??6時刻（P3(1) —> P2(2) —> P4(6) —> P1(1)）：6時刻，P1時間片用完，下處理機，重新放回就緒隊尾，發生調度。

??7時刻（P2(2) —> P4(6) —> P1(1)）：雖然P3的時間片沒用完，但是由于P3只需運行1個單位的時間，運行完了會主動放棄處理機，因此也會發生調度。隊頭進程P2上處理機。

??注意：雖然時間片大小為2，但如果進程本身只需運行1個單位的時間（如進程P3），同樣也會發生調度。只不過此時不是P3被剝奪處理機，而是P3進程主動放棄處理機。

??9時刻（P4(6) —> P1(1)）：進程P2時間片用完，并剛好運行完，發生調度，P4上處理機。

??11時刻（P1(1) —> P4(4)）：P4時間片用完，重新回到就緒隊列。P1上處理機。

??12時刻（P4(4)）：P1運行完，主動放棄處理機，此時就緒隊列中只剩P4，P4上處理機。

??14時刻（）：就緒隊列為空，因此讓P4緊接著運行一個時間片。

??16時刻：所有進程運行結束。

答2：

??時間片大小為5時。

??0時刻（P1(5) ）：只有P1到達，P1上處理機。

??2時刻（P2(4)）：P2到達，但P1時間片尚未結束，因此暫不調度 。

??4時刻（P2(4) —> P3(1)）：P3到達，但P1時間片尚未結束，因此暫不調度。

??5時刻（ P2(4) —> P3(1) —> P4(6) ）：P4到達，同時，P1運行結束。發生調度，P2上處理機。

??9時刻（ P3(1) —> P4(6) ）：P2運行結束，雖然時間片沒用完，但是會主動放棄處理機。發生調度。

??10時刻（ P4(6) ）：P3運行結束，雖然時間片沒用完，但是會主動放棄處理機。發生調度。

??15時刻（）：P4時間片用完，但就緒隊列為空，因此會讓P4繼續執行一個時間片。

??16時刻（）：P4運行完，主動放棄處理機。所有進程運行完。

??此時，分析——若按照先來先服務調度算法：

??會發現，它的執行過程，與時間片大小為5的時間片輪轉調度算法是類似的。

??結論：如果時間片太大，使得每個進程都可以在一個時間片內就完成，則時間片輪轉調度算法退化為先來先服務調度算法，并且會增大進程響應時間。因此時間片不能太大。

??另一方面，進程調度、切換是有代價的（保存、恢復運行環境），因此如果時間片太小，會導致進程切換過于頻繁，系統會花大量的時間來處理進程切換，從而導致實際用于進程執行的時間比例減少。可見，時間片也不能太小。

??說明1：什么叫“增大進程響應時間”？

??答：比如，系統中有10個進程在并發執行，如果時間片為1秒，則一個進程被響應可能需要等9秒。也就是說，如果用戶在自己進程的時間片外通過鍵盤發出調試命令，可能需要等待9秒才能被系統響應。而如果時間片為10ms，則一個進程被響應可能需要等90ms。

??說明2：如何定義“時間片太小”？

??答：一般來說，設計時間片時要讓切換進程的開銷占比不超過1%。

（二）優先級調度算法

1.算法思想

??隨著計算機的發展，特別是實時操作系統的出現，越來越多的應用場景需要根據任務的緊急程度來決定處理順序。

2.算法規則

??每個作業/進程有各自的優先級，調度時選擇優先級最高的作業/進程。

3.用于作業/進程調度

??既可用于作業調度，也可用于進程調度。甚至，還會用于在之后學習的I/O調度中。

4.是否可搶占

??搶占式、非搶占式都有。

??區別在于：非搶占式只需在進程主動放棄處理機時進行調度既可；而搶占式還需在就緒隊列發生變化時，檢查是否會發生搶占。

5.優缺點

??優點：用優先級區分緊急程度、重要程度，適用于實時操作系統。可靈活地調整對各種作業/進程的偏好程度。

??缺點：若源源不斷地有高優先級進程到來，則可能導致饑餓。

6.是否會導致饑餓

??會。

例子1

??各進程到達就緒隊列的時間、需要的運行時間、進程優先數如下表所示。使用非搶占式的優先級調度算法，分析進程運行情況。（注：優先數越大，優先級越高）

??說明：有的題目當中，也可能規定為——優先數越小，優先級越高。所以對于優先數的概念，要具體讀題目條件。

進程	到達時間	運行時間	優先數
P1	0	7	1
P2	2	4	2
P3	4	1	3
P4	5	4	2

答：

??注：以下括號內表示當前處于就緒隊列的進程

??0時刻（P1）：只有P1到達，P1上處理機。

??7時刻（P2、P3、P4）：P1運行完成主動放棄處理機，其余進程都已到達，P3優先級最高，P3上處理機。

??8時刻（P2、P4）：P3完成，P2、P4優先級相同，由于P2先到達，因此P2優先上處理機。

??12時刻（P4）：P2完成，就緒隊列只剩P4，P4上處理機。

??16時刻（）：P4完成，所有進程都結束。

例子2

??各進程到達就緒隊列的時間、需要的運行時間、進程優先數如下表所示。使用搶占式的優先級調度算法，分析進程運行情況。（注：優先數越大，優先級越高）

進程	到達時間	運行時間	優先數
P1	0	7	1
P2	2	4	2
P3	4	1	3
P4	5	4	2

??注意，搶占式的優先級調度算法：每次調度時選擇當前已到達且優先級最高的進程。當前進程主動放棄處理機時發生調度。另外，當就緒隊列發生改變時也需要檢查是否會發生搶占。

注：以下括號內表示當前處于就緒隊列的進程

0時刻（P1）：只有P1到達，P1上處理機。

2時刻（P2）：P2到達就緒隊列，優先級比P1更高，發生搶占。P1回到就緒隊列，P2上處理機。

4時刻（P1、P3）：P3到達，優先級比P2更高，P2回到就緒隊列，P3搶占處理機。

5時刻（P1、P2、P4）：P3完成，主動釋放處理機，同時，P4也到達，由于P2比P4更先進入就緒隊列，因此選擇P2上處理機。

7時刻（P1、P4）：P2完成，就緒隊列只剩P1、P4，P4上處理機。

11時刻（P1 ）：P4完成，P1上處理機。

16時刻（）：P1完成，所有進程均完成。

補充：

??就緒隊列未必只有一個，可以按照不同優先級來組織。

??另外，也可以把優先級高的進程排在更靠近隊頭的位置。

??根據優先級是否可以動態改變，可將優先級分為靜態優先級和動態優先級兩種。

??靜態優先級：創建進程時確定，之后一直不變。

??動態優先級：創建進程時有一個初始值，之后會根據情況動態地調整優先級。

問題1：如何合理地設置各類進程的優先級？

??通常的原則：

??1.系統進程優先級高于用戶進程

??2.前臺進程優先級高于后臺進程

??3.操作系統更偏好I/O型進程（或稱I/O繁忙型進程）

說明：與I/O型進程相對的是計算型進程（或稱CPU繁忙型進程）。

說明：為什么偏好I/O型進程？——已知I/O設備和CPU可以并行工作。如果優先讓I/O繁忙型進程優先運行的話，則越有可能讓I/O設備盡早地投入工作，則資源利用率、系統吞吐量都會得到提升。

問題2：如果采用的是動態優先級，什么時候應該調整？

??可以從追求公平、提升資源利用率等角度考慮。

?? 如果某進程在就緒隊列中等待了很長時間，則可以適當提升其優先級。

??如果某進程占用處理機運行了很長時間，則可適當降低其優先級。

??如果發現一個進程頻繁地進行I/O操作，則可適當提升其優先級。

??（有點類似于“高響應比優先”算法中的響應比的概念。可以理解為，“響應比”就是一種“動態優先級”。）

（三）多級反饋隊列調度算法

思考：

??FCFS算法的優點是公平；

??SJF算法的優點是能盡快處理完短作業，平均等待/周轉時間等參數很優秀；

??時間片輪轉調度算法可以讓各個進程得到及時的響應；

??優先級調度算法可以靈活地調整各種進程被服務的機會。

??那么，能否對這些算法做個折中權衡，得到一個綜合表現優秀平衡的算法呢？——多級反饋隊列調度算法。

1.算法思想

??對其他調度算法的折中權衡。

2.算法規則

??1）設置多級就緒隊列，各級隊列優先級從高到低，時間片從小到大。

??2）新進程到達時先進入第1級隊列，按FCFS原則排隊等待被分配時間片，若用完時間片進程還未結束，則進程進入下一級隊列隊尾。如果此時已經是在最下級的隊列，則重新放回該隊列隊尾。

??3）只有第k級隊列為空時，才會為k+1級隊頭的進程分配時間片。

3.用于作業/進程調度

??用于進程調度。

4.是否可搶占

??搶占式的算法。在k級隊列的進程運行過程中，若更上級的隊列（1~k-1級）中進入了一個新進程，則由于新進程處于優先級更高的隊列中，因此新進程會搶占處理機，原來運行的進程放回k級隊列隊尾。

??注：在實現的過程中，其實是可以將其實現為非搶占式的版本，但以教材上為準，認為它是一個搶占式的算法。

5.優缺點

??對各類進程相對公平（FCFS的優點）；

??每個新到達的進程都可以很快就得到響應（RR的優點）；

??短進程只用較少的時間就可以完成（SPF的優點）；

??不必實現估計進程的運行時間（避免用戶作假）；

??可靈活地調整對各類進程的偏好程度，比如CPU密集型進程、I/O密集型進程（說明：可將因I/O而阻塞的進程重新放回原隊列，這樣I/O型進程就可以保持較高優先級）。

6.是否會導致饑餓

??會。

例子

??各進程到達就緒隊列的時間、需要的運行時間如下表所示。使用多級反饋隊列調度算法，分析進程運行的過程。

進程	到達時間	運行時間
P1	0	8
P2	1	4
P3	5	1

答：

??設置多級就緒隊列，各級隊列優先級從高到低，時間片從小到大。

??新進程到達時先進入1級隊列，按FCFS原則排隊等待被分配時間片。若用完時間片進程還未結束，則進程進入下一級隊列隊尾。如果此時已經在最下級的隊列，則重新放回最下級隊列隊尾。

??只有第k級隊列為空時，才會為k+1級隊頭的進程分配時間片。

??被搶占處理機的進程重新放回原隊列隊尾。

例子

??如圖，0時刻P1到達，進入第1級隊列隊尾。P1上處理機運行1個單位的時間（因為第1級隊列的時間片就是1）。之后，由于P1進程還未運行完，因此P1進入第2級隊列隊尾。

??此時為1時刻，因此P2同時會到達。此時，由于更高級別（即：第1級）的隊列中還有進程沒處理完，因此暫時不會處理更低級別（即：第2級）的隊列。

??因此，1時刻會選擇P2上處理機運行。同樣地，P2運行的時間片大小為1個單位時間。此外，P2運行后，會被放到下一級隊列的隊尾。

??在2時刻，由于第1級隊列為空了（更高級的隊列為空），所以會對第2級隊列進行調度（才會對更低級的隊列進行調度）。

??因此，此時選擇第2級隊列隊頭的進程上處理機運行一個時間片，即P1進程上處理機運行2個單位的時間。

??同理，P1執行完一個時間片后，P1進程還沒運行結束，因此會被放到第3級隊列中。

??此時，先處理較高級別隊列中的進程，因此會讓P2上處理機運行。

??需要注意的是，在P2還未執行滿一個時間片的時刻5的時候，此時進程P3到達，P3進入第1級隊列。

??由于此時有更高優先級的進程到達，所以會發生搶占處理機的情況，所以此時P2進程會被剝奪處理機，但是P2并不是放到下一級隊列，而是放回原級隊列的隊尾。

??5時刻，P3搶占地上處理機運行。運行完1個單位的時間之后，剛好進程P3也運行完畢，所以P3執行完成后就可以調出內存了。

??6時刻，又是P2繼續運行。由于在這之前P2已經總共運行了2個單位的時間（在第1級隊列中運行了一個時間片 + 在第2級隊列中運行了半個時間片時被剝奪），所以在這次，P2上處理機運行完一個時間片后，就可以運行完畢，調出內存了。

??8時刻，讓進程P1上處理機運行（注：P1在這之前，已運行了共計3個單位的時間）一個時間片，即運行了4個單位的時間。由于P1進程還沒有運行完，因此按理說應該往更低1級的隊列去放入，但此時已經沒有更低級別的隊列了，P1也已經沒辦法再往下放了，因此它只會被重新放回最低級隊列的隊尾，再次等待被調度。

??12時刻，P1被調度，運行1個單位的時間后，P1完成，并調出內存。

總結

??注：比起早期的批處理操作系統來說，由于計算機造價大幅降低，因此之后出現的交互式操作系統（包括分時操作系統、實時操作系統等）更注重系統的響應時間、公平性、平衡性等指標。而這幾種算法恰好也能較好地滿足交互式系統的需求。因此這三種算法適合用于交互式系統。（比如UNIX使用的就是多級反饋隊列調度算法）

三、多級隊列調度算法

??系統中按進程類型設置多個隊列，進程創建成功后插入某個隊列。

??注：最上面那個隊列優先級最高，往下依次降低。

??說明：為什么圖中這樣設置各個進程的優先級。

??首先，系統進程的優先級最高，這無可厚非。

??另外，交互式進程需要得到比較及時的響應和反饋（如打游戲、打字的時候，你當然希望你的鍵盤/鼠標點下去之后就立即得到一個反饋），因此顯然需要被賦予更高的優先級，這樣才能更快地響應用戶的請求。

??最后，批處理進程的優先級較低，這個就很好理解了，例如模型訓練、視頻渲染，這種進程的優先級稍設置的低一些，對用戶的體驗來說也并沒有那么糟糕。

問題1：每次調度應該選中哪個隊列？

??隊列之間可采取固定優先級，或時間片劃分。

??1.固定優先級：高優先級空時，低優先級進程才能被調度。