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.

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.

In real-time embedded systems, a system functionality is often implemented using a data-flow chain over a set of communicating tasks. A critical non-functional requirement in such systems is to restrict the amount of time, i.e. cause-effect latency, for an input to impact its corresponding output. The problem of estimating the worst-case cause-effect latency is well-studied in the context of blocking inter-task communication. Recent research results show that non-blocking communication preserving functional semantics is critical for the model-based design of dynamically updatable systems. In this paper, we study the worst-case cause-effect reaction latency estimation problem in the context of non-blocking inter-task communication. We present a computationally efficient algorithm that tightly over-approximates the exact worst-case reaction latency in cause-effect data-flow chains.

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.