一种公平的动态轮转算法

胡赛　赵碧海　熊慧军

摘要时间片轮转算法作为一种经典的调度算法得到了广泛的应用．针对时间片轮转算法的调度策略和时间片长度的选取等问题开展深入的研究，提出了一种改进的动态轮转算法，算法是短作业优先算法、多级队列算法和时间片轮转算法的综合和发展．利用生灭过程理论建立了时间片轮转算法和动态轮转算法的性能模型，分析了两种算法的平均等待时间和平均周转时间，引入性能提高百分比的概念对比两种算法的差异．实验结果和理论分析均表明改进算法的性能优于传统的时间片轮转算法．

关键词时间片轮转；短作业优先；动态时间片；性能

中图分类号TP311 文献标识码A 文章编号10002537（2012）05003007

1.1定义及相关符号说明

为便于描述，首先给出论文中涉及的一些定义和符号说明.λ：进程进入等待队列的到达率，μ：CPU为进程提供服务的服务率，ρ：服务强度，即ρ=λμ，L：平均队长，Lq：平均等待的进程数量.

定义1性能提高比Rperformance_improve=WRR－WDRRWDRR×100%，WRR指传统的时间片轮转算法的平均周转时间，WDRR指改进的动态时间片轮转算法的平均周转时间．

定义2若进程调度过程具有下列性质：

（1）进程到达等待队列的数量服从参数为λ的泊松分布，时间间隔服从参数为λ的指数分布；

（2）进程服务时间服从参数为μ的指数分布；

（3）在一个无限短的时间间隔内只有一个进程到达或离开.

则称之为一个生灭过程．

1.2动态轮转算法

本文提出的动态轮转算法（DRR）综合了短作业优先算法、时间片轮转算法（RR）和多级队列调度算法．传统时间片轮转算法中每个进程获得的时间片相同.从公平的角度来说，运行时间长的进程希望得到更多的时间片，因为它们等待的时间更长．多级队列调度算法解决了这一问题，比时间片轮转算法具有更好的公平性．但是这种算法又带来了另一种不公平.由于算法采用多个队列，调度程序从当前队列中调度进程前会检查优先级高于当前队列的等待队列中是否有进程，若有进程在等待，则会优先调度优先级较高的队列中的进程，直到所有优先级较高的队列中都为空时才调度当前队列中的进程．由于有新进程不断进入，那些沦入优先级低的队列中的进程虽然得到了较长的时间片，却一直得不到被调度的机会，甚至会出现某些进程长时间在队列中休眠．

针对时间片长度的选取，动态轮转算法综合了时间片轮转算法和多级队列算法的优势．处于就绪状态的进程在等待队列中等候调度，每个进程被调度时所获得的时间片长度各不相同：进程首轮调度时，时间片长度为固定值a，从第二轮开始，进程所得到的时间片长度与该进程已经获得的CPU服务时间成正比．用Ti表示进程第i轮调度时得到的时间片长度，则

进程控制块（PCB）包含有进程的各种计时信息，进程的调度次数和已经获得的CPU的时间，进程被调度时，从PCB中获取调度次数和执行时间，并以此计算出本次调度可获得的时间片长度，调度结束后对PCB中的该部分信息进行更新．

华金先生曾指出，在允许优先占用时，对需要服务时间短的顾客给与高优先权的方式是减少平均等待时间的好办法．基于这一思想，在调度策略上，本文采取短作业优先算法和时间片轮转算法相结合，即在同一个轮转调度周期内将原有的先来先服务的调度方式改为短进程优先的方式，并在算法中引入了服务队列的概念．服务队列是指等待队列中的进程按照所需服务时间从短到长的顺序排列而形成的进程序列，进程调度程序从服务队列中调度进程并获取CPU的服务．

本次实验生成50个任务，任务到达时间随机产生，任务预期服务时间跨度为1000～25000，RR算法的时间片q=50，DRR算法的增长速率调节参数b=2.

实验结果如图4所示，其中X轴表示任务预期服务时间，Y轴表示性能提高比.由图4可以看出，随着预期服务时间跨度增大，平均切换次数提高比不断增长，而平均周转时间和平均等待时间提高比呈波浪式缓慢增长.当服务时间跨度在b（1+b）i（i>0）ms左右时，性能提高比位于波峰；而当服务时间跨度在b（1+b）i～b（1+b）i+1ms之间，性能提高比位于波谷.由此可见，任务服务时间跨度增大，DRR算法的综合性能优势缓慢增长.

综上所述，在模拟调度环境中，DRR算法的综合性能优于RR算法.当任务数目增多，服务时间跨度增大时，DRR算法的性能更优，RR算法的时间片较小时，DRR算法的平均切换次数更优，RR算法的时间片增大时，DRR算法的平均响应时间优势增大.

图3任务数目对算法性能的影响 图4任务服务时间跨度对算法性能的影响4结论及进一步研究工作

本文提出一种改进的动态轮转算法，算法将同一轮转周期内先来先服务方式改进为短作业优先方式，有效地缩短了进程的平均周转时间；将时间片由原来的定长方式修改为根据累计运行时间而自适应地动态增长方式，解决了原有的轮转方式中存在的时间片长度选取的矛盾，同时也提高了进程的响应时间，缩短了平均周转时间和等待时间．

本文的分析是以进程服务时间服从指数分布为前提.下一步工作中，我们将分析服务时间服从一般分布时算法如何有效工作等问题．

参考文献：

［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.