In many modern safety-critical cyber-physical sys-tems, such as in the automotive or robotic domain, the appli-cation complexity requires the use of multi-core platforms to execute all workloads under strict hard real-time constraints. The sporadic DAG task model is a parallel task model adept at representing tasks comprised of subtasks, which possess internal data flow and precedence constraints induced by synchronization. A significant challenge to the system's performance and its real-time verification stems from the communication-centric nature of applications in these domains. Inter-core communication, required for data sharing among sub tasks across different cores, depends on either a shared bus or a network-on-chip, culminating in significant overhead due to latency, congestion, and synchronization. To improve performance and reduce these overheads, it is advantageous to execute subtasks, those that either exchange large volumes of data or access the same data, on a singular physical processor, thereby utilizing more efficient intra-core communication. In this paper, we tackle this issue by introducing the DAG task model with execution groups, incorporating a constraint that mandates the execution of grouped sub tasks on the same pro-cessor. We provide an analysis of worst-case response times and propose optimizations for our DAG task model with execution groups, subsequently evaluating our approach against existing solutions. The evaluation results demonstrate that our approach, even with the imposition of group execution constraints, remains competitive in comparison to existing approaches that do not take group execution constraints into account. Additionally, we explore implementation strategies and potential extensions for multi-task systems.

This lightning talk introduces the motivations of the needs of formal properties that can be used modularly to compose safe and tight analysis and optimization for the scheduler design and schedulability test problems for cyber-physical real-time systems. The key challenge is the correct and precise translation from different schedule functions to proper mathematical properties that can be further used for property-based modulable designs.

Safety-critical systems are often subjected to transient faults. Since these transient faults may lead to soft errors that cause catastrophic consequences, error-handling must be addressed by design. Full-protection against faults is too costly in terms of resource usage. A common approach to relax the resource demands and limit the impact of errors is to consider (m, k)-constraints, which requires that at least m jobs out of any k consecutive jobs are error-free. To assure (m, k)-compliance, static patterns are widely used to select the job execution modes, i.e., either in an error-free mode at the cost of increased worst-case execution time or in an error-prone mode with the advantage of less execution time. Although static patterns have been shown to be effective in energy-aware designs, resource over-provision is inevitable due to the relatively low rate of error probability. In this work, we propose two dynamic (and adaptive) approaches that allow the scheduler to opportunistically select execution modes based on the error-history of the past jobs and the actual error probability. We firstly propose a Markov chain based solution if the error-probability is known and static and secondly a reinforcement learning-based approach that can handle unknown error probabilities. Experimental evaluations show that our approaches outperform the state-of-the-art in most of the evaluated cases in terms of average utilization for each task and the overall utilization for multitask systems.

To utilize the performance benefits of heterogeneous multicore platforms in real-time systems, we need task models that expose the parallelism and heterogeneity of the workload, such as typed DAG tasks, as well as scheduling algorithms that effectively exploit this information. In this paper, we introducetype-aware federated schedulingalgorithms for sporadic typed DAG tasks with implicit deadlines running on a heterogeneous multicore platform with two different types of cores. In type-aware federated scheduling, a task can be executed in one of the three strategies:Exclusive Allocation,Semi-Exclusive Allocation, andSequential and Share. InExclusive Allocation, clusters of cores of both core types are exclusively allocated to tasks, while cores of only one type are exclusively allocated to tasks inSemi-Exclusive Allocation. The workload of the other type from tasks inSemi-Exclusive Allocationand the workload from tasks inSequential and Shareshare the cores that are not exclusively allocated to any task. We prove that our type-aware federated scheduling algorithm has a capacity augmentation bound of 7.25. We also show that no constant capacity augmentation bound can be obtained withoutSemi-Exclusive Allocation. Compared to the state of the art, the type-aware federated scheduling algorithm achieves better schedulability, especially for task sets with skewed workload.

Increasing performance needs of modern cyber-physical systems leads to multiprocessor architectures being increasingly utilized. To efficiently exploit their potential parallelism in hard real-time systems, appropriate task models and scheduling algorithms that allow to provide timing guarantees are required. Such scheduling algorithms and the corresponding worst-case response time analyses usually suffer from resource over-provisioning due to pessimistic analyses based on worst-case assumptions. Hence, scheduling algorithms and analyses with high resource efficiency are required. A prominent fine-grained parallel task model is the directed-acyclic-graph (DAG) task model that is composed of precedence constrained subjobs. This paper studies the hierarchical real-time scheduling problem of sporadic arbitrary-deadline DAG tasks. We propose a parallel path progression scheduling property that is implemented with only two distinct subtask priorities, which allows to quantify the parallel execution of a user chosen collection of complete paths in the response time analysis. This novel approach significantly improves the state-of-the-art response time analyses for parallel DAG tasks for highly parallel DAG structures and can provably exhaust large core numbers. Two hierarchical scheduling algorithms are designed based on this property, extending the parallel path progression properties and improve the response time analysis for sporadic arbitrary-deadline DAG task sets.

Real-time systems require the formal guarantee of timing constraints, not only for the individual tasks but also for the end-to-end latency of data flows. The data flow among multiple tasks, e.g., from sensors to actuators, is described by a cause-effect chain, independent from the priority order of the tasks. In this article, we provide an end-to-end timing-analysis for cause-effect chains on asynchronized distributed systems with periodic task activations, considering the maximum reaction time (MRT) (i.e., the duration of data processing) and the maximum data age (MDA) (i.e., the worst-case data freshness). We first provide an analysis of the end-to-end latency on one local electronic control unit (ECU) that has to consider only the jobs in a bounded time interval. We extend our analysis to globally asynchronized systems by exploiting a compositional property to combine the local results. Throughout synthesized data based on an automotive benchmark as well as on randomized parameters, we show that our analytical results improve the state-of-the-art.

In many embedded systems, for instance, in the automotive, avionic, or robotics domain, critical functionalities are implemented via chains of communicating recurrent tasks. To ensure safety and correctness of such systems, guarantees on the reaction time, that is, the delay between a cause (e.g., an external activity or reading of a sensor) and the corresponding effect, must be provided. Current approaches focus on the maximum reaction time, considering the worst-case system behavior. However, in many scenarios, probabilistic guarantees on the reaction time are sufficient. That is, it is sufficient to provide a guarantee that the reaction does not exceed a certain threshold with (at least) a certain probability. This work provides such probabilistic guarantees on the reaction time, considering two types of randomness: response time randomness and failure probabilities. To the best of our knowledge, this is the first work that defines and analyzes probabilistic reaction time for cause-effect chains based on sporadic tasks.

In the domain of embedded systems, modern SoCs (System-on-Chips) increasingly employ dedicated hardware to improve the performance of specialized tasks. The herein generated performance benefits come at the cost of increased coordination complexity of multiple tasks accessing these various hardware units in varying alternating sequences. For example, a task may first execute on a processor and then proceed execution on a GPU. This problem is even more complex in the case of real-time constraints, i.e., the execution within formally guaranteed time bounds. Real-time constraints may lead to severe resource under-utilization if the scheduling algorithms are not properly designed. A solution to this problem is self-suspension and segment-level fixed-priority scheduling. In this approach, tasks are divided into successive alternating segments of computation and self-suspension. The task may self-suspend if it tries to access a hardware resource that is already held by another task. In this paper, we propose and discuss different implementations of the segmented self-suspension task model in the FreeRTOS real-time operating system. Moreover, we evaluate the overhead of the different implementations on the OM40007 IoT-module from NXP.

Modern autonomous vehicle platforms feature many interacting components and sensors, which add to the system complexity and affect their performance. A key aspect for such platforms are end-to-end timing guarantees, which are required for safe and predictable behavior in every situation. One widely used tool to develop such autonomous systems is the Robot Operating System 2 (ROS2), which allows creating robot applications composed of several components that communicate with each other to form complex systems. Furthermore, it guarantees real-time constraints and provides reliable timing behavior using a custom scheduler design that manages the execution of all components. These components and their data propagation form multiple cause-effect chains that can be analyzed to determine two key metrics: maximum reaction time (which is the maximum time for the system to react to an external input) and maximum data age (which equals the maximum time between sampling and the output of the system being based on that sample). However, an end-to-end analysis for cause-effect chains in ROS2 systems has not been provided yet. In this paper, we provide a theoretical upper bound for the end-to-end timing of a ROS2 system on a single electronic control unit (ECU). Additionally, we show how to simulate a ROS2 system to get a lower bound for the timing analysis and introduce an online end-to-end timing measurement method for existing ROS2 systems. We evaluate our methods with a basic autonomous navigation system and determine the timing behavior for different components and sensor configurations.

The performance of multiprocessor synchronization and locking protocols is a key factor to utilize the computation power of multiprocessor systems under real-time constraints. While multiple protocols have been developed in the past decades, their performance highly depends on the task partition and prioritization. The recently proposed Dependency Graph Approach showed its advantages and attracted a lot of interest. It is, however, restricted to task sets where each task has at most one critical section. In this article, we remove this restriction and demonstrate how to utilize algorithms for the classical job shop scheduling problem to construct a dependency graph for tasks with multiple critical sections. To show the applicability, we discuss the implementation in$\text{LITMUS}^{\text{RT}}$and report the overheads. Moreover, we provide extensive numerical evaluations under different configurations, which in many situations show significant improvement compared to the state-of-the-art.

Gang scheduling has long been adopted by the high-performance computing community as a way to reduce the synchronization overhead between related threads. It allows for several threads to execute in lock steps without suffering from long busy-wait periods or be penalized by large context-switch overheads. When combined with non-preemptive execution, gang scheduling significantly reduces the execution time of threads that work on the same data by decreasing the number of memory transactions required to load or store the data. In this work, we focus on two main types of gang tasks: rigid and moldable. A moldable gang task has a presumed known minimum and maximum number of cores on which it can be executed at runtime, while a rigid gang task always executes on the same number of cores. This work presents the first response-time analysis for non-preemptive moldable gang tasks. Our analysis is based on the notion of schedule abstraction; a new approach for response-time analysis with the promise of high accuracy. Our experiments on periodic rigid gang tasks show that our analysis is 4.9 times more successful in identifying schedulable tasks than the existing utilization-based test for rigid gang tasks.

Real-time systems require the formal guarantee of timing-constraints, not only for the individual tasks but also for the data-propagation paths. A cause-effect chain describes the data flow among multiple tasks, e.g., from sensors to actuators, independent from the priority order of the tasks. In this paper, we provide an end-to-end timing-analysis for cause-effect chains on asynchronized distributed systems with periodic task activations, considering the maximum reaction time (duration of data processing) and the maximum data age (worst-case data freshness). On one local electronic control unit (ECU), we present how to compute the exact local (worst-case) end-to-end latencies when the execution time of the periodic tasks is fixed. We further extend our analysis to globally asynchronized systems by combining the local results. Throughout synthesized data based on an automotive benchmark as well as on randomized parameters, we show that our analytical results improve the state-of-the-art for periodic task activations.

Multiprocessor resource synchronization and locking protocols are of great importance to utilize the computation power of multiprocessor real-time systems. Hence, in the past decades a large number of protocols have been developed and analyzed. The recently proposed dependency graph approach has significantly improved the schedulability for frame-based and periodic real-time task systems. However, the dependency graph approach only supports non-nested resource access, i.e., each critical section can only access one shared resource. In this paper, we develop a dependency graph based protocol that allows nested resource access, where a critical section can access multiple shared resources at the same time. First, constraint programming is applied to construct a dependency graph that determines the execution order of critical sections. Afterwards, a schedule is generated based on this order. To show the feasibility of our proposed protocol, we provide extensive numerical evaluations under different configurations. The evaluation results show that our approach has very good performance with respect to schedulability for frame-based and periodic real-time task systems, whereas the existing results applicable for sporadic task systems have worse performance under such a limited setting.

In real-time scheduling theory, self-suspension describes the behavior that a job can suspend itself from the ready state and thus be exempted from the scheduling for the suspension duration. This behavior makes it non-trivial to resort to established concepts such as the busy-interval analysis to self-suspending task sets which is required to analyze the worst-case response time of tasks with backlog, e.g., arbitrary-deadline task sets. In this paper, we present a novel suspension-aware busy-interval analysis for dynamic self-suspension tasks where the inter-arrival time of subsequent jobs can be bounded by an arrival curve. Based on the general analysis, we provide worst-case response time analyses and hence sufficient schedulability tests for fixed-priority preemptive uniprocessor scheduling algorithms for arrival-curve constrained and sporadic self-suspension task systems with arbitrary deadlines. Moreover, we provide evaluations based on synthetically generated task sets that show that our method indeed exploits the optimism that is introduced when enlarging the relative deadline of tasks. We demonstrate that our approach improves the state of the art by considering arrival curves that are obtained from tasks with release jitter.

Cyber-physical systems (CPS) increasingly use multicore processors in order to satisfy power and computational requirements. To exploit the architectural parallelism offered by the multicore processors, parallel task models and appropriate scheduling algorithms have to be provided. Directed-acyclic graphs (DAGs) are prominent models to express parallelism and precedence constraints. In classic real-time systems, all tasks have to comply with strict timing constraints, which however result in resource underutilization due to pessimistic assumptions. Applications in CPS that have traditionally been considered as hard real-time such as control algorithms have demonstrated inherent robustness that can tolerate occasional deadline misses. In this paper, we propose a hierarchical scheduling algorithm and probabilistic response-time analyses for probabilistic conditional DAG tasks that allow to guarantee a bounded probability for k consecutive deadline misses without enforcing late jobs to be immediately aborted.

Inter-core communication is a central challenge in many-core systems for which Network-on-chips (NoCs) have been demonstrated to scale well and to provide good overall performance. However, not only the distributed structure but also the link switching of NoCs have imposed a great challenge in the design and analysis for real-time systems where timing verification is mandatory. NoC protocols like worm-hole switching are designed with scalability and flexibility in mind, thus the existing link switching protocols usually consider each single link to be scheduled independently. The flexibility of such link-based arbitrations allows each packet to be distributed over multiple switches but also increases the number of possible link states (the number of flits in a buffer) that have to be considered in the worst-case timing analysis for real-time systems. To achieve timing predictability by design, we propose a family of less flexible switching protocols, called Simultaneous Progressing Switching Protocols (SP2), in which the links used by a flow either all simultaneously transmit one flit (if it exists) of this flow or none of them transmits any flit of this flow. Based on the all-or-nothing property of Sp2, we reduce the schedulability of the NoC to the uniprocessor self-suspension scheduling problem. Moreover, the proposed approach is not limited to any specific underlying routing protocols, which are usually constructed for deadlock avoidance instead of timing predictability.

In soft real-time systems, applications can tolerate rare deadline misses. Therefore, probabilistic arguments and analyses are applicable in the timing analyses for this class of systems, as demonstrated in many existing researches. Convolution-based analyses allow to derive tight deadline-miss probabilities, but suffer from a high time complexity. Among the analytical approaches, which result in a significantly faster runtime than the convolution-based approaches, the Chernoff bounds provide the tightest results. In this paper, we show that calculating the deadline-miss probability using Chernoff bounds can be solved by considering an equivalent convex optimization problem. This allows us to, on the one hand, decrease the runtime of the Chernoff bounds while, on the other hand, ensure a tighter approximation since a larger variable space can be searched more efficiently, i.e., by using binary search techniques over a larger area instead of a sequential search over a smaller area. We evaluate this approach considering synthesized task sets. Our approach is shown to be computationally efficient for large task systems, whilst experimentally suggesting reasonable approximation quality compared to an exact analysis.

When considering recurrent real-time tasks in multiprocessor systems, access to shared resources, via so-called critical sections, can jeopardize the schedulability of the system. The reason is that resource access is mutual exclusive and a task must finish its execution of the critical section before another task can access the same resource. Therefore, the problem of multiprocessor synchronization has been extensively studied since the 1990s, and a large number of multiprocessor resource sharing protocols have been developed and analyzed. Most protocols assume work-conserving scheduling algorithms which make it impossible to schedule task sets where a critical section of one task is longer than the relative deadline of another task that accesses the same resource. The only known exception to the work-conserving paradigm is the recently presented Dependency Graph Approach where the order in which tasks access a shared resource is not determined online, but based on a pre-computed dependency graph. Since the initial work only considers frame-based task systems, this paper extends the Dependency Graph Approach to periodic task systems. We point out the connection to the uniprocessor non-preemptive scheduling problem and exploit the related algorithms to construct dependency graphs for each resource. To schedule the derived dependency graphs, List scheduling is combined with an earliest-deadline-first heuristic. We evaluated the performance considering synthesized task sets under different configurations, where a significant improvement of the acceptance ratio compared to other resource sharing protocols is observed. Furthermore, to show the applicability in real-world systems, we detail the implementation in LITMUSRTand report the resulting scheduling overheads.

Effectively handling precedence constraints and resource synchronization is a challenging problem in the era of multiprocessor systems even with massively parallel computation power. One common approach is to apply list scheduling to a given task graph with precedence constraints. However, in some application scenarios, such as the OpenMP task model and multiprocessor partitioned scheduling for resource synchronization using binary semaphores, several operations can be forced to be tied to the same processor, which invalidates the list scheduling. This paper studies a special case of this challenging scheduling problem, where a task comprised of (at most) three subtasks is executed sequentially on the same processor and the second subtasks of the tasks may have sequential dependencies, e.g., due to synchronization. We demonstrate the limits of existing algorithms and provide effective heuristics considering preemptive execution. The evaluation results show a significant improvement, compared to the existing multiprocessor partitioned scheduling strategies.

The sporadic task model is often used to analyze recurrent execution of tasks in real-time systems. A sporadic task defines an infinite sequence of task instances, also called jobs, that arrive under the minimum inter-arrival time constraint. To ensure the system safety, timeliness has to be guaranteed in addition to functional correctness, i.e., all jobs of all tasks have to be finished before the job deadlines. We focus on analyzing arbitrary-deadline task sets on a homogeneous (identical) multiprocessor system under any given global fixed-priority scheduling approach and provide a series of schedulability tests with different tradeoffs between their time complexity and their accuracy. Under the arbitrary-deadline setting, the relative deadline of a task can be longer than the minimum inter-arrival time of the jobs of the task. We show that global deadline-monotonic (DM) scheduling has a speedup bound of 3-1/M against any optimal scheduling algorithms, where M is the number of identical processors, and prove that this bound is asymptotically tight.

Over the years, many multiprocessor locking protocols have been designed and analyzed. However, the performance of these protocols highly depends on how the tasks are partitioned and prioritized, and how the resources are shared locally and globally. This paper answers a few fundamental questions when real-time tasks share resources in multiprocessor systems. We explore the fundamental difficulty of the multiprocessor synchronization problem and show that a very simplified version of this problem is NP-hard in the strong sense regardless of the number of processors and the underlying scheduling paradigm. Therefore, the allowance of preemption or migration does not reduce the computational complexity. On the positive side, we develop a dependency-graph approach that is specifically useful for frame-based real-time tasks, i.e., when all tasks have the same period and release their jobs always at the same time. We present a series of algorithms with speedup factors between 2 and 3 under semi-partitioned scheduling. We further explore methodologies for and tradeoffs between preemptive and non-preemptive scheduling algorithms, and partitioned and semi-partitioned scheduling algorithms. Our approach is extended to periodic tasks under certain conditions.

Multicore systems are increasingly utilized in real-time systems in order to address the high computational demands. To fully exploit the advantages of multicore processing, possible intra-task parallelism modeled as a directed acyclic graph (DAG) must be utilized efficiently. This paper considers the scheduling problem for parallel real-time tasks with constrained and arbitrary deadlines. In contrast to prior work in this area, it generalizes federated scheduling and proposes a novel reservation-based approach. Namely, we propose a reservation-based federated scheduling strategy that reduces the problem of scheduling arbitrary-deadline DAG task sets to the problem of scheduling arbitrary-deadline sequential task sets by allocating reservation servers. We provide the general reservation design for sporadic parallel tasks, such that any scheduling algorithm and analysis for sequential tasks with arbitrary deadlines can be used to execute the allocated reservation servers of parallel tasks. Moreover, the proposed reservation-based federated scheduling algorithms provide constant speedup factors with respect to any optimal scheduler for arbitrary-deadline DAG task sets. We demonstrate via numerical and empirical experiments that our algorithms are competitive with the state of the art.