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

作者简介:

曾理宁(1986-),男,博士,主要研究领域为嵌入式软件,实时调度理论,信息物理融合系统.
徐成(1962-),男,博士,教授,博士生导师,CCF专业会员,主要研究领域为嵌入式系统,智能机器人.
李仁发(1956-),男,博士,教授,博士生导师,CCF杰出会员,主要研究领域为计算机系统结构,嵌入式系统,信息物理融合系统.
杨帆(1985-),男,博士,讲师,CCF专业会员,主要研究领域为数据建模,嵌入式系统.
徐洪智(1974-),男,博士,副教授,主要研究领域为嵌入式系统,并行计算.

通讯作者:

徐成,E-mail:cheng_xu@yeah.net

中图分类号:

基金项目:

国家自然科学基金(61772185,61672217,61173036);国家重点研发计划(2016YFB0200405);国家高技术研究发展计划(863)(2012AA01A301-01);湖南省自然科学基金(2019JJ50996)


Scheduling Algorithm for Mixed-criticality Jobs Based on Dynamical Demand Boundary
Author:
Affiliation:

Fund Project:

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)

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

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

    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 system. To deal with this problem, this paper expands the traditional demand boundary analysis theory to the mixed-criticality systems, presenting the concept of dynamical demand boundary for mixed-criticality jobs, which represents the dynamical demand of jobs in run-time as a vector. And then, based on the concept of slack time for mixed-criticality jobs and the criticality of system, the paper presents an algorithm CSDDB (criticality switch based on dynamical demand boundary). The algorithm chooses the criticality with the minimum slack time as the execution criticality of the system to take full advantage of system resources and to guarantee the execution of jobs with lower criticality without affecting the schedulability of high criticality jobs. Experiments with randomly generated workload show that CSDDB makes more than 10% of progress in guaranteeing the system criticality and the completion of jobs set compared with the existing research.

    参考文献
    相似文献
    引证文献
引用本文

曾理宁,徐成,李仁发,杨帆,徐洪智.一种基于动态需求边界的混合关键级作业调度算法.软件学报,2020,31(11):3657-3670

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2018-04-18
  • 最后修改日期:2018-09-20
  • 录用日期:
  • 在线发布日期: 2019-11-07
  • 出版日期: 2020-11-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号