基于网络演算的多窗口分区可调度性分析
收稿日期: 2021-10-29
修回日期: 2021-12-13
录用日期: 2022-01-06
网络出版日期: 2022-01-18
基金资助
国家自然科学基金(62071023)
Schedulability analysis for multi-window partition based on network calculus model
Received date: 2021-10-29
Revised date: 2021-12-13
Accepted date: 2022-01-06
Online published: 2022-01-18
Supported by
National Natural Science Foundation of China(62071023)
ARINC653-2规范定义综合模块化航空电子(IMA)实时操作系统采用分区和任务两层调度方案,在该框架下的任务可调度性分析是保证航空电子系统实时性、可靠性的关键。目前的可调度性分析无法计算多窗口分区下任务最大响应时间(WCRT)。为此,基于网络演算模型对服务能力的封装,定义处理平台服务曲线为平台所能提供计算资源的服务函数,定义分区任务到达曲线为分区任务对平台计算资源的需求函数。分析处理平台的服务曲线和分区任务的到达曲线,计算得到任务的最大响应时间,继而进行可调度性判断,由此从服务能力和服务需求角度诠释分区系统任务最大响应时间分析的物理意义。设计了主时间框架下分区包含多个激活窗口的验证案例,结果表明:本方法可以得到与传统WCRT分析同等的精度,并且能够准确计算分区包含多激活窗口条件下的任务最大响应时间,实现了网络演算视角下分区系统可调度性的解释。
何锋 , 张立 , 于思凡 , 周璇 . 基于网络演算的多窗口分区可调度性分析[J]. 航空学报, 2023 , 44(2) : 326581 -326581 . DOI: 10.7527/S1000-6893.2022.26581
It is defined in the ARINC653-2 specification that the Integrated Modular Avionics (IMA) real-time system adopts the two-level scheduling scheme of partitions and tasks. The scheduling analysis of tasks based on this scheduling algorithm is a key issue to ensure the real time and reliability of the avionics system. Current schedulability analysis methods cannot be adapted to the multi-window partition situation. Therefore, based on the encapsulation of service capabilities of the network calculus model, this paper defines the processing platform service curve as the service function of the computing resources that the platform can provide, and defines the partition task arrival curve as the demand function of partition tasks for platform computing resources. By analyzing the service curve of the processing platform and the arrival curve of partition tasks, the Worst-Case Respone Time (WCRT) of the task is calculated, and then the schedulability is judged. Thus, the physical significance of interpreting the maximum response time of partitioned system from the perspectives of service capability and service demand is developed. A validation case of partition containing multiple activation windows is designed under the main time frame. The result shows that the proposed method can obtain the same accuracy as the traditional WCRT analysis method. It can also accurately calculate the maximum response time of the task when partition contains multiple activation windows. The schedulability of the partition system is explained from the perspective of network calculation.
1 | ARINC. ARINC specification 653, avionics application software standard interface[M]∥Avionics. Los Angeles: CRC Press, 2018: 235-242. |
2 | LIM S. A feasibility study for ARINC 653 based operational flight program development[C]∥2012 IEEE/AIAA 31st Digital Avionics Systems Conference (DASC). Piscataway: IEEE Press, 2012: 1-15. |
3 | LEE Y H, KIM D, YOUNIS M, et al. Partition scheduling in APEX runtime environment for embedded avionics software[C]∥Proceedings Fifth International Conference on Real-Time Computing Systems and Applications (Cat. No.98EX236). Piscataway: IEEE Press, 1998: 103-109. |
4 | BINI E, BUTTAZZO G C. Schedulability analysis of periodic fixed priority systems[J]. IEEE Transactions on Computers, 2004, 53(11): 1462-1473. |
5 | 高晓光, 薛亚勇, 温增葵. IMA双层调度算法中的任务可调度性分析方法[J]. 航空学报, 2015, 36(2): 585-595. |
GAO X G, XUE Y Y, WEN Z K. Task schedulability analyzing method of two-level hierarchical scheduling algorithm in integrated modular avionics[J]. Acta Aeronautica et Astronautica Sinica, 2015, 36(2): 585-595 (in Chinese). | |
6 | 谭龙华, 杜承烈, 雷鑫. ARINC653分区实时系统的可调度分析[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). | |
7 | EASWARAN A, LEE I, SOKOLSKY O, et al. A compositional scheduling framework for digital avionics systems[C]∥2009 15th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications. Piscataway: IEEE Press, 2009: 371-380. |
8 | CHEN J, DU C, HAN P. Scheduling independent partitions in integrated modular avionics systems[J]. PLoS One, 2016, 11(12): e0168064. |
9 | DAVIS R I, BURNS A. A survey of hard real-time scheduling for multiprocessor systems[J]. ACM Computing Surveys, 2011, 43(4): 35. |
10 | LE BOUDEC J Y, THIRAN P. Network calculus: A theory of deterministic queuing systems for the Internet[M]. Berlin: Springer, 2001. |
11 | WEN B, LI J, ZHU G C, et al. Deterministic and stochastic performance analysis for real-time avionics networks[J]. Journal of Internet Technology, 2015, 16(7): 1239-1250. |
12 | JIANG Y M. A basic stochastic network calculus[J]. ACM SIGCOMM Computer Communication Review, 2006, 36(4): 123-134. |
13 | WU Z T, HUANG N, LI R Y, et al. A delay reliability estimation method for Avionics Full Duplex Switched Ethernet based on stochastic network calculus[J]. Eksploatacja i Niezawodnosc - Maintenance and Reliability, 2015, 17(2): 288-296. |
14 | CRUZ R L. A calculus for network delay. I. Network elements in isolation[J]. IEEE Transactions on Information Theory, 1991, 37(1): 114-131. |
15 | CRUZ R L. A calculus for network delay. II. Network analysis[J]. IEEE Transactions on Information Theory, 1991, 37(1): 132-141. |
16 | PAREKH A K, GALLAGER R G. A generalized processor sha-ring approach to flow control in integrated services networks: The single-node case[J]. IEEE/ACM Transactions on Networking, 1993, 1(3): 344-357. |
17 | PAREKH A K, GALLAGER R G. A generalized processor sharing approach to flow control in integrated services networks: The multiple node case[J]. IEEE /ACM Transactions on Networking, 1994, 2(2): 137-150. |
18 | 何锋, 周璇, 赵长啸, 等. 航空电子系统机载网络实时性能评价技术[J]. 北京航空航天大学学报, 2020, 46(4): 651-665. |
HE F, ZHOU X, ZHAO C X, et al. Real-time performance evaluation technology of airborne network for avionics system[J]. Journal of Beijing University of Aeronautics and Astronautics, 2020, 46(4): 651-665 (in Chinese). | |
19 | ZHAO L X. Probabilistic analysis of response latency for rate-constrained traffic in the TTEthernet network[C]∥2014 IEEE/AIAA 33rd Digital Avionics Systems Conference (DASC). Piscataway: IEEE Press, 2014: 1-26. |
20 | 郑重, 赵露茜, 何锋, 等. 基于一次性突发原则的TTE网络实时性能优化[J]. 北京航空航天大学学报, 2021, 47(12): 2503-2513. |
ZHENG Z, ZHAO L X, HE F, et al. Real-time performance optimization of TTE network based on “pay bursts only once” principle[J]. Journal of Beijing University of Aeronautics and Astronautics, 2021, 47(12): 2503-2513 (in Chinese). | |
21 | AUDSLEY N C. Flexible scheduling of hard real-time systems[D]. York: University of York, 1993. |
/
〈 |
|
〉 |