Yukai HAO, Ming MU, Xiaodi DAI, Xiangdong LI

Schedulability test for IMA systems based on mixed integer linear programming formulation

Integrated modular avionics (IMA) architecture is widely adopted for the design of modern aircraft. Itsimplifies the system development process and improves the system security and reliability. In IMA systems, avionicsapplications are packed into various partitions, and integrated into a standard computing platform. How to determinethe schedulability of systems is one of the key problems. In this paper, using the characters of avionics systems, apartition model with a strict period is built, and constraints in space, time, and communication are analyzed. Basedon the mixed integer linear programming formulation, a solution to determine the schedulability of IMA systems ispresented. Experience reveals that this solution not only determines the system schedulability, but also achieves therequired minimum number of modules and guides the design of IMA systems.

PDF

___

[1] Xiong HG, Zhou GR, Li Q. A survey on avionics bus and network interconnections and their progress. Acta Aeronautica et Astronautica Sinica 2006; 27: 1135-1144.
[2] Chen J, Du C. Schedulability analysis for independent partitions in integrated modular avionics systems. In: Proceedings of the IEEE International Conference on Progress in Informatics and Computing; 18–20 Dec 2015; Nangjing, China. New York, NY, USA: IEEE. pp. 521-525.
[3] Baruah SK, Chakraborty S. Schedulability analysis of non-preemptive recurring real-time tasks. In: Proceedings of the Parallel and Distributed Processing Symposium; 25–29 April 2006; Rhodes Island, Greece. New York, NY, USA: IEEE. pp. 8-15.
[4] Chen J, Du C, Xie F, Yang Z. Schedulability analysis of non-preemptive strictly periodic tasks in multi-core real-time systems. Real-Time Systems 2016; 52: 239-271.
[5] Kim JE, Yoon MK, Im S, Bradford R, Sha L. Multi-IMA partition scheduling with synchronized solo-partitions for multi-core avionics systems. Department of Computer Science, University of Illinois at Urbana-Champaign, Technical report, May 2012.
[6] Korst J, Aarts E, Lenstra JK, Wessels J. Periodic Multiprocessor Scheduling. Berlin, Germany: Springer, 1991.
[7] Kermia O, Sorel Y. Schedulability analysis for non-preemptive tasks under strict periodicity constraints. In: Embedded and Real-Time Computing Systems and Applications; 25–27 August 2008; Kao-hsiung shih, Taiwan. IEEE. pp. 25-32.
[8] Eisenbrand F, H¨ahnle N, Niemeier M, Skutella M, Verschae J, Wiese A. Scheduling periodic tasks in a hard realtime environment. In: Proceedings of the 37th International Colloquium Conference on Automata, Languages and Programming. ICALP’10; 6–10 July 2010; Bordeaux, France. IEEE. pp. 299-311.
[9] Eisenbrand F, Kesavan K, Mattikalli R. Solving an avionics real-time scheduling problem by advanced IP-methods. In: de Berg M, Meyer U, editors. Algorithms. Lecture Notes in Computer Science. Berlin, Germany: Springer, 2010; 21: 11-22.
[10] Marouf M, Sorel Y. Scheduling non-preemptive hard real-time tasks with strict periods. In: 2011 IEEE Emerging Technologies Factory Automation (ETFA); 5–9 Sep 2011; Toulouse, France. IEEE. pp. 1-8.
[11] Chen J, Du C, Han P. Scheduling independent partitions in integrated modular avionics systems. Plos One 2016; 11: 20-36.
[12] Sheikh AA, Brun O, Hladik PE. Strictly periodic scheduling in IMA-based architectures. Real- Time Systems 2012; 48: 359-386.
[13] Pira C, Artigues C. An efficient best response heuristic for a non-preemptive strictly periodic scheduling problem. Learning and Intelligent Optimization. Lecture Notes in Computer Science. Berlin, Germany: Springer, 2013; 20: 281-287.
[14] Pira C, Artigues C. Line search method for solving a non-preemptive strictly periodic scheduling problem. Journal of Scheduling 2016; 19: 1-17.
[15] Sheikh AA, Brun O, Hladik PE. Partition scheduling on an IMA platform with strict periodicity and communication delays. In: Proceedings of the 18th International Conference on Real-Time and Network Systems; 4–5 Sep 2011; Toulouse, France. IEEE. pp. 179-188.
[16] Al Sheikh A, Brun O, Hladik PE, Prabhu BJ. A best-response algorithm for multiprocessor periodic scheduling. In: 23rd Euromicro Conference on Real-Time Systems (ECRTS); 6–8 July 2011; Porto, Portugal. IEEE. pp. 228-237.
[17] Linderoth JT, Lodi A, Cochran J. MILP Software. Wiley Encyclopedia of Operations Research and Management Science. Hoboken, NJ, USA: Wiley, 2010.
[18] Hann M, Deredempt MH, Cortier A. Requirements baseline for integrated modular avionics for space separation kernel qualification. In: Proceedings of the ESA Special Publication; 23–27 March 2015; Bergen, Norway. IEEE. pp. 732-739.
[19] Chen J, Du C, Xie F, Lin B. Allocation and scheduling of strictly periodic tasks in multi-core real-time systems. In: Proceedings of the IEEE International Conference on Embedded and Real-Time Computing Systems and Applications; 17–19 Aug 2016; Daegu, South Korea. IEEE. pp. 130-138.
[20] Burer S, Saxena A. The MILP Road to MIQCP. New York, NY, USA: Springer, 2012.