Sensor fusion algorithms combine data from multiple sensors to produce more accurate and reliable results. However, temporal misalignment between sensors, caused by factors such as clock drift, jitter or networking delays, can significantly degrade fusion quality. Prior work on modeling temporal misalignment in sensor fusion algorithms assumes that in the ideal case all samples should be aligned with the same reference time point. We show that this assumption limits its applicability when samples are intentionally taken at different time points, e.g., when a single sensor is sampled multiple times or when sensors operate at different frequencies. In this paper, we introduce alignment sets, which allow system designers to explicitly specify the intended alignment between samples. This flexibility enables more precise temporal misalignment measures that better reflect the actual requirements of sensor fusion scenarios. We prove that alignment sets generalize the prior definitions of temporal misalignment of sensor fusion algorithms. We also provide an evaluation on a camera-LiDAR fusion pipeline for 3D object detection, showing that alignment sets provide more accurate misalignment measures and robustness estimates.

Cyber-physical systems typically have non-functional tasks to infrequently take care of some hardware and software components for maintaining correct functionality. For example, infrequently, sensors must be calibrated and endurance-limited memories must be wear-leveled. We study how a real-time system, consisting of care-taking tasks and sporadic real-time tasks, can be optimized and analyzed. We introduce a novel model to describe such systems and show how to intuitively utilize existing real-time scheduling theory to guarantee timeliness in this scenario. This is, however, very pessimistic since the care-taking tasks are executed infrequently, compared to the sporadic tasks utilizing the same components. We, therefore, examine how to properly handle care-taking tasks by controlling when to release them to avoid unnecessary interference spikes by proposing a low-overhead care-taking-task releaser. We demonstrate the improvements of schedulability using synthetic benchmarks, supported by an implementation for the proposed care-taking-task releaser in FreeRTOS and a case study for non-volatile memory.

Ensuring predictable and deterministic behavior in distributed cyber-physical systems (CPS) is essential for guaranteeing safety, reliability, and real-time behavior. However, achieving this predictability is challenging due to network uncertainties, asynchronous execution, and complex timing interactions.

In the context of automotive systems, the end-toend latency of a sequence of tasks (a so-called cause-effect chain) is a common metric to ensure correct timing behavior. To control the end-to-end latency, proper task configuration is crucial. While the literature considers the configuration of task periods, optimization of task phases to minimize the end-to-end latency is only sparsely discussed. In this work, we examine the configuration of task phases to optimize the end-to-end latency of a cause-effect chain that communicates under the Logical Execution Time (LET) paradigm. To that end, we develop a strategy for cause-effect chains with harmonic or semi-harmonic periods, which are very common in industrial applications. We prove that our strategy is optimal in the sense that it minimizes the end-to-end latency. Furthermore, our evaluation based on a real-world use-case and on synthetic automotive benchmarks shows that optimizing task phases can reduce end-to-end latencies significantly. Our approach takes at most$49 \mu ~\mathrm{s}$to find the optimal phasing and compute the end-toend latency for cause-effect chains with 50 tasks, reducing the end-to-end latency by 28 % in median.

Self-suspension behavior happens when a job has to wait for some activity to complete and results in substantial schedulability degradation in real-time systems. Despite extensive studies for self-suspending real-time task systems, the state of the art has barely addressed the optimality of the scheduling algorithms, especially for tasks with dynamic self-suspension. In this paper, we explore optimal priority assignment for periodic real-time tasks with dynamic self-suspension under Task-level Fixed-Priority (T-FP) scheduling. To that end, we provide exact schedulability tests for frame-based and synchronous harmonic tasks. We show that the Suspension-Aware Deadline-Monotonic (SADM) priority assignment is an optimal fixed-priority scheduler for many scenarios. Further, for cases where SADM is not optimal, we adopt Audsley's Optimal Priority Assignment (OPA) approach to derive an optimal fixedpriority assignment. Evaluation results show that the exact tests outperform state-of-the-art schedulability tests from the literature, and that optimal priority assignments significantly improve schedulability over classical priority assignments.

The Robot Operating System 2 (ROS 2) is a widely used middleware that provides software libraries and tools for developing robotic systems. In these systems, tasks are scheduled by ROS 2 executors. Since the scheduling behavior of the default ROS 2 executor is inherently different from classical real-time scheduling theory, dedicated analyses or alternative executors requiring substantial changes to ROS 2 have been developed. In 2023, the events executor was introduced into ROS 2. It features an events queue and allows the possibility to make scheduling decisions immediately after a job is completed. In this paper, we show that with minor modifications of the events executor, a large body of research results from classical real-time scheduling theory becomes directly applicable to ROS 2. This enables analytical bounds on the worst-case response time and the end-to-end latency, outperforming bounds for the default ROS 2 executor in many scenarios. Our solution is easy to integrate into existing ROS 2 systems since it requires only minor modifications of the events executor, which is natively included in ROS 2. The evaluation results show that our ROS 2 events executor with minor modifications can have significant improvement in terms of dropped jobs, worst-case response time, end-to-end latency, and performance compared to the default ROS 2 executor.

While preemptive Earliest-Deadline-First (EDF) has been studied extensively in real-time systems, there are only few results when considering tasks with dynamic self-suspension behavior scheduled under EDF. Furthermore, all schedulability tests that have been developed in this context are based on analyzing specific intervals, hindering the performance of the analytical tightness of the result. In this work, we develop a schedulability test for EDF, built on a dynamic interval extension. That is, whenever the analysis cannot derive a decision to conclude the schedulability test, we iteratively extend the analysis interval to include additional carry-in jobs into the analysis. This is achieved by specifying execution-exceedance requirement for infeasibility of the system, i.e., by specifying how much workload must be accumulated within a certain time interval to achieve a deadline miss. Our approach outperforms all previous analyses and is the first to surpass the schedulability guarantees that can be provided for Deadline-Monotonic (DM) scheduling for dynamic self-suspending tasks, hence achieving a milestone in the analysis of EDF scheduling.

In many applications of cyber-physical systems, a sequence of tasks is necessary to perform a certain functionality. For example, from a sensor to an actuator, the first task reads the sensor value (cause), the second task processes the data, and the third task produces an output for the actuator (an effect is triggered). For such scenarios, the end-to-end timing properties (the so-called end-to-end latency) of the sequence of tasks (the so-called cause-effect chain) are of importance. This tutorial recaps different metrics for the end-to-end latency of cause-effect chains, and summarizes fundamental properties and existing analytical results in a systematic manner. To that end, this tutorial has a special focus on the reaction time (how fast can a reaction be in the worst case) and the data age (how old is the data source of an actuation in the worst case). The goal of this tutorial is to provide a systematic view of the fundamental end-to-end timing properties of cause-effect chains and offer an outlook of possible research directions in the near future. Furthermore, we extend the proof of one fundamental property in the literature to comply with the current state-of-the-art definition of end-to-end latencies.

We introduce and study transfer schedulability , a novel concept that describes how properties of a reference schedule derived from a scheduling algorithm \(\mathcal {A}\) are transferred onto another scheduling algorithm \(\mathcal {B}\) for a given task system and fixed arrival times. Specifically, we say schedulability is transferred from \(\mathcal {A}\) to \(\mathcal {B}\) if the task set is schedulable under \(\mathcal {B}\) whenever all deadlines are met in the reference schedule produced by \(\mathcal {A}\) . We identify a sufficient criterion for schedulability to be transferred on uniprocessor systems, which we verify with the Rocq proof assistant, and based on this criterion develop runtime mechanisms that enforce transfer schedulability. We relate transfer schedulability to prior approaches from the literature and demonstrate how the concept can be utilized to avoid timing anomalies and lower runtime scheduling overheads. We demonstrate that transfer schedulability can be utilized to prevent timing anomalies for non-preemptive scheduling, self-suspending tasks, and directed acyclic graph (DAG) tasks where the edges induce delays. Our evaluation on synthesized task sets shows improved schedulability compared to standard scheduling algorithms. We also evaluated the number of interventions necessary to transfer schedulability, and additionally demonstrate that the proposed runtime mechanisms eliminate timing anomalies (like a completely static, fully table-driven approach) while achieving a response-time distribution closely resembling those of classic dynamic, event-driven schedulers like EDF.

Sensor fusion is the process of combining data from multiple sensors for acquiring a more accurate and comprehensive understanding of the observed environment. However, temporal misalignments between sensors can lead to incorrect fusion results, while the temporal robustness of sensor fusion algorithms is still a relatively unexplored research topic. To address this gap, we define three types of temporal robustness for sensor fusion: reference-point-based, strong sample-point-based, and weak sample-point-based temporal robustness. These definitions provide a framework to quantitatively evaluate the temporal robustness of sensor fusion functions. We also investigate the case where only a part of the sensors are misaligned. Furthermore, we consider potential probabilistic aspects for the proposed definitions. We assess the temporal robustness of a state-of-the-art fusion method in the context of 3D object detection, where camera and LiDAR data are fused. Our empirical evaluation shows that the examined fusion methods exhibit moderate robustness against temporal misalignment of images, but are especially sensitive to LiDAR misalignment. Our findings call attention to the necessity of providing robustness guarantees for sensor fusion functions against temporal misalignment.

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.

Modern robot systems, like autonomous vehicles, are complex, distributed systems that consist of many interacting components. End-to-end timing latency guarantees are key properties of such systems. They upper bound the data processing time and provide a predictable timing behavior. The Robot Operating System 2 (ROS 2) is a widely used and highly configurable set of software libraries for creating and deploying robot systems. It features a custom scheduler to execute time-triggered and event-triggered tasks and uses Data Distribution Services (DDS) for the communication between different system components. The data propagations between ROS 2 system components form cause-effect chains, which can be analyzed to determine the maximum reaction time (longest time between occurrence of an external cause and the earliest time when this external cause is fully processed) and maximum data age (longest time between the moment of a sensor measurement and the latest moment where an effect is based on this sensor measurement). In this paper, we provide an analysis of the end-to-end latencies in multi-executor ROS 2 systems to upper bound the end-to-end latencies of cause-effect chains in ROS 2 systems. Furthermore, we introduce an optimization using constrained programming that determines the optimal system configuration to minimize the end-to-end latencies for ROS 2 systems. We evaluate our upper-bound analysis to determine the end-to-end latencies of cause-effect chains in an autonomous driving-software stack for oval racing used in the Indy Autonomous Challenge and apply our optimization method to reduce the end-to-end latency upper bound, measured maximum, and measured mean by up to 50.2 %, 19.8 %, and 7.2 %, respectively.

Real-time tasks often exhibit correlated execution-time distributions due to common factors such as shared caches, resources, and inputs. Yet state-of-the-art probabilistic analysis still overlooks the impact of correlation, a gap that has been highlighted as a major open problem in the field. This paper responds to the open problem with the first correlation-aware analysis (CAA) of periodic tasks with stochastic execution times. The proposed analysis, which derives response-time distributions to infer upper bounds on deadline-failure probabilities, applies to a novel task model that incorporates information about both intra- and inter-task dependencies. In addition, the paper shows how to statistically infer the two model parameters using confidence intervals obtained via nonparametric bootstrapping. Notably, the inference method described is distribution-agnostic, meaning that it does not assume any particular probability distribution a priori, thereby eliminating a major risk of misclassifying the ground-truth execution behavior. By design, CAA dominates state-of-the-art correlation-tolerant analysis (CTA). The significantly better accuracy of CAA is demonstrated via experiments with synthetically generated workloads, while a case study based on the WATERS’ 17 industrial challenge provides a proof-of-concept of the statistical inference method.

Heterogeneous computing platforms running highly parallelized applications are becoming increasingly common in real-time embedded systems. This demands for expressive task models that can capture parallelism, precedence constraints and self-suspending behavior caused by work-offloading on coprocessors, access to shared resources or synchronization between tasks running on different (heterogeneous) cores. The Event-Driven Delay-induced (EDD) task model was specifically designed to address these needs. Yet, to date, a single schedulability test for the EDD task model exists, and that test is limited to the analysis of fully-preemptive partitioned scheduling.In this work, we provide the first worst-case response time analysis for limited-preemptive EDD tasks that are globally scheduled on a multicore platform. Moreover, our evaluation results show that our analysis also outperforms the state-of-the-art response time analyses for both limited-preemptive DAG tasks and self-suspending tasks.

The robot operating system 2 (ROS 2) is a widely used collection of tools and libraries for building robot applications. It is designed to be flexible and easy to use when creating complex robot systems with many interacting components.Since its alpha version release in 2015, ROS 2 provides two options in a multithreading operating system, namely the single-threaded executor and the multithreaded executor. The single-threaded executor is starvation-free by design (i.e., every task is eventually executed) even in over-utilized systems, since the set of eligible task instances (called wait set) is only refilled once all the task instances in the wait set are executed. The multithreaded executor extends this mechanism to multiple threads that manage the wait set collaboratively. While intuitively this extension preserves the starvation-free property, and analyses for the multithreaded executor even build upon this assumption, the multithreaded executor has not been shown to be starvation-free.In this work, we examine the mechanism of the multithreaded executor in ROS 2 and demonstrate that it is prone to starvation, i.e., some tasks may never be executed even in under-utilized systems. This indicates risks for multithreaded executors in the current ROS 2 design and further leads to counterexamples to the state-of-the-art response-time analyses by Jiang et al. (RTSS 2022) and Sobhani et al. (RTAS 2023). We propose a minimal change in the software architecture of the ROS 2 multithreaded executor to enable starvation- and deadlock-free behavior. We empirically test that we prevent starvation in concrete ROS 2 system configurations, and show that our solution incurs a negligible overhead using the autoware reference benchmark. Moreover, we prove that our solution is starvation- and deadlock-free using formal proofs and model checking.

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.

Timing guarantee is an important aspect and must be ensured for every individual task in real-time systems. Even for periodic tasks, providing timing guarantees for segmented self-suspending tasks is challenging due to timing anomalies, i.e., the reduction of execution or suspension time of some jobs enlarges the response time of another job. The existing worstcase response time analyses for sporadic self-suspending tasks are only over-approximations and lead to overly pessimistic results. In this paper, we focus on eliminating timing anomalies without negative impacts on the worst-case response time (WCRT) analysis when scheduling periodic tasks with segmented selfsuspension behavior. We propose two treatments, segment release time enforcement and segmentpriority modification, and prove that both treatments eliminate timing anomalies. In our evaluation, the proposed treatments achieve higher acceptance ratios in terms of schedulability compared to state-of-the-art scheduling algorithms. We also implement the segment-level fixed-priority scheduling mechanism on RTEMS, and showcase the validity of the treatment segment priority modification.

Self-suspension introduces further complexity in the scheduling of real-time tasks. As a result, the proofs of optimality for the typical Earliest-Deadline-First (EDF) and Deadline-Monotonic (DM) scheduling do not hold. The EDF-Like scheduling algorithms allows to optimize the scheduling algorithm by setting relative priority points. In this work, we show that a tuning process of the relative priority points leads to significantly better (analytical) schedulability guarantees. Moreover, we discuss open problems and alternative approaches.

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 soft real-time systems, tasks may occasionally miss their deadlines. This possibility has triggered research on probabilistic timing analysis for the execution time of a single program and probabilistic response time analysis of concurrently executed tasks. Under fixed-priority preemptive uniprocessor scheduling, it was shown that the classical critical instant theorem (for deriving the worst-case schedulability or response time) by Liu and Layland (in JACM 1973) can be applied to analyze the worst-case deadline failure probability (WCDFP) and the worst-case response time exceedance probability (WCRTEP). In this work, we present a counterexample for this result, showing that the WCDFP and WCRTEP derived by the classical critical instant theorem is unsound. We further provide two sound methods: one is to account for one additional carry-in job of a higher-priority task and another is to sample and inflate the execution time of certain jobs without adding one additional carry-in job. We show that these two methods do not dominate each other and, in the evaluation, apply them to two well-known approaches based on direct convolution and Chernoff bounds.

In real-time systems, schedulability analyses provide the required timing guarantees. However, current suspension-aware analyses are limited to Task-Level Fixed-Priority (TFP) scheduling or Earliest-Deadline-First (EDF) scheduling of constrained-deadline self-suspending task systems. In this work, we provide a unifying schedulability analysis for uniprocessor Global EDF-Like (GEL) schedulers of arbitrary-deadline task sets. While analyses for EDF-Like schedulers are rare, many widely used scheduling algorithms can be considered as EDF-Like, for example, EDF, First-In-First-Out (FIFO), Earliest-Quasi-Deadline-First (EQDF), and Suspension-Aware EDF (SAEDF). Therefore, the provided analysis is applicable to those algorithms. It can be applied to TFP scheduling as well. Our analysis is the first suspension-aware schedulability analysis for arbitrary-deadline sporadic real-time task systems under Job-Level Fixed-Priority (JFP) scheduling, such as EDF, and the first unifying suspension-aware schedulability analysis framework that covers a wide range of scheduling algorithms. Through numerical simulations, we show that our analysis improves the state of the art for constrained-deadline EDF scenarios.

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.

To overcome the memory wall in neural network (NN) inference systems, recent studies have proposed to use approximate memory, in which the supply voltage and access latency parameters are tuned, for lower energy consumption and faster access at the cost of reliability. To tolerate the occuring bit errors, the state-of-the-art approaches apply bit flip injections to the NNs during training, which require high overheads and do not scale well for large NNs and high bit error rates. In this work, we focus on binarized NNs (BNNs), whose simpler structure allows better exploration of bit error tolerance metrics based on margins. We provide formal proofs to quantify the maximum number of bit flips that can be tolerated. With the proposed margin-based metrics and the well-known hinge loss for maximum margin classification in support vector machines (SVMs), we are able to construct a modified hinge loss (MHL) to train BNNs for bit error tolerance without any bit flip injections. Our experimental results indicate that the MHL enables the possibility for BNNs to tolerate higher bit error rates than with bit flip training and, therefore, allows to further lower the requirements on approximate memories used for BNNs.

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.

Numerical simulations often play an important role when evaluating and comparing the performance of schedulability tests, as they allow to empirically demonstrate their applicability using synthesized task sets under various configurations. In order to provide a fair comparison of various schedulability tests, von der Brüggen et al. presented the first version of an evaluation framework for self-suspending task sets. In this work-in-progress, we further enhance the framework by providing more features to ease the use, e.g., Python 3 support, an improved GUI, multiprocessing, Gurobi optimization, and external task evaluation. In addition, we integrate the state-of-the-arts we are aware of into the framework. Moreover, the documentation is improved significantly to simplify the application in further research and development. To the best of our knowledge, the framework contains all suspension-aware schedulability tests for uniprocessor systems and we aim to keep it up-to-date.

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.

Abstract This paper provides counterexamples for the slack enforcement mechanisms to handle segmented self-suspending real-time tasks by Lakshmanan and Rajkumar (Proceedings of the Real-Time and Embedded Technology and Applications Symposium (RTAS), pp 3–12, 2010).

Dynamic power management (DPM) reduces the power consumption of a computing system when it idles, by switching the system into a low power state for hibernation. When all processors in the system share the same component, e.g., a shared memory, powering off this component during hibernation is only possible when all processors idle at the same time. For a real-time system, the schedulability property has to be guaranteed on every processor, especially if idle intervals are considered to be actively introduced. In this work, we consider real-time systems with hybrid shared-memory architectures, which consist of shared volatile memory (VM) and non-volatile memory (NVM). Energy-efficient execution is achieved by applying DPM to turn off all memories during the hibernation mode. Towards this, we first explore the hybrid memory architectures and suggest a task model, which features configurable hibernation overheads. We propose a multi-processor procrastination algorithm (HEART), based on partitioned earliest-deadline-first (pEDF) scheduling. Our algorithm facilitates reducing the energy consumption by actively enlarging the hibernation time. It enforces all processors to idle simultaneously without violating the schedulability condition, such that the system can enter the hibernation state, where shared memories are turned off. Throughout extensive evaluation of HEART, we demonstrate (1) the increase in potential hibernation time, respectively the decrease in energy consumption, and (2) that our algorithm is not only more general but also has better performance than the state of the art with respect to energy efficiency in most cases.

Self-suspension behavior has been demonstrated to appear in complex cyber-physical real-time systems, e.g., multiprocessor locking protocols, computation offloading, and multicore resource sharing, as demonstrated in (Chen et al. ( 2019 ), Section 2). Although the impact of self-suspension behavior has been investigated since 1990, the literature of this research topic has been flawed as reported in the review by Chen et al. ( 2019 ).

While the earliest-deadline-first (EDF) scheduling algorithm has extensively been utilized in real-time systems, there is almost no literature considering EDF for task sets with dynamic self-suspension behavior. To be precise, there is no specialized result for uniprocessor systems, besides the trivial suspension-oblivious approach. The work by Liu and Anderson (in ECRTS 2013) and Dong and Liu (in RTSS 2016) for suspension-aware multiprocessor global EDF can also be applied to uniprocessor systems and therefore be considered the state-of-the-art. In this work, two novel schedulability analyses (one for sporadic and one for periodic task sets) for suspension-aware EDF on uniprocessor systems are proposed, which outperform the state-of-the-art on such systems in empirical and theoretical comparison. We further show that the analysis by Dong and Liu is in fact not suspension-aware for uniprocessor systems.