多級反饋隊列調度算法

多級反饋隊列調度算法是一種CPU處理機調度算法，UNIX操作系統采取的便是這種調度算法。　　

多級反饋隊列調度算法即能使高優先級的作業得到響應又能使短作業(進程)迅速完成。（對比一下FCFS與高優先響應比調度算法的缺陷）。　　

多級(假設為N級)反饋隊列調度算法可以如下原理：　　

1、設有N個隊列（Q1,Q2….QN），其中各個隊列對於處理機的優先級是不一樣的，也就是說位於各個隊列中的作業(進程)的優先級也是不一樣的。一般來說，優先級Priority(Q1) > Priority(Q2) > … > Priority(QN)。怎麼講，位於Q1中的任何一個作業(進程)都要比Q2中的任何一個作業(進程)相對於CPU的優先級要高（也就是說，Q1中的作業一定要比Q2中的作業先被處理機調度），依次類推其它的隊列。

2、對於某個特定的隊列來說，裡面是遵循時間片輪轉法。也就是說，位於隊列Q2中有N個作業，它們的運行時間是通過Q2這個隊列所設定的時間片來確定的（為了便於理解，我們也可以認為特定隊列中的作業的優先級是按照FCFS來調度的）。　　

3、各個隊列的時間片是一樣的嗎？不一樣，這就是該算法設計的精妙之處。各個隊列的時間片是隨著優先級的增加而減少的，也就是說，優先級越高的隊列中它的時間片就越短。同時，為了便於那些超大作業的完成，最後一個隊列QN(優先級最低的隊列)的時間片一般很大(不需要考慮這個問題)。　　

多級反饋隊列調度算法描述：　　

1、進程在進入待調度的隊列等待時，首先進入優先級最高的Q1等待。　　

2、首先調度優先級高的隊列中的進程。若高優先級中隊列中已沒有調度的進程，則調度次優先級隊列中的進程。例如：Q1,Q2,Q3三個隊列，只有在Q1中沒有進程等待時才去調度Q2，同理，只有Q1,Q2都為空時才會去調度Q3。　　

3、對於同一個隊列中的各個進程，按照時間片輪轉法調度。比如Q1隊列的時間片為N，那麼Q1中的作業在經歷了N個時間片後若還沒有完成，則進入Q2隊列等待，若Q2的時間片用完後作業還不能完成，一直進入下一級隊列，直至完成。　　

4、在低優先級的隊列中的進程在運行時，又有新到達的作業，那麼在運行完這個時間片後，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再經過一個時間片，完成了任務。於是整個調度過程結束。　　

從上面的例子看，在多級反饋隊列中，後進的作業不一定慢完成。