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

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

doi:10.13700/j.bh.1001-5965.2015.0551

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

doi: 10.13700/j.bh.1001-5965.2015.0551

北京航空航天大学电子信息工程学院, 北京 100083

基金项目: 国家自然科学基金（61301086）；航空科学基金（20131951027）；中央高校基本科研业务费专项资金（YWF-14-DZXY-018）

详细信息

作者简介:
陈瑶,男,博士研究生。主要研究方向:航空电子系统、实时通信网络。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

通讯作者:
李峭,Tel.:010-82338894,E-mail:qiaolibuaa@163.com

中图分类号: TP316.2
计量
- 文章访问数: 784
- HTML全文浏览量: 34
- PDF下载量: 550
- 被引次数: 0
出版历程
- 收稿日期: 2015-08-27
- 网络出版日期: 2016-09-20

Improved schedulability analysis for multiprocessor mixed-criticality systems

School of Electronic and Information Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China

Funds: 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.
- real-time system /
- mixed-criticality /
- multiprocessor /
- global scheduling /
- earliest deadline first /
- schedulability analysis

HTML全文

参考文献(19)

[1]	BARHORST J,BELOTE T,BINNS P,et al.White paper:A research agenda for mixed-criticality systems:88ABW-2009-1383 [R].San Francisco:Cyber-Physical Systems Week,2009.
[2]	BARUAH S K,LI H,STOUGIE L.Towards the design of certifiable mixed-criticality systems[C]//Real-Time and Embedded Technology and Applications Symposium.Piscataway,NJ:IEEE Press,2010:13-22.
[3]	VESTAL S.Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[C]//Real-Time Systems Symposium.Piscataway,NJ:IEEE Press,2007:239-243.
[4]	BARUAH S K,BURNS A,DAVIS R.Response-time analysis for mixed criticality systems[C]//Real-Time Systems Symposium.Piscataway,NJ:IEEE Press,2011:33-43.
[5]	BARUAH S K,BONIFACI V,D'ANGELO G,et al.Mixed-criticality scheduling of sporadic task systems[C]//European Symposium on Algorithms.Heidelberg:Springer Verlag,2011:555-566.
[6]	BARUAH S K,FOHLER G.Certification-cognizant time-triggered scheduling of mixed-criticality systems[C]//Real-Time Systems Symposium.Piscataway,NJ:IEEE Press,2011:3-12.
[7]	GUAN N,EKBERG P,STIGGE M,et al.Effective and efficient scheduling of certifiable mixed-criticality sporadic task systems[C]//Real-Time Systems Symposium.Piscataway,NJ:IEEE Press,2011:13-23.
[8]	BARUAH S K,BONIFACI V,D'ANGELO G,et al.The preemptive uniprocessor scheduling of mixed-criticality implicit-deadline sporadic task systems[C]//Proceedings of Euromicro Conference on Real-Time Systems.Piscataway,NJ:IEEE Press,2012:145-154.
[9]	PONTUS E,WANG Y.Bounding and shaping the demand of mixed-criticality sporadic tasks[C]//Proceedings of Euromicro Conference on Real-Time Systems.Piscataway,NJ:IEEE Press,2012:135-144.
[10]	PONTUS E,WANG Y.Bounding and shaping the demand of generalized mixed-criticality sporadic task systems[J].Real-Time Systems,2014,50(1):48-86.
[11]	MOLLISON M S,ERICKSON J P,ANDERSON J H,et al.Mixed-criticality real-time scheduling for multicore systems[C]//International Conference on Computer and Information Technology.Piscataway,NJ:IEEE Press,2010:1864-1871.
[12]	KELLY O R,AYDIN H,ZHAO B.On partitioned scheduling of fixed-priority mixed-criticality task sets[C]//International Conference on Trust Security and Privacy in Computing and Communications.Piscataway,NJ:IEEE Press,2011:1051-1059.
[13]	谷传才,关楠,于金铭,等.多处理器混合关键性系统中的划分调度策略[J].软件学报,2014,25(2):284-297.GU C C,GUAN N,YU J M,et al.Partitioned scheduling policies on multi-processor mixed-criticality systems[J]Journal of Software,2014,25(2):284-297(in Chinese).
[14]	PATHAN R.Schedulability analysis of mixed-criticality systems on multiprocessors[C]//Proceedings of Euromicro Conference on Real-Time Systems.Piscataway,NJ:IEEE Press,2012:309-320.
[15]	LI H,BARUAH S K.Global mixed-criticality scheduling on multiprocessors[C]//Proceedings of Euromicro Conference on Real-Time Systems.Piscataway,NJ:IEEE Press,2012:166-175.
[16]	BARUAH S K,CHATTOPADHYAY B,LI H,et al.Mixed-criticality scheduling on multiprocessors[J].Real-Time Systems,2014,50(1):142-177.
[17]	BARUAH S K.Optimal utilization bounds for the fixed-priority scheduling of periodic task systems on identical multiprocessors[J].IEEE Transactions on Computers,2004,53(6):781-784.
[18]	GOOSSENS J,FUNK S,BARUAH S K.Priority-driven scheduling of periodic task systems on multiprocessors[J].Real-time Systems，2003,25(2-3):187-205.
[19]	BAKER T P,BARUAH S K.Sustainable multiprocessor scheduling of sporadic task systems[C]//Proceedings of Euromicro Conference on Real-Time Systems.Piscataway,NJ:IEEE Press,2009:141-150.