Schedulability bound for integrated modular avionics partitions
Pages 37 - 42
Abstract
In the avionics industry, as a hierarchical scheduling architecture Integrated Modular Avionics System has been widely adopted for its isolating capability. In practice, in an early development phase, a system developer does not know much about task execution times, but only task periods and IMA partition information. In such a case the schedulability bound for a task in a given partition tells a developer how much of the execution time the task can have to be schedulable. Once the developer knows the bound, then the developer can deal with any combination of execution times under the bound, which is safe in terms of schedulability. We formulate the problem as linear programming that is commonly used in the avionics industry for schedulability analysis, and compare the bound with other existing ones which are obtained with no period information.
References
[1]
ARINC Specification 651: Design Guidance for Integrated Modular Avionics. ARINC report. Airlines Electronic Engineering Committee and Aeronautical Radio Inc., Nov. 1991.
[2]
Avionics application software standard interface: Arinc specification 653p1--3. Aeronautical Radio, Inc., 2010.
[3]
L. Almeida and P. Pedreiras. Scheduling within temporal partitions: response-time analysis and server design. In Proceedings of the 4th ACM intl' conference on Embedded software, pages 95--103, 2004.
[4]
D. Chen, A. K. Mok, and T.-W. Kuo. Utilization bound revisited. IEEE Trans. Comput., 52(3), Mar. 2003.
[5]
R. I. Davis and A. Burns. Hierarchical fixed priority pre-emptive scheduling. In Proceedings of the 24th IEEE Real-Time Systems Symposium, pages 389--398, 2005.
[6]
R. I. Davis and A. Burns. An investigation into server parameter selection for hierarchical fixed priority pre-emptive systems. In Proc. of Real-Time and Network Systems, 2008.
[7]
F. Dewan and N. Fisher. Approximate bandwidth allocation for fixed-priority-scheduled periodic resources. In Proceedings of the 2010 16th IEEE Real-Time and Embedded Technology and Applications Symposium, RTAS '10, pages 247--256, 2010.
[8]
A. Easwaran. Compositional schedulability analysis supporting associativity, optimality, dependency and concurrency. PhD thesis, Computer and Information Science, University of Pennsylvania, 2007.
[9]
C.-C. Han and H.-Y. Tyan. A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithm. In Proceedings of the IEEE Real-Time Systems Symposium, pages 36--45. IEEE Computer Society, 1997.
[10]
J.-E. Kim, M.-K. Yoon, S. Im, R. Bradford, and L. Sha. Optimized scheduling of multi-ima partitions with exclusive region for synchronized real-time multi-core systems. In Proc. of the Conference on Design, Automation and Test in Europe, DATE '13, pages 970--975, 2013.
[11]
J. Krodel. Commercial off-the-shelf real-time operating system and architectural considerations. Federal Aviation Administration, Feb. 2004.
[12]
T.-W. Kuo, L.-P. Chang, Y.-H. Liu, and K.-J. Lin. Efficient online schedulability tests for real-time systems. IEEE Trans. Software Eng., 29(8): 734--751, 2003.
[13]
T.-W. Kuo and A. K. Mok. Load adjustment in adaptive real-time systems. In Proceedings of the IEEE Real-Time Systems Symposium, pages 160--170. IEEE Computer Society, 1991.
[14]
T.-W. Kuo and A. K. Mok. Incremental reconfiguration and load adjustment in adaptive real-time systems. IEEE Trans. Comput., 46(12): 1313--1324, Dec. 1997.
[15]
S. Lauzac, R. G. Melhem, and D. Moss. An efficient rms admission control and its application to multiprocessor scheduling. In IPPS/SPDP, pages 511--518, July 2003.
[16]
C.-G. Lee, L. Sha, and A. Peddi. Enhanced utilization bounds for qos management. IEEE Trans. Comput., 53(2): 187--200, Feb. 2004.
[17]
J. Liebeherr, A. Burchard, Y. Oh, and S. H. Son. New strategies for assigning real-time tasks to multiprocessor systems. IEEE Trans. Comput., 44(12): 1429--1442, Dec. 1995.
[18]
G. Lipari and E. Bini. Resource partitioning among real-time applications. In Proceedings of the 15th Euromicro Conference on Real-Time Systems, pages 151--158, 2003.
[19]
G. Lipari and E. Bini. A methodology for designing hierarchical scheduling systems. J. Embedded Comput., 1(2): 257--269, Apr. 2005.
[20]
C. L. Liu and J. W. Layland. Scheduling algorithms for multiprogramming in a hard real-time environment. Journal of the ACM, 20(1): 46--61, January 1973.
[21]
D.-W. Park, S. Natarajan, A. Kanevsky, and M. J. Kim. A generalized utilization bound test for fixed-priority real-time scheduling. In Proceedings of the 2nd International Workshop on Real-Time Computing Systems and Applications, 1995.
[22]
P. Parkinson and L. Kinnan. Safety-critical software development for integrated modular avionics. White Paper, Wind River Systems, 2007.
[23]
J. Rushby. Partitioning in avionics architectures: Requirements, mechanisms, and assurance. NASA Langley Technical Report, Mar. 1999.
[24]
S. Saewong, R. R. Rajkumar, J. P. Lehoczky, and M. H. Klein. Analysis of hierarchical fixed-priority scheduling. In Proceedings of the 14th Euromicro Conference on Real-Time Systems, pages 152--160, 2002.
[25]
L. Sha. Real-time virtual machines for avionics software porting and development. In Real-Time and Embedded Computing Systems and Applications, the 9th International Conference, RTCSA, Feb. 2003.
[26]
L. Sha and J. B. Goodenough. Real-time scheduling theory and ada. IEEE Computer, 23(4): 53--62, April 1990.
[27]
I. Shin and I. Lee. Periodic resource model for compositional real-time guarantees. In Proc. of the 24th IEEE International Real-Time Systems Symposium, pages 2--13, 2003.
[28]
I. Shin and I. Lee. Periodic resource model for compositional real-time guarantees. Tech. rep., Dep. of Computer & Information Science, University of Pennsylvania, 2003 (rev. 2010).
[29]
I. Shin and I. Lee. Compositional real-time scheduling framework with periodic model. ACM Transactions on Embedded Computing Systems, 7(3): 30:1--30:39, May 2008.
[30]
M.-K. Yoon, J.-E. Kim, R. Bradford, and L. Sha. Holistic design parameter optimization of multiple periodic resources in hierarchical scheduling. In Proc. of the 16th ACM/IEEE Design, Automation, and Test in Europe, pages 1313--1318, 2013.
Index Terms
- Schedulability bound for integrated modular avionics partitions
Recommendations
AADL-based Modeling and TPN-based Verification of Reconfiguration in Integrated Modular Avionics
APSEC '11: Proceedings of the 2011 18th Asia-Pacific Software Engineering ConferenceThis paper seeks to model the Integrated Modular Avionics (IMA) using Architectural Analysis and Design Language (AADL). In particular, the mechanism to describe the dynamic reconfiguration of multimodal system is presented. By translating the AADL ...
Resource Scheduling in Dependable Integrated Modular Avionics
DSN '00: Proceedings of the 2000 International Conference on Dependable Systems and Networks (formerly FTCS-30 and DCCA-8)In the recent development of avionics systems, Integrated Modular Avionics (IMA) is advocated for next generation architecture that needs integration of mixed-criticality real-time applications. These integrated applications meet their own timing ...
Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revised
Controller Area Network (CAN) is used extensively in automotive applications, with in excess of 400 million CAN enabled microcontrollers manufactured each year. In 1994 schedulability analysis was developed for CAN, showing how worst-case response times ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- EDAA: European Design Automation Association
- ECSI
- EDAC: Electronic Design Automation Consortium
- SIGDA: ACM Special Interest Group on Design Automation
- Russian Acadamy of Sciences: Russian Acadamy of Sciences
- IEEE Council on Electronic Design Automation (CEDA)
Publisher
EDA Consortium
San Jose, CA, United States
Publication History
Published: 09 March 2015
Check for updates
Qualifiers
- Research-article
Conference
DATE '15
Sponsor:
- EDAA
- EDAC
- SIGDA
- Russian Acadamy of Sciences
Acceptance Rates
DATE '15 Paper Acceptance Rate 206 of 915 submissions, 23%;
Overall Acceptance Rate 518 of 1,794 submissions, 29%
Upcoming Conference
DATE '25
- Sponsor:
- sigda
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 126Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 14 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in