多級反饋佇列調度算法

多級反饋佇列調度算法是一種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再經過一個時間片，完成了任務。於是整個調度過程結束。
從上面的例子看，在多級反饋佇列中，後進的作業不一定慢完成。