168 程序排程

目錄

• 一、先來先服務排程算法
• 二、短作業優先排程算法
• 三、時間片輪轉法
• 四、多級回報隊列

要想多個程序交替運作，作業系統必須對這些程序進行排程，這個排程也不是随即進行的，而是需要遵循一定的法則，由此就有了程序的排程算法。

先來先服務（FCFS）排程算法是一種最簡單的排程算法，該算法既可用于作業排程，也可用于程序排程。FCFS算法比較有利于長作業（程序），而不利于短作業（程序）。由此可知，本算法适合于CPU繁忙型作業，而不利于I/O繁忙型的作業（程序）。

短作業（程序）優先排程算法（SJ/PF）是指對短作業或短程序優先排程的算法，該算法既可用于作業排程，也可用于程序排程。但其對長作業不利；不能保證緊迫性作業（程序）被及時處理；作業的長短隻是被估算出來的。

時間片輪轉(Round Robin，RR)法的基本思路是讓每個程序在就緒隊列中的等待時間與享受服務的時間成比例。在時間片輪轉法中，需要将CPU的處理時間分成固定大小的時間片，例如，幾十毫秒至幾百毫秒。如果一個程序在被排程選中之後用完了系統規定的時間片，但又未完成要求的任務，則它自行釋放自己所占有的CPU而排到就緒隊列的末尾，等待下一次排程。同時，程序排程程式又去排程目前就緒隊列中的第一個程序。

顯然，輪轉法隻能用來排程配置設定一些可以搶占的資源。這些可以搶占的資源可以随時被剝奪，而且可以将它們再配置設定給别的程序。CPU是可搶占資源的一種。但列印機等資源是不可搶占的。由于作業排程是對除了CPU之外的所有系統硬體資源的配置設定，其中包含有不可搶占資源，是以作業排程不使用輪轉法。

在輪轉法中，時間片長度的選取非常重要。首先，時間片長度的選擇會直接影響到系統的開銷和響應時間。如果時間片長度過短，則排程程式搶占處理機的次數增多。這将使程序上下文切換次數也大大增加，進而加重系統開銷。反過來，如果時間片長度選擇過長，例如，一個時間片能保證就緒隊列中所需執行時間最長的程序能執行完畢，則輪轉法變成了先來先服務法。時間片長度的選擇是根據系統對響應時間的要求和就緒隊列中所允許最大的程序數來确定的。

在輪轉法中，加入到就緒隊列的程序有3種情況：

1. 第一種是分給它的時間片用完，但程序還未完成，回到就緒隊列的末尾等待下次排程去繼續執行。
2. 第二種情況是分給該程序的時間片并未用完，隻是因為請求I/O或由于程序的互斥與同步關系而被阻塞。當阻塞解除之後再回到就緒隊列。
3. 第三種情況就是新建立程序進入就緒隊列。

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