一.作業調度

作業調度算法需要知道以下公式

周轉時間=完成時間 - 到達時間

帶權周轉時間=周轉時間/運行時間

注：帶權周轉時間越大，作業（或進程）越短；帶權周轉時間越小，作業（或進程）越長。帶權周轉時間越小越好

平均周轉時間=作業周轉總時間/作業個數；

平均帶權周轉時間=帶權周轉總時間/作業個數

同時，作業調度算法會涉及一個概念：

饑餓：

作業饑餓（Job Starvation）或被餓死（Starvation）就是一個或多個低優先級的作業無法獲得系統資源，無法得到執行的機會，從而長時間處于等待狀態的情況。這種情況下，這些作業就會被餓死或者饑餓，因為它們無法得到所需的系統資源而無法完成執行。
?

看如下例子：

1.FCFS（先來先服務算法）

誰先到達，誰就先運行，所以作業運行順序為1->2->3->4

第一個作業完成后，第二個作業才能開始運行，所以第二個作業開始的時間是10：00

以此類推得到：

先來先服務算法的特點

先來先服務算法實現簡單，但是可以看到排在長作業后面的短作業需要等待很長時間，對短作業來說用戶體驗不好。

是否導致饑餓：此算法較為公平，不會導致饑餓

2.SJF(短作業優先調度算法)

誰的運行時間最短，誰就先運行

首先也從第一個開始，因為2，3，4都沒有到達

第一個的完成時間是10：00，這時候2，3，4都到達了，但是作業3的運行時間最短，所以接下來運行作業3

作業4的運行時間最短，所以接下來運行作業4，以此類推，最終的執行順序為：1->3->4->2

SJF算法的特點

短作業優先算法擁有“最短的”平均等待時間和平均周轉時間

是否導致饑餓：此算法會導致饑餓，如果有源源不斷的短作業進來，可能使長作業長時間得不到服務。如果一直得不到服務，則稱為“餓死”。

注：在實際情況下，作業的運行時間往往是由用戶提供的估計值，并不一定真實準確。這意味著在實際應用中，我們可能無法完全實現真正的短作業優先。

3.HRRF(高響應比優先算法)

(等待時間+運行時間)/運行時間

注:較高的響應比意味著作業等待時間相對較短，或者作業的服務時間相對較長，這可以確保作業盡快得到響應并完成。因此，響應比越高通常表示作業具有更好的調度優先級

從作業1開始：

若下一個執行的作業為作業2，那么響應比就是：（10：00-8：30）+40/40=13/4

若下一個執行的作業為作業3，那么響應比就是：（10：00-9:00）+25/25=85/25

若下一個執行的作業為作業4，那么響應比就是：（10：00-9：30）+30/30=2

因為85/25>13/4>2，下一個執行的作業是作業3

執行完后，要重新計算高響應比，響應比最高的運行，得到

若下一個執行的作業為作業2：（10：25-8：30）+40/40=155/40=3.875

若下一個執行的作業為作業4：（10：25-9：30）+30/30=85/30=2.8333...

所以下一個執行的作業為作業2,則最終執行的順序是：1->3->2->4

高響應比優先算法的特點

綜合考慮了等待時間和運行時間(要求服務時間)
等待時間相同時，要求服務時間短的優先(SJF 的優點)
要求服務時間相同時，等待時間長的優先(FCFS 的優點)
對于長作業來說，隨著等待時間越來越久，其響應比也會越來越大，從而避免了長作業饑餓的問題。

二.進程調度

以上的作業調度，我沒有提到進程二字，就是怕大家混淆起來，進程調度和作業調度是兩個不同的調度方法：

1、作業調度
作業調度又稱為高級調度，頻度較低。其主要工作是將位于外存后備隊列中的某個（或某幾個）作業調入內存，排在就緒隊列上。注意了，這個時候僅僅是將作業調入內存，并為作業創建進程、分配資源，此時進程處于就緒態，并沒有執行。

2、進程調度
進程調度又稱為低級調度，是最基本的、頻度最高的調度方式。其主要任務是從就緒隊列中選取一個（或幾個）進程，并分配處理機的過程，這時候才可以理解為“執行”。

3、區別
作業調度和進程調度最主要的區別在于，前者是為作業建立進程的過程，是將作業由外存調入內存的過程；而后者整個過程并沒有跑出內存的范圍，是將就緒態的進程變為運行態的過程。

進程調度也有饑餓的概念，同時進程調度中還有一個重要的概念：

搶占式/非搶占式：

搶占式調度：
?搶占式調度是指操作系統允許正在運行的進程被強制中斷，以便讓更高優先級的進程獲得CPU資源并開始運行。
?在搶占式調度中，操作系統會定期檢查所有正在運行的進程的優先級，并且如果有更高優先級的進程出現，操作系統會立即中斷當前進程的執行，將CPU資源分配給更高優先級的進程。
?例如，在搶占式調度中，當一個進程正在執行一個關鍵任務時，如果有更高優先級的進程需要運行，操作系統會立即中斷當前進程的執行，并將CPU資源分配給更高優先級的進程。

非搶占式調度：

?非搶占式調度是指一旦一個進程獲得處理器，它就會一直運行直到完成或者自愿讓出CPU。
?在非搶占式調度中，高優先級的進程必須等待當前正在運行的進程結束或者主動讓出CPU后，才能獲得CPU資源并開始運行。
?例如，在非搶占式調度中，當一個進程正在執行一個關鍵任務時，其他高優先級的進程需要等待該進程完成或者主動讓出CPU，才能獲得CPU資源并開始執行。

正因為進程調度有這兩個性質，所以除了擁有作業調度的三種算法（FCFS,SJF,HRRF），還有其他常見的算法：

1.SRTF（最短剩余時間優先調度算法）

SRTF與SJF最大的區別就是其是搶占式的算法。
運行原理：每當有進程加入就緒隊列改變時就需要調度，如果新到達的進程剩余時間比當前運行的進程剩余時間更短，則由新進程搶占處理機，當前運行進程重新回到就緒隊列等待下一次調度。

2.RR（時間片輪轉調度算法）

算法思想：公平地、輪流地為各個進程服務，讓每個進程在一定時間間隔內都可以得到響應。
調度程序每次把CPU分配給就緒隊列首進程/線程使用一個時間間隔（稱為時間片），就緒隊列中的每個進程/線程輪流運行一個時間片。

算法規則：按照各進程到達就緒隊列的順序，輪流讓各個進程執行一個時間片（每次選擇的都是排在就緒隊列隊頭的進程）。若進程未在一個時間片內執行完，則剝奪處理機，將進程重新放到就緒隊列隊尾重新排隊。
時間片的選取：時間片大小的確定要從進程個數、切換開銷、系統效率和響應時間等方面考慮。
常用輪轉法：
① 最常用的輪轉法是等時間片輪轉法，每個進程輪流運行相同時間片。
② 改進的輪轉法對于不同的進程分配不同的時間片，時間片的長短可以動態修改。

是否搶占式：搶占式

是否會產生饑餓：不會

優點：公平，響應快，適用于分時操作系統。
缺點：由于高頻率的進程切換，因此有一定開銷；不區分任務的緊急性。

對于時間片輪轉調度算法的實現，建議觀看如下視頻：

RR時間片輪轉調度算法 ～相同到達時間_嗶哩嗶哩_bilibili

RR時間片輪轉調度算法～不同到達時間_嗶哩嗶哩_bilibili

時間片太大或太小
① 如果時間片太大，使得每個進程都可以在一個時間片內就完成，則時間片輪轉調度算法退化為先來先服務調度算法，并且會增大進程的響應時間。
② 如果時間片太小，進程調度、切換是有時間代價的，會導致進程切換過于頻繁，系統會花大量的時間來處理進程切換，從而導致實際用于進程執行的時間比例減小。

3.PSA(優先級調度算法)

算法思想：根據任務的緊急程度來決定處理順序。
算法規則：根據確定的優先級選取進程/線程，每次總是選擇就緒隊列中優先級最高者運行。
用戶進程/線程優先級的規定者有兩種：
① 用戶：用戶自己提出優先級，稱為外部指定法。優先級越高，費用越高。
② 系統：由系統綜合考慮有關因素來確定用戶進程/線程的優先級，稱為內部指定法。
進程/線程優先級的確定方式：
根據優先級是否隨時間而變，進程/線程優先級的確定有靜態和動態兩種方式：
① 靜態優先級：在進程/線程創建時確定，此后不再改變。優先級主要由進程類型、資源需求、時間需求和用戶需求決定。
優點：比較簡單，開銷小。
缺點：不夠公平不太靈活，可能出現優先級低的作業/進程長時間得不到調度的情況。
② 動態優先級：隨時間而變，基本原則是：
a. 正在運行的進程/線程隨著占有CPU時間的增加優先級逐漸降低；
b. 就緒隊列中等待CPU的進程/線程隨著等待時間增加優先級逐漸提高。
優點：公平性好，靈活，資源利用率高。
缺點：需要花費比較多的執行程序時間，因而花費的系統開銷比較大。

是否可搶占：搶占式，非搶占式都有。

是否導致饑餓：會
若源源不斷地有高優先級進程到來，則可能導致饑餓。
區別在于：非搶占式只需在進程主動放棄處理機時進行調度即可，而搶占式還需在就緒隊列變化時，檢查是否發生搶占。
優點：用優先級區分緊急程度、重要程度，適用于實時操作系統。可靈活地調整對各種作業/進程的偏好程度。
缺點：若源源不斷地有高優先級進程到來，則可能導致饑餓。

優先級調度算法：

速通操作系統優先級調度算法_嗶哩嗶哩_bilibili

4. MLFQ(多級反饋隊列調度算法)

算法思想：對其他調度算法的折中權衡。
算法規則：
1、建立多級就緒進程隊列，各級隊列優先級從高到低，時間片從小到大。每個隊列賦予不同優先級，較高優先級隊列一般分配給較短的時間片。

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

3、處理器調度每次先從高優先級就緒隊列中選取可占有處理器的進程，只有在選不到時，才從較低優先級就緒隊列中選取進程。即只有第k級隊列為空時，才會為k+1級隊頭的進程分配時間片。

4、任務可以根據自身的行為（如CPU使用時間、等待時間等）在不同的隊列之間移動，實現動態優先級的調整。

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

是否導致饑餓：會
優點：對其他調度算法的折中權衡。
對各類進程相對公平（FCFS的優點）；
短進程只用較少的世界就可完成（SPF的優點）；
每個新到達的進程都可以很快得到響應（RR的優點）；
不必實現估計進程的運行時間（避免用戶作假）；
可靈活地調整對各類進程的偏好程度，比如：CPU密集型進程、I/O密集型進程（拓展：可以將因I/O而阻塞的進程重新放回原隊列，這樣I/O型進程就可以保持較高優先級）。
缺點：可能會導致饑餓

多級反饋隊列調度算法

【進程管理】多級反饋隊列調度算法_嗶哩嗶哩_bilibili