IMA双层调度算法中的任务可调度性分析方法
收稿日期: 2014-03-07
修回日期: 2014-07-29
网络出版日期: 2014-09-05
基金资助
国家自然科学基金(60774064);教育部博士点基金(20116102110026);航天技术支撑基金(2013-HT-XGD)
Task schedulability analyzing method of two-level hierarchical scheduling algorithm in integrated modular avionics
Received date: 2014-03-07
Revised date: 2014-07-29
Online published: 2014-09-05
Supported by
National Natural Science Foundation of China (60774064); Ph.D. Programs Foundation of Ministry of Education of China (20116102110026); Aerospace Science Foundation of China (2013-HT-XGD)
任务可调度性分析是综合模块化航电(IMA)系统双层调度算法研究中的一个关键问题。针对这个问题,首先剖析了单分区调度系统中任务精确响应时间计算方法所具有的计算复杂度高以及计算函数不连续等局限性;然后提出了一种计算任务响应时间上限的快速方法,分析该计算方法的推导过程,得到了双层调度情况下任务响应时间上限的计算方法,并由此推演出任务可调度性分析方法和分区参数设计方法;最后通过计算机仿真实验,分别使用定量的响应时间上限相对误差法以及定性的资源放大分析法考察了系统任务数量以及系统利用率对文中提出的响应时间上限计算方法精度的影响程度,并得到了该方法取得较高应用精度的可行性条件。
高晓光 , 薛亚勇 , 温增葵 . IMA双层调度算法中的任务可调度性分析方法[J]. 航空学报, 2015 , 36(2) : 585 -595 . DOI: 10.7527/S1000-6893.2014.0180
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.
[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.
/
| 〈 |
|
〉 |
CJA