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.

Self-suspending behavior in real-time embedded systems can have a major and non-trivial negative impact on timing predictability. In this work, we investigate how to analyze the schedulability of segmented self-suspending task systems under a fixed-priority assignment. For this purpose, we introduce the multi-segment workload function as well as the maximum workload function in order to quantify the maximum interference from the higher-priority tasks when constructing our (sufficient) schedulability test. Moreover, we derive an optimal priority assignment with respect to our schedulability test since it is compatible with Audsley's Optimal Priority Assignment (OPA). We show by means of comprehensive evaluations that our approach is highly effective concerning the number of schedulable task sets. Furthermore, one set of results reveals a rather non-intuitive observation, namely, that the worst-case suspension time of a computation segment should also be respected to improve the schedulability even if the suspension may finish earlier.

In this paper, we take a careful look at speedup factors, utilization bounds, and capacity augmentation bounds. These three metrics have been widely adopted in real-time scheduling research as the de facto standard theoretical tools for assessing scheduling algorithms and schedulability tests. Despite that, it is not always clear how researchers and designers should interpret or use these metrics. In studying this area, we found a number of surprising results, and related to them, ways in which the metrics may be misinterpreted or misunderstood. In this paper, we provide a perspective on the use of these metrics, guiding researchers on their meaning and interpretation, and helping to avoid pitfalls in their use. Finally, we propose and demonstrate the use of parametric augmentation functions as a means of providing nuanced information that may be more relevant in practical settings.

To tackle the unavoidable self-suspension behavior due to I/O-intensive interactions, multi-core processors, computation offloading systems with coprocessors, etc., the dynamic and the segmented self-suspension sporadic task models have been widely used in the literature. We propose new self-suspension models that are hybrids of the dynamic and the segmented models. Those hybrid models are capable of exploiting knowledge about execution paths, potentially reducing modelling pessimism. In addition, we provide the corresponding schedulability analysis under fixed-relative-deadline (FRD) scheduling and explain how the state-of-the-art FRD scheduling strategy can be applied. Empirically, these hybrid approaches are shown to be effective with regards to the number of schedulable task sets.

In computing systems, a job/process/task/thread may suspend itself when it has to wait for some other internal or external activities, such as computation offloading or memory accesses, to finish before it can continue its execution. In the literature, there are two commonly adopted self-suspending sporadic task models in real-time systems: 1) the dynamic self-suspension model and 2) the segmented self-suspension sporadic task model. A dynamic self-suspending sporadic task is specified with an upper bound on the maximum suspension time for a job (task instance), which allows a job to dynamically suspend itself arbitrary often as long as the suspension time upper bound is not violated. By contrast, a segmented self-suspending sporadic task has a predefined execution and suspension pattern in an interleaving manner. The dynamic self-suspension model is very flexible but inaccurate, whilst the segmented self-suspension model is very restrictive but very accurate. The gap between these two widely-adopted self-suspension task models can be potentially filled by the hybrid self-suspension task model. The investigation of the impact of self-suspension on timing predictability has been started in 1988. This survey paper provides a short summary of the state of the art in the design and analysis of scheduling algorithms and schedulability tests for self-suspending tasks in real-time systems.

1This paper answers several open questions of practical concerns to schedule soft real-time (SRT) tasks, to guarantee their bounded tardiness, under fixed-priority scheduling in homogeneous multiprocessor systems. We consider both cases with only SRT tasks and with mixed sets of SRT and hard real-time (HRT) tasks. For the case in which the system has only SRT tasks, we show that any fixed priority assignment policy yields a capacity augmentation factor of 2−1/M where M is the number of processors. We prove the optimality of the utilization-monotonic (UM) priority assignment (i.e., assigning higher priorities to high-utilization tasks) under our sufficient test for guaranteeing bounded tardiness. We show that UM priority assignment can yield a utilization bound of M+1/2M, which is shown asymptotically the best possible bound. For the case in which the system has mixed SRT and HRT tasks, we present two new fixed-priority assignment algorithms and their associated schedulability tests. One is a clustering-based greedy priority assignment policy and another is based on Audsley's optimal priority assignment (OPA) approach. We show that the utilization bounds, augmentation factors, and speedup factors are still maintained by the hard real-time cases. Therefore, introducing soft real-time tasks does not create additional problems (at least in those metrics) for scheduling if the priority assignments are properly done. As demonstrated by extensive experiments, these two policies yield reasonably good performance overall and much better performance than the deadline-monotonic priority assignment.

Formal models used for representing recurrent real-time processes have traditionally been characterized by a collection of jobs that are released periodically. However, such a modeling may result in resource under-utilization in systems whose behaviors are not entirely periodic. For instance, tasks in cyber-physical system (CPS) may change their service levels, e.g., periods and/or execution times, to adapt to the changes of environments. In this work, we study a model that is a generalization of the periodic task model, called multi-mode task model: a task has several modes specified with different execution times and periods to switch during runtime, independent of other tasks. Moreover, we study the problem of allocating a set of multi-mode tasks on a homogeneous multiprocessor system. We present a scheduling algorithm using any reasonable allocation decreasing (RAD) algorithm for task allocations for scheduling multi-mode tasks on multiprocessor systems. We prove that this algorithm achieves 38% utilization for implicit-deadline rate-monotonic (RM) scheduled multi-mode tasks on multiprocessor systems.

The emergence of multicore and manycore platforms poses a big challenge for the design of real-time embedded systems, especially for timing analysis. We observe in this paper that response-time analysis for multicore platforms with shared resources can be symmetrically approached from two perspectives: a core-centric and a shared-resource-centric perspective. The common "core-centric" perspective is that a task executes on a core until it suspends the execution due to shared resource accesses. The potentially less intuitive "shared-resource-centric" perspective is that a task performs requests on shared resources until suspending itself back to perform computation on its respective core.

For real-time embedded systems, self-suspending behaviors can cause substantial performance/schedulability degradations. In this paper, we focus on preemptive fixed-priority scheduling for the dynamic self-suspension task model on uniprocessor. This model assumes that a job of a task can dynamically suspend itself during its execution (for instance, to wait for shared resources or access co-processors or external devices). The total suspension time of a job is upper-bounded, but this dynamic behavior drastically influences the interference generated by this task on lower-priority tasks. The state-of-the-art results for this task model can be classified into three categories (i) modeling suspension as computation, (ii) modeling suspension as release jitter, and (iii) modeling suspension as a blocking term. However, several results associated to the release jitter approach have been recently proven to be erroneous, and the concept of modeling suspension as blocking was never formally proven correct. This paper presents a unifying response time analysis framework for the dynamic self-suspending task model. We provide a rigorous proof and show that the existing analyses pertaining to the three categories mentioned above are analytically dominated by our proposed solution. Therefore, all those techniques are in fact correct, but they are inferior to the proposed response time analysis in this paper. The evaluation results show that our analysis framework can generate huge improvements (an increase of up to 50% of the number of task sets deemed schedulable) over these state-of-the-art analyses.

In many practical real-time systems, the physical environment and the system platform can impose uncertain execution behaviour to the system. For example, if transient faults are detected, the execution time of a task instance can be increased due to recovery operations. Such fault recovery routines make the system very vulnerable with respect to meeting hard real-time deadlines. In theory and in practical systems, this problem is often handled by aborting not so important tasks to guarantee the response time of the more important tasks. However, for most systems such faults occur rarely and the results of not so important tasks might still be useful, even if they are a bit late. This implicates to not abort these not so important tasks but keep them running even if faults occur, provided that the more important tasks still meet their hard real time properties. In this paper, we present Systems with Dynamic Real-Time Guarantees to model this behaviour and determine if the system can provide full timing guarantees or limited timing guarantees without any online adaptation after a fault occurred. We present a schedulability test, provide an algorithm for optimal priority assignment, determine the maximum interval length until the system will again provide full timing guarantees and explain how we can monitor the system state online. The approaches presented in this paper can also be applied to mixed criticality systems with dual criticality levels.

In this paper, we present a general response-time analysis and schedulability-test framework, called k2Q (k to Q). It provides automatic constructions of closed-form quadratic bounds or utilization bounds for a wide range of applications in real-time systems under fixed-priority scheduling. The key of the framework is a k-point schedulability test or a k-point response time analysis that is based on the utilizations and the execution times of k-1 higher-priority tasks. The natural condition of k2Q is a quadratic form for testing the schedulability or analyzing the response time. The response time analysis and the schedulability analysis provided by the framework can be viewed as a "blackbox'' interface that can result in sufficient utilization-based analysis. Since the framework is independent from the task and platform models, it can be applied to a wide range of applications.

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.

Self-suspension is becoming an increasingly prominent characteristic in real-time systems such as: (i) I/O-intensive systems, where applications interact intensively with I/O devices, (ii) multi-core processors, where tasks running on different cores have to synchronize and communicate with each other, and (iii) computation offloading systems with coprocessors, like Graphics Processing Units (GPUs). In this paper, we show that rate-monotonic (RM), deadline-monotonic (DM) and laxity-monotonic (LM) scheduling will perform rather poor in dynamic self-suspending systems in terms of speed-up factors. On the other hand, the proposed PASS approach is guaranteed to find a feasible priority assignment on a speed-2 uniprocessor, if one exists on a unit-speed processor. We evaluate the feasibility of the proposed approach via a case study implementation. Furthermore, the effectiveness of the proposed approach is also shown via extensive simulation results.

For real time task sets, allowing preemption is often considered to be important to ensure the schedulability, as it allows high-priority tasks to be allocated to the processor nearly immediately. However, preemptive scheduling also introduces some additional overhead and may not be allowed for some hardware components, which motivates the needs of non-preemptive or limited-preemptive scheduling. We present a safe sufficient schedulability test for non-preemptive (NP) fixed priority scheduling that can verify the schedulability for Deadline Monotonic (DM-NP) and Rate Monotonic (RM-NP) scheduling in linear time, if task orders according to priority and period are given. This test leads to a better upper bound on the speedup factor for DM-NP and RM-NP in comparison to Earliest Deadline First (EDF-NP) than previously known, closing the gab between lower and upper bound. We improve our test, resulting in interesting properties of the blocking time that allow to determine schedulability by only considering the schedulability of the preemptive case if some conditions are met. Furthermore, we present a utilization bound for RM-NP, based on the ratio γ > 0 of the upper bound of the maximum blocking time to the execution time, significantly improving previous results.

With the advent of cyber-physical systems, realtime tasks shall be run in different modes over time to react to the change of the physical environment. It is preferable to adopt high expressive models in real-time systems. In the light of simple implementation in kernels, fixed-priority scheduling has been widely adopted in commercial real-time systems. In this work we derive a technique for analyzing schedulability of the system where tasks can undergo mode change under fixed-priority scheduling. We study two types of fixed-priority scheduling in mode change systems: task-level and mode-level fixed-priority scheduling. The proposed tests run in polynomial time. We further show that a utilization of 2 - √2 ≈ 0.5857 can be guaranteed in implicit-deadline multi-mode systems if each mode is prioritized according to rate-monotonic policy. The effectiveness of the proposed tests is also shown via extensive simulation results.

To deal with a large variety of workloads in different application domains in real-time embedded systems, a number of expressive task models have been developed. For each individual task model, researchers tend to develop different types of techniques for deriving schedulability tests with different computation complexity and performance. In this paper, we present a general schedulability analysis framework, namely the k2U framework, that can be potentially applied to analyze a large set of real-time task models under any fixed-priority scheduling algorithm, on both uniprocessor and multiprocessor scheduling. The key to k2U is a k-point effective schedulability test, which can be viewed as a "blackbox" interface. For any task model, if a corresponding k-point effective schedulability test can be constructed, then a sufficient utilization-based test can be automatically derived. We show the generality of k2U by applying it to different task models, which results in new and improved tests compared to the state-of-the-art.