北京航空航天大学学报 ›› 2016, Vol. 42 ›› Issue (9): 1918-1926.doi: 10.13700/j.bh.1001-5965.2015.0551

• 论文 • 上一篇    下一篇

改进的多处理器混合关键性系统可调度性分析

陈瑶, 李峭, 鲁俊, 熊华钢   

  1. 北京航空航天大学 电子信息工程学院, 北京 100083
  • 收稿日期:2015-08-27 出版日期:2016-09-20 发布日期:2015-12-08
  • 通讯作者: 李峭,Tel.:010-82338894,E-mail:qiaolibuaa@163.com E-mail:qiaolibuaa@163.com
  • 作者简介:陈瑶,男,博士研究生。主要研究方向:航空电子系统、实时通信网络。Tel.:010-82338712,E-mail:chenyao_kevin@163.com;李峭,男,博士,讲师。主要研究方向:航空电子系统、实时计算机网络。Tel.:010-82338894,E-mail:qiaolibuaa@163.com;鲁俊,男,博士研究生。主要研究方向:航空电子系统、实时计算机网络。E-mail:lujun217@163.com;熊华钢,男,博士,教授,博士生导师。主要研究方向:航空电子综合、高速数据总线、通信网络理论与技术。Tel.:010-82317202,E-mail:hgxiong@buaa.edu.cn
  • 基金资助:
    国家自然科学基金(61301086);航空科学基金(20131951027);中央高校基本科研业务费专项资金(YWF-14-DZXY-018)

Improved schedulability analysis for multiprocessor mixed-criticality systems

CHEN Yao, LI Qiao, LU Jun, XIONG Huagang   

  1. School of Electronic and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China
  • Received:2015-08-27 Online:2016-09-20 Published:2015-12-08
  • Supported by:
    National Natural Science Foundation of China (61301086); Aeronautical Science Foundation of China (20131951027); the Fundamental Research Funds for the Central Universities (YWF-14-DZXY-018)

摘要: 针对混合关键性系统的多重认证需求,研究多核处理器平台中全局调度算法fixed-priority and Earliest Deadline First by Virtual Deadline(fpEDF-VD)的可调度性分析问题。fpEDF-VD结合处理器利用率和虚拟截止期两个方面来计算任务优先级,系统可调度性取决于是否存在可行的虚拟截止期调整参数。考虑到现有可调度分析方法仅测试有限数量的调整参数候选值,不能有效地判定系统可调度性,故提出了一种改进的判定方法。该方法基于传统(非混合关键)任务调度算法fpEDF的可调度利用率约束条件,利用函数图像分析研究不同关键性级别的系统可调度性需求,并在此基础上给出有效虚拟截止期调整参数的确切范围。通过实例分析及与现有判定方法的比较,验证了该方法的正确性和高效性。与理论分析一致,基于随机生成任务集的仿真实验结果表明改进后的方法具有更优越的可调度性能,能显著地提高任务集的可调度接受率。

关键词: 实时系统, 混合关键性, 多处理器, 全局调度, 最早截止时间优先, 可调度性分析

Abstract: For mixed-criticality systems implemented upon multiprocessor platforms and scheduled by the popular global scheduling algorithm named fixed-priority and earliest deadline first by virtual deadline (fpEDF-VD), the issue how to determine their schedulability is studied, addressing the concern of multiple certification requirements. According to fpEDF-VD, the task's priority is determined by the combination of task utilization and virtual deadline, and the schedulability of the system depends on the existence of valid scaling factor for virtual deadline tuning. Considering that current approaches only verify finite scaling factor candidates, an improved schedulability analysis is proposed, which is capable of determining the feasible region of the scaling factor accurately. This approach investigates schedulability requirements at different criticality levels by exploiting the function graph of the schedulability condition derived for the regular (non mixed-criticality) fpEDF algorithm, and on this basis provides the accurate range of the parameter for tuning virtual deadlines. An illustrative example is presented to demonstrate its validity and efficiency. In accordance with theoretical analysis, extensive simulation experiments with randomly-generated task sets show the dominance of the proposed schedulability analysis over the existing ones in terms of acceptance ratio.

Key words: real-time system, mixed-criticality, multiprocessor, global scheduling, earliest deadline first, schedulability analysis

中图分类号: 


版权所有 © 《北京航空航天大学学报》编辑部
通讯地址:北京市海淀区学院路37号 北京航空航天大学学报编辑部 邮编:100191 E-mail:jbuaa@buaa.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发