一、調度的概念、層次

1.1 三個層次

• 高級調度（作業調度）：按一定的原則從外存的作業后備隊列中挑選一個作業調入內存，并創建進程。每個作業只調入一次，調出一次。作業調入時會建立PCB，調出時才撤銷PCB。
• 低級調度（進程調度/處理機調度）：按照某種策略從就緒隊列中選取一個進程，將處理機CPU分配給它。進程調度是操作系統中最基本的一種調度。
• 中級調度（內存調度）：按照某種策略決定將哪個處于掛起狀態的進程重新調入內存。
  內存不夠時，可將某些進程的數據調出外存。等內存空閑或者進程需要運行時再重新調入內存。

  暫時調到外存等待的進程狀態為掛起狀態。被掛起的進程PCB會被組織成掛起隊列

	要做什么	調度發生地	發生頻率	對進程的影響
高級調度（作業調度）	按照某種規則，從后備隊列中選擇合適的作業將其調入內存，并為其創建進程	外存→內存（面向作業）	最低	無→創建態→就緒態
中級調度（內存調度）	按照某種規則，從掛起隊列中選擇合適的進程將其數據調回內存	外存→內存（面向進程）	中等	掛起態→就緒態（阻塞掛起→阻塞態）
低級調度（進程調度）	按照某種規則，從就緒隊列中選擇一個進程為其分配處理機	內存→CPU	最高	就緒態→運行態

1.2 七狀態模型

暫時調到外存等待的進程狀態為掛起狀態，掛起態又可以進一步細分為就緒掛起、阻塞掛起兩種狀態

二、調度算法的評價指標

2.1 CPU利用率

CPU利用率：指CPU“忙碌”的時間占總時間的比例。
$$利用率=\frac{忙碌時間}{總時間}$$

2.2 系統吞吐率

系統吞吐量：單位時間內完成作業的數量

$$系統吞吐量=\frac{總共完成多少道作業}{總共花了多少時間}$$

2.3 周轉時間

周轉時間，是指從作業被提交給系統開始，到作業完成為止的這段時間間隔。
它包括四個部分：作業在外存后備隊列上等待作業調度（高級調度）的時間、進程在就緒隊列上等待進程調度（低級調度）的時間、進程在CPU上執行的時間、進程等待I/O操作完成的時間。后三項在一個作業的整個處理過程中，可能發生多次。
$$周轉時間=作業完成時間?作業提交時間$$
$$平均周轉時間=\frac{各作業周轉時間之和}{作業數}$$
$$帶權周轉時間=\frac{周轉時間}{作業實際運行的時間}$$
$$平均帶權周轉時間=\frac{各作業帶權周轉時間}{作業數}$$

2.4 等待時間

等待時間，指進程/作業處于等待處理機狀態時間之和，等待時間越長，用戶滿意度越低。

• 對于進程來說，等待時間就是指進程建立后等待被服務的時間之和，在等待I/O完成的期間其實進程也是在被服務的，所以不計入等待時間。
• 對于作業來說，不僅要考慮建立進程后的等待時間，還要加上作業在外存后備隊列中等待的時間。

2.5 響應時間

響應時間，用戶提交請求到首次產生0響應所用的時間。

三、進程調度（低級調度）的時機

3.1 需要進程調度的情況

• 主動放棄
  
  

  • 進程正常終止
  • 異常而終止
  • 進程主動請求阻塞（如等待I/O)

• 被動放棄

  • 當前運行的進程分給進程的時間片用完
  • 有更高優先級的進程進入就緒隊列
  • 有更緊急的事需要處理

3.2 不能進程調度的情況

• 在處理中斷的過程中。中斷處理過程復雜，與硬件密切相關，很難做到在中斷處理過程中進行進程切換。

• 在原子操作過程中（原語）。原子操作不可中斷，要一氣呵成（如之前講過的修改PCB中進程狀態標志，并把PCB放到相應隊列)

• 進程在操作系統內核程序臨界區中。

  臨界資源：一個時間段內只允許一個進程使用的資源。各進程需要互斥地訪問臨界資源。
  臨界區：訪問臨界資源的那段代碼。
  內核程序臨界區一般是用來訪問某種內核數據結構的，比如進程的就緒隊列（由各就緒進程的PCB組成）
  

3.3 閑逛進程

調度程序永遠的備胎，沒有其他就緒進程時，運行閑逛進程(idle)

• 閑逛進程的特性:
  • 優先級最低
  • 可以是0地址指令，占一個完整的指令周期(指令周期末尾例行檢查中斷)，這個中斷會周期性喚醒調度程序，讓調度程序檢查有沒有其他就緒進程已經就緒，如果有就讓閑逛進程下處理機，讓其他進程上處理機器。
  • 能耗低，0地址指令表示不需要訪存，也不需要訪問CPU的寄存器，這就會使CPU能耗較低

四、進程調度（低級調度）的方式

• 非剝奪調度方式，又稱非搶占方式。即，只允許進程主動放棄處理機。
  在運行過程中即便有更緊迫的任務到達，當前進程依然會繼續使用處理機，直到該進程終止或主動要求進入阻塞態。

  • 實現簡單，系統開銷小但是無法及時處理緊急任務，適合于早期的批處理系統

• 剝奪調度方式，又稱搶占方式。當一個進程正在處理機上執行時，如果有一個更重要或更緊迫的進程需要使用處理機，則立即暫停正在執行的進程，將處理機分配給更重要緊迫的那個進程。 可以優先處理更緊急的進程，也可實現讓各進程按時間片輪流執行的功能（通過時鐘中斷）。

  • 適合于分時操作系統、實時操作系統

五、進程調度（低級調度）的切換與過程

狹義的進程調度指的是從就緒隊列中選中一個要運行的進程。
進程切換是指一個進程讓出處理機，由另一個進程占用處理機的過程。
廣義的進程調度包含了選擇一個進程和進程切換兩個步驟。

• 進程切換的過程主要完成了：
  1. 對原來運行進程各種數據的保存
  2. 對新的進程各種數據的恢復（如：程序計數器、程序狀態字、各種數據寄存器等處理機現場信息，這些信息一般保存在進程控制塊）

六、調度算法

• 早期無交互式，只關心公平性、平均周轉時間和平均等待時間等整體性能的指標的算法：FCFS、SJF和HRRN
• 考慮交互式的算法：RR、優先級調度和多級反饋隊列

6.1 先來先服務FCFS

先來先服務FCFS
算法思想	主要從“公平”的角度考慮
算法規則	按照作業/進程到達的先后順序進行服務（誰先來就服務誰）
用于作業/進程調度	用于作業調度時，考慮的是哪個作業先到達后備隊列；用于進程調度時，考慮的是哪個進程先到達就緒隊列
是否可搶占？	非搶占式的算法
優缺點	優點：公平、算法實現簡單 缺點：排在長作業（進程）后面的短作業需要等待很長時間，帶權周轉時間很大，對短作業來說用戶體驗不好。即FCFS算法對長作業有利，對短作業不利（例如：排隊買奶茶…）
是否會導致饑餓	不會

6.2 短作業優先SJF

短作業優先SJF
算法思想	追求最少的平均等待時間，最少的平均周轉時間、最少的平均平均帶權周轉時間
算法規則	最短的作業/進程優先得到服務（所謂“最短”，是指要求服務時間最短）（誰用時短誰先來）
用于作業/進程調度	即可用于作業調度，也可用于進程調度。用于進程調度時稱為“短進程優先”（SPF，Shortest Process First）算法
是否可搶占？	SJF和SPF是非搶占式的算法。但是也有搶占式的版本：最短剩余時間優先算法（SRTN，Shortest Remaining Time Next）
優缺點	優點：“最短的”平均等待時間、平均周轉時間 缺點 ：不公平。對短作業有利，對長作業不利。可能產生饑餓現象。另外，作業/進程的運行時間是由用戶提供的，并不一定真實，不一定能做到真正的短作業優先會。如果源源不斷地有短作業/進程到來，可能使長作業/進程長時間得不到服務，產生“饑餓”現象。如果一直得不到服務，則稱為“餓死”
是否會導致饑餓	可能會產生饑餓現象

6.3 高響應比優先HRRN

高響應比優先HRRN
算法思想	要綜合考慮作業/進程的等待時間和要求服務的時間
算法規則	在每次調度時先計算各個作業/進程的響應比，選擇響應比最高的作業/進程為其服務（按“鬧”分配）
響應比公式	響應比 = (等待時間 + 要求服務時間) / 要求服務時間
用于作業/進程調度	即可用于作業調度，也可用于進程調度
是否可搶占?	非搶占式的算法。因此只有當前運行的作業/進程主動放棄處理機時，才需要調度，才需要計算響應比
優缺點	綜合考慮了等待時間和運行時間(要求服務時間) 等待時間相同時，要求服務時間短的優先(SJF的優點) 要求服務時間相同時，等待時間長的優先(FCFS的優點) 對于長作業來說，隨著等待時間越來越久，其響應比也會越來越大，從而避免了長作業饑餓的問題
是否會導致饑餓	不會導致饑餓

6.4 時間片輪轉RR

時間片輪轉RR
算法思想	公平地、輪流地為各個進程服務，讓每個進程在一定時間間隔內都可以得到響應
算法規則	按照各進程到達就緒隊列的順序，輪流讓各個進程執行一個時間片（如100ms）。若進程未在一個時間片內執行完，則剝奪處理機，將進程重新放到就緒隊列隊尾重新排隊。
用于作業/進程調度	用于進程調度（只有作業放入內存建立了相應的進程后，才能被分配處理機時間片）
是否可搶占？	若進程未能在時間片內運行完，將被強行剝奪處理機使用權，因此時間片輪轉調度算法屬于搶占式的算法。由時鐘裝置發出時鐘中斷來通知CPU時間片已到
優缺點	優點：公平；響應快，適用于分時操作系統； 缺點：由于高頻率的進程切換，因此有一定開銷；不區分任務的緊急程度。
是否會導致饑餓	不會

• 如果時間片太大，使得每個進程都可以在一個時間片內就完成，則時間片輪轉調度算法退化為先來先服務調度算法，并且會增大進程響應時間。因此時間片不能太大。
• 另一方面，進程調度、切換是有時間代價的（保存、恢復運行環境），因此如果時間片太小，會導致進程切換過于頻繁，系統會花大量的時間來處理進程切換，從而導致實際用于進程執行的時間比例減少。

6.5 優先級調度算法

優先級調度算法
算法思想	隨著計算機的發展，特別是實時操作系統的出現，越來越多的應用場景需要根據任務的緊急程度來決定處理順序
算法規則	調度時選擇優先級最高的作業/進程
用于作業/進程調度	既可用于作業調度，也可用于進程調度。甚至，還會用于在之后會學習的I/O調度中
是否可搶占?	搶占式、非搶占式都有。的別在于:非搶占式只需在進程主動放棄處理機時進行調度即可,而搶占式還需在就緒隊列變化時,檢查是否會發生搶占。
優缺點	優點:用優先級區分緊急程度、重要程度,適用于實時操作系統。可靈活地調整對各種作業/進程的偏好程度。 缺點:若源源不斷地有高優先級進程到來,則可能導致饑餓
是否會導致饑餓	會

6.6 多級隊列調度算法

多級隊列調度算法
算法思想	對其他調度算法的折中權衡
算法規則	設置多級就緒隊列，各級隊列優先級從高到低，時間片從小到大 新進程到達時先進入第1級隊列，按FCFS原則排隊等待被分配時間片，若用完時間片進程還未結束，則進程進入下一級隊列隊尾 如果此時已經在最下級的隊列，則重新放回該隊列隊尾 只有第k級隊列為空時，才會為k+1級隊頭的進程分配時間片
用于作業/進程調度	用于進程調度
是否可搶占？	搶占式的算法。在k級隊列的進程運行過程中，若更上級的隊列(1~k-1級)中進入了一個新進程，則由于新進程處于優先級更高的隊列中，因此新進程會搶占處理機，原來運行的進程放回k級隊列隊尾。
優缺點	對各類型進程相對公平(FCTS的優點)；每個新到達的進程都可以很快得到響應(RR的優點)；短進程只用較少的時間就可以完成(SPF的優點)；不必實現估計進程的運行時間(避免用戶作假)； 可靈活地調整對各類進程的偏好程度，比如CPU密集型進程、I/O密集型進程(拓展：可以將因I/O而阻塞的進程重新放回原隊列，這樣I/O型進程就可以保持較高優先級)
是否會導致饑餓	會