11 September 2018 in Real-Time Systems
In general computing systems, a job (process/task) may suspend itself whilst it is waiting for some activity to complete, e.g., an accelerator to return data. In real-time systems, such self-suspension can cause substantial performance/schedulability degradation. This observation, first made in 1988, has led to the investigation of the impact of self-suspension on timing predictability, and many relevant results have been published since. Unfortunately, as it has recently come to light, a number of the existing results are flawed. To provide a correct platform on which future research can be built, this paper reviews the state of the art in the design and analysis of scheduling algorithms and schedulability tests for self-suspending tasks in real-time systems. We provide (1) a systematic description of how self-suspending tasks can be handled in both soft and hard real-time systems; (2) an explanation of the existing misconceptions and their potential remedies; (3) an assessment of the influence of such flawed analyses on partitioned multiprocessor fixed-priority scheduling when tasks synchronize access to shared resources; and (4) a discussion of the computational complexity of analyses for different self-suspension task models.
7 October 2019 in ACM Transactions on Embedded Computing Systems
A cause-effect chain is used to define the logical order of data dependent tasks, which is independent from the execution order of the jobs of the (periodic/sporadic) tasks. Analyzing the worst-case End-to-End timing behavior, associated to a cause-effect chain, is an important problem in embedded control systems. For example, the detailed timing properties of modern automotive systems are specified in the AUTOSAR Timing Extensions. In this paper, we present a formal End-to-End timing analysis for distributed systems. We consider the two most important End-to-End timing semantics, i.e., the button-to-action delay (termed as the maximum reaction time ) and the worst-case data freshness (termed as the maximum data age ). Our contribution is significant due to the consideration of the sporadic behavior of job activations, whilst the results in the literature have been mostly limited to periodic activations. The proof strategy shows the (previously unexplored) connection between the reaction time (data age, respectively) and immediate forward (backward, respectively) job chains. Our analytical results dominate the state of the art for sporadic task activations in distributed systems and the evaluations show a clear improvement for synthesized task systems as well as for a real world automotive benchmark setting.
24 July 2023 in ACM Transactions on Embedded Computing Systems
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.
25 May 2023 in IEEE Transactions on Computers
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.
2 October 2020 in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
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.
6 November 2024 in IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems
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.