一、調度演算法評價標準

1.CPU資源利用率

1??.CPU資源利用率 = 忙碌時間 / 總時間

2??. 多道程式并發執行:用甘特圖

2.系統吞吐量

1??.單位時間內完成作業的數量
2??.系統吞吐量 = 總共完成了多少道作業 / 總共花了多少時間

3.周轉時間

1??.周轉時間：是指從作業被提交給系統開始，到作業完成為止的這段時間間隔，
↘? 計算：周轉時間 = 作業完成時間 - 作業提交時間
2??.平均周轉時間 = 各作業周轉時間之和 / 作業數
3??.帶權周轉時間：作業周轉時間 / 作業實際運行的時間 = （作業完成時間 - 作業提交時間） / 作業實際運行的時間
4??.平均帶權周轉時間：各作業帶權周轉時間之和 / 作業數

4.等待時間

1??.等待時間：指行程 / 作業處于等待處理機狀態時間之和，等待時間越長，用戶滿意度越低，
2??.對于行程來說，等待時間就是指行程建立后等待被服務的時間之和，在等待I/O完成的期間其實行程也是在被服務的，所以不計入等待時間，
3??.對于作業來說，不僅要考慮建立行程后的等待時間，還要加上作業在外存后備佇列中等待的時間
4??.一個作業總共需要被CPU服務多久，被I/O設備服務多久一般是確定不變的，因此調度演算法其實只會影響作業/行程的等待時間，當然，與前面指標類似，也有“平均等待時間”來評價整體性能，

5.回應時間

1??.回應時間：指從用戶提交請求到首次產生回應所用的時間，

二、FCFS、SJF、HRRN調度演算法

↘?（ 一般適用于早期的批處理系統）

1.先來先服務（FCFS）

①演算法思想、②演算法規則、③用于作業調度還是行程調度、④搶占式還是非搶占式、⑤優點、缺點、⑥是否會導致饑餓

1. 演算法思想：主要從“公平”的角度考慮（類似于我們生活中排隊買東西的例子)
2. 演算法規則：按照作業/行程到達的先后順序進行服務
3. 用于作業/行程調度：用于作業調度時，考慮的是哪個作業先到達后備佇列；用于行程調度時，考慮的是哪個行程先到達就緒佇列
4. 是否搶占：非搶占式演算法
5. 優缺點：優點：公平、實作簡單；缺點：排在長作業（行程）后面的短作業需要等待很長時間，帶權周轉時間很大，對短作業來說用戶體驗不好，即，FCFS演算法對長作業有利，對短作業不利(Eg :排隊買奶茶🍦…)
6. 是否會導致饑餓：不會
   7.
   
   

2.短作業優先（SJF）

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

3.高回應比優先（HRRN）

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

三、 三種調度演算法的對比

四、時間片輪轉、優先級調度、多級反饋佇列調度演算法

1.時間片輪轉調度演算法RR

1. 演算法思想：公平地、輪流地為各個行程服務，讓每個行程在一定時間間隔內都可以得到回應
2. 演算法規則：按照各行程到達就緒佇列的順序，輪流讓各個行程執行一個時間片(如100ms），若行程未在一個時間片內執行完，則剝奪處理機，將行程重新放到就緒佇列隊尾重新排隊，
3. 用于作業/行程調度：用于行程調度（只有作業放入記憶體建立了相應的行程后，才能被分配處理機時間片)
4. 是否可搶占：若行程未能在時間片內運行完，將被強行剝奪處理機使用權，因此時間片輪轉調度演算法屬于搶占式的演算法，由時鐘裝置發出時鐘中斷來通知CPU時間片已到
5. 優缺點：優點:公平;回應快，適用于分時作業系統；缺點：由于高頻率的行程切換，因此有一定開銷;不區分任務的緊急程度，
6. 是否會導致饑餓：不會
7. 如果時間片太大，使得每個行程都可以在一個時間片內就完成，則時間片輪轉調度演算法退化為先來先服務調度演算法，并且會增大行程回應時間，因此時間片不能太大，另一方面，行程調度、切換是有時間代價的（保存、恢復運行環境)，因此如果時間片太小，會導致行程切換過于頻繁，系統會花大量的時間來處理行程切換，從而導致實際用于行程執行的時間比例減少，可見時間片也不能太小，
8. 例題：各行程到達就緒佇列的時間、需要的運行時間如下表所示，使用時間片輪轉調度演算法，分析時間片大小分別是2、5時的行程運行情況，
   
   
   
   
   
   

2.優先級調度演算法

1. 演算法思想：隨著計算機的發展，特別是實時作業系統的出現，越來越多的應用場景需要根據任務的緊急程度來決定處理順序
2. 演算法規則：每個作業/行程有各自的優先級，調度時選擇優先級最高的作業/行程
3. 用于作業/行程調度：既可用于作業調度，也可用于行程調度，甚至，還會用于在之后會學習的I/o調度中
4. 是否可搶占：搶占式、非搶占式都有，做題時的區別在于:非搶占式只需在行程主動放棄處理機時進行調度即可，而搶占式還需在就緒佇列變化時，檢查是否會發生搶占，
5. 優缺點：優點：用優先級區分緊急程度、重要程度，適用于實時作業系統，可靈活地調整對各種作業/行程的偏好程度，缺點：若源源不斷地有高優先級行程到來，則可能導致饑餓；
6. 是否會導致饑餓：會
7. 例題：各行程到達就緒佇列的時間、需要的運行時間、行程優先數如下表所示，使用非搶占式的優先級調度演算法，分析行程運行情況，（注：優先數越大，優先級越高)
8. 
   
9. 例題：各行程到達就緒佇列的時間、需要的運行時間、行程優先數如下表所示，使用搶占式的優先級調度演算法，分析行程運行情況，（注:優先數越大，優先級越高)
   10.

3.多級反饋佇列調度演算法

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. 是否會導致饑餓：
7. 例題：各行程到達就緒佇列的時間、需要的運行時間如下表所示，使用多級反饋佇列調度演算法，分析行程運行的程序，
   
8. 程序分析：
   ①.設定多級就緒佇列，各級佇列優先級從高到低，時間片從小到大，
   ②.比如第一級佇列的執行時間片就是1個長度時間單位，新行程到達時先進入第一級佇列，按照FCFS原則排隊等待被分配時間片，剛開始0時刻，P1行程到達，所以P1會先放入第一級佇列，由于他是先到達的此時也沒有別的行程，所以P1被分配一個單位的時間片，當P1執行了一個單位的時間片之后，P1會進入第二級佇列的隊尾；
   ③.接下來，在第一這個時刻，當P1執行結束之后，P2會緊隨其后進入第一級佇列，此時由于更改級別的佇列還有行程，所以不會處理第二級佇列里面的P1行程，因此，1這個時刻會選擇P2這個行程讓他上處理機運行，運行完一個單位的時間之后，P2行程就會放到第二級佇列的隊尾；
   ④.接下來，在2這個時刻，由于更高級的第一級佇列已經全部為空了，所以才會對第二級佇列進行調度，P1會執行兩個單位的時間片，P1執行完后，他的運行時間還沒有到，所以P1會進入第三級的佇列；此時，下一次調度由于第二級佇列還有P2行程，所以讓P2執行兩個時間片，但是當P2運行了一個單位的時間片之后，
   ⑤.在5這個時刻，P3行程到達第一級佇列，由于此時有一個更高優先級的行程到達，所以會發生搶占處理機的情況，此時P2行程會被剝奪處理機，P2會被放到第二級佇列的隊尾，之后P3搶占處理機運行，運行完一個時間片之后，P3行程執行完畢，調出記憶體，
   ⑥.接下來P2開始運行，由于P2之前運行了2個時間片，所以這次P2上處理機運行的時候，運行完兩個單位的時間片之后，總的4個時間片執行完畢P2被調出記憶體；
   ⑦.當第一級第二級佇列都為空時，才會調度第三級佇列的行程，讓P1上處理機運行四個單位的時間，當P1運行完四個單位的時間之后，P1總共運行了1+2+4=7的單位的時間片，還需一個單位的時間片，由于此時P1已經在最下面一級，所以P1會被放入第三級佇列的隊尾，再次被調入，執行完一個單位的時間就滿足八個單位的時間，P1完成調出記憶體，

五、三種調度演算法的對比