多級反饋隊列調度算法

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

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

2、對於優先級最低的隊列來説，裏面是遵循時間片輪轉法。也就是説，位於隊列QN中有M個作業，它們的運行時間是通過QN這個隊列所設定的時間片來確定的；對於其他隊列，遵循的是先來先服務算法，每一進程分配一定的時間片，若時間片運行完時進程未結束，則進入下一優先級隊列的末尾。

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

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

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

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

4、在最後一個隊列QN中的各個進程，按照時間片輪轉分配時間片調度。

5、在低優先級的隊列中的進程在運行時，又有新到達的作業，此時須立即把正在運行的進程放回當前隊列的隊尾，然後把處理機分給高優先級進程。換而言之，任何時刻，只有當第1~i-1隊列全部為空時，才會去執行第i隊列的進程（搶佔式）。特別説明，當再度運行到當前隊列的該進程時，僅分配上次還未完成的時間片，不再分配該隊列對應的完整時間片。

假設系統中有3個反饋隊列Q1,Q2,Q3，時間片分別為2，4，8。 ^[1] 

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

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

2、時刻1 J2到達。 由於同一隊列採用先來先服務，於是J2等待。 J1在運行了1個時間片後，已經完成了在Q1中的2個時間片的限制，於是J1置於Q2等待被調度。當前處理機分配給J2。

3、時刻2 J1進入Q2等待調度，J2獲得CPU開始運行。

4、時刻3 J3到達，由於同一隊列採用先來先服務，故J3在Q1等待調度，J1也在Q2等待調度。

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

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

7、時刻6 由於Q1已經空閒，於是開始調度Q2中的作業，則J1得到處理器開始運行。 J1再經過一個時間片，完成了任務。於是整個調度過程結束。

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