轮转调度算法中动态时间片的CPN实现.doc

轮转调度算法中动态时间片的CPN实现
作者:

摘 要: 基于时间片的轮转调度算法中时间片大小影响着进程切换次数以及等待时间等方面。本文改进了时间片的取值方法,)]
else if lg 1=andalso tst < time then []
else
let
val tlt= ltask
val tlthd= 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和等待时间。
基于时间片的轮转调度算法的CPN模型
图1是基于时间片的轮转调度算法的CPN模型。整个流程是先按照进程到达时间的先后进行排序,然后按照初始时间片进行调度,并更新就绪队列和此轮被调度的进程信息,最后根据时间片大小调整算法,调整时间片的大小,对就绪队列再次进行调度。重复以上过程,直至就绪队列为空。
其中sort变迁完成根据指定的规则(可按到达时间或burst time)对进程进行排序生成就绪队列。Compute变迁完成三部分计算,第一部分根据时间片的大小,就绪队列队头的进程信息,可以占用CPU的起始时间对就绪队列中的进程进行更新,要么进程移除就绪队列,要么进程继续排在队首,要么进程排在队尾,此项信息存在库所SortTask中;第二部分根据时间片大小,就绪队列中队首进程的信息,更新下一次可以占用CPU的起始时间,此项信息存在库所FirstTaskInformation中;第三部分更新调度完成的进程队列信息,包括更新进程的开始服务时间,结束服务时间,等待时间和周转时间等信息,此项信息存在库所UpdateTask中,初始值为空。
一个进程在一个时间片的调用过程中,会出现以下两种情况,第一,一个时间片内完成了调度,此时需要退出就绪队列;第二,该时间片完成后并未完成整个调度,此时需要再次加入就绪队列等待下次调度,再次加入就绪队列分两种情况,第一,其完成时间大于就绪队列队首进程的开始时间,那么需要加入队尾;第二,其完成时间小于就绪队列队首的开始时间,那么需要加入队首,直接开始下一轮调度。
2 实验分析
时间片大小与等待时间的关系
对于基于