A recent trend in the theory of real-time scheduling is to consider generalizations of the classical periodic task model. Work on the associated schedulability and feasibility problems has resulted in algorithms that run efficiently and provide exact results. While these analyses give black-and-white answers about whether timing constraints are being met or not, response-time analysis adds a quantitative dimension. This brings new challenges for models more expressive than the classical periodic task model. An exact quantification of response time is difficult because of non-deterministic task behavior and a lack of combinable task-local worst cases. Therefore, previous approaches all make a trade-off between efficiency and precision, resulting in either prohibitively slow analysis run-times or imprecise over-approximate results. In this paper, we show that analysis can be both exact and efficient at the same time. We develop novel response-time characterizations to which we apply combinatorial abstraction refinement. Our algorithms for static-priority and EDF scheduling give exact results and are shown to be efficient for typical problem sizes. We advance the state-of-the-art by providing the first exact response-time analysis framework for graph-based task models.

The response time analysis problem is intractable for most existing real-time task models, except the simplest ones. Exact solutions for this problem in general have exponential complexity, and may run into scalability problems for large-scale task systems. In this paper, we study approximate analysis for static-priority scheduling of the Digraph Real-Time task model, which is a generalization of most existing graph-based real-time task models. We present two approximate analysis methods RBF and IBF, both of which have pseudo-polynomial complexity. We quantitatively evaluate their analysis precision using the metric speedup factor. We prove that RBF has a speedup factor of 2, and this is tight even for dual-task systems. The speedup factor of IBF is an increasing function with respect to k, the number of interfering tasks. This function converges to 2 as k approaches infinity and equals 1 when k = 1, implying that the IBF analysis is exact for dual-task systems. We also conduct simulation experiments to evaluate the precision and efficiency of RBF and IBF with randomly generated task sets. Results show that the proposed approximate analysis methods have very high efficiency with low precision loss.

The traditional periodic workload model for hard real-time systems has been extended by more expressive models in recent years. These models based on different classes of directed graphs allow modeling of structures like frames, branching and loops. With more expressiveness comes higher complexity of the associated analysis problems. Feasibility of digraph-based models with dynamic priority schedulers has been shown to be tractable via pseudo-polynomial algorithms. However, the problem was shown to be intractable for static priority scheduling since it is strongly coNP-hard already for the relatively simple class of cyclic digraphs. The core of this problem is an inherent combinatorial explosion caused by combining different behaviors of the participating tasks, lacking local worst cases. We introduce a novel iterative approach to efficiently cope with this combinatorial explosion, called combinatorial abstraction refinement. In combination with other techniques it significantly reduces exponential growth of run-time for most inputs. A prototype implementation for analysing static priority feasibility outperforms the state-of-the art pseudo-polynomial analysis for dynamic priority feasibility. It further shows better scaling behavior for typical problem sizes. We believe that this method can be applicable to a variety of combinatorial problems in the theory of real-time systems with certain abstraction structures.

Real-time systems are often modeled as a collection of tasks, describing the structure of the processor's workload. In the literature, task-models of different expressiveness have been developed, ranging from the traditional periodic task model to highly expressive graph-based models. For dynamic priority schedulers, it has been shown that the schedulability problem can be solved efficiently, even for graph-based models. However, the situation is less clear for the case of static priority schedulers. It has been believed that the problem can be solved in pseudo-polynomial time for the generalized multiframe model (GMF). The GMF model constitutes a compromise in expressiveness by allowing cycling through a static list of behaviors, but disallowing branching. Further, the problem complexity for more expressive models has been unknown so far. In this paper, we show that previous results claiming that a precise and efficient test exists are wrong, giving a counterexample. We prove that the schedulability problem for GMF models (and thus also all more expressive models) using static priority schedulers is in fact coNP-hard in the strong sense. Our result thus establishes the fundamental hardness of analyzing static priority real-time scheduling, in contrast to its dynamic priority counterpart of pseudo-polynomial complexity.

Future embedded real-time systems will be deployed on multi-core processors to meet the dramatically increasing high-performance and low-power requirements. This trend appeals to generalize established results on uniprocessor scheduling, particularly the various utilization bounds for schedulability test used in system design, to the multiprocessor setting. Recently, this has been achieved for the famous Liu and Lay land utilization bound by applying novel task splitting techniques. However, parametric utilization bounds that can guarantee higher utilizations (up to 100%) for common classes of systems are not yet known to be generalizable to multiprocessors as well. In this paper, we solve this problem for most parametric utilization bounds by proposing new task partitioning algorithms based on exact response time analysis. In addition to the worst-case guarantees, as the exact response time analysis is used for task partitioning, our algorithms significantly improve average-case utilization over previous work.

Previous works on real-time task graph models have ignored the crucial resource sharing problem. Due to the non-deterministic branching behavior, resource sharing in graph-based task models is significantly more difficult than in the simple periodic or sporadic task models. In this work we address this problem with several different scheduling strategies, and quantitatively evaluate their performance. We first show that a direct application of the well-known EDF+SRP strategy to graph-based task models leads to an unbounded speedup factor. By slightly modifying EDF+SRP, we obtain a new scheduling strategy, called EDF+saSRP, which has a speedup factor of 2. Then we propose a novel resource sharing protocol, called ACP, to better manage resource sharing in the presence of branching structures. The scheduling strategy EDF+ACP, which applies ACP to EDF, can achieve a speedup factor of 1.618, the golden ratio.

In formal analysis of real-time systems, a major concern is the analysis efficiency. As the expressiveness of models grows, so grows the complexity of their analysis. A recently proposed model, the digraph real-time task model (DRT), offers high expressiveness well beyond traditional periodic task models. Still, the associated feasibility problem on preemptive uniprocessors remains tractable. It is an open question to what extent the expressiveness of the model can be further increased before the feasibility problem becomes intractable. In this paper, we study that tractability border. We show that system models with the need for global timing constraints make feasibility analysis intractable. However, our second technical result shows that it remains tractable if the number of global constraints is bounded by a constant. Thus, this paper establishes a precise borderline between tractability and intractability.

Models for real-time systems have to balance the inherently contradicting goals of expressiveness and analysis efficiency. Current task models with tractable feasibility tests have limited expressiveness, restricting their ability to model many systems accurately. In particular, they are all recurrent, preventing the modeling of structures like mode switches, local loops, etc. In this paper, we advance the state-of-the-art with a model that is free from these constraints. Our proposed task model is based on arbitrary directed graphs (digraphs) for job releases. We show that the feasibility problem on preemptive uniprocessors for our model remains tractable. This even holds in the case of task systems with arbitrary deadlines.

An increasing trend in embedded system design is to integrate components with different levels of criticality into a shared hardware platform for better cost and power efficiency. Such mixed-criticality systems are subject to certifications at different levels of rigorousness, for validating the correctness of different subsystems on various confidence levels. The real-time scheduling of certifiable mixed-criticality systems has been recognized to be a challenging problem, where using traditional scheduling techniques may result in unacceptable resource waste. In this paper we present an algorithm called PLRS to schedule certifiable mixed-criticality sporadic tasks systems. PLRS uses fixed-job-priority scheduling, and assigns job priorities by exploring and balancing the asymmetric effects between the workload on different criticality levels. Comparing with the state-of-the-art algorithm by Li and Baruah for such systems, which we refer to as LB, PLRS is both more effective and more efficient: (i) The schedulability test of PLRS not only theoretically dominates, but also on average significantly outperforms LB's. (ii) The run-time complexity of PLRS is polynomial (quadratic in the number of tasks), which is much more efficient than the pseudo-polynomial run-time complexity of LB.

Liu and Layland discovered the famous utilization bound for fixed-priority scheduling on single processor systems in the 1970's. Since then, it has been a long standing open problem to find fixed-priority scheduling algorithms with the same bound for multiprocessor systems. In this paper, we present a partitioning-based fixed-priority multiprocessor scheduling algorithm with Liu and Layland's utilization bound.

The major obstacle to use multicores for real-time applications is that we may not predict and provide any guarantee on real-time properties of embedded software on such platforms; the way of handling the on-chip shared resources such as L2 cache may have a significant impact on the timing predictability. In this paper, we propose to use cache space isolation techniques to avoid cache contention for hard real-time tasks running on multicores with shared caches. We present a scheduling strategy for real-time tasks with both timing and cache space constraints, which allows each task to use a fixed number of cache partitions, and makes sure that at any time a cache partition is occupied by at most one running task. In this way, the cache spaces of tasks are isolated at run-time.

Recently, there have been several promising techniques developed for schedulability analysis and response time analysis for multiprocessor systems based on over-approximation. This paper contains two contributions. First, to improve the analysis precision, we apply Baruah's window analysis framework to response time analysis for poradic tasks on multiprocessor systems where the deadlines of tasks are within their periods. The crucial observation is that for global fixed priority scheduling, a response time bound of each task can be efficiently estimated by fixed-point computation without enumerating all the busy window sizes as in for schedulability analysis. The technique is proven to dominate theoretically state-of-the-art techniques for response time analysis for multiprocessor systems. Our experiments also show that the technique results in significant performance improvement compared with several existing techniques for multiprocessor schedulability analysis. As the second main contribution of this paper, we extend the proposed technique to task systems with arbitrary deadlines, allowing tasks to have deadlines beyond the end of their periods. This is a non-trivial extension even for single-processor systems. To our best knowledge, this is the first work of response time analysis for multiprocessor systems in this setting, which involves sophisticated techniques for the characterization and computation of response time bounds.