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

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

在图 5 和图 6 中,x 轴表示系统负载;y 轴表示作业集的完成率,为 20 次运行结果的平均值.可以看出,CSDDB
在作业集的完成率方面具有较好的性能.特别是在系统负载较高时,OCBP 和 CaP 的完成率保持在 17%左右.这
意味着几乎只有最高关键级的作业完成,但 CSDDB 的完成率仍能保证 30%左右的作业能够完成.这是因为
CSDDB 能够通过松弛时间把关键级切换尽可能地延后,在整个运行过程中,能够满足更多的作业完成.显然,在
作业的完成率方面,CSDDB 具有明显的优势.
在实际的应用中,作业完成率性能的优势对于一个系统而言至关重要.特别是在当今的嵌入式系统中,正确
性不再是系统运行的唯一目标.在很多情况下,低关键级作业的完成能够为系统带来很多的优势,比如使用者的
体验性等.因此,在保证系统基本的安全性、可靠性能够得到保证的前提下,尽可能地使得混合关键级作业系统
的平均系统关键级降低,同时使更多的作业能够得到完成,是混合关键级系统调度问题的重点之一.CSDDB 在
混合关键级作业系统的调度上,充分考虑了低关键级作业的执行,通过系统执行关键级的切换,尽可能在保证高
关键级作业完成的情况下,为低关键级作业提供更多的执行机会.实验证明,CSDDB 具有较好的性能.
5 结束语

本文针对混合关键级作业系统,在传统实时调度理论中的时间需求边界函数的基础上,提出了混合关键级
系统中的动态时间需求边界函数.该函数考虑了作业在不同关键级上的执行时间、可能被阻塞的情况以及在实
例中作业执行关键级的变化可能带来的影响,以矢量的形式表述了一个混合关键级作业在不同关键级上的时
间需求边界,且该边界随着系统运行产生动态的变化.在动态需求边界函数的基础上,本文提出了作业松弛时间
的概念,并进一步提出了关键级松弛时间的概念,以之为根本参数,提出了一种基于动态需求边界的混合关键级
作业调度算法 CSDDB.该算法总是选取不小于 0 的松弛时间中的最小值所对应的关键级作为系统的执行关键
级,通过系统执行关键级的切换,尽可能地在不损害高关键级作业执行的情况下,为低关键级作业创造运行机
会,从而提高作业集的整体完成率.仿真实验证明,CSDDB 在系统关键级与作业的完成率方面具有较优的性能.
当系统的运行环境为多处理器平台,特别是异构多处理器平台,或者系统的目标涉及功耗、能量等其他因
素时,动态需求边界的描述和应用都会变得更复杂,这也是本文继续研究的主要方向.

References:
[1] Vestal S. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance. In: Proc. of the 28th
IEEE Real-time Systems Symp. (RTSS). IEEE, 2007. 239−243.
[2] Baruah S, Bonifaci V. Scheduling real-time mixed-criticality jobs. IEEE Trans. on Computer, 2011,61(8):1140−1152.
[3] Baruah S. Schedulability analysis for a general model of mixed-criticality recurrent real-time tasks. In: Proc. of the IEEE Real-
Time Systems Symp. 2016. 25−34.
[4] Burns A, Davis RI. Adaptive mixed criticality scheduling with deferred preemption. In: Proc. of the IEEE Real-time Systems Symp.
2014. 21−30.
[5] de Niz D, Lakshmanan K, Rajkumar R. On the scheduling of mixed-criticality real-time task sets. In: Proc. of the IEEE Real-time
Systems Symp. IEEE, 2009. 291−300.
[6] Huang H, Gill C. Implementation and evaluation of mixed-criticality scheduling approaches for period tasks. In: Proc. of the Real
Time and Embedded Technology and Application Symp. IEEE, 2012. 23−32.
[7] Lakshmanan K, de Niz D, Rajkumar R. Mixed-criticality task synchronization in zero-slack scheduling. In: Proc. of the 17th Real-
Time and Embedded Technology and Applications Symp. (RTAS). IEEE, 2011. 47−56.
[8] Li H, Baruah S. An algorithm for scheduling certifiable mixed-criticality sporadic task systems. In: Proc. of the Real-time Systems
Symp. San Diego: IEEE Computer Society Press, 2015. 183−192.
[9] Baruah S, Bonifaci V, D’Angelo G, Marchetti-Spaccamela A, van der Ster S, Stougie L. Mixed-criticality scheduling of sporadic
task systems. In: Proc. of the 19th Annual European Symp. on Algorithms. Saarbrucken: Springer-Verlag, 2013. 555−566.
[10] Li H. Scheduling mixed-criticality real-time systems [Ph.D. Thesis]. University of North Carolina at Chapel Hill, 2013.