IMA双层调度算法中的任务可调度性分析方法

doi:10.7527/S1000-6893.2014.0180

Abstract

Abstract:

The task schedulability analysis on the two-level hierarchical scheduling algorithm in integrated modular avionics(IMA) is a key issue. As for this problem, this paper firstly dissects the method of calculating a task's exact response time and we learn that this method is limited by its features of high calculating complexity and non-continuity. To overcome these limitations, a method of calculating a task's upper bound response time is proposed. Further analyzing the method's deducing process, we achieve the formulation of calculating the response upper bound of a task under two-level hierarchical scheduling. Moreover, a task schedulability analysis method and partition parameters' designing method are inferred from the formulation. Finally, we deeply investigate how the factors, including the number of all the system tasks and the system utilization, would affect the precision of the upper bound response time calculating method proposed ahead using a quantitative analysis method of upper bound response time relative error and a qualitative analysis method of resource augmentation analyzing respectively. And the practical requirements of obtaining relatively high precision are acquired when applying this method.

Key words: integrated modular avionics, two-level hierarchical scheduling, schedulability analysis, partition parameter designing, resource augmentation analysis

CLC Number:

V279
TP2

GAO Xiaoguang, XUE Yayong, WEN Zengkui. Task schedulability analyzing method of two-level hierarchical scheduling algorithm in integrated modular avionics[J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2015, 36(2): 585-595.

References

[1] Aeronautical Radio, Inc. ARINC specification 653: avionics application software standard interface part 1-required services[S]. Annapolis: Aeronautical Radio, Inc, 2006.

[2] Aeronautical Radio, Inc. ARINC specification 653: avionics application software standard interface part 2-extended services[S]. Annapolis: Aeronautical Radio, Inc, 2007.

[3] Radio Technical Commission for Aeronautics, Inc. (RTCA).DO-297: integrated modular avionics (IMA) development guidance and certification considerations[S]. Washington D. C.: RTCA, 2004.

[4] Zhu W K, Zhang F M. Overview on software architecture of integrated modular avionic systems[J]. Acta Aeronautica et Astronautica Sinica, 2009, 21(30): 1912-1917(in Chinese). 褚文奎, 张凤鸣. 综合模块化航空电子系统软件体系结构综述[J]. 航空学报, 2009, 21(30): 1912-1917.

[5] Liu C L, Layland J W. Scheduling algorithms for multi-programming in a hard real-time environment[J]. Journal of ACM, 1973, 20(1): 174-189.

[6] Lehoczky J P, Sha L, Ding Y. The rate monotonic scheduling algorithm: exact characterization and average case behavior[C]//Proceedings of the 10th IEEE Real-Time Systems Symposium. Santa Monica: IEEE Computer Society Press, 1989: 166-171.

[7] Han C C, Lin K J, Hou C J. Distance-constrained scheduling and its applications to real-time systems[J]. IEEE Transactions on Computers, 1996, 45(7): 814-826.

[8] Katcher D I, Arakawa H, Strosnider J K. Engineering and analysis of fixed priority schedulers[J]. IEEE Transactions on Software Engineering, 1993, 19(9): 920-934.

[9] Han C C, Tyan H. A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithms[C]//Proceedings of the18th IEEE Real-Time Systems Symposiums. San Francisco: IEEE Computer Society Press, 1997: 36-45.

[10] Bini E, Buttazzo G C, Buttazzo G. A hyperbolic bound for the rate monotonic algorithm[C]//Proceedings of the 13th Euromicro Conference on Real-Time Systems (ECRTS 2001). Delft: IEEE Computer Society Press, 2001: 933-942.

[11] Zhou Y, Huai X Y, Li M S. The self-adaption of dispatching method in open real-time system[J]. Chinese Journal of Computers, 2004, 27(1): 58-65 (in Chinese). 邹勇, 淮晓永, 李明树. 开放式实时系统中的自适应调度方法[J]. 计算机学报, 2004, 27(1): 58-65.

[12] Almeida L, Pedreiras P. Scheduling within temporal partitions: response-time analysis and server design[C]//Proceedings of the 4th ACM International Conference on Embedded Software. Pisa: University of Pavia, 2004: 95-103.

[13] Joseph M, Pandya P K. Finding response time in a real-time system[J]. The Computer Journal, 1986, 29(5): 390-395.

[14] Audsley N C, Burns A, Richardson M, et al. Applying new scheduling theory to static priority preemptive scheduling[J]. Software Engineering Journal, 1993, 8(5): 284-292.

[15] Zhang F X, Burns A. Analysis of hierarchical EDF preemptive scheduling[C]//28th IEEE International Real-time Systems Symposium. Tucson: IEEE Computer Society Press, 2007: 423-434.

[16] Davis R I, Burns A. Hierarchical fixed priority preemptive scheduling[C]//26th IEEE International Real-time Systems Symposium. Miami: IEEE Computer Society Press, 2005: 389-398.

[17] Bini E, Huyen T, Richard P, et al. A response time bound in fixed-priority scheduling with arbitrary deadlines[J]. IEEE Transactions on Computers, 2009, 58(2): 279-286.

[18] Balbastre P, Ripoll I, Crespo A. Exact response time analysis of hierarchical fixed-priority scheduling[C]//15th IEEE International Conference on Embedded and Real-time Computing Systems and Applications. Beijing: IEEE Computer Society Press, 2009: 315-320.

[19] Josep M, Pandya P K. Finding response times in a real-time system[J]. The Computer Journal, 1986, 29(5): 390-395.

[20] Palencia J C, Gonz'alez H. Schedulability analysis for tasks with staputertic and dynamic offsets[C]//Proceedings of the 19th IEEE Real-Time Systems Symposium. Madrid: IEEE Computer Society Press, 1998: 26-37.

[21] Lehoczky J P. Fixed priority scheduling of periodic task sets with arbitrary deadline[C]//Proceedings of the 11th IEEE Real-Time Systems Symposium. Florida: IEEE Computer Society Press, 1990: 201-209.

[22] Zhou T R, Xiong H G. Two-level hierarchical scheduling for hybrid real-time tasks in avionic systems[J]. Acta Aeronautica et Astronautica Sinica, 2011, 32(11): 1067-1074 (in Chinese). 周天然, 熊华刚. 航空电子系统混合实时任务的双层调度[J]. 航空学报, 2011, 32(11): 1067-1074.

[23] Wang G, Zhang Y P, Gu Q F. Research on IMA task scheduling based on dynamic resource allocation[J].Avionics Technology, 2013, 40(1): 48-53 (in Chinese). 王冠, 张育平, 谷青范. 基于资源动态配置的IMA 任务调度机制研究[J]. 航空电子技术, 2013, 40(1): 48-53.

[24] Zhou T R, Xiong H G, Zhang Z. Hierarchical resource allocation for integrated modular avionics systems[J]. Journal of Systems Engineering and Electronics, 2011, 22(5): 780-787.

[25] Zhou Q, Liu B, Yu Z W, et al. A framework of simulation testing environment for integrated modular avionics software[J]. Acta Aeronautica et Astronautica Sinica, 2012, 33(4): 722-733 (in Chinese). 周庆, 刘斌, 余正伟, 等. 综合模块化航电软件仿真测试环境研究[J]. 航空学报, 2012, 33(4): 722-733.

[26] Ming W, Song T. Research on schedulability of partition scheduling for IMA[C]//4th IEEE International Symposium on Computational Intelligence and Design. Hangzhou: IEEE Computer Society Press, 2012: 322-325.

Task schedulability analyzing method of two-level hierarchical scheduling algorithm in integrated modular avionics

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 9

Recommended Articles

Metrics

Comments

[1]	Feng HE, Li ZHANG, Sifan YU, Xuan ZHOU. Schedulability analysis for multi-window partition based on network calculus model [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2023, 44(2): 326581-326581.
[2]	LUO Qing, ZHANG Tao, SHAN Peng, ZHANG Wentao, LIU Zihao. Generating reconfiguration blueprints for IMA systems based on improved Q-learning [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2021, 42(8): 525792-525792.
[3]	YAN Fang, XING Peipei, ZHAO Changxiao, WANG Peng. Reliability modeling and analysis of DIMA system based on joint k/n(G) model [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2018, 39(6): 321971-321971.
[4]	TAN Longhua, DU Chenglie, LEI Xin. Schedulability analysis for ARINC 653 partitioned real-time systems [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2015, 36(11): 3698-3705.
[5]	QU Yepin. Research on General Architecture of Avionics Mission System for Operational Support Aircraft [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2014, 35(8): 2307-2318.
[6]	ZHOU Qing, LIU Bin, YU Zhengwei, FENG Shiyu. A Framework of Simulation Testing Environment for Integrated Modular Avionics Software [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2012, (4): 722-733.
[7]	ZHANG Yongtao, HUANG Zhen, XIONG Huagang. Study on Network Reliability in Avionics Based on Performance Degradation Constraints [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2011, 32(8): 1461-1468.
[8]	ZHOU Tianran, XIONG Huagang. Two-level Hierarchical Scheduling for Hybrid Real-time Tasks in Avionic Systems [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2011, 32(6): 1067-1074.
[9]	Chu Wenkui;Zhang Fengming;Fan Xiaoguang. Overview on Software Architecture of Integrated Modular Avionic Systems [J]. ACTA AERONAUTICAET ASTRONAUTICA SINICA, 2009, 30(10): 1912-1917.