處理機排程算法詳解----作業排程

處理機排程算法詳解----作業排程

​ 在之前的理論篇中，我們也介紹了處理機排程的層次，不同的作業系統也會根據自己的設計目标來配置不同層次的排程算法，并且因為排程算法衆多，如果全部糅雜在一起來講，會讓人比較困惑，是以将排程算法按照層次來講解，本文會先講作業排程算法。下文涉及到的一些名詞，如果不明白，可以參考上一篇​​博文​​。

​ 作業排程排程的對象是作業，作業在概念上和程式還是有些差別的，作業是處于外存中的，也就是在後備隊列上的，作業排程的任務就是從外存的後備對列選取某些作業調入記憶體，并為他們建立程序、配置設定必要的資源，也隻有作業被調入到記憶體中，并為之配置設定資源，才能完成程序的建立工作，OS才可以進行其他的排程。

​ 作業排程其執行周期較長，大約幾分鐘一次，是以也稱為長程排程。下面我們一起來看下作業排程的幾種排程算法。

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

​ FCFS是最早期、最簡單的排程算法，是一種非搶占式的排程算法，該算法既可用于作業排程也可用于程序排程。

​ 在用于作業排程時，系統按照作業到達的先後次序來進行排程，從後備作業隊列中選擇幾個最先進入該隊列的作業，将他們調入記憶體，為他們建立程序和配置設定資源，并将程序插入到就緒隊列中。

​ 在用于程序排程時，把處理機配置設定給最先進入就緒隊列的程序，一個程序一旦分得處理機，便執行下去，直到該程序完成或阻塞時，才釋放處理機。（非搶占式）

​ 缺點：沒考慮優先級。

​ FCFS有利于長作業而不利于短作業，因為短作業必須一直等待前面的長作業執行完畢才能執行，而長作業又需要執行很長時間，造成了短作業等待時間過長。

​ FCFS有利于CPU繁忙型作業而不利于I/O繁忙型作業，因為對于I/O繁忙型作業，處理機需要等待I/O完成，這樣會導緻CPU的使用率降低。

2.短作業優先（SJF）排程算法

​ 由于在實際情況中，短作業所占的比重較大，為了能使它們能比長作業優先執行，短作業優先算法由此産生。SJF以作業的長短來計算優先級，作業越短，其優先級越高。作業的長短是以作業所要求的運作時間來衡量的。SJF也是非搶占式的，同樣可以分别用于作業排程和程序排程。

​ 缺點：

1. 必須預知作業的運作時間；
2. 對長作業非常不利，長作業的周轉時間會明顯增長，長作業甚至會發生饑餓現象；
3. 在采用SJF算法時，人-機無法實作互動；
4. 該排程算法完全未考慮作業的緊迫程度。

對于上面的3、4兩點，不隻是SJF，FCFS同樣存在類似的問題。

3.高響應比優先（HRRN）排程算法

​ 綜合上述兩種排程算法的缺點，也就是綜合考慮作業運作的時間和等待時間，産生了高響應比優先排程算法。因為HRRN既考慮了作業的等待時間，又考慮了作業運作時間的排程算法，是以既照顧了短作業，又不使長作業的等待時間過長，進而改善排程的性能。

​ HRRN因為綜合考慮了作業運作的時間和等待時間，是以就需要為每個作業引入一個動态優先級，即優先級是可以改變的，令它随作業等待的時間延長而增加，這将使長作業的優先級在等待期間不斷增加，當等待時間足夠長時，必然有機會被作業排程算法選中，并将改作業調入記憶體中。

​ 優先級的定義描述如下：

優

先

權

=

等

待

時

間

+

要

求

服

務

優先權=\frac{等待時間 + 要求服務時間}{要求服務時間}

優先權=要求服務時間等待時間+要求服務時間​

​ 由上式可以看出：1.如果作業的等待時間相同，則要求服務時間越短，其優先級越高，類似于SJF算法，有利于短作業。2.當要求服務時間相同時，作業的優先權有決定于其等待時間，因為有類似于FCFS算法。3.對于場作業的優先級，可以随等待的時間增加而增加，當等待時間足夠長時，也可被選中。

​ 不過該算法實作了FCFS與SJF兩者的較好折中，但是因為增加的動态優先級，每次在進行排程之前，都需要先做響應比的計算，顯然會增加系統開銷。

4.例子

​ 為了加深大家的了解，我給出一道例題，同樣，為了簡單起見，我們規定OS是單道批處理系統，即OS一次隻能執行一個作業，被作業排程算法選中後，即可獲得處理機并執行，無須等待進行排程程式為之配置設定處理機。

​ 例題：假設一個系統中有5個作業，它們的到達時間和服務時間如下表所示，忽略I/O以及其他開銷，若分别按先來先服務，短程序優先，高響應比優先進行CPU排程，請給出各程序的開始執行時間，完成時間，周轉時間，帶權周轉時間，平均周轉時間和平均帶權周轉時間。

作業名	到達時間/h	服務時間/h
A	3
B	2	6
C	4
D		5
E	8

​ 答案如下：

​ 先來先服務排程算法：

程序名
開始時間		9	13	18
完成時間					20
周轉時間		7		12
帶權周轉時間	1	7/6	2.25	2.4

​ 平均周轉時間為：T = (3+7+9+12+12)/5=8.6

​ 平均帶權周轉時間為：W=(1+7/6+2.25+2.4+6)/5≈2.56

​ 短作業優先排程算法：

		11	15
				14
			2.75	2.8	1.5

​ 平均周轉時間為：T = (3+7+11+14+3)/5=7.6

​ 平均帶權周轉時間為：W=(1+7/6+2.75+2.8+1.5)/5≈1.84

​ 高響應比優先排程算法：

					1.4

​ 平均周轉時間為：T = (3+7+9+14+7)/5=8

​ 平均帶權周轉時間為：W=(1+7/6+2.25+2.8+1.4)/5≈1.72

注：在每次執行排程時，需要計算動态優先級，本題中省略計算過程。

​ 又到了分隔線以下，本文到此就結束了，本文内容全部都是由部落客自己進行整理并結合自身的了解進行總結，如果有什麼錯誤，還請批評指正。

​ 如有興趣，還可以檢視我的其他幾篇部落格，都是OS的幹貨，喜歡的話還請點贊、評論加關注_。