一種公平的動態(tài)輪轉(zhuǎn)算法

胡賽　趙碧?！⌒芑圮?/p>

摘要時(shí)間片輪轉(zhuǎn)算法作為一種經(jīng)典的調(diào)度算法得到了廣泛的應(yīng)用．針對時(shí)間片輪轉(zhuǎn)算法的調(diào)度策略和時(shí)間片長度的選取等問題開展深入的研究，提出了一種改進(jìn)的動態(tài)輪轉(zhuǎn)算法，算法是短作業(yè)優(yōu)先算法、多級隊(duì)列算法和時(shí)間片輪轉(zhuǎn)算法的綜合和發(fā)展．利用生滅過程理論建立了時(shí)間片輪轉(zhuǎn)算法和動態(tài)輪轉(zhuǎn)算法的性能模型，分析了兩種算法的平均等待時(shí)間和平均周轉(zhuǎn)時(shí)間，引入性能提高百分比的概念對比兩種算法的差異．實(shí)驗(yàn)結(jié)果和理論分析均表明改進(jìn)算法的性能優(yōu)于傳統(tǒng)的時(shí)間片輪轉(zhuǎn)算法．

關(guān)鍵詞時(shí)間片輪轉(zhuǎn)；短作業(yè)優(yōu)先；動態(tài)時(shí)間片；性能

中圖分類號TP311 文獻(xiàn)標(biāo)識碼A 文章編號10002537（2012）05003007

1.1定義及相關(guān)符號說明

為便于描述，首先給出論文中涉及的一些定義和符號說明.λ：進(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)的動態(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動態(tài)輪轉(zhuǎn)算法

本文提出的動態(tài)輪轉(zhuǎn)算法（DRR）綜合了短作業(yè)優(yōu)先算法、時(shí)間片輪轉(zhuǎn)算法（RR）和多級隊(duì)列調(diào)度算法．傳統(tǒng)時(shí)間片輪轉(zhuǎn)算法中每個(gè)進(jìn)程獲得的時(shí)間片相同.從公平的角度來說，運(yùn)行時(shí)間長的進(jìn)程希望得到更多的時(shí)間片，因?yàn)樗鼈兊却臅r(shí)間更長．多級隊(duì)列調(diào)度算法解決了這一問題，比時(shí)間片輪轉(zhuǎn)算法具有更好的公平性．但是這種算法又帶來了另一種不公平.由于算法采用多個(gè)隊(duì)列，調(diào)度程序從當(dāng)前隊(duì)列中調(diào)度進(jìn)程前會檢查優(yōu)先級高于當(dāng)前隊(duì)列的等待隊(duì)列中是否有進(jìn)程，若有進(jìn)程在等待，則會優(yōu)先調(diào)度優(yōu)先級較高的隊(duì)列中的進(jìn)程，直到所有優(yōu)先級較高的隊(duì)列中都為空時(shí)才調(diào)度當(dāng)前隊(duì)列中的進(jìn)程．由于有新進(jìn)程不斷進(jìn)入，那些淪入優(yōu)先級低的隊(duì)列中的進(jìn)程雖然得到了較長的時(shí)間片，卻一直得不到被調(diào)度的機(jī)會，甚至?xí)霈F(xiàn)某些進(jìn)程長時(shí)間在隊(duì)列中休眠．

針對時(shí)間片長度的選取，動態(tài)輪轉(zhuǎn)算法綜合了時(shí)間片輪轉(zhuǎn)算法和多級隊(duì)列算法的優(yōu)勢．處于就緒狀態(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é)束后對PCB中的該部分信息進(jìn)行更新．

華金先生曾指出，在允許優(yōu)先占用時(shí)，對需要服務(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)勢緩慢增長.

綜上所述，在模擬調(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)勢增大.

圖3任務(wù)數(shù)目對算法性能的影響 圖4任務(wù)服務(wù)時(shí)間跨度對算法性能的影響4結(jié)論及進(jìn)一步研究工作

本文提出一種改進(jìn)的動態(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)地動態(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.