1、多級反響隊(duì)列調(diào)度多級反響隊(duì)列調(diào)度最復(fù)雜的算法多級反響隊(duì)列算法多級反響隊(duì)列算法Multilevel Feedback Queue, MFQ 多級反響隊(duì)列調(diào)度算法是一種多級反響隊(duì)列調(diào)度算法是一種CPU處置機(jī)調(diào)度算處置機(jī)調(diào)度算法，它不用事先知道各種進(jìn)程所需的執(zhí)行時(shí)間，而且法，它不用事先知道各種進(jìn)程所需的執(zhí)行時(shí)間，而且還可以滿足各種類型進(jìn)程的需求，因此它是目前被公還可以滿足各種類型進(jìn)程的需求，因此它是目前被公認(rèn)的一種較好的進(jìn)程調(diào)度算法。認(rèn)的一種較好的進(jìn)程調(diào)度算法。 UNIX操作系統(tǒng)采取操作系統(tǒng)采取的便是這種調(diào)度算法。的便是這種調(diào)度算法。 設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級和不同長度的時(shí)間片

2、；第一個(gè)隊(duì)列的優(yōu)先級最高，進(jìn)程所執(zhí)行時(shí)間片最小。 新創(chuàng)建的進(jìn)程掛到第一優(yōu)先級的隊(duì)列后，然后按 FCFS 原那么排隊(duì)等待調(diào)度。當(dāng)輪到其執(zhí)行時(shí)，如它能在時(shí)間片內(nèi)完成，便撤離系統(tǒng)；假設(shè)不能完成，便被掛入第二級隊(duì)列后，； 僅當(dāng)?shù)谝患夑?duì)列空閑時(shí)，調(diào)度程序才調(diào)度第二級隊(duì)列中的進(jìn)程運(yùn)轉(zhuǎn)，依次類推；新進(jìn)程可搶占低級進(jìn)程的處置機(jī)。1 1多級反響隊(duì)列調(diào)度算法的思想多級反響隊(duì)列調(diào)度算法的思想2 2多級反響隊(duì)列調(diào)度算法的表示圖多級反響隊(duì)列調(diào)度算法的表示圖3 3多級反響隊(duì)列調(diào)度算法的原理多級反響隊(duì)列調(diào)度算法的原理1、設(shè)有N個(gè)隊(duì)列Q1,Q2.QN，其中各個(gè)隊(duì)列對于處置機(jī)的優(yōu)先級是不一樣的，也就是說位于各個(gè)隊(duì)列中的作業(yè)(進(jìn)

3、程)的優(yōu)先級也是不一樣的。普通來說，優(yōu)先級Priority(Q1) Priority(Q2) . Priority(QN)。怎樣講，位于Q1中的任何一個(gè)作業(yè)(進(jìn)程)都要比Q2中的任何一個(gè)作業(yè)(進(jìn)程)相對于CPU的優(yōu)先級要高也就是說，Q1中的作業(yè)一定要比Q2中的作業(yè)先被處置機(jī)調(diào)度，依次類推其它的隊(duì)列。2、對于某個(gè)特定的隊(duì)列來說，里面是遵照時(shí)間片輪轉(zhuǎn)法。也就是說，位于隊(duì)列Q2中有N個(gè)作業(yè)，它們的運(yùn)轉(zhuǎn)時(shí)間是經(jīng)過Q2這個(gè)隊(duì)列所設(shè)定的時(shí)間片來確定的為了便于了解，我們也可以以為特定隊(duì)列中的作業(yè)的優(yōu)先級是按照FCFS來調(diào)度的。3 3多級反響隊(duì)列調(diào)度算法的原理多級反響隊(duì)列調(diào)度算法的原理 不一樣，這就是該算法設(shè)

4、計(jì)的精妙之處。各個(gè)隊(duì)列的時(shí)間片是隨著優(yōu)先級的添加而減少的，也就是說，優(yōu)先級越高的隊(duì)列中它的時(shí)間片就越短。同時(shí)，為了便于那些超大作業(yè)的完成，最后一個(gè)隊(duì)列QN(優(yōu)先級最低的隊(duì)列)的時(shí)間片普通很大。3、各個(gè)隊(duì)列的時(shí)間片是一樣的嗎？4 4多級反響隊(duì)列調(diào)度算法的描畫多級反響隊(duì)列調(diào)度算法的描畫1、進(jìn)程在進(jìn)入待調(diào)度的隊(duì)列等待時(shí)，首先進(jìn)入優(yōu)先級最高的Q1等待。2、首先調(diào)度優(yōu)先級高的隊(duì)列中的進(jìn)程。假設(shè)高優(yōu)先級中隊(duì)列中已沒有調(diào)度的進(jìn)程，那么調(diào)度次優(yōu)先級隊(duì)列中的進(jìn)程。例如：Q1,Q2,Q3三個(gè)隊(duì)列，只需在Q1中沒有進(jìn)程等待時(shí)才去調(diào)度Q2，同理，只需Q1,Q2都為空時(shí)才會去調(diào)度Q3。3、對于同一個(gè)隊(duì)列中的各個(gè)進(jìn)程，按

5、照時(shí)間片輪轉(zhuǎn)法調(diào)度。比如Q1隊(duì)列的時(shí)間片為N，那么Q1中的作業(yè)在閱歷了N個(gè)時(shí)間片后假設(shè)還沒有完成，那么進(jìn)入Q2隊(duì)列等待，假設(shè)Q2的時(shí)間片用完后作業(yè)還不能完成，不斷進(jìn)入下一級隊(duì)列，直至完成。4、在低優(yōu)先級的隊(duì)列中的進(jìn)程在運(yùn)轉(zhuǎn)時(shí)，又有新到達(dá)的作業(yè)，那么在運(yùn)轉(zhuǎn)完這個(gè)時(shí)間片后，CPU馬上分配給新到達(dá)的作業(yè)搶占式。5 5多級反響隊(duì)列調(diào)度算法如何運(yùn)作多級反響隊(duì)列調(diào)度算法如何運(yùn)作假設(shè)系統(tǒng)中有3個(gè)反響隊(duì)列Q1,Q2,Q3，時(shí)間片分別為2，4，8。如今有3個(gè)作業(yè)J1,J2,J3分別在時(shí)間 0 ，1，3時(shí)辰到達(dá)。而它們所需求的CPU時(shí)間分別是3，2，1個(gè)時(shí)間片。1、時(shí)辰0 J1到達(dá)。于是進(jìn)入到隊(duì)列1 ， 運(yùn)轉(zhuǎn)1個(gè)

6、時(shí)間片 ， 時(shí)間片還未到，此時(shí)J2到達(dá)。2、時(shí)辰1 J2到達(dá)。 由于時(shí)間片依然由J1掌控，于是等待。 J1在運(yùn)轉(zhuǎn)了1個(gè)時(shí)間片后，曾經(jīng)完成了在Q1中的2個(gè)時(shí)間片的限制，于是J1置于Q2等待被調(diào)度。如今處置機(jī)分配給J2。3、時(shí)辰2 J1進(jìn)入Q2等待調(diào)度，J2獲得CPU開場運(yùn)轉(zhuǎn)。5 5多級反響隊(duì)列調(diào)度算法如何運(yùn)作多級反響隊(duì)列調(diào)度算法如何運(yùn)作4、時(shí)辰3 J3到達(dá)，由于J2的時(shí)間片未到，故J3在Q1等待調(diào)度，J1也在Q2等待調(diào)度。5、時(shí)辰4 J2處置完成，由于J3，J1都在等待調(diào)度，但是J3所在的隊(duì)列比J1所在的隊(duì)列的優(yōu)先級要高，于是J3被調(diào)度，J1繼續(xù)在Q2等待。6、時(shí)辰5 J3經(jīng)過1個(gè)時(shí)間片，完成。7、時(shí)辰6 由于Q1曾經(jīng)空閑