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.

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.

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.

Parallel tasks have been paid growing attention in recent years, and the scheduling with shared resources is of significant importance to real-time systems. As an efficient mechanism to provide mutual exclusion for parallel processing, spin-locks are ubiquitous in multi-processor real-time systems. However, the spin-locks suffer the scalability problem, and the intra-task parallelism further exacerbates the analytical pessimism. To overcome such deficiencies, we propose a Hierarchical Hybrid Locking Protocol (H2LP) under federated scheduling. The proposed H2LP integrates the classical Multiprocessor Stack Resource Policy (MSRP) and uses a token mechanism to reduce global contentions. We provide a complete analysis framework supporting both heavy and light tasks under federated scheduling and develop a blocking analysis with the state-of-the-art linear optimization technique. Empirical evaluations showed that the H2LP outperformed the other state-of-the-art locking protocols in at least configurations when considering exclusive clustering. Furthermore, our partitioned approach for light tasks can substantially improve schedulability by mitigating the over-provisioning problem.

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.

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.

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.

Predictable scheduling and resource sharing primitives are fundamental aspects of real-time systems. To prevent race conditions, access to shared resources must ensure mutual exclusion, e.g., using semaphores. Further, real-time locking protocols are required to avoid un-controlled priority inversions. For uniprocessor systems, the Priority Ceiling Protocol (PCP) has been widely accepted and supported in real-time operating systems. However, it remains arguable as to whether there exists a preferable approach for resource sharing in multiprocessor systems. In this paper, we show that the proposed Resource-Oriented Partitioned (ROP) scheduling with a distributed resource sharing policy, originating from the concept of the Distributed Priority Ceiling Protocol (DPCP), can achieve a non-trivial speedup factor guarantee. Specifically, we prove that the proposed R-PCP-rm-rm algorithm achieves a speedup factor of $11-6/(m+1)$11-6/(m+1) on a platform consisting of $m$m processors, where each job of a task may request at most one shared resource at most one time. Our empirical evaluations show that the proposed algorithm is highly effective in terms of task sets deemed schedulable.

When concurrent real-time tasks have to access shared resources, to prevent race conditions, the synchronization and resource access must ensure mutual exclusion, e.g., by using semaphores. That is, no two concurrent accesses to one shared resource are in their critical sections at the same time. For uniprocessor systems, the priority ceiling protocol (PCP) has been widely accepted and supported in real-time operating systems. However, it is still arguable whether there exists a preferable approach for resource sharing in multiprocessor systems. In this paper, we show that the proposed resource-oriented partitioned scheduling using PCP combined with a reasonable allocation algorithm can achieve a non-trivial speedup factor guarantee. Specifically, we prove that our task mapping and resource allocation algorithm has a speedup factor 11-6/(m+1) on a platform comprising m processors, where a task may request at most one shared resource and the number of requests on any resource by any single job is at most one. Our empirical investigations show that the proposed algorithm is highly effective in terms of task sets deemed schedulable.

All major real-time suspension-based locking protocols (or semaphore protocols) for global fixed-priority scheduling are reviewed and a new, unified response-time analysis framework applicable to all protocols is proposed. The newly proposed analysis, based on linear programming, is shown to be clearly preferable compared to all prior conventional approaches. Based on the new analysis, all protocols are directly compared with each other in a large-scale schedulability study. Interestingly, the Priority Inheritance Protocol (PIP) and the Flexible Multiprocessor Locking Protocol (FMLP), which are the two oldest and simplest of the considered protocols, are found to perform best.