文章目錄

• 一：時間片輪轉調度算法（RR）
• 二：優先級調度算法（HPF）
• 三：多級反饋隊列調度算法（MFQ）
• 總結

進程調度算法也稱為CPU調度算法，操作系統內存在著多種調度算法，有的調度算法適用于作業調度，有的調度算法適用于進程調度，有的兩者都適用。常見的調度算法有（本節介紹適合于分時系統、交互式系統的調度算法）：

• 時間片輪轉調度算法
• 最高優先級調度算法
• 多級反饋隊列調度算法

一：時間片輪轉調度算法（RR）

算法思想：公平地、輪流地為各個進程服務，讓每個進程在一定時間間隔內都可以得到響應。按照各進程到達就緒隊列的順序，輪流讓各個進程執行一個時間片(Quantum)，若進程未在一個時間片內執行完畢，則剝奪處理機，然后將其放入就緒隊列重新排隊

• 用于進程調度（因為只有作業放入內存建立了相應進程后，才能被分配處理機時間片）
• 若進程未能在時間片內運行完畢，則會被強行剝奪，屬于搶占式算法，由時鐘裝置發出時鐘中斷通知CPU時間片已到

比如，下面有4個進程$P_1$、$P_2$、$P_3$和$P_4$，他們到達就緒隊列的到達時間和運行時間如下表所示，使用$P_n(m)$表示當前進程的剩余運行時間為$m$，

進程到達時間運行時間

$P_1$	0	5
$P_2$	2	4
$P_3$	4	1
$P_4$	5	6

假設時間片大小為2，其變化過程如下

• 在0時刻，$P_1(5)$。$P_1$到達，讓$P_1$上處理機運行一個時間片
  

• 在2時刻，有$P_2(4)$，$P_1(3)$。$P_2$到達就緒隊列，同時此時 $P_1$的時間片用完，被剝奪處理機，重新放回就緒隊列隊尾 （需要注意這種情況中默認新到達的進程先進入就緒隊列）
  

• 此時$P_2$處于就緒隊列隊頭，因此它上處理機
  

• 在4時刻，$P_1(3)$，$P_3(1)$，$P_2(2)$。$P_3$到達就緒隊列，$P_3$插入到就緒隊列隊尾，而此時$P_2$時間片也已經到了，因此$P_2$下處理機插入到隊尾。此時$P_1$處于隊頭，因此$P_1$處理機
  

• 在5時刻，$P_3(1)$，$P_2(2)$，$P_4(6)$。$P_4$到達就緒隊列，$P_4$插入到就緒隊列隊尾。此時不進行調度，因為$P_1$還處于運行態，它的時間片還沒有用完
  

• 在6時刻，$P_3(1)$，$P_2(2)$，$P_4(6)$，$P_1(1)$。$P_1$的時間片用完，下處理機，重新放回隊尾，然后$P_3$開始運行
  

• 在7時刻，$P_2(2)$，$P_4(6)$，$P_1(1)$。雖然$P_3$的時間片還沒用完，但是它已經結束了，所以$P_3$主動放棄處理機，$P_2$上處理機
  

• 在9時刻，$P_4(6)$，$P_1(1)$。$P_2$時間片用完，而恰好$P_2$也已經結束，此時$P_4$上處理機
  

• 在11時刻，$P_1(1)$，$P_4(4)$。$P_1$時間片用完，放回隊尾，P1上處理機
  

• 在12時刻，$P_4(4)$。$P_1$運行完畢主動放棄處理機，$P_4$上處理機
  

• 在14時刻，就緒隊列為空，$P_4$會繼續再運行1個時間片

• 在16時刻，所有進程運行完畢

假設時間片大小為5，其變化過程如下

• 在0時刻，$P_1(5)$。$P_1$到達，讓$P_1$上處理機運行一個時間片
• 在2時刻，$P_2(4)$。$P_2$到達，但是$P_1$的時間片還未結束，暫不調度
• 在4時刻，$P_2(4)$，$P_3(1)$。$P_3$到達，但是$P_1$的時間片還未結束，暫不調度
• 在5時刻，$P_2(4)$，$P_3(1)$，$P_4(6)$。$P_4$到達，同時$P_1$運行結束，接著讓$P_2$上處理機
• 在9時刻，$P_3(1)$，$P_4(6)$。$P_4$運行結束，主動放棄處理機發生調度。讓$P_3$上處理機
• 在10時刻，$P_4(6)$。$P_3$運行結束，主動放棄處理機，發生調度。讓$P_4$上處理機
• 在15時刻。$P_4$時間片用光，且就緒隊隊列為空，故讓$P_4$繼續下一個時間片
• 在16時刻。所有進程運行結束

時間片大小的影響

• 時間片太大：使得每個進程都可以在一個時間片內完成，此時RR算法就退化為了FCFS算法，并且會增大進程響應時間
• 時間片太小：由于進程調度、切換是有時間代價的，因此如果時間片太小，會導致進程切換過于頻繁，系統會花大量時間來處理進程切換

優缺點

• 優點： 公平、響應快
• 缺點： 由于高頻率的進程切換，因此會有一定開銷，且不能區分任務的緊急程度

是否會導致饑餓現象：不會

二：優先級調度算法（HPF）

隨著計算機的發展，特別是實時操作系統的出現，越來越多的應用場景需要根據任務的緊急程度（優先級） 來決定處理順序。進程的優先級可以被劃分為

• 靜態優先級：創建進程的時候，就已經確定好了優先級，整個運行過程優先級都不會發生變化
• 動態優先級：根據進程的動態變化調整優先級（比如當進程的運行時間增加則降低其優先級、進程等待時間增加則提高其優先級等等）

算法思想 ：每個作業/進程都有各自的優先級，調度時選擇優先級最高的作業/進程

• 可用于作業調度、進程調度，甚至I/O調度
• 有搶占式（當就緒隊列中出現優先級高的進程，當前進程被掛起，調度優先級高的進程）和非搶占（當就緒隊列中出現優先級高的進程，運行完當前進程，再選擇優先級高的進程）兩種

比如，下面有4個進程$P_1$、$P_2$、$P_3$和$P_4$，他們到達就緒隊列的到達時間、運行時間及進程優先數 ，如下表所示

• 一般來說，優先數越大，優先級越高

進程到達時間運行時間優先數

$P_1$	0	7	1
$P_2$	2	4	2
$P_3$	4	1	3
$P_4$	5	4	2

采用非搶占式優先級調度算法，意味著只有進程主動放棄處理機時才發生調度，因此其過程也顯而易見

采用搶占式優先級調度算法，除了進程主動放棄處理機時會發生調度之外，當新進程到達時（就緒隊列改變）也要考慮是否會發生調度，其變化過程如下

• 在0時刻，$P_1$到達，$P_1$上處理機
• 在2時刻，$P_2$到達，使就緒隊列發生改變，同時由于$P_2$的優先級要高于$P_1$，因此$P_1$被剝奪回到就緒隊列，$P_2$上處理機
• 在4時刻，$P_3$到達，其優先級高于$P_2$，因此$P_2$回到就緒隊列，$P_3$上處理機
• 在5時刻，$P_3$結束運行，主動放棄處理機，同時恰好$P_4$到達，這里$P_2$和$P_4$優先級是一樣的，但是$P_2$要比$P_4$更早進入就緒隊列，所以$P_2$上處理機
• 在7時刻，$P_2$完成，$P_4$上處理機
• 在11時刻，$P_4$完成，$P_1$上處理機
• 在16時刻，所有進程結束運行

進程優先級的設置原則

• 系統進程大于用戶進程：系統進程作為系統的管理者，理應擁有更高的優先級
• 交互型進程大于非交互型進程（前臺進程大于后臺進程）：類比使用手機時的前臺應用程序和后臺應用程序
• I/O密集型進程大于計算密集型進程：I/O密集型進程是指那些會頻繁使用I/O設備的進程；計算密集型進程是指那些頻繁使用CPU的進程。如果將I/O密集型進程設置得更高，就更有可能讓I/O設備盡早開始投入工作，進而提升系統的整體效率

優缺點

• 優點： 使用優先級區分緊急程度、重要程度、適用于實時操作系統，可以靈活調整對各種作業/進程的偏好程度
• 缺點： 有可能導致低優先級進程得不到運行

是否會導致饑餓：會

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

算法思想：MFQ算法其實是RR算法和HPF算法的綜合和發展

• 多級：表示有多個隊列，每個隊列優先級從高到低，同時優先級越高時間片越短
• 反饋：表示如果有新的進程加入優先級高的隊列時，立刻停止當前正在運行的進程，轉而去運行優先級高的隊列

算法具體規則

• 設置了多個隊列，賦予每個隊列不同的優先級，每個隊列優先級從高到低，同時優先級越高時間片越短
• 新的進程會被放入到第一級隊列的末尾，按FCFS算法的原則排隊等待被調度，如果在第一級隊列規定的時間片內沒有運行完畢，則將其轉入第二級隊列的末尾，依次類推，直至完成
• 當較高優先級的隊列為空時，才調度較低優先級隊列中的進程。如果進程運行時，有新的進程進入較高優先級隊列時，則停止當前運行的進程并將其移入原隊列的末尾，接著讓較高優先級的進程運行

比如，下面有3個進程$P_1$、$P_2$和$P_3$，他們到達就緒隊列的到達時間和運行時間如下表所示

進程到達時間運行時間

$P_1$	0	8
$P_2$	1	4
$P_3$	5	1

根據“算法規則”中的敘述，建立優先級隊列，其優先級和時間片分配如下

整個變化過程如下

• $P_1$到達，進入第1級隊列，按FCFS算法分配時間片
  

• 第1級隊列其時間片只有1，因此1個時刻后，$P_1$時間片用完。但是其剩余時間還有7，還未運行完畢，所以會進入第2級隊列
  

• 同時在1時刻，$P_2$到達并進入第1級隊列，對于$P_1$來說，它處在第2級隊列，由于此時第1級隊列不為空，所以它不會被調度，此時先調度第1級隊列中的$P_2$
  

• $P_2$的一個時間片用完之后繼續放到第2級隊列
  

• 在2時刻沒有新的進程到來，同時對于 $P_1$和 $P_2$來說相對于它們所在的更高一級的優先級隊列，也就是第1級隊列是空的，因此為它們分配時間片，按照FCFS原則， $P_1$被調度，時間片為2
  

• $P_1$時間片到后還沒有完成運行，因此會被放入第3級隊列
  

• 接著 $P_2$被調度
  

• 在 $P_2$運行1個時間片后，也即在5時刻 $P_3$到達并進入第1級隊列，此時更高優先級隊列中有進程存在，所以處在處理機上的 $P_2$會被剝奪下來，仍然回到其所在的隊列隊尾，接著讓 $P_3$上處理機
  

• $P_3$運行1個時間片后結束運行
  

• 然后$P_2$繼續被調度，其剩余時間為2，所以正好運行2個時間片后結束運行
  

• 此時第1級、第2級隊列為空，因此處在第3級隊列$P_1$此時可以被調度，因此分配4個時間片
  

• 4個時間片結束之后，$P_1$剩余時間還有1，而此時它已經處在了最下級的隊列了，因此重新放回最下級隊列隊尾即可，然后結束運行
  

從以上的敘述中大家可以感受到：

• 短作業可能可以在第一級隊列很快地被處理完
• 長作業如果第一級處理不完，可以移入下一級等待。等待時間雖然變長了，但是運行時間也會變長

多級反饋隊列的優點

• 終端型作業用戶：短作業優先（例如命令行輸入命令）
• 短批處理作業用戶：周轉時間較短
• 長批處理作業用戶：經過前面幾個隊列得到部分執行，不會長期得不到處理

是否會導致饑餓：會

---

總結

總結

以上是生活随笔為你收集整理的(王道408考研操作系统)第二章进程管理-第二节4：调度算法详解2(RR、HPF和MFQ)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。