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

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software,2020,31(11):3657−3670 [doi: 10.13328/j.cnki.jos.005839] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

∗
一种基于动态需求边界的混合关键级作业调度算法

1
1
2
1
曾理宁 , 徐 成 , 李仁发 , 杨 帆 , 徐洪智 1,3
1
(嵌入式与网络计算湖南省重点实验室(湖南大学),湖南 长沙 410082)
2
(中南林业科技大学 计算机与信息工程学院,湖南 长沙 410004)
3 (吉首大学 软件学院,湖南 张家界 427000)
通讯作者: 徐成, E-mail:cheng_xu@yeah.net

摘 要: 把具有不同重要性的功能集成到一个共享平台上的混合关键级系统,是当前嵌入式系统发展的主要趋势
之一.已有的混合关键级调度理论为了保证高关键级作业的完成,大多不支持关键级向下切换,在系统进入高关键级
后直接放弃低关键级作业的执行,这对系统中作业集的整体完成率有负面影响.为了应对这一问题,把需求边界分析
理论扩展到混合关键级作业系统中,提出了作业的动态需求边界函数,以矢量的形式记录系统在运行时需求边界函
数的动态变化,并相应地提出了作业的混合关键级松弛时间与系统关键级松弛时间的概念.在此基础上,提出了一种
基于动态需求边界的混合关键级作业调度算法 CSDDB(criticality switch based on dynamical demand boundary).该算
法选择具有最小松弛时间的关键级作为执行关键级,在保证高关键级作业可调度的情况下,充分利用系统资源,尽可
能地满足低关键级作业的执行.应用随机生成的任务集进行仿真实验,结果表明,与已有算法相比,CSDDB 在系统关
键级的保证与作业集整体完成率方面比现有算法有 10%以上的提升.
关键词: 混合关键级;关键级切换;实时调度;需求边界函数;松弛时间
中图法分类号: TP316

中文引用格式: 曾理宁,徐成,李仁发,杨帆,徐洪智.一种基于动态需求边界的混合关键级作业调度算法.软件学报,2020,
31(11):3657−3670. http://www.jos.org.cn/1000-9825/5839.htm
英文引用格式: Zeng LN, Xu C, Li RF, Yang F Xu HZ. Scheduling algorithm for mixed-criticality jobs based on dynamical
demand boundary. Ruan Jian Xue Bao/Journal of Software, 2020,31(11):3657−3670 (in Chinese). http://www.jos.org.cn/1000-
9825/5839.htm
Scheduling Algorithm for Mixed-criticality Jobs Based on Dynamical Demand Boundary

1
2
1
1
ZENG Li-Ning , XU Cheng , LI Ren-Fa , YANG Fan , XU Hong-Zhi 1,3
1
(Key Laboratory for Embedded and Network Computing of Hu’nan Province (Hu’nan University), Changsha 410082, China)
2
(College of Computer and Information Engineering, Central South University of Forestry and Technology, Changsha 410004, China)
3
(College of Software, Jishou University, Zhangjiajie 427000, China)
Abstract: An important trend in embedded system is integrating functions with different level of importance into a sharing hardware
platform, which is called mixed-criticality system. Most of the existing mixed-criticality theory did not support switching the system
criticality from high to low in order to guarantee the jobs with higher criticality, which is not good for the overall performance of the

∗ 基金项目: 国家自然科学基金(61772185, 61672217, 61173036); 国家重点研发计划(2016YFB0200405); 国家高技术研究发展
计划(863)(2012AA01A301-01); 湖南省自然科学基金(2019JJ50996)
Foundation item: National Natural Science Foundation of China (61772185, 61672217, 61173036); National Key Research and
Development Program of China (2016YFB0200405); National High Technology Research and Development Program of China (863)
(2012AA01A301-01); Natural Science Foundation of Hu’nan Province (2019JJ50996)
收稿时间: 2018-04-18; 修改时间: 2018-09-20; 采用时间: 2019-03-25; jos 在线出版时间: 2019-11-06
CNKI 网络优先出版: 2019-11-06 11:49:10, http://kns.cnki.net/kcms/detail/11.2560.TP.20191106.1148.004.html