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

3668 Journal of Software 软件学报 Vol.31, No.11, November 2020

确性这一目标上具有优势.这是因为在这 4 种算法中,CaP 总是选择具有最高关键级的作业进行调度,一旦作业
集负载较高或者超载概率增加,低关键级作业就会被大量放弃,因此,即使在超载概率 25%的情况下,CaP 在负载
85%时的平均系统关键级也达到了接近 5.也就是说,CaP 几乎只能保证具有最高关键级的作业完成.OCBP 提前
为作业计算关键级,但当出现超载时,就直接放弃低关键级的作业,因此当超载率较高,作业被大量放弃,系统平
均关键级无法降低.BP 提供了关键级回退的机制,这使得系统关键级在很多情况下能够完成从高到低的切换,
更多低关键级的作业被完成,从而提升了系统在平均关键级上的性能;但是相对于 CSDDB,BP 关键级切换的过
程有一定的滞后,这导致了在系统负载较高时,部分较低关键级作业错过时限.CSDDB 在关键级切换方面更为
灵活,系统的状态会直接反映在关键级的松弛时间上,因此整体系能更优.但需要特别注意的是,当 P χ =50%时,在
系统负载超过 0.8 时,CSDDB 的系统平均关键级高于 BP.这是因为当系统负载很高时,BP 不会切换到非常低的
关键级,如 1 或 2,但始终能尽量保证关键级 4 或 5 的作业的执行,而 CSDDB 由于总是选择具有最小松弛时间的
关键级,导致在某些时刻,系统运行的是更低关键级的作业.而在系统负载很高的前提下,这种情况事实上对系
统平均关键级参数是有负面影响的.然而,考虑实际应用中的大多数情况与作业 WCET 的测算方式,P χ =50%的
可能性非常低,因此,CSDDB 在这种情况下的不足是可以接受的.
4.2.2 作业集整体完成率的对比实验
在混合关键级作业的调度中,由于调度的目标不仅仅是保证高关键级的作业完成,而也应尽可能多地调度
低关键级作业,因此作业集的整体完成率是混合关键级作业调度中的另一个重要指标.如果作业集的整体完成
率较高,意味着作业集中更多的作业能够完成,系统的计算资源能得到更好的利用,算法性能也相应地更好.关
于作业集整体完成率的对比实验,如图 5 和图 6 所示.

Fig.5 Complement ratio of jobsetτ when P χ =25%
图 5 当 P χ =25%时作业集τ的完成率

Fig.6 Complement ratio of jobset τ when P χ =50%
图 6 当 P χ =50%时作业集τ的完成率