轮转调度算法中动态时间片的CPN实现
来源:用户上传
作者:
摘 要： 基于时间片的轮转调度算法中时间片大小影响着进程切换次数以及等待时间等方面。本文改进了时间片的取值方法，并通过颜色Petri网对该算法进行建模仿真，实验结果证明改进后的算法在进程切换次数，等待时间方面有着更好的性能。
关键词： 轮转调度算法;颜色Petri网;时间片
中图分类号： TP391.41 文献标识码： A DOI：10.3969/j.issn.1003-6970.2020.08.035
本文著录格式：赵丽敏，郑文艳，王文博. 轮转调度算法中动态时间片的CPN实现[J]. 软件，2020，41（08）：129-131
【Abstract】： The time slice size affects the process of switching times and waiting time in round robin scheduling algorithm. The paper improve the value of time slice， model and simulate of the algorithm based on the Color Petri nets. The experimental results prove that the improved algorithm has a better performance in switching times and waiting time.
【Key words】： Round robin scheduling algorithm; Coloured Petri nets; Slice
0 引言
基于時间片的轮转调度算法[1-4]的基本思想是把CPU的处理时间划分为一个固定的时间片，就绪队列中的进程依次占用CPU。如果在当前时间片内，进程调度全部完成那么就退出就绪队列，否则必须释放CPU，并返回就绪队列进行排队，等待再次调度。
在该算法中，时间片大小的设置非常关键。如果时间片过大，则算法退化为FCFS算法，如果过小，则会频繁切换进程，增加系统开销。国内外大量学者从各个方面对轮转调度算法进行了改进。文献[5]对进程最后一次执行时的时间片进行适当增加，从而减少进程的切换次数。文献[6]提出了短任务优先的动态时间片轮转调度算法提高了调度性能。文献[7]为解决公平性和优先级之间的矛盾提出了一种基于动态优先级驱动的RQ算法，为任务分配优先级不同的队列，调度过程中动态调整任务优先级从而动态调整就绪队列。文献[8]提出动态修改时间片，随着进程的减少，动态更改时间片为burst time的平均数，调度一次，时间片的大小更新一次。文献[9]根据进程的到达时间和burst time动态调整每个进程时间片的大小。
本文利用颜色Petri网（CPN：Coloured Petri Nets）[10]对FCFS算法及基于时间片的轮转调度算法进行建模仿真。通过具体实例展示等待时间与时间片取值间的关系，从而调整时间片从固定到动态取值。实验表明，动态时间片可以减少切换次数和等待时间。
1 相关知识
1.1 进程的属性信息
进程的属性信息定义为如下八元组：（ID，到达时间，优先级，burst time，开始时间，结束时间，等待时间，周转时间）。
其中，进程ID从编号1按顺序自动生成;进程到达时间、服务时间分布服从参数不同的指数分布;优先级从1到10随机生成。
1.2 就绪队列的生成
进程的产生根据函数随机生成，在不同的算法开始调度前，按策略重新对进程排序，从而生成就绪队列。比如按先来先服务的原则，首先按到达时间进行排序，如果到达时间相同，再按优先级进行排序，如果优先级相同，那么按id进行排序。
1.3 就绪队列的更新
fun RRTaskUpdateN（time： INT，startt ： INT，ltask ： LTask）=
if ltask = [] then []
else
let
val hdt = List.hd ltask
val lg= length ltask
val tst = #4hdt
in
if lg =1 andalso tst >= time then
[（#1 hdt， #2 hdt， # 3 hdt，# 4 hdt -time，startt， startt + time， startt -#2 hdt， 0）]
else if lg 1 = andalso tst < time then []
else
let
val tlt = List.tl ltask
val tlthd = List.hd tlt
val tlthd 4=#2 tlthd
in
if tst <= time then tl t
else
if tst > time
else
[（#1 hdt， #2 hdt # 3 hdt， # 4 hdt-time，startt，startt+time， startt-#2hdt， 0）] ^ ^tlt
else
tlt ^ ^[（#1 hdt， #2 hdt， #3 hdt， #4 hdt-time，sta rtt， startt+time， startt-#2 hdt， 0）] end
end （2）
按时间片大小，对整个就绪队列进行更新，如果判断该进程在时间片内完成调度，那么从就绪队列移除，否则，比较该进程在调度完成后，与下一个进程的到达时间进行比较，如果完成本次调度，下一个进程还未到达就绪队列那么把该进程放置就绪队列隊首，否则放在队尾。并更新进程的剩余burst time和等待时间。
1.4 基于时间片的轮转调度算法的CPN模型
图1是基于时间片的轮转调度算法的CPN模型。整个流程是先按照进程到达时间的先后进行排序，然后按照初始时间片进行调度，并更新就绪队列和此轮被调度的进程信息，最后根据时间片大小调整算法，调整时间片的大小，对就绪队列再次进行调度。重复以上过程，直至就绪队列为空。
其中sort变迁完成根据指定的规则（可按到达时间或burst time）对进程进行排序生成就绪队列。Compute变迁完成三部分计算，第一部分根据时间片的大小，就绪队列队头的进程信息，可以占用CPU的起始时间对就绪队列中的进程进行更新，要么进程移除就绪队列，要么进程继续排在队首，要么进程排在队尾，此项信息存在库所SortTask中;第二部分根据时间片大小，就绪队列中队首进程的信息，更新下一次可以占用CPU的起始时间，此项信息存在库所FirstTaskInformation中;第三部分更新调度完成的进程队列信息，包括更新进程的开始服务时间，结束服务时间，等待时间和周转时间等信息，此项信息存在库所UpdateTask中，初始值为空。
一个进程在一个时间片的调用过程中，会出现以下两种情况，第一，一个时间片内完成了调度，此时需要退出就绪队列;第二，该时间片完成后并未完成整个调度，此时需要再次加入就绪队列等待下次调度，再次加入就绪队列分两种情况，第一，其完成时间大于就绪队列队首进程的开始时间，那么需要加入队尾;第二，其完成时间小于就绪队列队首的开始时间，那么需要加入队首，直接开始下一轮调度。
2 实验分析
2.1 时间片大小与等待时间的关系
对于基于时间片的轮转调度算法，观察进程的服务时间（burst time）、进程的到达时间与等待时间三者间的关系如图2所示。图2中FCFS/RRavg/RRmedian/ Rmax/Rmin wait time分别代表FCFS算法、时间片取值为burst time的平均值/中位数/最大值/最小值的等待时间。通过观察发现：
对于到达时间比burst time大的进程来说，等待时间依次为FCFS最大，然后是时间片大小取值为平均值，中位数，最小值;对于到达时间比burst time小的话，时间片取值为最小值反而等待时间最长，取值为中位数稍好一些;到达时间和burst time差不多的情况下，时间片取值为最小值等待时间最短。
基于此对时间片大小进行如下改进：
如果burst time小于到达时间，则时间片改为burst time的最小值;
如果burst time与到达时间差值小于最小值则用进程的burst time;
如果差值大于最小值，则用burst time的中位数;
如果burst time大于到达时间，则时间片改为burst time的最大值。
改进后的进程等待时间与其他时间片取值对比图如图3所示，其中RD wait time是改进时间片取值后的等待时间，其余同图2。
2.2 时间片大小与轮转次数的关系
图4展示了时间片大小不同的轮转调度算法中，进程切换的次数。其中x轴取值为1代表FCFS调度算法，2-5时间片取值为burst time的最大值，最小值，平均值，中位数，6代表改进后的算法产生的切换次数。
综合图3和图4可知，利用本文采用的时间片大小的取值算法，不仅切换次数可以保持最低，而且等待时间也比其他取值更短。
3 结论
时间片的取值影响着整个调度的性能，如果取值为固定值，既不能体现进程的优先级也不能很好的照顾到公平性。而进程的到达时间和burst time的大小关系也影响了时间片的取值。考虑以上各种因素改进的动态时间片取值方法可以减少等待时间和切换次数。
参考文献
[1] 汤小丹编著. 计算机操作系统第4版[M]. 西安： 西安电子科技大学出版社， 2014.
[2] 黄辉. 基于权重的MPTCP 数据调度算法设计[J]. 软件， 2016， 37（02）; 77-80.
[3] 李啸剑， 王智立. 虚拟化环境中服务监控调度系统的设计与实现[J]. 软件， 2016， 37（02）： 103-106.
[4] 詹文涛， 艾中良， 刘忠麟， 等. 一种基于YARN 的高优先级作业调度实现方案[J]. 软件， 2016， 37（3）： 84-88.
[5] 肖建明， 张向利. 一种改进的时间片轮转调度算法[J]. 计算机应用， 2005（S1）： 447-448.
[6] 李正平， 程八意， 陈军宁. 优先级驱动的短任务优先RTOS进程调度算法[J]. 计算机应用研究， 2014， 31（04）： 1020- 1022+1026.
[7] 李薛剑， 李凯. 一种基于动态优先级的RQ作业调度算法[J]. 小型微型计算机系统， 2017， 38（01）： 124-128.
[8] Amar Ranjan Dash， Sandipta kumar Sahu， Sanjay Kumar Samantra. An Optimized Round Robin CPU Scheduling Algorithm with Dynamic Time Quantum[J]. International Journal of Computer Science， Engineering and Information Technology. 2015： 7-26.
[9] Dibyendu Barman. Dynamic Time Quantum in Round Robin Algorithm （DTQRR） Depending on Burst and Arrival Time of the Processes[J]. International Journal of Innovative Technology and Exploring Engineering. 2013， Vol. 2（No. 4）： 60-64.
[10] 郑文艳. 基于颜色Petri网的不确定库存模型性能仿真[J].计算机工程与应用， 2014， 50（22）： 250-255.
转载注明来源:https://www.xzbu.com/8/view-15321628.htm
