|
|
论文:2023,Vol:41,Issue(3):557-567 |
|
|
引用本文： |
|
|
张旻, 武君胜, 崔西宁, 孙景昌. 机载多分区系统可调度性分析算法研究[J]. 西北工业大学学报 |
|
|
ZHANG Min, WU Junsheng, CUI Xining, SUN Jingchang. Research on schedulability analysis algorithm of airborne multi partition system[J]. Journal of Northwestern Polytechnical University |
|
|
|
|
|
|
|
| 机载多分区系统可调度性分析算法研究 |
|
| 张旻1,2, 武君胜1, 崔西宁2, 孙景昌2 |
|
1. 西北工业大学 软件学院, 陕西 西安 710072;
2. 中国航空工业集团有限公司 西安航空计算技术研究所, 陕西 西安 710065 |
| 摘要: |
| 机载领域普遍采用符合ARINC653标准的分区操作系统支撑应用软件综合化。在分区操作系统的两级调度模型下，机载软件苛刻的实时性要求通常难以得到有效的确定性保证，因此对系统进行可调度性分析显得至关重要。通过可调度性分析算法判断调度表是否能满足分区内进程的实时性要求，是保障系统中所有的进程在规定的时间内完成运算任务的有效手段。基于运筹学方法，通过引入虚拟进程，设计了一种多分区系统可调度性分析算法，并进行了数值验证。验证结果表明，该算法能够准确判断调度表与进程时间属性是否匹配，给出系统是否可调度的定性分析结论，帮助系统集成人员在系统实际运行前对调度表的合理性进行先期验证，降低试验和试飞风险。 |
| 关键词:
ARINC653
综合化
可调度性分析
多分区
虚拟进程
|
|
| Research on schedulability analysis algorithm of airborne multi partition system |
|
| ZHANG Min1,2, WU Junsheng1, CUI Xining2, SUN Jingchang2 |
|
1. School of Software, Northwestern Polytechnical University, Xi'an 710072, China;
2. Xi'an Aeronautics Computing Technique Research Institute, Aviation Industry Corporation of China, Ltd., Xi'an 710065, China |
| Abstract: |
| Partition operating system conforming to ARINC653 is widely used in airborne to support application software integration. Under the two-level scheduling model for partition operating system, the demanding real-time requirements of airborne software are usually difficult to obtain effective deterministic guarantee, so it is very important to analyze the schedulability of the system. Judging whether the scheduling table can meet the real-time requirements of the process in the partition through the schedulability analysis algorithm is an effective means to ensure that all processes in the system complete the computing task within the specified time. Based on the method of operations research and the introduction of virtual process, a schedulability analysis algorithm for multi partition system is designed, and the numerical verification is carried out. The verification results show that the algorithm can accurately judge whether the scheduling table matches the process time attribute, give the qualitative analysis conclusion of whether the system can be scheduled, help the system integrator to verify the rationality of the scheduling table before the actual operation of the system, and reduce the risk of test and flight test. |
| Key words:
ARINC653
integration
schedulability analysis
multi partition
virtual process
|
|
| 收稿日期: 2022-09-04
修回日期:
|
| DOI: 10.1051/jnwpu/20234130557 |
| 基金项目: 国防基础科研项目（JCKY2016607B006）资助 |
| 通讯作者: 武君胜(1962—),西北工业大学教授,主要从事领域软件工程技术研究。e-mail:wujunsheng@nwpu.edu.cn
Email：wujunsheng@nwpu.edu.cn |
| 作者简介: 张旻(1980—),西北工业大学博士研究生,主要从事嵌入式软件集成开发环境研究。
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] 邓世龙, 赵士杰, 赵雪娇, 等. 多核并行实时仿真平台多任务调度管理系统研究与设计[C]//全国仿真技术学术会议, 2021:48-52 DENG Shilong, ZHAO Shijie, ZHAO Xuejiao, et al. The design of multi-task management system based on multi-core parallel real-time simulation platform[C]//Processdings of National Conference on Simulation Technology, 2021:48-52(in Chinese)
[2] 毛佳, 张振花, 戴红, 等. 实时系统调度算法的优化设计[J]. 计算机工程与应用,2003,2003(15):112-115 MAO Jia, ZHANG Zhenhua, DAI Hong, et al. Optimum design to scheduling algorithm for real-time systems[J]. Computer Engineering and Applications, 2003, 2003(15):112-115(in Chinese)
[3] AEEC Aeronautical Radio Inc. Avionics application software standard interface[S]. ARINC 653, 2003
[4] 谭龙华, 杜承烈, 雷鑫. 分区实时系统的可调度分析[J]. 航空学报, 2015, 36(11):3698-3705 TAN Longhua, DU Chenglie, LEI Xin. Schedulability analysis for ARINC 653 partitioned real-time systems[J]. Acta Aeronautica et Astronautica Sinica, 2015, 36(11):3698-3705(in Chinese)
[5] 何锋, 宋丽茹, 熊华钢. 航空电子双层任务分区调度设计[J]. 北京航空航天大学学报, 2008, 11:1364-1368 HE Feng, SONG Liru, XIONG Huagang. Two-level task partition scheduling design in integrated modular avionics[J]. Journal of Beijing University of Aeronautics and Astronautics, 2008, 11:1364-1368(in Chinese)
[6] SAIDI S. On the benefits of multicores for realtime systems[C]//Proceedings of 2017 Euromicro Conference on Digital System Design, 2017
[7] MARKO B, MICHELE C, GIUSEPPE L. Schedulability analysis of global scheduling algorithms on multiprocessor platforms[J]. IEEE Trans on Parallel and Distributed Systems, 2009, 20(4):553-566
[8] 代声馨, 洪玫, 郭兵, 等. 多处理器实时系统可调度性分析的UPPAAL模型[J]. 软件学报, 2015, 26(2):279-296 DAI Shengxin, HONG Mei, GUO Bing, et al. Schedulability analysis model for multiprocessor real-time systems using UPPAAL[J]. Joural of Software, 2015, 26(2):279-296(in Chinese)
[9] ZHANG Shaohui. Schedulability analysis of real time system[J]. International Journal of Education and Economics, 2020, 3(3):63-65
[10] 陈聪, 洪中, 陈杨杨, 等. 移动系统的实时调度与可调度性分析[J]. 计算机工程与科学, 2020, 42(9):1544-1555 CHEN Cong, HONG Zhong, CHEN Yangyang, et al. Real-time scheduling and schedulability analysis for mobile system[J]. Computer Engineering & Science, 2020, 42(9):1544-1555(in Chinese)
[11] 陈莹, 邢建春, 杨启亮, 等. 时间约束下任务关键系统的可调度性分析[J]. 计算机工程, 2018, 44(12):115-119 CHEN Ying, XING Jianchun, YANG Qiliang, et al. Schedulability analysis of mission critical system under timing constraint[J]. Computer Engineering, 2018, 44(12):115-119(in Chinese)
[12] 孙景昊, 孙景昶, 关楠, 等. 偶发实时系统可调度性分析问题的整数规划方法[J]. 软件学报, 2017, 28(2):411-428 SUN Jinghao, SUN Jingchang, GUAN Nan, et al. Integer programming approach for schedulability of sporadic real-time systems[J]. Journal of Software, 2017, 28(2):411-428(in Chinese)
[13] 景维鹏, 霍帅起, 陈广胜, 等. 混合关键任务可靠调度方法与调度性分析[J]. 西安电子科技大学学报, 2016, 43(6):158-163 JING Weipeng, HUO Shuaiqi, CHEN Guangsheng, et al. Novel mixed-criticality reliability scheduling strategy and schedulability test[J]. Journal of Xidian University, 2016, 43(6):158-163(in Chinese)
[14] 朱振宇, 张仕, 蒋建民, 等. 并发系统中基于优先级的调度分析[J]. 计算机科学, 2016, 43(增刊2):523-528 ZHU Zhenyu, ZHANG Shi, JIANG Jianmin, et al. Analyzing scheduling based on priority in concurrent systems[J]. Computer Science, 2016, 43(suppl 2):523-528(in Chinese)
[15] 陈瑶, 李峭, 鲁俊, 等. 改进的多处理器混合关键性系统可调度性分析[J]. 北京航空航天大学学报, 2016, 42(9):1918-1926 CHEN Yao, LI Qiao, LU Jun, et al. Improved schedulability analysis for multiprocessor mixed-criticality systems[J]. Journal of Beijing University of Aeronautics and Astronautics, 2016, 42(9):1918-1926(in Chinese)
[16] FONSECA J, NELISSEN G, NELIS V, et al. Response time analysis of sporadic DAG tasks under partitioned scheduling[C]//2016 11th IEEE Symposium on Industrial Embedded Systems, 2016
[17] DINH S, LI J, AGRAWAL K, et al. Blocking analysis for spin locks in real-time parallel tasks[J]. IEEE Trans on Parallel and Distributed Systems, 2018, 29(4):789-802
[18] CASINI D, BIONDI A, NELISSEN G, et al. Partitioned fixed-priority scheduling of parallel tasks without preemptions[C]//2018 IEEE Real-Time Systems Symposium, 2018
[19] JIANG X, GUAN N, LIU W, et al. Scheduling and analysis of parallel real-time tasks with semaphores[C]//The 56th Annual Design Automation Conference, 2019
[20] BRONSHTEIN I N, SEMENDYAYEV K A, MUSIOL G. Handbook of mathematics[M]. Berlin:Springer, 2007:324-325
[21] XIAO J, ALTMEYER S, PIMENTEL A D. Schedulability analysis of global scheduling for multicore systems with shared caches[J]. IEEE Trans on Computers, 2020, 69(10):1487-1499
[22] SAAD S, MUHAMMAD A P. A dynamic cache-partition schedulability analysis for partitioned scheduling on multicore real-time systems[J]. IEEE Letters of the Computer Society, 2020, 3(2):46-49
[23] LEE H, CHOI J. Constraint-based schedulability analysis in multiprocessor real-time systems[J]. IEEE Access, 2020, 8(8):165168-165177
[24] 杨茂林. 共享资源约束下的多核实时调度算法研究[D]. 成都:电子科技大学, 2016 YANG Maolin. Research on real-time scheduling algorithms with shared resources[D]. Chengdu:University of Electronic Science and Technology of China, 2016(in Chinese)
[25] CHEN Z, YANG M, LEI H, et al. SET-MRTS:schedulability experiment toolkit for multiprocessor real-time systems[J]. Journal of Computer Applications, 2017, 37(5):1270-1275 |
|
|
|
|
|
|
|
