Many parallel real-time applications can be modeled as DAG tasks. Guaranteeing timing constraints of such applications executed on multicore systems is challenging, especially for the applications with non-preemptive execution blocks. The existing approach for timing analysis of such tasks with sporadic release relies on computing a bound on the interfering workload on a task, which depends on the number of priority inversions the task may experience. The number of priority inversions, in turn, is a function of the total number of additional cores a task instance may request after each node spawning. In this paper, we show that the previously proposed polynomial-time algorithm to compute the maximum number of additional core requests of a DAG is not correct, providing a counter example. We show that the problem is in fact NP-hard. We then present an ILP formulation as an exact solution to the problem. Our evaluations show that the problem can be solved in a few minutes even for DAGs with hundreds of nodes.

Wireless sensor and actuator networks (WSAN) are real-time systems which demand timing requirements. To ensure this level of requirements, different timing analysis approaches have been proposed for WSAN systems. Among different alternatives, analytical analysis and model checking approaches are two common ones which are widely used for the timing analysis of WSAN systems. Analytical approaches apply worst-case response time analysis techniques, whereas model checking generates explicit states of models to analyze them. In this paper, we develop schedulability analysis techniques based on two approaches, i.e., analytical and model checking approaches. We apply and compare the proposed analysis approaches on WSAN systems with an application in monitoring and control of civil infrastructures implemented on the Imote2 wireless sensor platform. We show that the highest possible data acquisition frequency for this application is computed while meeting the deadlines, and compare the results of the two approaches in terms of scalability, extensibility, and flexibility.

Guaranteeing timing constraints for parallel real-time applications deployed on multicore platforms is challenging, especially for applications containing non-preemptive execution blocks, that suffer from priority inversions. In this article, we propose to model such applications using a sporadic directed acyclic graph (DAG) model where preemption may take place only between the nodes of a DAG task. We present a new method for response-time analysis of such tasks scheduled with the global fixed-priority scheduling policy. We show that our method outperforms the state-of-the-art techniques significantly in terms of resource utilization in experimental evaluations using both benchmark and randomly generated task sets. We also present a method to deal with global EDF scheduling, which is a new technique proposed for response time analysis of sporadic DAG tasks with non-preemptive nodes.

Designing timing-anomaly free multiprocessor scheduling algorithms is a notoriously hard problem, especially for parallel tasks with non-preemptive execution regions. In this paper, we first propose a simple yet expressive model which abstracts a parallel task as a single computation unit, and then, present a sufficient condition for timing-anomaly free scheduling of such units. On top of this, we design an algorithm for scheduling a set of periodic parallel tasks, represented as DAG with non-preemptive subtasks, on multicore processors. The algorithm has several desirable properties, including timing-anomaly freedom, high resource utilization, and low memory requirement. Timing-anomaly freedom enables an exact schedulability test for the algorithm, which, as shown in our evaluations, provides a significantly high schedulability ratio compared to those state-of-the-art methods that suffer from timing anomalies.

Currently the main approaches to model-based design of embedded software rely on the synchronous paradigm where the executions of software components are either statically ordered or enforced using predefined orderings e.g. Simulink diagrams. However, these approaches may result in resource over provisioning and inflexibility e.g. adding a new function block may require re-designing the whole system. To overcome these drawbacks, we use a dynamic approach allowing multi-tasking implementation of software components using real-time tasks. The challenge is run-time scheduling and schedulability analysis of real-time tasks with inter-task communication (i.e. resource sharing). In this paper, we use a graph-based task model (DRT developed in previous work) to describe software components as a system of real-time tasks sharing not only a uniprocessor but also non-preemptive resources e.g. accesses to shared data. However, timing analysis for such general task model with mixed execution of preemptive and non-preemptive jobs is yet to be developed. As the main technical contribution, we present an exact schedulability test for task systems containing both preemptive and non-preemptive computation jobs with experimental evaluations showing the efficiency of our approach for realistic workload such as the engine control applications. We also present an approach to generate event-triggered Ada programs from analyzed design models.

Harmonic periods have wide applicability in industrial real-time systems. Rate monotonic (RM) is able to schedule task sets with harmonic periods up to 100% utilization. Also, if there is no release jitter and execution time variation, RM and EDF generate the same schedule for each instance of a task. As a result, all instances of a task are interfered by the same amount of workload. This property decreases the jitters that happen during sampling and actuation of the tasks, and hence, it increases the quality of service in control systems. In this paper, we consider the problem of optimal period assignment where the periods are constrained to be harmonic and the task set is required to be feasible. We study two variants of this problem. In the first one, the objective is to maximize the system utilization, while in the second one, the goal is to minimize the total weighted sum of the periods. First, we assume that an interval is determined a priori for each task from which its period can be selected. We show that both variants of the problem are (at least) weakly NP-hard. This is shown by reducing the NP-complete number partitioning problem to the mentioned harmonic period assignment problems. Afterwards, we consider a variant of the second problem in which the periods are not restricted to a special interval. We present two approximation algorithms with polynomial-time complexity for this problem and show that the maximum relative error of these algorithms is bounded by a factor of 1.125. Our evaluations show that, on the average, results of the approximation algorithms are very close to an optimal solution.

Conformance testing is a formal and structured approach to verifying system correctness. We propose a conformance testing algorithm for cyber-physical systems, based on the notion of hybrid conformance by Abbas and Fainekos. We show how the dynamics of system specification and the sampling rate play an essential role in making sound verdicts. We specify and prove error bounds that lead to sound test-suites for a given specification and a given sampling rate. We use reachability analysis to find such bounds and implement the proposed approach using the CORA toolbox in Matlab. We apply the implemented approach on a case study from the automotive domain.

We study an engine control application where the behavior of engine controllers depends on the engine's rotational speed. For efficient and precise timing analysis, we use the Digraph Real-Time (DRT) task model to specify the workload of control tasks where we employ optimal control theory to faithfully calculate the respective minimum inter-release times. We show how DRT models can be refined by finer grained partitioning of the state space of the engine up to a model which enables an exact timing analysis. Compared to previously proposed methods which are either unsafe or pessimistic, our work provides both abstract and tight characterizations of the corresponding workload.

Real-time task models have evolved from periodic models to more sophisticated graph-based ones like the Digraph Real Time task model (DRT) to specify branching and loop structures of real-time embedded software. For independent DRT tasks, efficient techniques for schedulability analysis have been developed in previous work. In this paper, we extend the DRT model to specify inter-task synchronization through a rendezvous mechanism. We present an abstraction technique for static priority schedulability analysis of the corresponding tasks. Our experiments show that, despite the high computational complexity of the problem, the proposed technique scales very well for large sets of dependent tasks.

This paper deals with thermal management of a multicore processor executing multiple stochastic real-time job streams. The main objective is to reduce the chip-wide temperature gradient to decelerate processor aging, and the subordinate goal is to decrease the hotspot temperature. A pair of active and passive cores is dedicated to each stream, which the active one services the corresponding real-time jobs. In order to reduce the chip-wide temperature gradient between cores, the active and passive cores of an individual stream are replaced at appropriate times through job migration. The thermal management of this system is a specific stochastic control problem. Regarding the inter-effects of core temperatures and the stochastic nature of the system, systematic achievement of the objective needs an appropriate method. The control theory of Markov jump linear system (MJLS) has been used to design the desired thermal controller and analytically study its stability. The efficacy of the proposed approach in terms of the thermal management objectives is investigated through simulation experiments.

Conformance testing is a formal and structured approach to verifying system correctness. We propose a conformance testing algorithm for cyber-physical systems, based on the notion of hybrid conformance by Abbas and Fainekos. We show how the dynamics of system specification and the sampling rate play an essential role in making sound verdicts. We specify and prove error bounds that lead to sound test-suites for a given specification and a given sampling rate.

We consider a firm real-time system with a single processor working in two power modes depending on whether it is idle or executing a job. The system is equipped with dynamic thermal management through a cooling subsystem which can switch between two cooling modes. Real-time jobs which arrive to the system have stochastic properties and are prone to soft errors. A successful job is one that enters the system and completes its execution with no timing or soft error. Appropriateness of the system is evaluated based on its performance, temperature behavior, reliability, and energy consumption. It is noteworthy that these criteria have mutual interactions to each other: the stochastic nature of the system affects the success ratio of jobs beside the system dynamic power, the leakage as well as dynamic power impacts the processor temperature, this temperature affects the leakage power, the cooling subsystem power, and the soft error rate, which the latter in turn impacts the system reliability and the success ratio of jobs. This paper proposes an analytical evaluation method with a Markovian view to the system which considers these reciprocal effects. A number of simulation experiments are carried out to validate the accuracy of the proposed method.

Energy management is an important issue in today's real-time systems due to the high costs of energy supplying. Using renewable, like wave, wind, and solar energy sources seem promising methods to address this issue. However, because of the existing contrast between the critical nature of hard real-time systems and the unpredictable nature of renewable energies, some supplementary energy source like electricity grid or battery is needed. In this paper, we consider hard real-time systems with two renewable and nonrenewable energy sources. In order to reduce the costs, we present two dynamic voltage scaling controllers to minimize the energy attained from the latter source. In order to handle variations of the environmental energy and workload, the model predictive control approach is employed. One nonlinear approach beside one fast linear piecewise affine explicit controller are proposed. The efficacies of the proposed approaches have been investigated through extensive simulations. Comparisons to an ideal clairvoyant controller as a baseline show that, in the studied scenarios, the proposed controllers guarantee at least 78% of the baseline performance.

This paper considers object-based distributed real-time systems within which objects provide system services to the real-time tasks. Each task is subject to a time/utility function (TUF) which determines the accrued utility of the task according to its completion time. One major problem in such systems is to place the objects onto the computing nodes so as to maximize the total accrued utility. Thus, we propose a utility accrual object distribution (UAOD) algorithm which consists of two phases. In the first phase, through object placement and replication beside some types of deadline decomposition and adaptation, the computing nodes are reserved for the most beneficial tasks. As the second phase, UAOD follows a load-balancing algorithm for the placement of the remaining objects on the nodes to service the less beneficial tasks. Simulation results reveal that the total accrued utility is improved with the UAOD algorithm comparing to the traditional object placement methods.