ACTA AERONAUTICAET ASTRONAUTICA SINICA >
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)
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.
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 . DOI: 10.7527/S1000-6893.2022.26581
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. |
/
〈 |
|
〉 |