多級回報隊列排程算法（轉）

多級回報隊列排程算法

如果有很多任務排隊等着被處理，哪個任務先被處理，哪個任務後處理，這個需要由作業系統決定，這就是排程。多級回報隊列排程算法是目前作業系統排程算法中被公認的一種較好的排程算法。它可以滿足各種類型程序的需要，既能使高優先級的作業得到響應又能使短作業（程序）迅速完成。

基本概念

多級回報隊列排程算法是一種根據先來先服務原則給就緒隊列排序，為就緒隊列賦予不同的優先級數，不同的時間片，按照優先級搶占CPU的排程算法。算法的實施過程如下：

按照先來先服務原則排序，設定N個就緒隊列為Q1，Q2...QN，每個隊列中都可以放很多作業；
為這N個就緒隊列賦予不同的優先級，第一個隊列的優先級最高，第二個隊列次之，其餘各隊列的優先權逐個降低；
設定每個就緒隊列的時間片，優先權越高，算法賦予隊列的時間片越小。時間片大小的設定按照實際作業（程序）的需要調整；
程序在進入待排程的隊列等待時，首先進入優先級最高的Q1等待。
首先排程優先級高的隊列中的程序。若高優先級中隊列中已沒有排程的程序，則排程次優先級隊列中的程序。例如：Q1,Q2,Q3三個隊列，隻有在Q1中沒有程序等待時才去排程Q2，同理，隻有Q1,Q2都為空時才會去排程Q3。
對于同一個隊列中的各個程序，按照時間片輪轉法排程。比如Q1隊列的時間片為N，那麼Q1中的作業在經曆了時間片為N的時間後，若還沒有完成，則進入Q2隊列等待，若Q2的時間片用完後作業還不能完成，一直進入下一級隊列，直至完成。
在低優先級的隊列中的程序在運作時，又有新到達的作業，那麼在運作完這個時間片後，CPU馬上配置設定給新到達的作業即搶占式排程CPU。

此算法應用于同一個資源的多個使用者可分優先級使用資源的情況。

假設系統中有3個就緒隊列Q1,Q2,Q3，時間片分别為2，4，8。

現在有3個作業J1,J2,J3分别在時間 0 ，1，3時刻到達。而它們所需要的CPU時間分别是3，2，1個時間片。

1、時刻0： J1到達。于是進入到隊列1 ，運作1個時間片，時間片還未到，此時J2到達。

2、時刻1： J2到達。由于時間片仍然由J1掌控，于是等待。 J1在運作了1個時間片後，已經完成了在Q1中的2個時間片的限制，于是J1置于Q2等待被排程。現在處理機配置設定給J2。

3、時刻2： J1進入Q2等待排程，J2獲得CPU開始運作。

4、時刻3：J3到達，由于J2的時間片未到，故J3在Q1等待排程，J1也在Q2等待排程。

5、時刻4：J2處理完成，由于J3，J1都在等待排程，但是J3所在的隊列比J1所在的隊列的優先級要高，于是J3被排程，J1繼續在Q2等待。

6、時刻5：J3經過1個時間片，完成。

7、時刻6：由于Q1已經空閑，于是開始排程Q2中的作業，則J1得到處理器開始運作。

8、時刻7：J1再經過一個時間片，完成了任務。于是整個排程過程結束。

案例：中國男人在婆媳關系的融洽中起着非常重要的作用。現有一例子，母親有一件事情A要男人幫忙，1小時後妻子也有一件事情B要男人幫忙，兩件事情各自需要的時間為2小時和1小時。假設事情在家裡就可以完成，男人在家，母親叫兒子幫忙後，男人開始做的時間為下午3:00。男人該怎麼樣配置設定做事情的順序？

解決步驟：

這個過程中，男人既完了了母親的任務，也完成了妻子的任務，兩件事情交叉處理，沒有出現母親一直等，或是妻子一直等的情況。這就是多任務的一種排程方式。