Page 352 - 《软件学报》2020年第11期

曾理宁 等:一种基于动态需求边界的混合关键级作业调度算法 3667

作业集生成的方式是:作业集被初始化为空τ=∅,然后依次随机生成混合关键级作业,在满足系统约束的情
况下,依次加入作业集中,直到作业集生成完成.其中,添加作业时的约束是:在生成任何一个作业后都计算所有
χ
作业的动态需求边界,并依此获得关键级的松弛时间,如果所有的关键级松弛时间都满足 S ≥0,那么把该作业
加入作业集中;否则放弃该作业.作业集生成完成的标志是:连续生成 3 个作业不满足作业添加的约束,或者不满
足作业的最大负载.
4.2 实验对比
为了测试 CSDDB 的性能,本文主要从两个方面进行仿真:(1) 系统关键级;(2) 作业集整体完成率.实验方式
如下.
(1) 按照第 4.1 节中描述的方式产生作业集.
(2) 设定超载概率分别为 25%与 50%,在不同的系统总负载条件下分别进行仿真.
(3) 分别使用 CSDDB,BP,OCBP 以及 CaP 算法对同一作业集进行调度,并分别记录结果.
(4) 将上述两个步骤重复执行 20 次,取 20 次结果的平均值作为最终的实验结果.
4.2.1 系统关键级的对比实验
在混合关键级作业集的调度中,系统关键级是调度正确性的重要体现.根据定义 3,系统关键级越低,意味着
有更多关键级下的作业能够被正确调度,算法性能越好;反之,系统关键级越高,意味着调度能够保证正确执行
的作业越少,算法性能越差.关于系统关键级的对比实验结果如图 3 与图 4 所示.

Fig.3 Average system criticality when P χ =25%
图 3 当 P χ =25%时的平均系统关键级

Fig.4 Average system criticality when P χ =50%
图 4 当 P χ =50%时的平均系统关键级

在图 3 和图 4 中,x 轴表示系统负载;y 轴表示 20 次运行中,系统关键级的平均值.可以看出,在 4 种算法中,
CSDDB 相对于 BP、OCBP 与 CaP,能够使得系统关键级更低.这意味着 CSDDB 在使系统满足更多关键级的正