【Linux系統程式設計】程序常用排程算法

01. 概述

排程算法是指：根據系統的資源配置設定政策所規定的資源配置設定算法

02. 先來先服務排程算法

​ 先來先服務排程算法是一種最簡單的排程算法，也稱為先進先出或嚴格排隊方案。當每個程序就緒後，它加入就緒隊列。目前正運作的程序停止執行，選擇在就緒隊列中存在時間最長的程序運作。該算法既可以用于作業排程，也可以用于程序排程。先來先去服務比較适合于常作業（程序），而不利于段作業（程序）。

FCFS排程算法是一種最簡單的排程算法，該排程算法既可以用于作業排程也可以用于程序排程。在作業排程中，算法每次從後備作業隊列中選擇最先進入該隊列的一個或幾個作業，将它們調入記憶體，配置設定必要的資源，建立程序并放入就緒隊列。

​ 在程序排程中，FCFS排程算法每次從就緒隊列中選擇最先進入該隊列的程序，将處理機配置設定給它，使之投入運作，直到完成或因某種原因而阻塞時才釋放處理機。

​ 下面通過一個執行個體來說明FCFS排程算法的性能。假設系統中有4個作業，它們的送出時間分别是8、8.4、8.8、9，運作時間依次是2、1、0.5、0.2，系統釆用FCFS排程算法，這組作業的平均等待時間、平均周轉時間和平均帶權周轉時間如下表所示。

作業号	送出時間	運作時間	開始時間	等待時間	完成時間	周轉時間	帶權周轉時間
1	8	2	8	10	2	1
2	8.4	1	10	1.6	11	2.6	2.6
3	8.8	0.5	11	2.2	11.5	2.7	5.4
4	9	0.2	11.5	2.5	11.7	2.7	13.5

平均等待時間 t = (0+1.6+2.2+2.5)/4=1.575平均周轉時間 T = (2+2.6+2.7+2.7)/4=2.5平均帶權周轉時間 W = (1+2.6+5.牡13.5)/4=5.625

​ FCFS排程算法屬于不可剝奪算法。從表面上看，它對所有作業都是公平的，但若一個長作業先到達系統，就會使後面許多短作業等待很長時間，是以它不能作為分時系統和實時系統的主要排程政策。但它常被結合在其他排程政策中使用。例如，在使用優先級作為排程政策的系統中，往往對多個具有相同優先級的程序按FCFS原則處理。

​ FCFS排程算法的特點是算法簡單，但效率低；對長作業比較有利，但對短作業不利（相對SJF和高響應比）；有利于CPU繁忙型作業，而不利于I/O繁忙型作業。

03. 時間片輪轉排程法

時間片輪轉排程算法主要适用于分時系統。在這種算法中，系統将所有就緒程序按到達時間的先後次序排成一個隊列，程序排程程式總是選擇就緒隊列中第一個程序執行，即先來先服務的原則，但僅能運作一個時間片，如100ms。在使用完一個時間片後，即使程序并未完成其運作，它也必須釋放出（被剝奪）處理機給下一個就緒的程序，而被剝奪的程序傳回到就緒隊列的末尾重新排隊，等候再次運作。

​ 在時間片輪轉排程算法中，時間片的大小對系統性能的影響很大。如果時間片足夠大，以至于所有程序都能在一個時間片内執行完畢，則時間片輪轉排程算法就退化為先來先服務排程算法。如果時間片很小，那麼處理機将在程序間過于頻繁切換，使處理機的開銷增大，而真正用于運作使用者程序的時間将減少。是以時間片的大小應選擇适當。

​ 時間片的長短通常由以下因素确定：系統的響應時間、就緒隊列中的程序數目和系統的處理能力。

04. 短作業(SJF)優先排程算法

​ 短作業（程序）優先排程算法是指對短作業（程序）優先排程的算法。短作業優先(SJF)排程算法是從後備隊列中選擇一個或若幹個估計運作時間最短的作業，将它們調入記憶體運作。而短程序優先(SPF)排程算法，則是從就緒隊列中選擇一個估計運作時間最短的程序，将處理機配置設定給它，使之立即執行，直到完成或發生某事件而阻塞時，才釋放處理機。

​ 短作業優先排程算法是一個非搶占政策，他的原則是下一次選擇預計處理時間最短的程序，是以短程序将會越過長作業，跳至隊列頭。該算法即可用于作業排程，也可用于程序排程。但是他對長作業不利，不能保證緊迫性作業（程序）被及時處理，作業的長短隻是被估算出來的。

缺點：

• 該算法對長作業不利，SJF排程算法中長作業的周轉時間會增加。更嚴重的是，如果有一長作業進入系統的後備隊列，由于排程程式總是優先排程那些 (即使是後進來的）短作業，将導緻長作業長期不被排程（“饑餓”現象，注意區分“死鎖”。後者是系統環形等待，前者是排程政策問題）。
• 該算法完全未考慮作業的緊迫程度，因而不能保證緊迫性作業會被及時處理。
• 由于作業的長短隻是根據使用者所提供的估計執行時間而定的，而使用者又可能會有意或無意地縮短其作業的估計運作時間，緻使該算法不一定能真正做到短作業優先排程。

【注意】 SJF排程算法的平均等待時間、平均周轉時間最少。

05. 最短剩餘時間優先

​ 最短剩餘時間是針對最短程序優先增加了搶占機制的版本。在這種情況下，程序排程總是選擇預期剩餘時間最短的程序。當一個程序加入到就緒隊列時，他可能比目前運作的程序具有更短的剩餘時間，是以隻要新程序就緒，排程程式就能可能搶占目前正在運作的程序。像最短程序優先一樣，排程程式正在執行選擇函數是必須有關于處理時間的估計，并且存在長程序饑餓的危險。

06. 高響應比優先排程算法

​ 根據比率：R=(w+s)/s （R為響應比，w為等待處理的時間，s為預計的服務時間）

如果該程序被立即調用，則R值等于歸一化周轉時間（周轉時間和服務時間的比率）。R最小值為1.0，隻有第一個進入系統的程序才能達到該值。排程規則為：目前程序完成或被阻塞時，選擇R值最大的就緒程序，它說明了程序的年齡。當偏向短作業時，長程序由于得不到服務，等待時間不斷增加，進而增加比值，最終在競争中赢了短程序。和最短程序優先、最短剩餘時間優先一樣，使用最高響應比政策需要估計預計服務時間。

​ 高響應比優先排程算法主要用于作業排程，該算法是對FCFS排程算法和SJF排程算法的一種綜合平衡，同時考慮每個作業的等待時間和估計的運作時間。在每次進行作業排程時，先計算後備作業隊列中每個作業的響應比，從中選出響應比最高的作業投入運作。

根據公式可知：

• 當作業的等待時間相同時，則要求服務時間越短，其響應比越高，有利于短作業。
• 當要求服務時間相同時，作業的響應比由其等待時間決定，等待時間越長，其響應比越高，因而它實作的是先來先服務。
• 對于長作業，作業的響應比可以随等待時間的增加而提高，當其等待時間足夠長時，其響應比便可升到很高，進而也可獲得處理機。克服了饑餓狀态，兼顧了長作業。

07. 優先級排程算法

優先級排程算法又稱優先權排程算法，該算法既可以用于作業排程，也可以用于程序排程，該算法中的優先級用于描述作業運作的緊迫程度。

在作業排程中，優先級排程算法每次從後備作業隊列中選擇優先級最髙的一個或幾個作業，将它們調入記憶體，配置設定必要的資源，建立程序并放入就緒隊列。在程序排程中，優先級排程算法每次從就緒隊列中選擇優先級最高的程序，将處理機配置設定給它，使之投入運作。

根據新的更高優先級程序能否搶占正在執行的程序，可将該排程算法分為：

• 非剝奪式優先級排程算法。當某一個程序正在處理機上運作時，即使有某個更為重要或緊迫的程序進入就緒隊列，仍然讓正在運作的程序繼續運作，直到由于其自身的原因而主動讓出處理機時（任務完成或等待事件），才把處理機配置設定給更為重要或緊迫的程序。
• 剝奪式優先級排程算法。當一個程序正在處理機上運作時，若有某個更為重要或緊迫的程序進入就緒隊列，則立即暫停正在運作的程序，将處理機配置設定給更重要或緊迫的程序。

而根據程序建立後其優先級是否可以改變，可以将程序優先級分為以下兩種：

• 靜态優先級。優先級是在建立程序時确定的，且在程序的整個運作期間保持不變。确定靜态優先級的主要依據有程序類型、程序對資源的要求、使用者要求。
• 動态優先級。在程序運作過程中，根據程序情況的變化動态調整優先級。動态調整優先級的主要依據為程序占有CPU時間的長短、就緒程序等待CPU時間的長短。

08. 多級回報隊列排程算法

多級回報隊列算法，不必事先知道各種程序所需要執行的時間，他是目前被公認的一種較好的程序排程算法。

多級回報隊列排程算法的實作思想如下：

1. 應設定多個就緒隊列，并為各個隊列賦予不同的優先級，第1級隊列的優先級最高，第2級隊列次之，其餘隊列的優先級逐次降低。
2. 賦予各個隊列中程序執行時間片的大小也各不相同，在優先級越高的隊列中，每個程序的運作時間片就越小。例如，第2級隊列的時間片要比第1級隊列的時間片長一倍， ……第i+1級隊列的時間片要比第i級隊列的時間片長一倍。
3. 當一個新程序進入記憶體後，首先将它放入第1級隊列的末尾，按FCFS原則排隊等待排程。當輪到該程序執行時，如它能在該時間片内完成，便可準備撤離系統；如果它在一個時間片結束時尚未完成，排程程式便将該程序轉入第2級隊列的末尾，再同樣地按FCFS 原則等待排程執行；如果它在第2級隊列中運作一個時間片後仍未完成，再以同樣的方法放入第3級隊列……如此下去，當一個長程序從第1級隊列依次降到第 n 級隊列後，在第 n 級隊列中便釆用時間片輪轉的方式運作。
4. 僅當第1級隊列為空時，排程程式才排程第2級隊列中的程序運作；僅當第1 ~ (i-1)級隊列均為空時，才會排程第i級隊列中的程序運作。如果處理機正在執行第i級隊列中的某程序時，又有新程序進入優先級較高的隊列（第 1 ~ (i-1)中的任何一個隊列），則此時新程序将搶占正在運作程序的處理機，即由排程程式把正在運作的程序放回到第i級隊列的末尾，把處理機配置設定給新到的更高優先級的程序。

多級回報隊列的優勢有：

• 終端型作業使用者：短作業優先。
• 短批處理作業使用者：周轉時間較短。
• 長批處理作業使用者：經過前面幾個隊列得到部分執行，不會長期得不到處理。