多級反饋佇列調度算法即能使高優先權的作業得到回響又能使短作業(進程)迅速完成。(對比一下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再經過一個時間片,完成了任務。於是整個調度過程結束。
從上面的例子看,在多級反饋佇列中,後進的作業不一定慢完成。
相關詞條
-
調度算法
作業系統管理了系統的有限資源,當有多個進程(或多個進程發出的請求)要使用這些資源時,因為資源的有限性,必須按照一定的原則選擇進程(請求)來占用資源。這就...
調度算法 評價因素 確定進程調度原則 調度算法分類 linux進程調度算法 -
時間片輪轉調度算法
時間片輪轉調度是一種最古老,最簡單,最公平且使用最廣的算法。每個進程被分配一時間段,稱作它的時間片,即該進程允許運行的時間。
含義 基本原理 時間片 算法 瓶頸問題 -
進程調度
無論是在批處理系統還是分時系統中,用戶進程數一般都多於處理機數、這將導致它們互相爭奪處理機。另外,系統進程也同樣需要使用處理機。這就要求進程調度程式按一...
基本屬性 基本狀態 處理機 方式 算法 -
作業調度算法
每次調度時將CPU分派給隊首進程,讓其執行一個時間片。 進程可以未使用完一個時間片,就出讓CPU(如阻塞)。 過長-
1.先來先服務 2. 輪轉法 3. 多級反饋佇列算法 4. 優先權法 5.短作業優先法 -
計算機進程調度
系統中處於就緒狀態的進程對處理機的競爭是由進程調度程式來協調的。調度是依照確定的策略將一批進程排序,從就緒佇列中移出一個進程並給它提供處理機的使用權。
基本屬性 基本狀態 處理機 調度方式 算法 -
作業調度
作業調度的主要功能是根據作業控制塊中的信息,審查系統能否滿足用戶作業的資源需求,以及按照一定的算法,從外存的後備佇列中選取某些作業調入記憶體,並為它們創建...
作業調度簡介 作業調度算法 輪轉法 多級反饋佇列算法 靜態優先權 -
任務調度優先權
優先權是指計算機作業系統給任務指定的優先等級。它決定任務在使用資源時的優先次序。②給設備指定的優先等級。它決定設備在提出中斷請求時,得到處理機回響的先後...
任務調度 優先權的類型 任務調度算法 總結 -
執行緒調度器
執行緒調度器是一個常駐記憶體的程式,不斷地對執行緒佇列進行掃描,利用特定的算法(時間片輪轉法、優先權調度法、多級反饋佇列調度法等)找出比當前占有CPU的執行緒更...
-
動態優先權
很高,從而也可獲得處理機。多級反饋佇列多級反饋佇列調度算法是一種CPU...佇列的進程將因其動態優先權變得最高而優先獲得處理機,此即FCFS 算法...搶占式優先權調度算法時,如果再規定當前進程的優先權以速率 b 下降,則可...
定義 靜態優先權 調度算法