As ROS 2 becomes increasingly adopted in safety-critical real-time systems, the performance of its communication layer, especially inter-process communication (IPC), has emerged as a key bottleneck. While intra-process communication benefits from zero-copy transmission, IPC suffers from significant latency due to serialization and memory copying. Existing shared memory approaches offer limited support for ROS 2 applications, as they impose strict constraints on message formats (e.g., requiring statically sized, POD-compatible types) and overlook end-to-end communication across multi-stage pipelines. In this work, we propose a novel and flexible architecture for enabling zero-copy IPC in ROS 2. Our design supports dynamically structured and non-POD message types, integrates seamlessly with the existing communication framework, and requires no modification to application logic. It consists of a Mini Memory Management System (MMS) for shared memory handling and a Message Propagation Adapter (MPA) that ensures compatibility with the ROS 2 communication framework. Our experimental results show that our method significantly reduces communication latency and supports efficient end-to-end message propagation.

Controller area networks (CANs) are widely adopted in real-time automotive control and are increasingly standard in factory automation. Considering their critical application in safety-critical systems, The error rate of the system must be accurately predicted and guaranteed. Through simulation, it is possible to obtain a low-precision overview of the system’s behavior. However, for low-probability events, the required number of samples in simulation increases rapidly, making it difficult to conduct a sufficient number of simulations in practical applications, and the statistical results may deviate from the actual outcomes. Therefore, a formal analysis is needed to evaluate the error rate of the system. This article improves the worst case probability response time analysis by using convolution-based busy window and backlog techniques under the error retransmission protocol of CANs. Empirical analysis shows that the proposed method improves upon existing methods in terms of accuracy and efficiency.

Tridiagonalization, which is a key step in symmetric eigenvalue decomposition (EVD), aims to convert a symmetric matrix to a tridiagonal form. In Nvidia's cuSOLVER library, the FP64 precision tridiagonalization process only reach 2.1 TFLOPs out of 67 TFLOPs on H100 GPU, and it consumes a significant portion of the elapsed time in the entire EVD process, accounting for over 97%. Thus, improving the tridiagonalization performance is crucial on accelerating EVD. In this paper, we analyze the reasons behind the suboptimal performance of tridiagonalization on GPU architectures, and we propose a new double blocking band reduction algorithm along with an implementation of GPU-based bulge chasing to improve the tridiagonalization performance. Through experimental evaluation, the proposed FP64 precision tridiagonalization method yields up to 19.6 TFLOPs which is 9.3x and 5.2x faster compared cuSOVLER and MAGMA, respectively.

As modern real-time systems become more complex, traditional deterministic analysis techniques often cannot accurately capture the system characteristics and offer meaningful design guidance. In contrast, probabilistic analysis is usually more practical and provides superior design insight while ensuring timing correctness with the required level of confidence. Earliest Deadline First (EDF) is one of the most widely used real-time scheduling algorithms. Although previous research has proposed a worst-case deadline failure probability (WCDFP) analysis for EDF, such an analysis tends to be overly pessimistic. Meanwhile, we observe that any analytical approach has inherent limitations, indicating that further reductions in WCDFP cannot be achieved solely through improved the analysis. In response to the first issue, this paper proposes a new technique to improve the accuracy of the WCDFP analysis. For the second issue, we enhance EDF by incorporating an active-dropping policy to reduce the analytical deadline failure probability. Empirical experiments demonstrate that our techniques lower the job failure probability in most tested scenarios, with especially significant improvements for task sets with high utilization.

The Robot Operating System 2 (ROS 2) has become a widely adopted middleware framework for building modular and distributed robotic systems. Its intra-process communication mechanism is designed to reduce latency by avoiding serialization and memory copying, which is often treated as a negligible or constant-cost operation in both system design and performance analysis. However, this assumption oversimplifies the underlying behavior and may lead to inaccurate performance models and misleading conclusions, especially in latency-sensitive applications. In this paper, we present a comprehensive analysis of intraprocess communication in ROS 2, revealing that its performance is highly sensitive to message configuration, workload structure, and message usage strategies. We identify a scalability risk caused by misaligned communication configurations and propose a guideline to ensure efficient and predictable intra-process communication across varying execution patterns. In addition, we uncover a performance bottleneck in the default ROS 2 implementation stemming from repeated message creation. To address this, we propose a novel message pooling mechanism that reuses message objects to exploit temporal locality and eliminate redundant allocations. Our design is fully compatible with existing ROS 2 APIs and requires no modifications to application-level code. Experimental evaluations using synthetic benchmarks and real-world case studies demonstrate substantial improvements in communication latency, validating the practicality of our design.

Most existing research in probabilistic real-time scheduling analysis has primarily focused on systems with only stochastic execution times, neglecting the stochastic nature of task release patterns in many real-world applications. Current approaches for handling stochastic release times rely on computationally expensive convolution-based methods, which has poor scalability, especially when both execution and release times are stochastic. This paper presents novel techniques to apply the Chernoff Bound approach to the analysis of systems with both stochastic execution and release times. The key challenge lies in adapting the Chernoff Bound, which traditionally operates on a fixed number of random variables, to handle the stochastic job counts resulting from stochastic release patterns. Our main contribution is a new technique for bounding convolutions involving random numbers of random variables using Chernoff principles. Through comprehensive evaluation, we demonstrate that our approach achieves several orders of magnitude speedup compared to state-of-the-art convolution-based methods while simultaneously improving analysis precision.

The 2-stage eigenvalue decomposition (EVD) method outperforms conventional 1-stage method on GPUs and heterogeneous architectures, especially when eigenvectors are not required. However, its performance advantage diminishes when performing back transformation to obtain eigenvectors. To address this, we propose two key solutions: 1) replacing BLAS3 operations with BLAS2 operations during the bulge-chasing back transformation for better performance, and 2) reordering the back transformation workflow from a backward pattern to a new parallelism-driven pattern to hide divide-and-conquer latency, at the cost of one additional GEMM computation. Experimentally, the proposed back transformation algorithm demonstrates significant performance improvements, outperforming the SOTA implementation in MAGMA by an average factor of 3.58x. For complete FP64 precision symmetric EVD with eigenvectors, the proposed algorithm, incorporating both solutions, surpasses the SOTA implementations in MAGMA and cuSOLVER by average factors of 2.62x and 2.21x, respectively.

Real-time systems are increasingly shifting from single processors to multiprocessors, where software must be parallelized to fully exploit the additional computational power. While the scheduling of real-time parallel tasks modeled as directed acyclic graphs (DAGs) has been extensively studied in the context of global scheduling, the scheduling and analysis of real-time DAG tasks under partitioned scheduling remain far less developed compared to the traditional scheduling of sequential tasks. Existing approaches primarily target plain fixed-priority partitioned scheduling and often rely on self-suspension–based analysis, which limits opportunities for further optimization. In particular, such methods fail to fully leverage fine-grained scheduling management that could improve schedulability. In this paper, we propose a novel approach for scheduling periodic DAG tasks, in which each DAG task is transformed into a set of real-time transactions by incorporating mechanisms for enforcing release offsets and intra-task priority assignments. We further develop corresponding analysis techniques and partitioning algorithms. Through comprehensive experiments, we evaluate the real-time performance of the proposed methods against state-of-the-art scheduling and analysis techniques. The results demonstrate that our approach consistently outperforms existing methods for scheduling periodic DAG tasks across a wide range of parameter settings.

Kernels are scheduled on Graphics Processing Units (GPUs) in the granularity of GPU warp, which is a bunch of threads that must be scheduled together. When executing kernels with conditional branches, the threads within a warp may execute different branches sequentially, resulting in a considerable utilization loss and unpredictable execution time. This problem is known as the control flow divergence. In this work, we propose a novel method to predict threads' execution path before the launch of the kernel by deploying a branch prediction network on the GPU's tensor cores, which can efficiently parallel run with the kernels on CUDA cores, so that the divergence problem can be eased in a large extent with the lowest overhead. Combined with a well-designed thread data reorganization algorithm, this solution can better mitigate GPUs' control flow divergence problem.

Abstract This paper considers the real-time scheduling of a parallel task with reclaiming computing resources, which can be utilized for soft real-time tasks or switching to low-energy mode to save energy. Existing works allocate a rectangular piece of computing resources based on the worst-case characterizations of the task to guarantee the deadline, which inherently incurs severe resource wasting due to coarse-grained resource allocation. To address this resource-wasting problem, this paper proposes the ladder-like resource allocation (i.e., a series of rectangular pieces of computing resources). To characterize the ladder-like resource allocation, we present two concepts called resource distribution and allocation vector, which serve as the interfaces between hard and soft real-time tasks. For the former, we derive schedulability tests under the given two interfaces; for the latter, we discuss the methods of determining the two interfaces to reclaim computing resources. This paper is the first work to fully explore the concept of ladder-like resource allocation and its potential consequences on computing resources, soft real-time tasks, and energy. Experiments demonstrate that the proposed approach can effectively reclaim more computing resources than existing approaches while maintaining hard real-time guarantees.

ROS (Robot Operating System) is a widely used robotic software development framework. In safety-critical applications that require timing guarantees, the first generation of ROS falls short. The introduction of ROS 2 has addressed some of these limitations, but its multi-threaded executor still struggles to meet real-time requirements. To address this issue, we design a new multi-threaded executor called RTeX for ROS 2. The goal of RTeX is to improve system performance in terms of both run-time efficiency and timing predictability. We have implemented RTeX in the latest version of ROS 2 and conducted experiments on a real platform. The experimental results demonstrate that RTeX outperforms both the default ROS 2 multi-threaded executor and its state-of-the-art variant, achieving significant real-time performance improvements.

There is an increasing move towards implementing embedded real-time systems upon multiprocessors with parallel applications, which are usually modeled as Directed Acyclic Graphs (DAGs). Plentiful work has been presented to optimize the bound of Worst-Case Response Time (WCRT) since the cornerstone work proposed by Graham in 1969. However, all these works are developed on the basis of Graham’s bound and failed to tackle the root of pessimism in it. In this work, we present a novel method to optimize the WCRT bound of a DAG task by designing mutually exclusive groups so that a sequential execution is enforced for some nodes, under which the problem of bounding WCRT becomes a problem of identifying a mutually exclusive path and thus does not suffer the pessimism in Graham’s bound. Experiments are conducted to evaluate the performance of our method against other WCRT optimization approaches in the state-of-the-art.

Many real-time systems process and react to external events by a chain of tasks, and have constraints on the maximum reaction time which describes how long it takes to respond to an external event. While a processing chain typically starts with a sampling task periodically triggered to sample the sensor data, other tasks in the chain could be triggered in two different ways: event-triggered or time-triggered, which have their own pros and cons. In this paper, we propose the third option to trigger the processing tasks in a chain, namely, the event-triggered with data refreshing approach, which combines the benefits of the event-triggered or time-triggered approaches. As the main technical contribution, we develop techniques to formally upper-bound its maximum reaction time and analytically compare it with the existing approaches. Experiments with synthetic workload are conducted to show the performance improvement by our proposed techniques.

In automotive systems, an important timing requirement is that the time disparity (the maximum difference among the timestamps of all raw data produced by sensors that an output originates from) must be bounded in a certain range, so that information from different sensors can be correctly synchronized and fused. In this paper, we study the problem of analyzing the worst-case time disparity in cause-effect chains. In particular, we present two bounds, where the first one assumes all chains are independent from each other and the second one takes the fork-join structures into consideration to perform more precise analysis. Moreover, we propose a solution to cut down the worst-case time disparity for a task by designing buffers with proper sizes. Experiments are conducted to show the correctness and effectiveness of both our analysis and optimization methods.

Firmware update is an essential service on Internet-of-Things (IoT) devices to fix vulnerabilities and add new functionalities. Firmware update is energy-consuming since it involves intensive flash erase/write operations. Nowadays, IoT devices are increasingly powered by energy harvesting. As the energy output of the harvesters on IoT devices is typically tiny and unstable, a firmware update will likely experience power failures during its progress and fail to complete. This paper presents an approach to increase the success rate of firmware update on energy-harvesting IoT devices. The main idea is to first conduct a lightweight flash write with reduced erase/write time (and thus less energy consumed) to quickly save the new firmware image to flash memory before a power failure occurs. To ensure a long data retention time, a reinforcement step follows to re-write the new firmware image on the flash with default erase/write configuration when the system is not busy and has free energy. Experiments conducted with different energy scenarios show that our approach can significantly increase the success rate and the efficiency of firmware update on energy-harvesting IoT devices.

Semi-supervised deep facial expression recognition (SS-DFER) has recently attracted rising research interest due to its more practical setting of abundant unlabeled data. However, there are two main problems unconsidered in current SS-DFER methods: 1) label ambiguity, i.e., given labels mismatch with facial expressions; 2) inefficient utilization of unlabeled data with low-confidence. In this paper, we propose a novel SS-DFER method, including a Label DIsambiguation module and a PrOgressive Negative Learning module, namely LION, to simultaneously address both problems. Specifically, the label disambiguation module operates on labeled data, including data with accurate labels (clear data) and ambiguous labels (ambiguous data). It first uses clear data to calculate prototypes for all the expression classes, and then re-assign a candidate label set to all the ambiguous data. Based on the prototypes and the candidate label set, the ambiguous data can be relabeled more accurately. As for unlabeled data with low-confidence, the progressive negative learning module is developed to iteratively mine more complete complementary labels, which can guide the model to reduce the association between data and corresponding complementary labels. Experiments on three challenging datasets show that our method significantly outperforms the current state-of-the-art approaches in SS-DFER and surpasses fully-supervised baselines. Code will be available at https://github.com/NUM-7/LION.

Robot Operating System (ROS) is a prevailing software framework for robotic appliscation development. Graphics Processing Unit (GPU) is widely used in many ROS applications as a first-order computation resource. Unfortunately, ROS does not do any resource management for GPU, and different components in a ROS application directly submit their GPU workload without coordinating with each other, which may cause severe problems in both general performance and realtime capability. This paper presents ROSGM, a real-time ROS 2G PUM anagement framework. Instead of providing a fixed GPU management policy for all scenarios, ROSGM allows the addition of any management policy as a plug-in and dynamic switching among different management policies at run-time, which is helpful since GPU management policies are typically device-dependent, and different applications or the same application in different modes may need different GPU management policies. Besides, ROSGM supports dynamic task loading and unloading for integrating additional functionalities when required at run-time. We conduct experiments to evaluate ROSGM. The results show that by properly managing the GPU resource using ROSGM, we can significantly improve the performance of ROS 2 applications. The flexibility of adding management policies as plug-ins, dynamic switching of management policies, and dynamic task loading and unloading helps improve the adaptability of ROSGM.

ROS (Robot Operating System) is one of the most popular robotic software development frameworks. Robotic systems in safety-critical domains are usually subject to hard realtime constraints, so timing behaviors must be formally modeled and analyzed to guarantee that real-time constraints are always honored at run-time. Although a series of analysis techniques has been proposed to analyze the timing performance of ROS 2, the state-of-the-art still generates pessimistic results for ROS 2 systems modeled as DAG (Directed Acyclic Graph). This paper focuses on the analysis of such systems, and proposes techniques to analyze the timing performance in a more precise manner. Experiments with both randomly generated workload and a case study are conducted to evaluate and demonstrate our results.

Analysis and optimization of end-to-end latency in cause-effect chains is an important problem in real-time systems. Under task-level fixed-priority scheduling, the end-to-end latency largely relies on the relative priority of the tasks in the chain, so previous work has tried to improve the latency via priority assignment. However, the improvement of static priority assignment is limited due to the conflict between schedulability of individual tasks and end-to-end latency of the chain, i.e., a priority assignment leading to good end-to-end latency may make the task set unschedulable. This work proposes a novel method named Dynamic Priority Inheritance Protocol (DPI) to optimize the end-to-end latency of sporadic cause-effect chains. Under DPI, the propagation delay between two communicating jobs is independent of the task relative priority. So the optimization can work on any priority assignment, and no longer conflicts with task schedulability. Moreover, we propose DPI-B, a combination of DPI and a Buffer Manipulation Protocol, for cause-effect chains that also need to meet the determinism requirement. We conduct experiments with both automotive benchmarks and randomly generated workload. The results show the effectiveness of our method in comparison with the state-of-the-art.

Multi-sensor data fusion is crucial for modern autonomous systems to accurately perceive their surrounding environments and make intelligent decisions. However, as different sensor sources may have significant time disparity, it is necessary to synchronize their data before sending them to the fusion algorithm, in order to control such differences and get meaningful fusion results. This paper discusses the message synchronization policy in ROS, a popular framework for robotic systems. The ROS message synchronization policy has proven to be highly effective in reducing the time disparity, but it introduces a certain level of latency. Therefore, to use it for real-time systems, it is essential to establish an upper bound for the worst-case latency that may occur. Specifically, we analyze two key latency metrics of the ROS message synchronization policy, the passing latency and reaction latency, which are needed to analyze the end-to-end delay and reaction time on the system level. We conduct experiments under different settings to evaluate the precision of our proposed latency upper bounds against the maximum observed latency in real execution.

ROS 2, the second-generation ROS, is a popular development framework for real-time robotic software. To ensure the timing correctness of applications based on ROS 2, one must model the time delay incurred by two aspects: computation and communication. While significant work has been conducted on computing delay, formal modeling and analysis of communication delay in ROS 2 is still an open issue. In this paper, we first present a formal description on the timing behavior of inter-process communication in ROS 2 with two typical communication policies, namely the InterestTree policy and FIFO policy, and then develop analysis techniques to upper-bound the incurred delay. We conduct experiments to validate the correctness and evaluate the efficacy of our method with case studies on realistic platform.

Spin locks are widely used in embedded systems to coordinate mutually exclusive accesses to shared resources from different tasks. Although the design and analysis of locking protocols have been intensively studied forsequentialreal-time tasks, there have been few works on this topic forparallelreal-time tasks. In this paper, we study the analysis of parallel real-time tasks modeled by directed acyclic graphs (DAGs) under global fixed priority scheduling using both preemptable and non-preemptable spin locks to protect accesses to shared resources in three commonly used request serving orders (unordered, FIFO-order and priority-order). In particular, we develop a general schedulability analysis framework where the blocking time caused by resource contention is formally defined, so that the blocking analysis can be performed independently and easy to combine with the traditional interference analysis techniques. Moreover, we present a unified blocking analysis technique where the blocking time is analyzed in a scalable manner based on a linear-programming (LP) approach, making our method flexible and extendable. We conduct comprehensive experiments to evaluate our method with other the-state-of-the-art approaches for scheduling real-time parallel tasks using semaphores and spin locks.

A cause-effect chain is a sequence of multi-rate real-time tasks with data dependency. Cause-effect chains are generally subject to end-to-end timing constraints, especially in safety-critical systems. Communication paradigms greatly affect the end-to-end latency of cause-effect chains. This paper compares different communication paradigms (implicit communication, LET, DBP) with regards to the end-to-end latency of cause-effect chains using them, and proposes priority assignment strategies to optimize the end-to-end latency with specific communication paradigm. Experiments with synthesized data based on an automotive benchmark and randomly generated parameters are conducted to evaluate our results.

In many popular parallel programming models, e.g., OpenMP (OpenMP, 2013), applications are usually dispatched into several dedicated scheduling entities (named ”threads” in common) for which the processor time of physical platform is provided through the OS schedulers. This behavior requires for a hierarchical scheduling framework, considering each thread as a virtual processor (VP). Moreover, hierarchical scheduling allow separate applications to execute together on a common hardware platform, with each application having the “illusion” of executing on a dedicated component. However, the problem for scheduling parallel real-time tasks on virtual multiprocessor platform has not been addressed yet. An analogous approach to virtual scheduling for parallel real-time tasks is federeted scheudling, where each task exclusively executes on a set of dedicated physical processors. However, federated scheduling suffers significant resource wasting. In this article, we study the scheduling of real-time parallel task on virtual multiprocessors. As a physical processor is shared by virtual processors, tasks effectively share processors with each other. We conduct comprehensive performance evaluation to compare our proposed approach with existing methods of different types. Experiment results show that our approach consistently outperforms existing methods to a considerable extent under a wide range of parameter settings.

Locks are the most widely used mechanisms to coordinate simultaneous accesses to exclusive shared resources. While locking protocols and associated schedulability analysis techniques have been extensively studied for sequential real-time tasks, work for parallel tasks largely lags behind. In the limited existing work on this topic, a common assumption is that a critical section must execute sequentially. However, this is not necessarily the case with parallel programming languages. In this paper, we study the analysis of parallel heavy real-time tasks (the density of which is greater than 1) with critical sections in parallel structures. We show that applying existing analysis techniques directly could be unsafe or much pessimistic for the considered model, and develop new techniques to address these problems. Comprehensive experiments are conducted to evaluate the performance of our method.

In 1969, Graham developed a well-known response time bound for a DAG task using the total workload and the longest path of the DAG, which has been widely applied to solve many scheduling and analysis problems of DAG-based task systems. This paper presents a new response time bound for a DAG task using the total workload and the lengths of multiple long paths of the DAG, instead of the longest path in Graham's bound. Our new bound theoretically dominates and empirically outperforms Graham's bound. We further extend the proposed approach to multi-DAG task systems. Our schedulability test theoretically dominates federated scheduling and outperforms the state-of-the-art by a considerable margin.

ROS (Robot Operating System) is currently one of the most popular development frameworks for robotic software, which is usually subject to hard real-time constraints in safe-critical domains. Designers must formally model and analyze its timing behaviors to guarantee that real-time constraints are always honored at run-time. This paper studies real-time scheduling and analysis under a multi-threaded executor in ROS 2. We present a formal description of the scheduling model of multi-threaded executors, and develop response time analysis techniques for processing chains executing on it. Moreover, we identify a risk of increasing the response time of chains that may be caused by improper design when deploying systems on multi-threaded executors, which provides a useful guidance to designers. We conduct experiments with both randomly generated workloads and case studies on a realistic ROS 2 platform to evaluate and demonstrate our results.

Multi-sensor data fusion is essential in autonomous systems to support accurate perception and intelligent decisions. To perform meaningful data fusion, input data from different sensors must be sampled at time points in close propinquity to each other, otherwise the result cannot accurately reflect the status of the physical environment. ROS (Robotic Operating System), a popular software framework for autonomous systems, provides message synchronization mechanisms to address the above problem, by buffering messages carrying data from different sensors and grouping those with similar timestamps. Although message synchronization is widely used in applications developed based on ROS, little knowledge is known about its actual behavior and performance, so it is hard to guarantee the quality of data fusion. In this paper, we model the message synchronization policy in ROS and formally analyze its worst-case time disparity (maximal difference among the timestamps of the messages grouped into the same output set). We conduct experiments to evaluate the precision of the proposed time disparity upper bound against the maximal observed time disparity in real execution, and compare it with the synchronization policy in Apollo Cyber RT, another popular software framework for autonomous driving systems. Experiment results show that our analysis has good precision and ROS outperforms Apollo Cyber RT in terms of both observed worst-case time disparity and the theoretical bound.

Deep neural networks (DNNs) have been widely used in many cyber–physical systems (CPSs). However, it is still a challenging work to deploy DNNs in real-time systems. In particular, the execution time of DNN inference must be predictable, s.t. it could be known whether the runtime inference can complete within a required timing constraint. Moreover, the timing constraints may change dynamically with the runtime environment in many embedded applications, such as autonomous cars. A possible way to meet such dynamic real-time requirements is to execute different subnetworks of a DNN at runtime. However, improper construction of subnetworks may not only introduce unpredictable inference time, s.t. the real-timing constraints could be violated unexpectedly, but also has poor compatibility with the well-optimized machine learning framework (e.g., TensorFlow). In this article, we study the predictability when executing different subnetworks of a DNN. In particular, we present a featurewise runtime adaptation framework for DNN inference, which is implemented and validated on NVIDIA Jetson TX2 and Nano with TensorFlow. The experimental results show that our method can achieve predictable inference time in comparison with the state-of-the-art methods.

Suspension-based locks are widely used in real-time systems to coordinate simultaneous accesses to exclusive shared resources. Although suspension-based locks have been well studied forsequentialreal-time tasks, little work has been done on this topic forparallelreal-time tasks. This article for the first time studies the problem of how to extend existing sequential-task locking protocols and their analysis techniques to the parallel task model. More specifically, we extend two locking protocols OMLP and OMIP, which were designed for clustered scheduling ofsequentialreal-time tasks, to federated scheduling ofparallelreal-time tasks. We present corresponding blocking analysis techniques, and developpath-orientedtechniques to analyze and count blocking time. Schedulability tests with different efficiency and accuracy are further developed. Experiments are conducted to evaluate the performance of our proposed approaches against the state-of-the-art.

All existing work on real-time scheduling of parallel task graph models with shared resources assumes that a critical section must be contained inside a single vertex. However, this assumption does not hold in many realistic parallel real-time software. In this work, we conduct the first study on real-time scheduling and analysis of parallel task graphs where critical sections are allowed to cross different vertices. We show that allowing this may potentially lead to deadlocks and the so-called resource unrelated blocking time problem. We formalize the conditions for the deadlocks and resource unrelated blocking time to happen, and propose two different solutions to address them and develop corresponding schedulability analysis techniques. We conduct comprehensive experiments to evaluate our method. The results indicate that there is a significant impact to the system schedulability when tasks incur deadlock and resource unrelated blocking. Moreover, the schedulability can benefit from the execution of workload in parallel with critical sections if tasks can be carefully designed so that all deadlocks and resource unrelated blocking time can be avoided, and our methods are efficient to determine the schedulability of systems where critical sections across different vertices exist.

The Round Robin scheduling policy is used in many real-time embedded systems because of its simplicity and low overhead. In this paper, we study a variation of Round Robin used in practical systems, named Lazy Round Robin, which is simpler to implement and has lower runtime overhead than ordinary Round Robin. The key difference between Round Robin and Lazy Round Robin lies in when the scheduler reacts to newly released task instances. The Round Robin scheduler checks whether a newly released task instance is eligible for execution in the remaining part of the current round, while the Lazy Round Robin scheduler does not react to any task release until the end of the current round. This paper develops techniques to calculate upper bounds of response time of tasks scheduled by Lazy Round Robin. Experiments are conducted to evaluate our analysis techniques and compare the real-time performance of Round Robin and Lazy Round Robin.

Federated scheduling is a promising approach to schedule parallel real-time tasks, where each task exclusively executes on a set of dedicated processors. However, federated scheduling suffers significant resource wasting since a task typically only uses part of the processing capacity allocated to it, while the unused part cannot be shared with other tasks. To solve this problem, we present a virtually-federated scheduling approach, which both enjoys the good analyzability of federated scheduling and allows tasks to efficiently share processors with others. The main idea is to construct virtual processors on physical processors, and let a task exclusively execute on a set of virtual processors. As a physical processor is shared by virtual processors, tasks effectively share processors with each other. On the other hand, as each task exclusively executes on its own virtual processor set, the good analyzability of federated scheduling can be carried into to our virtually-federated scheduling approach. We conduct comprehensive performance evaluation to compare our proposed approach with existing methods of different types. Experiment results show that our approach consistently outperforms existing methods to a considerable extent under a wide range of parameter settings.

Locking protocol is an essential component in resource management of real-time systems, which coordinates mutually exclusive accesses to shared resources from different tasks. Although the design and analysis of locking protocols have been intensively studied for sequential real-time tasks, there has been a little work on this topic for parallel real-time tasks. In this article, we study the analysis of parallel real-time tasks using spin locks to protect accesses to shared resources in three commonly used request serving orders (unordered, FIFO-order, and priority-order). A remarkable feature making our analysis method more accurate is to systematically analyze the blocking time which may delay a task's finishing time, where the impact to the total workload and the longest path length is jointly considered, rather than analyzing them separately and counting all blocking time as the workload that delays a task's finishing time, as commonly assumed in the state-of-the-art.

OpenMP is a popular programming framework in both general and high-performance computing and has recently drawn much interest in embedded and real-time computing. Although the execution semantics of OpenMP are similar to the DAG task model, the constraints posed by the OpenMP specification make them significantly more challenging to analyze. A tied task is an important feature in OpenMP that must execute on the same thread throughout its entire life cycle. A previous work [1] succeeded in analyzing the real-time scheduling of tied tasks by modifying the Task Scheduling Constraints (TSCs) in OpenMP specification. In this article, we also study the real-time scheduling of OpenMP task systems with tied tasks but without changing the original TSCs. In particular, we propose a partitioning-based algorithm, P-EDF-omp, by which the tied constraint can be automatically guaranteed as long as an OpenMP task system can be successfully partitioned to a multiprocessor platform. Furthermore, we conduct comprehensive experiments with both synthetic workloads and established OpenMP benchmarks to show that our approach consistently outperforms the work in [1] -even without modifying the TSCs.

Real-time scheduling and locking protocols are fundamental facilities to construct time-critical systems. For parallel real-time tasks, predictable locking protocols are required when concurrent sub-jobs mutually exclusive access to shared resources. This paper for the first time studies the distributed synchronization framework of parallel real-time tasks, where both tasks and global resources are partitioned to designated processors, and requests to each global resource are conducted on the processor on which the resource is partitioned. We extend the Distributed Priority Ceiling Protocol (DPCP) for parallel tasks under federated scheduling, with which we proved that a request can be blocked by at most one lower-priority request. We develop task and resource partitioning heuristics and propose analysis techniques to safely bound the task response times. Numerical evaluation (with heavy tasks on 8-, 16-, and 32-core processors) indicates that the proposed methods improve the schedulability significantly compared to the state-of-the-art locking protocols under federated scheduling.

Locking protocol is an essential component in resource management of real-time systems, which coordinates mutually exclusive accesses to shared resources from different tasks. OpenMP is a promising framework for multi-core realtime embedded systems as well as provides spin locks to protect shared resources. In this paper, we propose a resource model for analyzing OpenMP programs with spin locks. Based on our resource model, we also develop a technique for analyzing the blocking time which impacts the total workload. Notably, the resource model provides detailed resource access behavior of the programs, making our blocking analysis more accurate. Further, we derive the schedulability analysis for real-time OpenMP tasks with spin locks protecting shared resources. Experiments with realistic OpenMP programs are conducted to evaluate the performance of our method.

ROS (Robot Operating System) is currently the most popular robotic software development framework. Robotic software in safe-critical domain are usually subject to hard real-time constraints, so designers must formally model and analyze their timing behaviors to guarantee that real-time constraints are always honored at runtime. This paper studies real-time scheduling and analysis of processing chains in ROS2, the second-generation ROS with a major consideration of real-time capability. First, we study response time analysis of processing chains on ROS2 executors. We show that the only existing result of this problem is both optimistic and pessimistic, and develop new techniques to address these problems and significantly improve the analysis precision. Second, we reveal that the response time of a processing chain on an executor only depends on its last scheduling entity (callback), which provides useful guidance for designers to improve not only the response time bound, but also the actual worst-case/average response time of the system at little design cost. We conduct experiments with both randomly generated workload and a case study on realistic ROS2 platforms to evaluate and demonstrate our results.

Utilization bound is a well-known concept in real-time scheduling theory for sequential periodic tasks, which can be used both for quantifying the performance of scheduling algorithms and as efficient schedulability tests. However, the schedulability of parallel real time task graphs depends on not only utilization, but also another parameter tensity, the ratio between the longest path length and period. In this paper, we use utilization-tensity bounds to better characterize the schedulability of parallel real-time tasks. In particular, we derive utilization-tensity bounds for parallel DAG tasks under global EDF scheduling, which facilitate significantly more precise schedulability analysis than the state-of-the-art analysis techniques based on capacity augmentation bound and response time analysis. Moreover, we apply the above results to the federated scheduling paradigm to improve the system schedulability by choosing proper scheduling strategies for tasks with different workload and structure features.

Multicore processors have become mainstream computation platforms not only for general and high-performance computers but also for real-time embedded systems. To fully utilize the computation power of multicores, software must be parallelized. Recently, there has been a rapidly increasing interest in real-time scheduling of parallel real-time tasks, but the field is still much less mature than traditional real-time scheduling of sequential tasks. In this article, we study the real-time scheduling and techniques for parallel real-time tasks based on decomposition, where a task graph is transferred to a set of independent sporadic tasks. In particular, we propose new decomposition strategies that better explore the structure feature of each task to improve schedulability. We develop schedulability tests for the global earliest deadline first (EDF) scheduling algorithm based on decomposition and three types of its variants, with their own pros and cons in different aspects. We conduct experiments to evaluate the real-time performance of our proposed scheduling algorithms against the state-of-the-art scheduling and analysis methods of different types.

This paper for the first time studies the scheduling and analysis of parallel real-time tasks with semaphores. In parallel task systems, each task may issue multiple requests to a semaphore, which raises new challenges to the design and analysis problems. We propose a new locking protocol LPP that limits the maximal number of requests to a semaphore by a task that can block other tasks at any time. We develop analysis techniques to safely bound the task response times, with which we prove that the best real-time performance is achieved if only one request to a semaphore by a task is allowed to block other tasks at a time. Experiments under different parameter settings are conducted to compare our proposed protocol and analysis techniques with the state-of-the-art spinlock protocol and analysis techniques for parallel real-time tasks.

Real-time and embedded systems are shifting from single-core to multi-core processors, on which software must be parallelized to fully utilize the computation capacity of hardware. Recently much work has been done on real-time scheduling of parallel tasks modeled as directed acyclic graphs (DAG). However, most of these studies assume tasks to have implicit or constrained deadlines. Much less work considered the general case of arbitrary deadlines (i.e., the relative deadline is allowed to be larger than the period), which is more difficult to analyze due to intra-task interference among jobs. In this paper, we study the analysis of Global Earliest Deadline First (GEDF) scheduling for DAG parallel tasks with arbitrary deadlines. We develop new analysis techniques for GEDF scheduling of a single DAG task, which not only outperform the state-of-the-art in general evidenced by empirical evaluation, but also guarantee a better capacity augmentation bound 2.41 (the best known result is 2.5). The proposed analysis techniques are also extended to and evaluated with the case of multiple DAG tasks using the federated scheduling approach.

We propose an approach to calculate delay bound for multiprocessor real-time systems scheduled by GEDF. Different from most existing analysis techniques analyzing sporadic tasks, we consider bursty tasks which have more general arrival patterns. In detail, we use shapers to eliminate burst in original system inputs and generate sporadic job sequences, and then calculate the delay bound of each task. To further improve our approach, we design a heuristic algorithm to make as more tasks as possible to meet their deadlines by adjusting settings of shapers. Experiments show that the proposed algorithm can lead to improvement of acceptance ratio and the delay bound derived is much smaller than that by compared existing work.

DAG task model is a general parallel task model that has been widely concerned and studied by researchers. The combination of mixed-criticality and DAG task model makes it difficult to analyze system behaviors. Under federated mixed-criticality scheduling algorithm, tasks are physically isolated with regard to computation resources, which leads to lower analysis complexity and better performance. However, federated mixed-criticality scheduling algorithm suffers resource waste as in federated scheduling, and almost half of processor resources can be wasted in extreme cases. In this paper, we address the problem and propose a novel semi-federated mixed-criticality algorithm (SFMC). SFMC combines semi-federated scheduling with mixed-criticality systems, whose original architecture is changed to a dual-hierarchical one. When analyzing the combined system, we first allocate finer-grained processor resources to each MC DAG task, then we prove the correctness of the SFMC algorithm in both normal and critical states. The proposed algorithm is evaluated on randomly generated independent DAG task sets based on OpenMP benchmarks. Experiment results present that our algorithm has better performance on schedulability than the federated mixed-criticality scheduling algorithm.

Real-Time Calculus (RTC) is a powerful framework for modeling and analyzing complex networked real-time systems. RTC builds up on and shares many similarities with Network Calculus (NC), but some concepts are not completely the same in RTC and NC. One of the most important properties in NC is pay-burst-only-once, which can improve the precision of end-to-end performance analysis. Naturally, people would expect the pay-burst-only-once property to also hold in RTC. In fact, some existing work has used it in some performance analysis problems. Unfortunately, the pay-burst-only-once property has never been proved in RTC. There are even some results seeming to be against the pay-burst-only-once property in RTC. In this paper, we prove that the pay-burst-only-once property indeed holds in RTC.

Suspension-based locks are widely used in realtime systems to coordinate simultaneous accesses to exclusive shared resources. Although suspension-based locks have been well studied for sequential real-time tasks, little work has been done on this topic for parallel real-time tasks. This paper for the first time studies the problem of how to extend existing sequential-task locking protocols and their analysis techniques to the parallel task model. More specifically, we extend two locking protocols OMLP and OMIP, which were designed for clustered scheduling of sequential real-time tasks, to federated scheduling of parallel real-time tasks, and develop path-oriented techniques to analyze and count blocking time. Experiments are conducted to evaluate the performance of our proposed approaches and compare them against the state-of-the-art.

In this paper, we propose a novel approach to schedule conditional DAG parallel tasks, with which we can derive safe response time upper bounds significantly better than the state-of-the-art counterparts. The main idea is to eliminate the notorious timing anomaly in scheduling parallel tasks by enforcing certain order constraints among the vertices, and thus the response time bound can be accurately predicted off-line by somehow “simulating” the runtime scheduling. A key challenge to apply the timing-anomaly free scheduling approach to conditional DAG parallel tasks is that at runtime it may generate exponentially many instances from a conditional DAG structure. To deal with this problem, we develop effective abstractions, based on which a safe response time upper bound is computed in polynomial time. We also develop algorithms to explore the vertex orders to shorten the response time bound. The effectiveness of the proposed approach is evaluated by experiments with randomly generated DAG tasks with different parameter configurations.

Real-time and embedded systems are shifting from single-core to multi-core processors, on which the software must be parallelized to fully utilize the computation capacity of the hardware. Recently, much work has been done on real-time scheduling of parallel tasks modeled as directed acyclic graphs (DAG). However, most of these studies assume tasks to have implicit or constrained deadlines. Much less work considered the general case of arbitrary deadlines (i.e., the relative deadline is allowed to be larger than the period), which is more difficult to analyze due to intra-task interference among jobs. In this article, we study the analysis of Global Earliest Deadline First (GEDF) scheduling for DAG parallel tasks with arbitrary deadlines. We develop new analysis techniques for GEDF scheduling of a single DAG task and this new analysis techniques can guarantee a better capacity augmentation bound 2.41 (the best known result is 2.5) in the case of a single task. Furthermore, the proposed analysis techniques are also extended to the case of multiple DAG tasks under GEDF and federated scheduling. Finally, through empirical evaluation, we justify the out-performance of our schedulability tests compared to the state-of-the-art in general.

Real-time scheduling and analysis of parallel tasks modeled as directed acyclic graphs (DAG) have been intensively studied in recent years. However, no existing work has explored the execution order of eligible vertices within a DAG task. In this paper, we show that this intra-task vertex execution order has a large impact on system schedulability and propose to control the execution order by vertex-level priority assignment. We develop analysis techniques to bound the worst-case response time for the proposed scheduling strategy and design heuristics for proper priority assignment to improve system schedulability as much as possible. We further extend the proposed approach to the general setting of multiple recurrent DAG tasks. Experiments with both realistic parallel benchmark applications and randomly generated workload show that our method consistently outperforms state-of-the-art methods with different task graph structures and parameter configurations.

Capacity augmentation bound is a widely used quantitative metric in theoretical studies of schedulability analysis for directed acyclic graph (DAG) parallel real-time tasks, which not only quantifies the suboptimality of the scheduling algorithms, but also serves as a simple linear-time schedulability test. Earlier studies on capacity augmentation bounds of the sporadic DAG task model were either restricted to a single DAG task or a set of tasks with implicit deadlines. In this paper, we consider parallel tasks with constrained deadlines under global earliest deadline first policy. We first show that it is impossible to obtain a constant bound for our problem setting, and derive both lower and upper bounds of the capacity augmentation bound as a function with respect to the maximum ratio of task period to deadline. Our upper bound is at most 1.47 times larger than the optimal one. We conduct experiments to compare the acceptance ratio of our capacity augmentation bound with the existing schedulability test also having linear-time complexity. The results show that our capacity augmentation bound significantly outperforms the existing linear-time schedulability test under different parameter settings.

Federated scheduling is a promising approach to schedule parallel real-time tasks on multi-cores, where each heavy task exclusively executes on a number of dedicated processors, while light tasks are treated as sequential sporadic tasks and share the remaining processors. However, federated scheduling suffers resource waste since a heavy task with processing capacity requirement x+epsilon (where x is an integer and 0 epsilon 1) needs x+1 dedicated processors. In the extreme case, almost half of the processing capacity is wasted. In this paper we propose the semi-federate scheduling approach, which only grants x dedicated processors to a heavy task with processing capacity requirement x+epsilon, and schedules the remaining epsilon part together with light tasks on shared processors. Experiments with randomly generated task sets show the semi-federated scheduling approach significantly outperforms not only federated scheduling, but also all existing approaches for scheduling parallel real-time tasks on multi-cores.

Real-time systems are shifting from single-core to multi-core processors, on which software must be parallelized to fully utilize the additional computation power. Recently different types of scheduling algorithms and analysis techniques have been proposed for parallel real-time tasks modeled as directed acyclic graphs (DAG). However, this field is still much less mature than traditional real-time scheduling of sequential tasks. In this paper, we study the decomposition-based scheduling for parallel real-time tasks, where a task graph is transferred to a set of independent sporadic tasks. In particular, we proposed a new decomposition strategy that better explores the feature of each task, represented by its structure characteristic value, to improve schedulability. The structure characteristic values do not only provide a clear guidance in task decomposition, but also can be directly used for schedulability tests, as well as to quantify the suboptimality of our scheduling algorithm in terms of capacity augmentation bounds. We conduct comprehensive experiments to evaluate the real-time performance of our proposed scheduling algorithm, against the state-of-the-art scheduling and analysis methods of different types. Experiment results show that our method consistently outperforms all of the previous methods under different parameter settings.