多級反饋隊列調(diào)度ppt課件

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

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

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

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

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

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