基本介紹
- 中文名：多級反饋佇列調度算法
- 性質：CPU處理機調度算法
- 套用：UNIX作業系統
- 領域：計算機
算法原理,算法描述,算法示例,
算法原理
多級(假設為N級)反饋佇列調度算法可以如下原理：
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個作業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再經過一個時間片，完成了任務。於是整個調度過程結束。
從上面的例子看，在多級反饋佇列中，後進的作業不一定慢完成。
