实时单核和谐周期分区系统时间窗口分配算法

doi:10.13700/j.bh.1001-5965.2016.0980

北京航空航天大学学报 ›› 2018, Vol. 44 ›› Issue (1): 43-49.doi: 10.13700/j.bh.1001-5965.2016.0980

实时单核和谐周期分区系统时间窗口分配算法

尚利宏¹, 谭特¹, 周密²

1. 北京航空航天大学计算机学院, 北京 100083;
2. 北京中航瑞博航空电子技术有限公司, 北京 100192

收稿日期:2016-12-29 修回日期:2017-03-24 出版日期:2018-01-20 发布日期:2017-04-27
通讯作者: 尚利宏 E-mail:shanglh@buaa.edu.cn
作者简介:尚利宏,男,博士,副教授,硕士生导师。主要研究方向:嵌入式系统、容错技术;谭特,男,硕士研究生。主要研究方向:嵌入式系统;周密,男,博士。主要研究方向:嵌入式系统、容错技术。

Time windows distribution algorithm for real-time harmonic-period partition system on uniprocessor platform

SHANG Lihong¹, TAN Te¹, ZHOU Mi²

1. School of Computer Science and Engineering, Beijing University of Aeronautics and Astronautics, Beijing 100083, China;
2. Reliable Avionics Technology Co., Ltd., Beijing 100192, China

Received:2016-12-29 Revised:2017-03-24 Online:2018-01-20 Published:2017-04-27

摘要/Abstract

摘要： 目前航空电子系统正快速朝着综合模块化方向发展。为了防止同一计算平台上的应用相互干扰，IMA软件普遍采用分区机制。由于时间分区的引入，传统的实时周期任务可调度性分析已经不再适用。为此研究了一类特殊的分区系统——和谐周期分区系统在单处理器下的可调度性。给出了和谐周期分区系统的形式化定义以及系统中任务可调度性的充分必要条件，并基于此提出了一种分区时间窗口分配算法。该算法为每个分区在主时间帧内分配多个时间窗口，并且保证只要和谐周期分区系统在理论上可调度，该算法就一定能生成一个可行的调度表，使得当全局调度器按照此调度表周期地调度分区时，各个分区中的任务不会超时。本文提出的算法可以运用在实际的工程中。

关键词: 分区, 实时, 和谐周期, 可调度性, 时间窗口

Abstract: Recently the avionics system is quickly transferring to integrated modular architecture. To prevent the mutual interference between different applications, IMA software usually adopts partition mechanism. Due to the "time partition", the traditional real-time schedulability analytical method is not applicable. This paper researches a class of special partition system, which is called harmonic-period partition system on uniprocessor platform. This paper gives the formalized definition of harmonic-period partition system and the necessary and sufficient condition of schedulability of tasks in harmonic-period partition system. On this basis, this paper proposes an algorithm, which is called time windows distribution algorithm. This algorithm distributes multiple time windows for each partition in the main time frame. This algorithm must be able to find a feasible schedule table for a harmonic-period partition system if this system is schedulable theoretically,and all tasks in partitions will not timeout if the global scheduler schedules partitions according to this schedule table. The algorithm proposed in this paper can be applied to practical engineering.

Key words: partition, real-time, harmonic-period, schedulability, time window

中图分类号:

V247
TP316.2

尚利宏, 谭特, 周密. 实时单核和谐周期分区系统时间窗口分配算法[J]. 北京航空航天大学学报, 2018, 44(1): 43-49.

SHANG Lihong, TAN Te, ZHOU Mi. Time windows distribution algorithm for real-time harmonic-period partition system on uniprocessor platform[J]. JOURNAL OF BEIJING UNIVERSITY OF AERONAUTICS AND A, 2018, 44(1): 43-49.

参考文献

[1] WATKINS C B,WALTER R. Transitioning from federated avionics architectures to integrated modular avionics[C]//Digital Avionics Systems Conference,2007.Piscataway,NJ:IEEE Press,2007:2.A.1-1-2.A.1-10.
[2] 周强,熊华钢.新一代民机航空电子互连技术发展[J].电光与控制,2009,16(4):1-6.ZHOU Q,XIONG H G.Development of the new generation civil avionic interconnection technology[J].Electronics Optics & Control,2009,16(4):1-6(in Chinese).
[3] 沈玉龙,崔西宁,马建峰,等.综合化航空电子系统可信软件技术[J].航空学报, 2009,30(5):938-945.SHEN Y L,CUI X N,MA J F,et al.Trust software technology in integrated avionics systems[J].Acta Aeronautica et Astronautica Sinica,2009,30(5):938-945(in Chinese).
[4] ARINC.avionics application software standards interface:ARINC 653[S].Annapolis:AEEC,2003.
[5] 杨霞,桑楠,雷剑,等.嵌入式高可信架构中基于静态模型的调度研究[J].航空学报,2009,30(12):2387-2394.YANG X,SANG N,LEI J,et al.Scheduling based on static model in trusted architecture for embedded systems[J].Acta Aeronautica et Astronautica Sinica,2009,30(12):2387-2394(in Chinese).
[6] LIU J W S.Real-time sytem[M].Upper Saddle River:Prentice Hall,2003:130-140.
[7] MOK A K,FENG X,CHEN D.Resource partition for real-time systems[C]//7th IEEE Proceedings of Real-time Technology and Applications Symposium.Piscataway,NJ:IEEE Press,2001:75-84.
[8] 谭龙华,杜承烈,雷鑫.ARINC 653分区实时系统的可调度分析[J].航空学报,2015, 36(11):3698-3705.TAN L H,DU C L,LEI X.Schedulability analysis for ARINC 653 partitioned real-time systems[J].Acta Aeronautica et Astronautica Sinica,2015, 36(11):3698-3705(in Chinese).
[9] CARNEVALI L,PINZUTI A,VICARIO E.Compositional verification for hierarchical scheduling of real-time systems[J].IEEE Transactions on Software Engineering,2013,39(5):638-657.
[10] 陈平,魏峰,李蜀瑜.ARINC 653调度算法研究[J].现代电子技术,2015,38(15):29-32.CHEN P,WEI F,LI S Y.Study on ARINC 653 scheduling algorithm[J].Modern Electronics Technique,2015,38(15):29-32(in Chinese).
[11] 李昕颖,顾健,何锋,等.硬实时系统在强分区约束下的双层分区调度[J].计算机学报,2010,33(6):1032-1039.LI X Y,GU J,HE F,et al.Two-level partition scheduling in hard real time system under strong partition constraints[J].Chinese Journal of Computers,2010,33(6):1032-1039(in Chinese).
[12] 周天然,熊华钢.航空电子系统混合实时任务的双层调度[J].航空学报,2011, 32(6):1067-1074.ZHOU T R,XIONG H G.Two-level hierarchical scheduling for hybrid real-time tasks in avionics systems[J].Acta Aeronautica et Astronautica Sinica,2011, 32(6):1067-1074(in Chinese).
[13] LIPARI G,BINI E,NGUYEN C,et al.A methodology for designing hierarchical scheduling system[J].Journal of Embedded Computing-Real-time System,2005,1(2):257-269.
[14] WAN M,TIAN S.Research on schedulability of partition scheduling for IMA[C]//20114th International Symposium on Computational Intellingence and Design.Piscataway,NJ:IEEE Press,2011,2:322-325.
[15] NASRI M,FOHLER G.An efficient method for assigning harmonic periods to hard real-time tasks with period ranges[C]//201527th Euromicro Conference on Real-Time Systems.Piscataway,NJ:IEEE Press,2015:149-159.
[16] 桥乃强,徐涛,谷青范.ARINC 653分区调度算法的研究与改进[J].计算机工程,2011,37(20):249-251.QIAO N Q,XU T,GU Q F.Research and improvement of ARINC 653 partition schedule algorithm[J].Computer Engineering,2011,37(20):249-251(in Chinese).

实时单核和谐周期分区系统时间窗口分配算法

Time windows distribution algorithm for real-time harmonic-period partition system on uniprocessor platform

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	王庞伟, 邓辉, 于洪斌, 李振华, 王力. 车路协同系统下区域路径实时决策方法[J]. 北京航空航天大学学报, 2019, 45(7): 1349-1360.
[2]	单睿斌, 李秋红, 何凤林, 冯海龙, 管庭筠. 基于ADMM算法的航空发动机模型预测控制[J]. 北京航空航天大学学报, 2019, 45(6): 1240-1247.
[3]	王鹏, 曹云峰, 许蕾, 丁萌, 张洲宇, 曲金秋. 一种图像缩放算法的SoC协同加速设计方法[J]. 北京航空航天大学学报, 2019, 45(2): 333-339.
[4]	王智宇, 何锋, 谷晓燕. 基于度中心性的AFDX网络拓扑生成[J]. 北京航空航天大学学报, 2019, 45(11): 2327-2334.
[5]	庞丽萍, 李恒, 王天博, 范俊, 邹凌宇. 民机客舱中太阳辐射对热舒适性的影响[J]. 北京航空航天大学学报, 2019, 45(10): 1924-1930.
[6]	吕志峰, 张金生, 王仕成, 李婷. 基于超前调节的磁场模拟实时控制方法[J]. 北京航空航天大学学报, 2018, 44(7): 1454-1460.
[7]	黄亮, 刘君强, 贡英杰. 基于Wiener过程的发动机多阶段剩余寿命预测[J]. 北京航空航天大学学报, 2018, 44(5): 1081-1087.
[8]	宋梓旭, 李峭, 汪晶晶, 熊华钢. 基于可调度性排序的时间触发调度表生成方法[J]. 北京航空航天大学学报, 2018, 44(11): 2388-2395.
[9]	范维思, 尹继豪, 袁丁, 朱红梅. 基于特征交叉检验的实时视觉里程计方法[J]. 北京航空航天大学学报, 2018, 44(11): 2444-2453.
[10]	李二帅, 何锋, 熊华钢. AVB网络流量整形帧模型端到端延迟计算[J]. 北京航空航天大学学报, 2017, 43(7): 1442-1449.
[11]	苏东林, 李冰, 王珺珺, 宋欣蔚. 线缆耦合信号实时监测方法[J]. 北京航空航天大学学报, 2017, 43(4): 645-653.
[12]	熊颖, 陈俊延, 何锋, 熊华钢, 刘成. 机载时间触发光网络的设计与实时性分析[J]. 北京航空航天大学学报, 2017, 43(12): 2466-2472.
[13]	赵琳, 何锋, 熊华钢. 航空电子AFDX与AVB传输实时性抗干扰对比[J]. 北京航空航天大学学报, 2017, 43(12): 2359-2369.
[14]	程阳, 程林, 张庆振, 倪昆, 储培. 基于在线约束限制的飞行器预测校正制导[J]. 北京航空航天大学学报, 2017, 43(10): 2143-2153.
[15]	林夏, 白涛, 武国强, 熊淑杰, 林宝军. 基于小波的反作用轮力矩测量系统校准[J]. 北京航空航天大学学报, 2017, 43(1): 200-206.