Schedulability analysis of real-time multiframe cosimulations on multicore platforms

For real-time simulations, the fidelity of simulation depends not only on the functional accuracy of simulationbut also on its timeliness. It is helpful for simulation designers if they can analyze and verify that a simulation willalways meet its timing requirements without unnecessarily sacrificing functional accuracy. Abstracting the simulatedprocesses simply as software tasks allows us to transform the problem of verifying timeliness into a schedulability analysisproblem where tasks are checked as to whether they are schedulable under the timing constraints or not. In this paperwe extend a timed automaton-based framework due to Fersman and Yi for schedulability analysis of real-time systems,for the special case of real-time multiframe cosimulations. To the best of our knowledge, this work is the first to analyzethe schedulability of single- or multiframe real-time simulations. We found that there are some special requirementsposed by multiframe simulations, which necessitate changes and improvements in the existing framework designed foractual real-time systems. We made the required theoretical extensions to the framework and implemented our extendedframework in UPPAAL, a tool for modeling, simulation, and verification of real-time systems modeled as timed automata.The functional correctness and resource requirements of the implemented framework are then demonstrated using simpleexamples.

PDF

___

[1] Gomes C, Thule C, Broman D, Larsen PG, Vangheluwe H. Co-simulation: a survey. ACM Computing Surveys 2018; 51: 49.
[2] Crosbie R. Real-time simulation using hybrid models. In: Popovici K, Pieter JM (editors). Real-Time Simulation Technologies: Principles, Methodologies, and Applications. Boca Raton, FL, USA: CRC Press. Taylor & Francis Group, 2013. pp. 4-31.
[3] Gear CW, Wells DR. Multirate linear multistep methods. BIT 1984; 24: 484-502.
[4] Ledin J. Simulation Engineering. Lawrence, KS, USA: CMP Books, 2001.
[5] Alur R, Dill D. A theory of timed automata. Theoretical Computer Science 1994; 126: 183–235.
[6] Abdedda Y, Asarin E, Maler O. Scheduling with timed automata. Theoretical Computer Science 2006; 354: 272-300.
[7] Abdeddaim Y, Kerbaa A, Maler O. Task graph scheduling using timed automata. In: International Parallel and Distributed Processing Symposium; Nice, France; 2003. p. 8.
[8] Fersman E, Yi W. A generic approach to schedulability analysis of real-time tasks. Nordic Journal of Computing 2004; 11: 129-147.
[9] Fersman E, Mokrushin L, Pettersson P, Yi W. Schedulability analysis of fixed-priority systems using timed automata. Theoretical Computer Science 2006; 354: 301-317.
[10] Fersman E, Krcal P, Pettersson P, Yi W. Task automata: schedulability, decidability and undecidability. Information and Computing 2007; 205: 1149-1172.
[11] Stigge M, Yi W. Graph-based models for real-time workload: a survey. Real-Time Systems 2015; 51: 602-636.
[12] Larsen KG, Pettersson P, Yi W. Uppaal in a nutshell. International Journal of Software Tools and Technology Transfer 2014; 1: 134-152.
[13] Behrmann G, David A, Larsen KG. A tutorial on Uppaal. In: Bernardo M, Corradini F (editors). Formal Methods for the Design of Real-Time Systems. SFM-RT 2004, Lectures Notes in Computer Science. Berlin, Germany: Springer, 2004. pp. 200-236.
[14] Norstrom C, Wall a. Timed automata as task models for event-driven systems. In: Sixth International Conference on Real-Time Computing Systems and Applications. RTCSA’99 (Cat. No. PR00306). Hong Kong, China: IEEE Computer Society, 1999. pp. 182-189.
[15] Fersman E, Pettersson P, Yi W. Timed automata with asynchronous processes: schedulability and decidability. In: Katoen JP, Stevens P (editors). Tools and Algorithms for the Construction and Analysis of Systems. Berlin, Germany: Springer; 2002. pp. 67-82.
[16] David A, Illum J, Larsen KG, Skou A. Model-based framework for schedulability analysis using Uppaal 4.1. In: Nicolescu G, Mosterman PJ (editors). Model-Based Design for Embedded Systems. Boca Raton, FL, USA: CRC Press, 2009. pp. 117-144.
[17] Boudjadar A, Kim JH, Larsen KG, Nyman U. Compositional schedulability analysis of an avionics system using Uppaal. In: International Conference on Advanced Aspects of Software Engineering; Constantine, Algeria; 2014. pp. 140-147.
[18] Shan L, Graf S, Quinton S, Fejoz L. A framework for evaluating schedulability analysis tools. In: Aceto L, Bacci G, Bacci G, Ingólfsdóttir A, Legay A et al. (editors). Models, Algorithms, Logics and Tools. Lecture Notes in Computer Science. Cham, Switzerland: Springer, 2017. pp. 539-559.
[19] Gonzalez Perez CA, Varmazyar M, Nejati S, Briand L, Isasi Y. Enabling model testing of cyber-physical systems. In: ACM/IEEE 21st International Conference on Model Driven Engineering Languages and Systems; Copenhagen, Denmark; 2018. pp. 179-186.
[20] Brandstetter V, Wehrstedt JC. A framework for multidisciplinary simulation of cyber-physical production systems. IFAC PapersOnLine 2018; 51: 809-814.
[21] Domenici A, Fagiolini A, Palmieri M. Integrated simulation and formal verification of a simple autonomous vehicle. In: International Conference on Software Engineering and Formal Methods; Cham, Switzerland; 2017. pp. 300-314.
[22] Fersman E, Mokrushin L, Pettersson P, Yi W. Schedulability analysis using two clocks. In: International Conference on Tools and Algorithms for the Construction and Analysis of Systems; Berlin, Germany; 2003. pp. 224-239.
[23] Krcal P, Stigge M, Yi W. Multi-processor schedulability analysis of preemptive real-time tasks with variable execution times. Lecture Notes in Computer Science 2007; 4763: 274-289.
[24] Blockwitz T, Otter M, Akesson J, Arnold M, Clauss C et al. Functional mockup interface 2.0: The standard for tool independent exchange of simulation models. In: 9th International Modelica Conference; Munich, Germany; 2012. pp. 173-184.
[25] Prabhu SM, Mosterman PJ. Model-based design of a power window system: Modeling , simulation and validation. In: IMAC-XXII: A Conference on Structural Dynamics, Society for Experimental Mechanics, Inc.; Dearborn, MI, USA; 2004.