胡賽 趙碧?!⌒芑圮?/p>
摘要時(shí)間片輪轉(zhuǎn)算法作為一種經(jīng)典的調(diào)度算法得到了廣泛的應(yīng)用.針對(duì)時(shí)間片輪轉(zhuǎn)算法的調(diào)度策略和時(shí)間片長度的選取等問題開展深入的研究,提出了一種改進(jìn)的動(dòng)態(tài)輪轉(zhuǎn)算法,算法是短作業(yè)優(yōu)先算法、多級(jí)隊(duì)列算法和時(shí)間片輪轉(zhuǎn)算法的綜合和發(fā)展.利用生滅過程理論建立了時(shí)間片輪轉(zhuǎn)算法和動(dòng)態(tài)輪轉(zhuǎn)算法的性能模型,分析了兩種算法的平均等待時(shí)間和平均周轉(zhuǎn)時(shí)間,引入性能提高百分比的概念對(duì)比兩種算法的差異.實(shí)驗(yàn)結(jié)果和理論分析均表明改進(jìn)算法的性能優(yōu)于傳統(tǒng)的時(shí)間片輪轉(zhuǎn)算法.
關(guān)鍵詞時(shí)間片輪轉(zhuǎn);短作業(yè)優(yōu)先;動(dòng)態(tài)時(shí)間片;性能
中圖分類號(hào)TP311 文獻(xiàn)標(biāo)識(shí)碼A 文章編號(hào)10002537(2012)05003007
1.1定義及相關(guān)符號(hào)說明
為便于描述,首先給出論文中涉及的一些定義和符號(hào)說明.λ:進(jìn)程進(jìn)入等待隊(duì)列的到達(dá)率,μ:CPU為進(jìn)程提供服務(wù)的服務(wù)率,ρ:服務(wù)強(qiáng)度,即ρ=λμ,L:平均隊(duì)長,Lq:平均等待的進(jìn)程數(shù)量.
定義1性能提高比Rperformance_improve=WRR-WDRRWDRR×100%,WRR指傳統(tǒng)的時(shí)間片輪轉(zhuǎn)算法的平均周轉(zhuǎn)時(shí)間,WDRR指改進(jìn)的動(dòng)態(tài)時(shí)間片輪轉(zhuǎn)算法的平均周轉(zhuǎn)時(shí)間.
定義2若進(jìn)程調(diào)度過程具有下列性質(zhì):
(1)進(jìn)程到達(dá)等待隊(duì)列的數(shù)量服從參數(shù)為λ的泊松分布,時(shí)間間隔服從參數(shù)為λ的指數(shù)分布;
(2)進(jìn)程服務(wù)時(shí)間服從參數(shù)為μ的指數(shù)分布;
(3)在一個(gè)無限短的時(shí)間間隔內(nèi)只有一個(gè)進(jìn)程到達(dá)或離開.
則稱之為一個(gè)生滅過程.
1.2動(dòng)態(tài)輪轉(zhuǎn)算法
本文提出的動(dòng)態(tài)輪轉(zhuǎn)算法(DRR)綜合了短作業(yè)優(yōu)先算法、時(shí)間片輪轉(zhuǎn)算法(RR)和多級(jí)隊(duì)列調(diào)度算法.傳統(tǒng)時(shí)間片輪轉(zhuǎn)算法中每個(gè)進(jìn)程獲得的時(shí)間片相同.從公平的角度來說,運(yùn)行時(shí)間長的進(jìn)程希望得到更多的時(shí)間片,因?yàn)樗鼈兊却臅r(shí)間更長.多級(jí)隊(duì)列調(diào)度算法解決了這一問題,比時(shí)間片輪轉(zhuǎn)算法具有更好的公平性.但是這種算法又帶來了另一種不公平.由于算法采用多個(gè)隊(duì)列,調(diào)度程序從當(dāng)前隊(duì)列中調(diào)度進(jìn)程前會(huì)檢查優(yōu)先級(jí)高于當(dāng)前隊(duì)列的等待隊(duì)列中是否有進(jìn)程,若有進(jìn)程在等待,則會(huì)優(yōu)先調(diào)度優(yōu)先級(jí)較高的隊(duì)列中的進(jìn)程,直到所有優(yōu)先級(jí)較高的隊(duì)列中都為空時(shí)才調(diào)度當(dāng)前隊(duì)列中的進(jìn)程.由于有新進(jìn)程不斷進(jìn)入,那些淪入優(yōu)先級(jí)低的隊(duì)列中的進(jìn)程雖然得到了較長的時(shí)間片,卻一直得不到被調(diào)度的機(jī)會(huì),甚至?xí)霈F(xiàn)某些進(jìn)程長時(shí)間在隊(duì)列中休眠.
針對(duì)時(shí)間片長度的選取,動(dòng)態(tài)輪轉(zhuǎn)算法綜合了時(shí)間片輪轉(zhuǎn)算法和多級(jí)隊(duì)列算法的優(yōu)勢(shì).處于就緒狀態(tài)的進(jìn)程在等待隊(duì)列中等候調(diào)度,每個(gè)進(jìn)程被調(diào)度時(shí)所獲得的時(shí)間片長度各不相同:進(jìn)程首輪調(diào)度時(shí),時(shí)間片長度為固定值a,從第二輪開始,進(jìn)程所得到的時(shí)間片長度與該進(jìn)程已經(jīng)獲得的CPU服務(wù)時(shí)間成正比.用Ti表示進(jìn)程第i輪調(diào)度時(shí)得到的時(shí)間片長度,則
進(jìn)程控制塊(PCB)包含有進(jìn)程的各種計(jì)時(shí)信息,進(jìn)程的調(diào)度次數(shù)和已經(jīng)獲得的CPU的時(shí)間,進(jìn)程被調(diào)度時(shí),從PCB中獲取調(diào)度次數(shù)和執(zhí)行時(shí)間,并以此計(jì)算出本次調(diào)度可獲得的時(shí)間片長度,調(diào)度結(jié)束后對(duì)PCB中的該部分信息進(jìn)行更新.
華金先生曾指出,在允許優(yōu)先占用時(shí),對(duì)需要服務(wù)時(shí)間短的顧客給與高優(yōu)先權(quán)的方式是減少平均等待時(shí)間的好辦法.基于這一思想,在調(diào)度策略上,本文采取短作業(yè)優(yōu)先算法和時(shí)間片輪轉(zhuǎn)算法相結(jié)合,即在同一個(gè)輪轉(zhuǎn)調(diào)度周期內(nèi)將原有的先來先服務(wù)的調(diào)度方式改為短進(jìn)程優(yōu)先的方式,并在算法中引入了服務(wù)隊(duì)列的概念.服務(wù)隊(duì)列是指等待隊(duì)列中的進(jìn)程按照所需服務(wù)時(shí)間從短到長的順序排列而形成的進(jìn)程序列,進(jìn)程調(diào)度程序從服務(wù)隊(duì)列中調(diào)度進(jìn)程并獲取CPU的服務(wù).
本次實(shí)驗(yàn)生成50個(gè)任務(wù),任務(wù)到達(dá)時(shí)間隨機(jī)產(chǎn)生,任務(wù)預(yù)期服務(wù)時(shí)間跨度為1000~25000,RR算法的時(shí)間片q=50,DRR算法的增長速率調(diào)節(jié)參數(shù)b=2.
實(shí)驗(yàn)結(jié)果如圖4所示,其中X軸表示任務(wù)預(yù)期服務(wù)時(shí)間,Y軸表示性能提高比.由圖4可以看出,隨著預(yù)期服務(wù)時(shí)間跨度增大,平均切換次數(shù)提高比不斷增長,而平均周轉(zhuǎn)時(shí)間和平均等待時(shí)間提高比呈波浪式緩慢增長.當(dāng)服務(wù)時(shí)間跨度在b(1+b)i(i>0)ms左右時(shí),性能提高比位于波峰;而當(dāng)服務(wù)時(shí)間跨度在b(1+b)i~b(1+b)i+1ms之間,性能提高比位于波谷.由此可見,任務(wù)服務(wù)時(shí)間跨度增大,DRR算法的綜合性能優(yōu)勢(shì)緩慢增長.
綜上所述,在模擬調(diào)度環(huán)境中,DRR算法的綜合性能優(yōu)于RR算法.當(dāng)任務(wù)數(shù)目增多,服務(wù)時(shí)間跨度增大時(shí),DRR算法的性能更優(yōu),RR算法的時(shí)間片較小時(shí),DRR算法的平均切換次數(shù)更優(yōu),RR算法的時(shí)間片增大時(shí),DRR算法的平均響應(yīng)時(shí)間優(yōu)勢(shì)增大.
圖3任務(wù)數(shù)目對(duì)算法性能的影響 圖4任務(wù)服務(wù)時(shí)間跨度對(duì)算法性能的影響4結(jié)論及進(jìn)一步研究工作
本文提出一種改進(jìn)的動(dòng)態(tài)輪轉(zhuǎn)算法,算法將同一輪轉(zhuǎn)周期內(nèi)先來先服務(wù)方式改進(jìn)為短作業(yè)優(yōu)先方式,有效地縮短了進(jìn)程的平均周轉(zhuǎn)時(shí)間;將時(shí)間片由原來的定長方式修改為根據(jù)累計(jì)運(yùn)行時(shí)間而自適應(yīng)地動(dòng)態(tài)增長方式,解決了原有的輪轉(zhuǎn)方式中存在的時(shí)間片長度選取的矛盾,同時(shí)也提高了進(jìn)程的響應(yīng)時(shí)間,縮短了平均周轉(zhuǎn)時(shí)間和等待時(shí)間.
本文的分析是以進(jìn)程服務(wù)時(shí)間服從指數(shù)分布為前提.下一步工作中,我們將分析服務(wù)時(shí)間服從一般分布時(shí)算法如何有效工作等問題.
參考文獻(xiàn):
[1]BEHEARHS,MOHANTYR,DEBASHREEN.Anewproposeddynamicquantumwithreadjustedroundrobinschedulingalgorithmanditsperformanceanalysis[J].InterJComputAppl,2010,5(5):1015.
[2]RAMIJM.Selfadjustmenttimequantuminroundrobinalgorithmdependingonbursttimeofthenowrunningprocesses[J].AmJApplSci,2009,6(10):18311837.
[3]SAADZR,SAFWATHH,SAMIHM.Improvingwaitingtimeoftasksscheduledunderpreemptiveroundrobinusingchangeabletimequantum[EB/OL].2010,http://arxiv.org/abs/1003.5342.
[4]RAKESHKY,AHHISHEKKM,NAVINP.AnimprovedroundrobinschedulingalgorithmforCPUscheduling[J].InterJComputSciEng,2010,2(4):10641066.
[5]MAMUNURR,NASIMA.AnewmultilevelCPUschedulingalgorithm[J].JApplSci,2006,6(9):20362039.
[6]HELMYT,DEKDOUKA.Burstroundrobinasaproportionalshareschedulingalgorithm[C]//IEEEGCC,Urumchi,Xinjiang,China,1618Aug,2007.Wiley:IEEEComputerSocietyPress,2007:424428.
[7]MOHAMMEDA.BestjobfirstCPUschedulingalgorithm[J].InforTechJ,2007,6(2):288293.
[8]YAASHUWANTHC.Anewschedulingalgorithmsforrealtimetasks[J].InterJComputSciInforSecurity,2009,6(2):6166.
[9]PANDURANGARM,SHETK,ROOPAK.Asimplifiedstudyofschedulerforrealtimeandembeddedsystemdomain[J].InterJComputCog,2009,5(22):6073.
[10]SHUKLAD,OJHAS,JAINS.DatamodelapproachandMarkovchainbasedanalysisofmultilevelqueuescheduling[J].JApplComputSciMath,2010,8(4):5056.
[11]SHUKLAD,JAINS,SINGHAIR,etal.AMarkovchainmodelfortheanalysisofroundrobinschedulingscheme[J].JAdvNetworkAppl,2009,1(1):17.
[12]PANDEYD,VANDANA.Improvedroundrobinpolicyamathematicalapproach[J].InterJComputSciEng,2010,2(4):948954.