Probabilistic approaches for time critical embedded systems Liliana Cucu-Grosjean AOSTE team, INRIA Paris-Rocquencourt Domaine de Voluceau, BP 105 78153, Le Chesnay France liliana.cucu@inria.fr During the last twenty years different design solutions have been proposed for time critical embedded systems through pessimistic estimation of performances of the processors (thus increased costs) while using average time behavior processors. A possible solution to decrease the pessimism while designing time critical embedded systems is to enrich existing models with appropriate probabilistic descriptions. time critical embedded systems, probabilistic worst-case reasoning 1. INTRODUCTION embedded systems. This solution defines several possible values for the worst case execution time An embedded system is a computing system with of a program on a processor and it has propagated a dedicated function, embedded within a larger from the original work on scheduling theory Burns device,e.g., a defibrillator or an airplane. Today and Davis (2015) to synchronous languages Yip 95% of current processors are embedded, making and al. (2014), predictable processors Zimmer embedded systems central computing systems and al. (2014), model checking Boudjadar and al. of our society. Beside constraints like power (2014), etc. Nevertheless today the mixed criticality consumption and weight, embedded systems may solutions are heterogeneous and they are proposed have time constraints and such systems are for different phases of design without a common called time critical embedded systems. Time critical framework. embedded systems design is mainly based on commercial processors with a good average time A possible solution to build such common framework behavior. During the last twenty years different while decreasing the pessimism may be proposed design solutions have been proposed through by enriching existing models with appropriate pessimistic estimation of performances of the probabilistic descriptions. Probabilistic description of processors (thus increased costs) while using a model provides more information to the designer average time behavior processors. while allowing several values for a parameter, or several states for a property. Nevertheless, the The pessimism of all existing solutions comes mainly introduction of probabilities is not trivial as not from the implementation phase where an absolute every probabilistic approach may be used to study value is considered for the worst case execution time critical embedded systems. First, we prove time of a program. The arrival of modern and more that the worst case values of the execution times complex processors (e.g., use of caches, multi- of a program are rare events Cucu-Grosjean and and many-core processors) increases the timing al. (2012). Secondly, the average-case probabilistic variability of programs, i.e., the absolute worst case reasoning is not useful to guarantee time constraints execution time is becoming significantly larger. For Maxim and Cucu (2013). We define the probabilistic instance, larger execution times require an increased worst case reasoning as a probabilistic bound on number of processors or more powerful processors. possible values for a parameter or a property of the system Cucu-Grosjean (2013). An intuitive solution to overcome this pessimism is the introduction by Steve Vestal in Vestal (2007) In this talk we define probabilistic upper bounds of the notion of mixed criticality for time critical on all possible values or states as the probabilistic worst case reasoning ensuring the migration of • Probabilistic approaches for asynchronous probabilistic methods from modelling soft time models taking into account mixed criticality constraints to analysing hard time constraints. Two systems. Here the transition between states common misconceptions concerning probabilistic may be the first to be described probabilisti- time critical embedded systems are discussed: cally. independence and the identical distribution. We summarize recent state-of-the-art research into • Probabilistic approaches for real-time schedul- probabilistic approaches, and we conclude with the ing analysis for mixed criticality systems. main open challenges in this area. • Probabilistic approaches for verification for mixed criticality systems. The integration of 2. DESIGN OF TIME CRITICAL EMBEDDED rare events probability distributions in current SYSTEMS probabilistic model checking seems to be the first reasonable step. The design of a time critical embedded system may have basically three main phases: (i) the description REFERENCES of the physical process that should be controlled (control theory), (ii) the description of the functional Vestal, S. (2007) Preemptive scheduling of multi- requirements that should be fulfilled (synchronous criticality systems with varying degrees of execu- and asynchronous models) and (iii) the description tion time assurance the IEEE Real-Time Systems of the implementation of the time critical embedded Symposium. system (scheduling or verification). Burns, A. and Davis, R., (2015) Mixed Criticality Systems - Review University of York. Control* Theory* Yip, E. and Kuo, M. and Roop, P. and Broman, requirements* D., (2015) Relaxing the synchronous approach Func8onal* for mixed-criticality systems the 20th IEEE Real- Time and Embedded Technology and Application Synchronous** Asynchronous** Models* Models* Symposium. Zimmer, M. and Broman, D. and Shaver, C. and Lee, E., (2014) FlexPRET: A processor platform Processor* for mixed-criticality systems the 20th IEEE Real- Implementa8on* Time and Embedded Technology and Application Symposium. Model* Real78me* Checking* Scheduling* Boudjadar, A.J. and David, A. and Kim, J. and Larsen, K.G. and Mikucionis, M. and Nyman, U. and Skou, A., (2014) Degree of Schedulability Figure 1: Different phases of the design of a time critical of Mixed-Criticality Real-Time Systems with embedded system Probabilistic Sporadic Tasks Theoretical Aspects of Software Engineering Conference. In order to decrease the pessimism of the design solutions, while ensuring time critical constraints, Maxim, D. and Cucu-Grosjean, L., (2014) Response probabilistic description of parameters may be Time Analysis for Fixed-Priority Tasks with Multiple defined at different levels of design of a time critical Probabilistic Parameters the 34th IEEE Real-Time embedded system: Systems Symposium. • Probabilistic approaches for control theory for Cucu-Grosjean, L. and Santinelli, L. and Houston, mixed criticality systems. Solving a control sys- M. and Lo, C. and Vardanega, T. and Kosmidis, tem problem consists in finding the sampling L. and Abella, J. and Mezzeti, E. and Quinones, frequency and we identify it as the first property E. and Cazorla, F., (2012) Measurement-Based to be described probabilistically. Probabilistic Timing Analysis for Multi-path Pro- grams the 24th Euromicro Conference on Real- • Probabilistic approaches for synchronous time Systems. models for mixed criticality systems. The transition between states might be the first Cucu-Grosjean, L., (2013) Independence - a property to be described probabilistically by misunderstood property of and for (probabilistic) relaxing the synchrony hypothesis. real-time systems Real-Time Systems: the past, the present, and the future.