Safety-critical real-time embedded systems are becoming difficult to model and analyze as they accommodate more and more functionalities, and they rely on more and more complex HW and SW implementations. One of the main difficulty with such systems is to find the right coupling between the task model and the analysis method. Indeed, if the task model is too simple it may add pessimism to the result of the analysis, and it may not be possible to prove the correctness of the systems. If the model is too complex, the analysis may be not efficient enough to be usable; or worst the model may have an incomplete method only or no method at all, so the system cannot be analyzed. Finding, the right couple task model analysis method is a balance between expressiveness and analysis efficiency. In this article, we introduce a new graph real-time task model (noted GGTM) which has been used for several years for the deployment and the analysis of different embedded systems. We discuss its expressiveness compared to the literature and demonstrate its advantages. We also, present a decidable and efficient, exact schedulability analysis.

Mixed-Criticality (MC) systems have been widely studied in the past decade, majorly due to their potential to consolidate applications with different criticality levels onto the same platform. In the original design proposed by Vestal, a target probability of failure per hour specified by certification requirements is assigned to each criticality level. These requirements have been mainly conceived for hardware faults. Software fault tolerance techniques are available to mitigate hardware faults, but their adaptation to real-time systems is challenging due to the introduced overhead. This paper proposes an extension to the traditional MC scheduling theory to implement fault tolerance strategies against transient faults, with the goal of complying with both failure and timing requirements. In particular, we introduce the dropping relationships that generalize the concept of criticality and allow, on the one hand, to improve the schedulability analysis, on the other, to control the dependency between tasks satisfying the certification requirements. The simulation study shows a schedulability ratio improvement of 20-30% compared to classical scheduling while maintaining compliance with failure requirements.

The problem of estimating a tight and safe Worst-Case Execution Time (WCET), needed for certification in safety-critical environment, is a challenging problem for modern embedded systems. A possible solution proposed in past years is to exploit statistical tools to obtain a probability distribution of the WCET. These probabilistic real-time analyses for WCET are, however, subject to errors, even when all the applicability hypotheses are satisfied and verified. This is caused by the uncertainties of the probabilistic-WCET distribution estimator. This article aims at improving the measurement-based probabilistic timing analysis approach providing some techniques to analyze and deal with such uncertainties. The so-called region of acceptance model based on state-of-the-art statistical test procedures is defined over the distribution space parameters. From this model, a set of strategies is derived and discussed to provide the methodology to deal with the trade-off safety/tightness of the WCET estimation. These techniques are then tested over real datasets, including industrial safety-critical applications, to show the increased value of using the proposed approach in probabilistic WCET analyses.

Mixing workloads with multiple criticality levels raises challenges both in timing analysis and schedulability analysis. The timing models have to characterize the different behaviors that real-time tasks can experience under the various criticality modes. Instead, the schedulability analysis has to combine every task and task interactions providing several guarantees, depending on the criticality level demanded at runtime. With this work, at first we propose representations to model every possible system criticality mode as a combination of task criticality modes. A set of bounding functions is obtained, a bound for each mode combination thus corresponding to a system criticality level. Secondly, we develop the schedulability analysis that applies such sets and derives schedulability conditions with mixed criticalities. The tasks are scheduled with fixed priority and earlies deadline first, and various levels of schedulability are defined from the mode combinations. Finally, we make use of the sensitivity analysis to evaluate the impact that multi mode task behaviors have on schedulability. Trade-offs between schedulability, criticality levels and resource availability are explored. A mixed critical real-time system case study validates the framework proposed.

The Measurement-Based Probabilistic Timing Analysis (MBPTA) computes probabilistic Worst-Case Execution Time (pWCET) estimates with the Extreme Value Theory (EVT) from measurements of tasks execution time. In this work we approach the MBPTA open problems by proposing guidelines for a formal and correct EVT application. Statistical analyses of measurement of execution times, the EVT parameters selection, the pWCET reliability and the worst-case guarantees are investigated in order to provide the best possible MBPTA. The MBPTA enhancements proposed are validated with test cases from both artificially time randomized real-time systems and non-time randomized real-time systems.

Providing guarantees on the system behavior is mandatory in order to let the robots enter our every-day life. Among these guarantees, proving the fulfillment of real-time constraints on the software is a key issue, as their violation could result into unexpected and unsafe behaviors. In this paper, we present a methodology to guarantee real-time constraints on component-based software architectures of robots. This methodology relies on the MAUVE language to model the component architecture, and on a set of analysis tools that first estimate the worst case execution time of elementary functions from actual component traces, and then check the real-time constraints of each component. We illustrate this process on the architecture developed for the autonomous navigation of a partially known area by a mobile robot.

Current processors have gone through multiple internal optimization to speed-up the average execution time e.g. pipelines, branch prediction. Besides, internal communication mechanisms and shared resources like caches or buses have a significant impact on Worst-Case Execution Times (WCETs). Having an accurate estimate of a WCET is now a challenge. Probabilistic approaches provide a viable alternative to single WCET estimation. They consider WCET as a probabilistic distribution associated to uncertainty or risk.

Nowadays dangerous, repetitive or precision requiring jobs are done by robots like flying drones, industrial assembly arms or medical assistants. In all these cases, human beings can interact with the machines, therefore it is essential to guarantee that every part of the robot's software and hardware will produce a safe behavior: both the overall behavior and the local behaviors of such embedded systems have to be carefully analyzed. The complexity of embedded systems software architectures increase with more and more tasks involved; state-machines are applied to implement more functional capabilities of the tasks; and the task models used in the analyses gain in complexity. The analysis techniques have to be adapted in order to face such new complexities. This paper focuses on the real-time analysis of state-machine-based software architectures. We propose a method to analyze the temporal behavior of a component-based architecture in which the components are described by state-machines. The method computes an accurate worst-case response time by taking into account the state-machines of the components. Finally, we validate our approach with a real real-time robotic case study.

Many safety critical real-time systems are considered certified when they meet failure probability requirements with respect to the maximum permitted incidences of failure per hour. In this paper, the mixed-criticality task model with multiple worst case execution time (WCET) estimations is extended to incorporate such system-level certification restrictions. A new parameter is added to each task, characterizing the distribution of the WCET estimations -- the likelihood of all jobs of a task finishing their executions within the less pessimistic WCET estimate. An efficient algorithm named LFF-Clustering is derived for scheduling mixed-criticality systems represented by this model. Experimental analyses show our new model and algorithm out-perform current state-of-the-art mixed-criticality scheduling algorithms.

Challenges within real-time research are mostly in terms of modeling and analyzing the complexity of actual real-time embedded systems. Probabilities are effective in both modeling and analyzing embedded systems by increasing the amount of information for the description of elements composing the system. Elements are tasks and applications that need resources, schedulers that execute tasks, and resource provisioning that satisfies the resource demand. In this work, we present a model that considers component-based real-time systems with component interfaces able to abstract both the functional and nonfunctional requirements of components and the system. Our model faces probabilities and probabilistic real-time systems unifying in the same framework probabilistic scheduling techniques and compositional guarantees varying from soft to hard real time. We provide an algebra to work with the probabilistic notation developed and form an analysis in terms of sufficient probabilistic schedulability conditions for task systems with either preemptive fixed-priority or earliest deadline first scheduling paradigms.

This paper integrates analysis of probabilistic cache related pre-emption delays (pCRPD) and static probabilistic timing analysis (SPTA) for multipath programs running on a hardware platform that uses an evict-on-miss random cache replacement policy. The SPTA computes an upper bound on the probabilistic worst-case execution time (pWCET) of the program, which is an exceedance function giving the probability that the execution time of the program will exceed any given value on any particular run. The pCRPD analysis determines the maximum effect of a pre-emption on the pWCET. The integration between SPTA and pCRPD updates the pWCET to account for the effects of one or more pre-emptions at any arbitrary points in the program. This integration is a necessary step enabling effective schedulability analysis for probabilistic hard real-time systems that use pre-emptive or co-operative scheduling. The analysis is illustrated via a number of benchmark programs.

Realistic real-time systems experience variability and unpredictabilities, which can be compensated by potentially very pessimistic worst-cases. Recent trends apply measurement-based approaches in modeling worst-cases with a certain confidence. While observing system evolution it is possible to extract probabilistic models to the task execution with a guaranteed probabilistic version of worst-case execution time. In this work we exploit such probabilistic models in order to study the effect of dependences on the task execution time, and we apply the developed probabilistic framework to few relevant cases studies.

Static timing analysis is the state-of-the-art practice of ascertaining the timing behavior of current-generation real-time embedded systems. The adoption of more complex hardware to respond to the increasing demand for computing power in next-generation systems exacerbates some of the limitations of static timing analysis. In particular, the effort of acquiring (1) detailed information on the hardware to develop an accurate model of its execution latency as well as (2) knowledge of the timing behavior of the program in the presence of varying hardware conditions, such as those dependent on the history of previously executed instructions. We call these problems the timing analysis walls. In this vision-statement article, we present probabilistic timing analysis , a novel approach to the analysis of the timing behavior of next-generation real-time embedded systems. We show how probabilistic timing analysis attacks the timing analysis walls; we then illustrate the mathematical foundations on which this method is based and the challenges we face in the effort of efficiently implementing it. We also present experimental evidence that shows how probabilistic timing analysis reduces the extent of knowledge about the execution platform required to produce probabilistically accurate WCET estimations.

The rigorous application of static timing analysis requires a large and costly amount of detail knowledge on the hardware and software components of the system. Probabilistic Timing Analysis has potential for reducing the weight of that demand. In this paper, we present a sound measurement-based probabilistic timing analysis technique based on Extreme Value Theory. In all the experiments made as part of this work, the timing bounds determined by our technique were less than 15% pessimistic in comparison with the tightest possible bounds obtainable with any probabilistic timing analysis technique. As a point of interest to industrial users, our technique also requires a comparatively low number of measurement runs of the program under analysis, less than 650 runs were needed for the benchmarks presented in this paper.

A crucial objective in battery operated embedded systems is to work under the minimal power consumption that provides a desired level of performance. Dynamic Voltage and Frequency Scaling (DVFS) and Dynamic Power Management (DPM) are typical techniques used on processors and devices to reduce the power consumption through speed variations and power switching, respectively. The effectiveness of DVFS and DPM methods needs to be considered in the development of a power management policy for systems that consist of DVFS-enabled or DPM-enabled components. This paper explores how to efficiently reduce the power consumption of real-time applications with constrained resources, like energy, CPU and transmission bandwidth. A combined DVFS-DPM approach with a reduced complexity is proposed to make use of on-line strategies for embedded systems.

A challenging research issue of analyzing a real-time system is to model the tasks composing the system and the resource provided to the system. In this paper, we propose a probabilistic component-based model which abstracts in the interfaces both the functional and non-functional requirements of such systems. This approach allows designers to unify in the same framework probabilistic scheduling techniques and compositional guarantees that go from soft to hard real-time. We provide sufficient schedulability tests for task systems using such framework when the scheduler is either preemptive Fixed-Priority or Earliest Deadline First.

Often real-time systems can run in different modes depending on the external environment or their internal state. Each operational mode is characterized by a set of tasks with different computational demand, resource requirements, and resource availability. When resource reservation is used to achieve temporal isolation among applications, the reservation parameters may need to change from mode to mode. Hence, an additional guarantee is required to ensure feasibility not only of the applications, but also of the reservations. This paper presents a schedulability analysis to predict the timing behavior of a multi-moded resource reservation, whose parameters may change due to a mode transition. Resource provisioning is analyzed in all the operational modes and also during mode-changes in order to guarantee a minimum amount of resources and derive a feasibility condition for realtime applications and reservations. Theoretical results are also illustrated with examples and test cases.

Dynamic power management has become essential for battery-driven embedded systems. This paper explores how to efficiently and effectively reduce the energy consumption of a device (system) for serving multiple event streams. Considering two different preemptive scheduling, i.e., earliest deadline first and fixed priority, we propose new method to adaptively control the power mode of the device according to historical arrivals of events. Our method can not only tackle arbitrary event arrivals but also provide hard real-time guarantees with respect to both timing and backlog constraints. Simulation results are presented as well to demonstrate the effectiveness of our approach.

Multi-Processor Systems-on-Chip (MPSoC) are an increasingly important design paradigm not only for mobile embedded systems but also for industrial applications such as automotive and avionic systems. Such systems typically execute multiple concurrent applications, with different execution modes. Modes define differences in functionality and computational resource demands and are assigned with an execution probability. We propose a dynamic mapping approach to maintain low power consumption over the system lifetime. Mapping templates for different application modes and execution probabilities are computed offline and stored on the system. At runtime a manager monitors the system and chooses an appropriate pre-computed template. Experiments show that our approach outperforms global static mapping approaches up to 45%.

A crucial objective in battery operated embedded systems is to work under the minimal power consumption that provides a desired level of performance. Dynamic Voltage Scaling (DVS) and Dynamic. Power Management (DPM) are typical techniques used on processors and devices to reduce the power consumption through speed variations and power switching, respectively. The effectivenes of both DVS and DPM needs to be considered in the development of a power management policy for a system that consists of both DVS-enabled and DPM-enabled components.

Many real-time applications are designed to work in different operating modes each characterized by different functionality and resource demands. With each mode change, resource demands of applications change, and static resource reservations may not be feasible anymore. Dynamic environments where applications may be added and removed online also need to adapt their resource reservations. In such scenarios, resource reconfigurations are needed for changing the resource reservations during runtime and achieve better resource allocations. There are a lot of results in the scientific literature of how to find the optimal amount of resources needed by an application in the different operating modes, or how an application can perform safe mode transitions. However, the problem of resource reconfigurations for systems with reservations has not been addressed. A resource scheduler should be reconfigured online in such a way that it still guarantees a certain amount of resources during the reconfiguration process, otherwise applications may miss deadlines. The paper proposes a framework for scheduling real-time applications through scheduling servers that provide resource reservations, and algorithms for changing the resource reservations online while still guaranteeing the feasibility of the system and the schedulability of applications. The framework analysis is integrated into a well-known modular performance analysis paradigm based on Real-Time Calculus. The results are illustrated with examples and a case study.

Power dissipation has constrained the performance boosting of modern computer systems in the past decade. Dynamic power management has been widely applied to change the system (or device) state dynamically to reduce the power consumption. This paper explores how to effectively reduce the energy consumption to handle event streams with hard real-time guarantees. We adopt Real-Time Calculus to describe the event arrival and resource service by arrival curves and service curves in the interval domain, respectively. We develop online algorithms to adaptively control the power mode of the device, postponing the processing of arrival events as late as possible. Profited from the worst-case interval-based abstraction, our algorithms can on one hand tackle arbitrary event arrivals (even with burstiness) and on the other hand guarantee hard real-time requirements in terms of both timing and backlog constraints. We also present simulation results to demonstrate the effectiveness of our algorithms.