This paper addresses the problem of uniform random generation of vectors of values with a fixed sum, subject to upper and lower constraints on the individual component values. Solutions to this problem are used extensively in the generation of tasksets, specifically task utilization values, in support of the performance assessment of schedulability tests for real-time systems. This paper introduces a general-purpose solution in the form of an Inverse Volume Ratio Sampling method that is applicable provided that it is possible to determine the ratio of the volume below a given hyperplane to the total volume of the valid region in$n$-dimensional space, as demarcated by the constraints and the fixed sum. An efficient approach is derived for volume calculation using numerical convolution, thus instantiating the ConvolutionalFixedSum algorithm, which provides a user-specified level of precision, while scaling at$O\left(n^{3} \log (n)\right)$. A stringent uniformity test is developed, called the slices test, which is able to fully explore the extent of the valid region in each of the$n$dimensions. The slices test reveals that while the outputs of UUnifast and ConvolutionalFixedSum form uniform distributions, in some cases the outputs of prior state-of-the-art algorithms do not.

An IDK classifier is a computational element that classifies an input provided to it into one of a set of predefined categories provided that it can achieve the necessary confidence level to do so; otherwise, it outputs “I Don't Know” (IDK). The concept of IDK classifier cascades has emerged as a strategy for striking a balance between the requirements of rapid response and precise classification in machine perception. Effective algorithms for constructing IDK classifier cascades have recently been developed. Here we extend these prior approaches by incorporating fault-tolerance: enabling classification that is concurrently rapid and accurate even in the event of some of the IDK classifiers exhibiting faulty behavior.

Abstract This paper introduces and evaluates a general construct for trading off accuracy and overall execution duration in classification-based machine perception problems—namely, the generalized IDK classifier cascade . The aim is to select the optimal sequence of classifiers required to minimize the expected (i.e. average) execution duration needed to achieve successful classification, subject to a constraint on quality, and optionally a latency constraint on the worst-case execution duration. An IDK classifier is a software component that attempts to categorize each input provided to it into one of a fixed set of classes, returning “I Don’t Know” (IDK) if it is unable to do so with the required level of confidence. An ensemble of several different IDK classifiers may be available for the same classification problem, offering different trade-offs between effectiveness (i.e. the probability of successful classification) and timeliness (i.e. execution duration). A model for representing such characteristics is defined, and a method is proposed for determining the values of the model parameters for a given ensemble of IDK classifiers. Optimal algorithms are developed for sequentially ordering IDK classifiers into an IDK cascade, such that the expected duration to successfully classify an input is minimized, optionally subject to a latency constraint on the worst-case overall execution duration of the IDK cascade. The entire methodology is applied to two real-world case studies. In contrast to prior work, the methodology developed in this paper caters for arbitrary dependences between the probabilities of successful classification for different IDK classifiers. Effective practical solutions are developed considering both single and multiple processors.

Abstract A classifier is a software component, often based on Deep Learning, that categorizes each input provided to it into one of a fixed set of classes. An IDK classifier may additionally output “I Don’t Know” (IDK) for certain inputs. Multiple distinct IDK classifiers may be available for the same classification problem, offering different trade-offs between effectiveness, i.e. the probability of successful classification, and efficiency, i.e. execution time. Optimal offline algorithms are proposed for sequentially ordering IDK classifiers such that the expected duration to successfully classify an input is minimized, optionally subject to a hard deadline on the maximum time permitted for classification. Solutions are provided considering independent and dependent relationships between pairs of classifiers, as well as a mix of the two.

An IDK classifier is a computing component that categorizes inputs into one of a number of classes, if it is able to do so with the required level of confidence, otherwise it returns “I Don’t Know” (IDK). IDK classifier cascades have been proposed as a way of balancing the needs for fast response and high accuracy in classification-based machine perception. Efficient algorithms for the synthesis of IDK classifier cascades have been derived; however, the responsiveness of these cascades is highly dependent on the accuracy of predictions regarding the run-time behavior of the classifiers from which they are built. Accurate predictions of such run-time behavior is difficult to obtain for many of the classifiers used for perception. By applying the algorithms using predictions framework, we propose efficient algorithms for the synthesis of IDK classifier cascades that are robust to inaccurate predictions in the following sense: the IDK classifier cascades synthesized by our algorithms have short expected execution durations when the predictions are accurate, and these expected durations increase only within specified bounds when the predictions are inaccurate.

In this paper, we use the term “Analysis-Runtime Co-design” to describe the technique of modifying the runtime protocol of a scheduling scheme to closely match the analysis derived for it. Carefully designed modifications to the runtime protocol make the schedulability analysis for the scheme less pessimistic, while the schedulability guarantee afforded to any given application remains intact. Such modifications to the runtime protocol can result in significant benefits with respect to other important metrics. An enhanced runtime protocol is designed for the Adaptive Mixed-Criticality (AMC) scheduling scheme. This protocol retains the same analysis, while ensuring that in the event of high-criticality behavior, the system degrades less often and remains degraded for a shorter time, resulting in far fewer low-criticality jobs that either miss their deadlines or are not executed.

While academia favours general research that is applicable to a large class of systems, this paper highlights the necessity of research into specific scenarios and aims to increase its acceptance in the real-time systems community. We argue that such research is not only motivated by greater applicability to industry, but that specialization can also provide valuable information from a purely academic perspective. In addition, the trade-offs between generalization and specialization are examined, considering not only theoretical performance, but also the impact on essential non-functional properties that are important for industry, namely composability, robustness, extensibility, and parametric simplicity.

Abstract This paper presents results and observations from a survey of 120 industry practitioners in the field of real-time embedded systems. The survey provides insights into the characteristics of the systems being developed today and identifies important trends for the future. It extends the results from the survey data to the broader population that it is representative of, and discusses significant differences between application domains. The survey aims to inform both academics and practitioners, helping to avoid divergence between industry practice and academic research. The value of this research is highlighted by a study showing that the aggregate findings of the survey are not common knowledge in the real-time systems community.

Abstract Timing verification of multi-core systems is complicated by contention for shared hardware resources between co-running tasks on different cores. This paper introduces the Multi-core Resource Stress and Sensitivity (MRSS) task model that characterizes how much stress each task places on resources and how much it is sensitive to such resource stress. This model facilitates a separation of concerns, thus retaining the advantages of the traditional two-step approach to timing verification (i.e. timing analysis followed by schedulability analysis). Response time analysis is derived for the MRSS task model, providing efficient context-dependent and context independent schedulability tests for both fixed priority preemptive and fixed priority non-preemptive scheduling. Dominance relations are derived between the tests, along with complexity results, and proofs of optimal priority assignment policies. The MRSS task model is underpinned by a proof-of-concept industrial case study. The problem of task allocation is considered in the context of the MRSS task model, with Simulated Annealing shown to provide an effective solution.

Timing verification of multi-core systems is complicated by contention for shared hardware resources between co-running tasks on different cores. This paper introduces the Multi-core Resource Stress and Sensitivity (MRSS) task model that characterizes how much stress each task places on resources and how much it is sensitive to such resource stress. This model facilitates a separation of concerns, thus retaining the advantages of the traditional two-step approach to timing verification (i.e. timing analysis followed by schedulability analysis). Response time analysis is derived for the MRSS task model, providing efficient context-dependent and context independent schedulability tests for both fixed priority preemptive and fixed priority non-preemptive scheduling. Dominance relations are derived between the tests, and proofs of optimal priority assignment provided. The MRSS task model is underpinned by a proof-of-concept industrial case study.

This paper presents results and observations from a survey of 120 industry practitioners in the field of real-time embedded systems. The survey provides insights into the characteristics of the systems being developed today and identifies important trends for the future. The survey aims to inform both academics and practitioners, helping to avoid divergence between industry practice and fundamental academic research.

This paper provides analysis of the Adaptive Mixed Criticality (AMC) scheduling scheme for mixed-criticality systems that include tasks with arbitrary deadlines and semi-clairvoyant behavior. An arbitrary deadline task is one that can have a deadline that may be greater than its period. A semi-clairvoyant task is one that upon arrival of each job, reveals which of its two WCET parameters will be respected. This enables an earlier switch to be made from the normal mode of operation to the abnormal mode. The previously published schedulability test AMC-max is modified to cater for both of these extensions. Evaluation shows that there is a significant improvement in schedulability for semi-clairvoyant tasks over non-clairvoyant, and for arbitrary-deadline tasks over considering those deadlines as being constrained by the task's period.

This paper introduces the Dirichlet-Rescale (DRS) algorithm. The DRS algorithm provides an efficient general-purpose method of generating n-dimensional vectors of components (e.g. task utilizations), where the components sum to a specified total, each component conforms to individual constraints on the maximum and minimum values that it can take, and the vectors are uniformly distributed over the valid region of the domain of all possible vectors, bounded by the constraints.The DRS algorithm can be used to improve the nuance and quality of empirical studies into the effectiveness of schedulability tests for real-time systems; potentially making them more realistic, and leading to new conclusions. It is efficient enough for use in large-scale studies where millions of task sets need to be generated. Further, the constraints on individual task utilizations can be used for fine-grained control of task set parameters enabling more detailed exploration of schedulability test behavior. Finally, the real power of the algorithm lies in the fact that it can be applied recursively, with one vector acting as a set of constraints for the next. This is particularly useful in task set generation for mixed criticality systems and multi-core systems, where task utilizations are either multi-valued or can be decomposed into multiple constituent parts.

This article describes the motivation, design, analysis, and configuration of the criticality-aware multi-hop wireless communication protocol AirTight. Wireless communication has become a crucial part of the infrastructure of many cyber-physical applications. Many of these applications are real-time and also mixed-criticality, in that they have components/subsystems with different consequences of failure. Wireless communication is inevitably subject to levels of external interference. In this article, we represent this interference using a criticality-aware fault model; for each level of temporal interference in the fault model, we guarantee the timing behaviour of the protocol (i.e., we guarantee that packet deadlines are satisfied for certain levels of criticality). Although a new protocol, AirTight is built upon existing standards such as IEEE 802.15.4. A prototype implementation and protocol-accurate simulator have been produced. This article develops a series of schedulability analysis techniques for single-channel and multichannel wireless Cyber-Physical Systems (CPS). Heuristics are specified and evaluated as the starting point of design space exploration. Genetic algorithms are then defined and evaluated to assess their performance in developing schedule tables incorporating multichannel allocations in these systems.

This paper assesses the potential for mechanised assistance in the formulation of schedulability tests. The novel idea is to use evolutionary algorithms to semi-automate the process of deriving response time analysis equations. The proof of concept presented in this paper focuses on the synthesis of mathematical expressions for the schedulability analysis of messages on Controller Area Network (CAN). This problem is of particular interest, since the original analysis developed in the early 1990s was later found to be flawed. Further, as well as known exact tests that have been formally proven, there are a number of useful sufficient tests of pseudo-polynomial complexity and closed-form polynomial-time upper bounds on response times that provide useful comparisons.

This paper describes four impact case studies where real-time systems research has been successfully transferred into industrial practice. In three cases, the technology created was translated into a viable commercial product via a start-up company. This technology transfer led to the creation and sustaining of a large number of high technology jobs over a 20 year period. The final case study involved the direct transfer of research results into an engineering company. Taken together, all four case studies have led to significant advances in automotive electronics and avionics, providing substantial returns on investment for the companies using the technology.

In mixed criticality systems, it is vital to ensure that there is sufficient separation between tasks of LO- and HI-criticality applications, so that the behavior or mis-behavior of the former cannot affect the functional or timing correctness of the latter. To ensure appropriate spatial isolation, the memory address spaces and cache use by LO- and HI-criticality tasks must be distinct. A consequence of this separation is that the cost of switching between tasks of the same criticality can be small, whereas the cost of context switching between tasks of different criticality levels can be much larger. In this paper, we focus on integrating the differing context switch costs into fixed priority preemptive scheduling, and the two mixed criticality scheduling schemes based on it: SMC and AMC. We derive simple, refined, and multi-set analyses for each scheme. Further, we show that the refined and multi-set analyses are not compatible with Audsley's Optimal Priority Assignment algorithm, we therefore propose a heuristic priority assignment policy aimed at reducing the number of high cost context switches. Our evaluation is grounded in measurements of context switch times (save and restore costs) from a prototype implementation of an explicitly managed cache on an FPGA. The evaluation shows the effectiveness of the derived analyses and the proposed priority assignment policy.

The OS scheduler's memory and runtime overheads form crucial design constraints for embedded systems implemented on low-cost hardware platforms. Table-driven scheduling can provide a high level of schedulability; however, it also consumes significant amounts of memory. By contrast, effective non-preemptive scheduling policies, such as the non-work-conserving Critical-Window EDF (CW-EDF), have low memory usage, but substantial runtime overheads. This paper aims to achieve efficient and effective non-preemptive scheduling by using a First-In-First-Out (FIFO) scheduling policy combined with a novel offset tuning technique. This technique enables the FIFO policy to reproduce a given feasible schedule, such as that followed by CW-EDF, resulting in a high level of schedulability, combined with comparatively low runtime overheads. Further, by using a small number of offsets per task, memory overheads are also tightly constrained. The proposed solution is evaluated in terms of runtime overhead, memory consumption, and schedulability ratio, using a prototype implementation on an Arduino board. This shows that FIFO with offset tuning can match the schedulability ratio of CW-EDF, while typically exhibiting lower scheduling overheads and memory consumption than the state-of-the-art Offline Equivalence technique, which is based on Non-Preemptive Fixed Priority (NP-FP) scheduling.

This paper describes the motivation, design, analysis and implementation of a new protocol for critical wireless communication called AirTight. Wireless communication has become a crucial part of the infrastructure of many cyber-physical applications. Many of these applications are real-time and also mixed-criticality, in that they have components/subsystems with different consequences of failure. Wireless communication is inevitably subject to levels of external interference. In this paper we represent this interference using a criticality-aware fault model; for each level of interference in the fault model we guarantee the timing behaviour of the protocol (i.e. we guarantee that packet deadlines are satisfied for certainly levels of criticality). Although a new protocol, AirTight is built upon existing standards such as IEEE 802.15.4. A prototype implementation and protocol-accurate simulator, which are also built upon existing technologies, demonstrate the effectiveness and functionality of the protocol.

In this paper, we introduce a multicore response time analysis ( MRTA ) framework , which decouples response time analysis from a reliance on context-independent WCET values. Instead, the analysis formulates response times directly from the demands placed on different hardware resources. The MRTA framework is extensible to different multicore architectures, with a variety of arbitration policies for the common interconnects, and different types and arrangements of local memory. We instantiate the framework for single level local data and instruction memories (cache or scratchpads), for a variety of memory bus arbitration policies, including: Round-Robin, FIFO, Fixed-Priority, Processor-Priority, and TDMA, and account for DRAM refreshes. The MRTA framework provides a general approach to timing verification for multicore systems that is parametric in the hardware configuration and so can be used at the architectural design stage to compare the guaranteed levels of real-time performance that can be obtained with different hardware configurations. We use the framework in this way to evaluate the performance of multicore systems with a variety of different architectural components and policies. These results are then used to compose a predictable architecture, which is compared against a reference architecture designed for good average-case behaviour. This comparison shows that the predictable architecture has substantially better guaranteed real-time performance, with the precision of the analysis verified using cycle-accurate simulation.

This paper introduces analyses of write-back caches integrated into response-time analysis for fixed-priority preemptive and non-preemptive scheduling. For each scheduling paradigm, we derive four different approaches to computing the additional costs incurred due to write backs. We show the dominance relationships between these different approaches and note how they can be combined to form a single state-of-the-art approach in each case. The evaluation explores the relative performance of the different methods using a set of benchmarks, as well as making comparisons with no cache and a write-through cache. We also explore the effect of write buffers used to hide the latency of write-through caches. We show that depending upon the depth of the buffer used and the policies employed, such buffers can result in domino effects. Our evaluation shows that even ignoring domino effects, a substantial write buffer is needed to match the guaranteed performance of write-back caches.

Fixed priority scheduling is used in many real-time systems; however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive earliest deadline first (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP). As this lower bound matches a recently published upper bound for the same quantity, it closes the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, in other words, there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive the exact speed-up factor required to guarantee FP-P feasibility of any constrained-deadline FP-NP feasible task set.

Probabilistic hard real-time systems, based on hardware architectures that use a random replacement cache, provide a potential means of reducing the hardware over-provision required to accommodate pathological scenarios and the associated extremely rare, but excessively long, worst-case execution times that can occur in deterministic systems. Timing analysis for probabilistic hard real-time systems requires the provision of probabilistic worst-case execution time (pWCET) estimates. The pWCET distribution can be described as an exceedance function which gives an upper bound on the probability that the execution time of a task will exceed any given execution time budget on any particular run. This paper introduces a more effective static probabilistic timing analysis (SPTA) for multi-path programs. The analysis estimates the temporal contribution of an evict-on-miss, random replacement cache to the pWCET distribution of multi-path programs. The analysis uses a conservative join function that provides a proper over-approximation of the possible cache contents and the pWCET distribution on path convergence, irrespective of the actual path followed during execution. Simple program transformations are introduced that reduce the impact of path indeterminism while ensuring sound pWCET estimates. Evaluation shows that the proposed method is efficient at capturing locality in the cache, and substantially outperforms the only prior approach to SPTA for multi-path programs based on path merging. The evaluation results show incomparability with analysis for an equivalent deterministic system using an LRU cache. For some benchmarks the performance of LRU is better, while for others, the new analysis techniques show that random replacement has provably better performance.

Certification authorities require correctness and survivability. In the temporal domain this requires a convincing argument that all deadlines will be met under error free conditions, and that when certain defined errors occur the behaviour of the system is still predictable and safe. This means that occasional execution-time overruns should be tolerated and where more severe errors occur levels of graceful degradation should be supported. With mixed-criticality systems, fault tolerance must be criticality aware, i.e. some tasks should degrade less than others. In this paper a quantitative notion of robustness is defined, and it is shown how fixed priority-based task scheduling can be structured to maximise the likelihood of a system remaining fail operational or fail robust (the latter implying that an occasional job may be skipped if all other deadlines are met). Analysis is developed for fail operational and fail robust behaviour, optimal priority ordering is addressed and an experimental evaluation is described. Overall, the approach presented allows robustness to be balanced against schedulability. A designer would thus be able to explore the design space so defined.

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.

Schedulability analysis for tasks running on micro- processors with cache memory is incomplete without a treatment of Cache Related Preemption Delays (CRPD) and Cache Persistence Reload Overheads (CPRO). State-of-the-art analyses compute CRPD and CPRO independently, which might result in counting the same overhead more than once. In this paper, we analyze the pessimism associated with the independent calculation of CRPD and CPRO in comparison to an integrated approach. We answer two main questions: (1) Is it benecial to integrate the calculation of CRPD and CPRO? (2) When and to what extent can we gain in terms of schedulability by integrating the calculation of CRPD and CPRO? To achieve this, we (i) identify situations where considering CRPD and CPRO separately might result in overestimating the total memory overhead suffered by tasks, (ii) derive new analyses that integrate the calculation of CRPD and CPRO; and (iii) perform a thorough experimental evaluation using benchmarks to compare the performance of the integrated analysis against the separate calculation of CRPD and CPRO.

Commercial off-the-shelf programmable platforms for real-time systems typically contain a cache to bridge the gap between the processor speed and main memory speed. Because cache-related pre-emption delays (CRPD) can have a significant influence on the computation times of tasks, CRPD have been integrated in the response time analysis for fixed-priority pre-emptive scheduling (FPPS). This paper presents CRPD aware response-time analysis of sporadic tasks with arbitrary deadlines for fixed-priority pre-emption threshold scheduling (FPTS), generalizing earlier work. The analysis is complemented by an optimal (pre-emption) threshold assignment algorithm, assuming the priorities of tasks are given. We further improve upon these results by presenting an algorithm that searches for a layout of tasks in memory that makes a task set schedulable. The paper includes an extensive comparative evaluation of the schedulability ratios of FPPS and FPTS, taking CRPD into account. The practical relevance of our work stems from FPTS support in AUTOSAR, a standardized development model for the automotive industry. [(This paper forms an extended version of Bril et al. (in Proceedings of 35th IEEE real-time systems symposium (RTSS), 2014 ). The main extensions are described in Sect. 1.2 .]

Recent technological advances have led to an increasing gap between memory and processor performance, since memory bandwidth is progressing at a much slower pace than processor bandwidth. Pre-fetching techniques are traditionally used to bridge this gap and achieve high processor utilization while tolerating high memory latencies. Following this trend, new computational models have been proposed to split task execution in two consecutive phases: a memory phase in which the required instructions and data are pre-fetched to local memory (M-phase), and an execution phase in which the task is executed with no memory contention (C-phase). Decoupling memory and execution phases not only simplifies the timing analysis, but also allows a more efficient (and predictable) pipelining of memory and execution phases through proper co-scheduling algorithms. This paper takes a further step towards the design of smart co-scheduling algorithms for sporadic real-time tasks complying with the memory-computation (M/C) model, by proposing a theoretical framework aimed at tightly characterizing the schedulability improvement obtainable with the adopted M/C task model on single-core systems. In particular, a critical instant is identified for M/C tasks scheduled with fixed priority and an exact response time analysis with pseudo-polynomial complexity is provided. Then, we investigate the problem of priority assignment for M/C tasks, showing that a necessary condition to achieve optimality is to allow different priorities for the two phases. Our experiments show that the proposed techniques provide a significant schedulability improvement with respect to classic execution models, placing an important building block towards the design of more efficient partitioned multi-core systems.

To move mixed criticality research into industrial practice requires models whose run-time behaviour is acceptable to systems engineers. Certain aspects of current models, such as abandoning lower criticality tasks when certain situations arise, do not give the robustness required in application domains such as the automotive and aerospace industries. In this paper a new bailout protocol is developed that still guarantees high criticality software but minimises the negative impact on lower criticality software via a timely return to normal operation. We show how the bailout protocol can be integrated with existing techniques, utilising both offline slack and online gain-time to further improve performance. Static analysis is provided for schedulability guarantees, while scenario-based evaluation via simulation is used to explore the effectiveness of the protocol.

In hard real-time systems, cache partitioning is often suggested as a means of increasing the predictability of caches in pre-emptively scheduled systems: when a task is assigned its own cache partition, inter-task cache eviction is avoided, and timing verification is reduced to the standard worst-case execution time analysis used in non-pre-emptive systems. The downside of cache partitioning is the potential increase in execution times. In this paper, we evaluate cache partitioning for hard real-time systems in terms of overall schedulability. To this end, we examine the sensitivity of (i) task execution times and (ii) pre-emption costs to the size of the cache partition allocated and present a cache partitioning algorithm that is optimal with respect to taskset schedulability. We also devise an alternative algorithm which primarily optimises schedulability but also minimises processor utilization. We evaluate the performance of cache partitioning compared to state-of-the-art pre-emption cost analysis based on benchmark code and on a large number of synthetic tasksets with both fixed priority and EDF scheduling. This allows us to derive general conclusions about the usability of cache partitioning and identify taskset and system parameters that influence the relative effectiveness of cache partitioning. We also examine the improvement in processor utilization obtained using an alternative cache partitioning algorithm, and the tradeoff in terms of increased analysis time.

To move mixed criticality research into industrial practice requires models whose run-time behaviour is acceptable to systems engineers. Certain aspects of current models, such as abandoning lower criticality tasks when certain situations arise, do not give the robustness required in application domains such as the automotive and aerospace industries. In this paper a new bailout protocol is developed that still guarantees high criticality tasks but minimises the negative impact on lower criticality tasks via a timely return to normal operation. We show how the bailout protocol can be integrated with existing techniques, utilising offline slack to further improve performance. Static analysis is provided for the strong schedulability guarantees, while scenario based evaluation via simulation is used to explore the effectiveness of the protocol.

Schedulability analyses, while valuable in theoretical research, cannot be used in practice to reason about the timing behaviour of a real-time system without including the overheads induced by the implementation of the scheduling algorithm. In this paper, we provide an overhead-aware schedulability analysis based on demand bound functions for two hard real-time semi-partitioned scheduling algorithms, EDF-WM and C=D. This analysis is based on a novel implementation that uses a global clock to reduce the overheads incurred due to the release jitter of migrating subtasks. The analysis is used to guide the respective off-line task assignment and splitting procedures. Finally, results of an evaluation are provided highlighting how the different algorithms perform with and without a consideration of overheads.

Fixed priority scheduling is used in many real-time systems, however, both preemptive and non-preemptive variants (FP-P and FP-NP) are known to be sub-optimal when compared to an optimal uniprocessor scheduling algorithm such as preemptive Earliest Deadline First (EDF-P). In this paper, we investigate the sub-optimality of fixed priority non-preemptive scheduling. Specifically, we derive the exact processor speed-up factor required to guarantee the feasibility under FP-NP (i.e. schedulablability assuming an optimal priority assignment) of any task set that is feasible under EDF-P. As a consequence of this work, we also derive a lower bound on the sub-optimality of non-preemptive EDF (EDF-NP), which since it matches a recently published upper bound gives the exact sub-optimality for EDF-NP. It is known that neither preemptive, nor non-preemptive fixed priority scheduling dominates the other, i.e., there are task sets that are feasible on a processor of unit speed under FP-P that are not feasible under FP-NP and vice-versa. Hence comparing these two algorithms, there are non-trivial speedup factors in both directions. We derive the exact speed-up factor required to guarantee the FP-NP feasibility of any FP-P feasible task set. Further, we derive upper and lower bounds on the speed-up factor required to guarantee FP-P feasibility of any FP-NP feasible task set. Empirical evidence suggests that the lower bound may be tight, and hence equate to the exact speed-up factor in this case.

This paper introduces an effective Static Probabilistic Timing Analysis (SPTA) for multi-path programs. The analysis estimates the temporal contribution of an evict-on-miss, random replacement cache to the probabilistic Worst-Case Execution Time (pWCET) distribution of multi-path programs. The analysis uses a conservative join function that provides a proper overapproximation of the possible cache contents and the pWCET distribution on path convergence, irrespective of the actual path followed during execution. Simple program transformations are introduced that reduce the impact of path indeterminism while ensuring sound pWCET estimates. Evaluation shows that the proposed method is efficient at capturing locality in the cache, and substantially outperforms the only prior approach to SPTA for multi-path programs based on path merging. The evaluation results show incomparability with analysis for an equivalent deterministic system using an LRU cache.

This article introduces schedulability analysis for Global Fixed Priority Scheduling with Deferred Preemption (gFPDS) for homogeneous multiprocessor systems. gFPDS is a superset of Global Fixed Priority Preemptive Scheduling (gFPPS) and Global Fixed Priority Nonpreemptive Scheduling (gFPNS). We show how schedulability can be improved using gFPDS via appropriate choice of priority assignment and final nonpreemptive region lengths, and provide algorithms that optimize schedulability in this way. Via an experimental evaluation we compare the performance of multiprocessor scheduling using global approaches: gFPDS, gFPPS, and gFPNS, and also partitioned approaches employing FPDS, FPPS, and FPNS on each processor.

In this paper, we investigate Static Probabilistic Timing Analysis (SPTA) for single processor systems that use a cache with an evict-on-miss random replacement policy. We show that previously published formulae for the probability of a cache hit can produce results that are optimistic and unsound when used to compute probabilistic Worst-Case Execution Time (pWCET) distributions. We investigate the correctness, optimality, and precision of different approaches to SPTA. We prove that one of the previously published formulae for the probability of a cache hit is optimal with respect to the limited information that it uses. We improve upon this formulation by using extra information about cache contention. To investigate the precision of various approaches to SPTA, we introduce a simple exhaustive method that computes a precise pWCET distribution, albeit at the cost of exponential complexity. Further, we integrate this precise approach, applied to small numbers of frequently accessed memory blocks, with imprecise analysis of other memory blocks, to form a combined approach that improves precision, without significantly increasing its complexity. The performance of the various approaches are compared on benchmark programs.

In hard real-time systems, cache partitioning is often suggested as a means of increasing the predictability of caches in pre-emptively scheduled systems: when a task is assigned its own cache partition, inter-task cache eviction is avoided, and timing verification is reduced to the standard worst case execution time (WCET) analysis used in non-pre-emptive systems. The downside of cache partitioning is the potential increase in execution times. In this paper, we evaluate cache partitioning for hard real time systems in terms of overall schedulability. To this end, we examine the sensitivity of task execution times to the size of the cache partition allocated and present a cache partitioning algorithm that is optimal with respect to task set schedulability. We then evaluate the performance of cache partitioning compared to state-of-the-art pre-emption cost analysis based on benchmark code and on a large number of synthetic task sets. This allows us to derive general conclusions about the usability of cache partitioning and identify task set and system parameters that influence the relative e effectiveness of cache partitioning.

Automotive embedded real-time systems such as Engine Management utilise cyclic tasks that are activated periodically based on angular rotation rather than time. As well as having variable inter-arrival times, these tasks also have deadlines and worst-case execution times that are dependent on angular velocity i.e. engine speed or rpm. Such tasks exhibit Variable Rate-dependent Behaviour (VRB). In this paper, we introduce response time analysis for systems comprising VRB and sporadic tasks under fixed priority scheduling. Sufficient schedulability tests are introduced; from simple linear upper bounds on interference, to a more complex analysis using information about the physical limitations of the system to provide constraints for an ILP formulation of the problem.

Cache-related pre-emption delays (CRPD) have been integrated into the schedulability analysis of sporadic tasks with constrained deadlines for fixed-priority pre-emptive scheduling (FPPS). This paper generalizes that work by integrating CRPD into the schedulability analysis of tasks with arbitrary deadlines for fixed-priority pre-emption threshold scheduling (FPTS). The analysis is complemented by an optimal threshold assignment algorithm that minimizes CRPD. The paper includes a comparative evaluation of the schedulability ratios of FPPS and FPTS, for constrained-deadline tasks, taking CRPD into account.

Adaptive Mixed Criticality (AMC) scheduling has previously been shown to be the most effective fixed priority approach for scheduling mixed criticality systems, while the idea of final non-preemptive regions has been shown to improve the schedulability of systems with a single criticality level. In this paper, we combine AMC with the concept of non-preemptive regions by making the final part of each task's execution at each criticality level non-preemptive. We derive schedulability analysis for this approach, and provide an effective algorithm for choosing each task's priority and the durations of its non-preemptive regions. Evaluations illustrate the benefits of this approach in terms of increased schedulability.

We describe and evaluate explicit reservation of cache memory to reduce the cache-related preemption delay (CRPD) observed when tasks share a cache in a preemptive multitasking hard real-time system. We demonstrate the approach using measurements obtained from a hardware prototype, and present schedulability analyses for systems that share a cache by explicit reservation. These analyses form the basis for a series of experiments to further evaluate the approach. We find that explicit reservation is most useful for larger task sets with high utilization. Some task sets cannot be scheduled with a conventional cache, but are schedulable with explicit reservation.

An increasingly important trend in the design of real-time and embedded systems is the integration of components with different levels of criticality onto a common hardware platform. Where the platform incorporates a communication media it is necessary for that media to be able to safely and efficiently transfer messages of different criticality levels. In this paper we consider the Controller Area Network (CAN), and define mixed criticality protocols that could form the basis of a Trusted Network Component for CAN. Sufficient response-time analysis is derived for these protocols and an optimal priority assignment scheme is provided. Evaluations illustrate the benefits of the schemes.

This paper integrates analysis of probabilistic cache related pre-emption delays (pCRPD) and static probabilistic timing analysis (SPTA) for multipath programs running on a hardware platform that uses an evict-on-miss random cache replacement policy. The SPTA computes an upper bound on the probabilistic worst-case execution time (pWCET) of the program, which is an exceedance function giving the probability that the execution time of the program will exceed any given value on any particular run. The pCRPD analysis determines the maximum effect of a pre-emption on the pWCET. The integration between SPTA and pCRPD updates the pWCET to account for the effects of one or more pre-emptions at any arbitrary points in the program. This integration is a necessary step enabling effective schedulability analysis for probabilistic hard real-time systems that use pre-emptive or co-operative scheduling. The analysis is illustrated via a number of benchmark programs.

Cache memories have been introduced into embedded systems to prevent memory access times from becoming an unacceptable performance bottleneck. Memory and cache are split into blocks containing instructions and data. During a pre-emption, blocks from the pre-empting task can evict those of the pre-empted task. When the pre-empted task is resumed, if it then has to re-load the evicited blocks, cache related pre-emption delays (CRPD) are introduced which then affect schedulability of the task. In this paper, we show how existing approaches for calculating CRPD for FP scheduling can be adapted and integrated into schedulability analysis for EDF. We then compare the performance of the different approaches against an existing approach for calculating CRPD for EDF. Using a case study and empirical evaluation, we show the benefits of our CRPD analysis.

This paper introduces schedulability analysis for global fixed priority scheduling with deferred pre-emption (gFPDS) for homogeneous multiprocessor systems. gFPDS is a superset of global fixed priority pre-emptive scheduling (gFPPS) and global fixed priority non-pre-emptive scheduling (gFPNS). We show how schedulability can be improved via appropriate choice of priority assignment and final non-pre-emptive region lengths, and we provide algorithms which optimize schedulability in this way. An experimental evaluation shows that gFPDS significantly outperforms both gFPPS and gFPNS.

In this paper a limited pre-emptive global fixed task priority scheduling policy for multiprocessors is presented. This scheduling policy is a generalization of global fully pre-emptive and non-pre-emptive fixed task priority policies for platforms with at least two homogeneous processors. The scheduling protocol devised is such that a job can only be blocked at most once by a body of lower priority non-pre-emptive workload. The presented policy dominates both fully pre-emptive and fully non-pre-emptive with respect to schedulability. A sufficient schedulability test is presented for this policy. Several approaches to estimate the blocking generated by lower priority non-pre-emptive regions are presented. As a last contribution it is experimentally shown that, on the average case, the number of pre-emptions observed in a schedule are drastically reduced in comparison to global fully pre-emptive scheduling.

The schedulability of systems using fixed priority pre-emptive scheduling can be improved by the use of non-pre-emptive regions at the end of each task's execution, an approach referred to as deferred pre-emption. Choosing the appropriate length for the final non-pre-emptive region of each task is a trade-off between improving the worst-case response time of the task itself and increasing the amount of blocking imposed on higher priority tasks. In this paper we present an optimal algorithm for determining both the priority ordering of tasks and the lengths of their final non-pre-emptive regions. This algorithm is optimal for fixed priority scheduling with deferred pre-emption, in the sense that it is guaranteed to find a schedulable combination of priority ordering and final non-pre-emptive region lengths if such a schedulable combination exists.

We present a multitasking scratchpad memory reuse scheme (MSRS) for the dynamic partitioning of scratchpad memory between tasks in a preemptive multitasking system. We specify a means to compute the worst-case response time (WCRT) and schedulability of task sets executed using MSRS. Our scratchpad-related preemption delay (SRPD) is an analog of cache-related preemption delay (CRPD), proposed in previous work as a way to compute the worst-case cost imposed upon a preempted task by preemption in a multitasking system. Unlike CRPD, however, SRPD is independent of the number of tasks and the local memory size. We compare SRPD with CRPD by experiment and determine that neither dominates the other, i.e. either may be better for certain task sets. However, MSRS leads to improved schedulability versus cache when contention for local memory space is high, either because the local memory size is small, or because the task set is large, provided that the cost of loading blocks from external memory to scratchpad is similar to the cost of loading blocks into cache.

Controller Area Network (CAN) is widely used in automotive applications. Existing schedulability analysis for CAN is based on the assumption that the highest priority message ready for transmission at each node on the network will be entered into arbitration on the bus. However, in practice, some CAN device drivers implement FIFO rather than priority-based queues invalidating this assumption. In this paper, we introduce response time analysis and optimal priority assignment policies for CAN messages in networks where some nodes use FIFO queues while other nodes use priority queues. We show, via a case study and experimental evaluation, the detrimental impact that FIFO queues have on the real-time performance of CAN.

The analysis of the real-time properties of an embedded communication system relies on finding upper bounds on the Worst-Case Response Time (WCRT) of the messages that are exchanged among the nodes on the network. The classical WCRT analysis of Controller Area Network (CAN) implicitly assumes that at any given time, each node is able to enter its highest priority ready message into arbitration. However, in reality, CAN controllers may have some characteristics, such as non-abortable transmit buffers, which may break this assumption. This paper provides analysis for networks that contain nodes with non-abortable transmit buffers, as well as nodes that meet the requirements of the classical analysis. The impact on message WCRTs due to a limited number of transmission buffers with non-abortable behaviour is examined via two case-studies.

This paper presents the Fixed Priority until Zero Laxity (FPZL) scheduling algorithm for multiprocessor realtime systems. FPZL is similar to global fixed priority preemptive scheduling, however, whenever a task reaches a state of zero laxity it is given the highest priority. FPZL is a minimally dynamic algorithm, in that the priority of a job can change at most once during its execution, bounding the number of pre-emptions. Polynomial time and pseudopolynomial time sufficient schedulability tests are derived for FPZL. These tests are then improved by computing upper bounds on the amount of execution that each task can perform in the zero laxity state. An empirical evaluation shows that FPZL is highly effective, with a significantly larger number of task sets deemed schedulable by the tests derived in this paper, than by state-of-the-art schedulability tests for Earliest Deadline until Zero Laxity (EDZL) scheduling.

In multicore processors, the execution environment is defined as the environment in which tasks run and it is determined by the hardware resources they get and the workload with which they are executed. Thus, different execution environments lead to different inter-task interferences accessing shared hardware resources due to conflicts with the other corunning tasks, making the WCET estimation of a task dependent on the execution environment in which it runs. Despite such dependency, current partitioned scheduling approaches use a single WCET estimation per task: typically the highest for all execution environments in which a task runs. In this paper we introduce IA3: an interference-aware allocation algorithm that considers not a single WCET estimation but a set of WCET estimations per task. IA3 is based on two novel concepts: the WCET-matrix and the WCET-sensitivity. The former associates every WCET estimation with its corresponding execution environment. The latter measures the impact of changing the execution environment on the WCET estimation. This allows IA3 to reduce the number of resources required to schedule a given taskset. In particular, our results show that in a four-core processor considering tasksets with a total utilization of 2.9, IA3 is able to schedule 70% of the tasksets using 3-cores while a classical partitioned approach with a First-Fit Decreasing heuristic is able to schedule only 5% of the tasksets using 3-cores.

Without the use of cache the increasing gap between processor and memory speeds in modern embedded microprocessors would have resulted in memory access times becoming an unacceptable bottleneck. In such systems, cache related pre-emption delays can be a significant proportion of task execution times. To obtain tight bounds on the response times of tasks in pre-emptively scheduled systems, it is necessary to integrate worst-case execution time analysis and schedulability analysis via the use of an appropriate model of pre-emption costs. In this paper, we introduce a new method of bounding pre-emption costs, called the ECB-Union approach. The ECB-Union approach complements an existing UCB-Union approach. We combine the two into a simple composite approach that dominates both. These approaches are integrated into response time analysis for fixed priority pre-emptively scheduled systems. Further, we extend this analysis to systems where tasks can access resources in mutual exclusion, in the process resolving omissions in existing models of pre-emption delays. A case study and empirical evaluation demonstrate the e?ectiveness of the ECB-Union and combined approaches for a wide range of di?erent cache configurations including cache utilization, cache set size, reuse, and block reload times.

Many safety-critical embedded systems are subject to certification requirements. However, only a subset of the functionality of the system may be safety-critical and hence subject to certification, the rest of the functionality is non safety-critical and does not need to be certified, or is certified to a lower level. The resulting mixed criticality system offers challenges both for static schedulability analysis and run-time monitoring. This paper considers a novel implementation scheme for fixed priority uniprocessor scheduling of mixed criticality systems. The scheme requires that jobs have their execution times monitored (as is usually the case in high integrity systems). An optimal priority assignment scheme is derived and sufficient response-time analysis is provided. The new scheme formally dominates those previously published. Evaluations illustrate the benefits of the scheme.

This paper addresses the problem of priority assignment in multiprocessor real-time systems using global fixed task-priority pre-emptive scheduling. In this paper, we prove that Audsley's Optimal Priority Assignment (OPA) algorithm, originally devised for uniprocessor scheduling, is applicable to the multiprocessor case, provided that three conditions hold with respect to the schedulability tests used. Our empirical investigations show that the combination of optimal priority assignment policy and a simple compatible schedulability test is highly effective, in terms of the number of tasksets deemed to be schedulable. We also examine the performance of heuristic priority assignment policies such as Deadline Monotonic, and an extension of the TkC priority assignment policy called DkC that can be used with any schedulability test. Here we find that Deadline Monotonic priority assignment has relatively poor performance in the multiprocessor case, while DkC priority assignment is highly effective.

This paper derives closed form upper bounds on the response times of tasks in fixed priority real-time systems. These bounds are valid for tasks with arbitrary deadlines, release jitter, and blocking. Response time upper bounds are given for tasks that are scheduled pre-emptively, cooperatively with intervals where pre-emption is deferred, and non-preemptively. The set of upper bounds for n tasks can be computed in O(n) time, providing a linear-time sufficient schedulability test, applicable to complex commercial real-time systems.

Efficient exact schedulability tests are required both for on-line admission of applications to dynamic systems and as an integral part of design tools for complex distributed real-time systems. This paper addresses performance issues with exact response time analysis (RTA) for fixed priority preemptive systems. Initial values are introduced that improve the efficiency of the standard RTA algorithm (i) when exact response times are required, and (ii) when only exact schedulability need be determined. The paper also explores modifications to the standard RTA algorithm, including; the use of a response time upper bound to determine when exact analysis is needed, incremental computation aimed at faster convergence, and checking tasks in reverse priority order to identify unschedulable task sets early. The various initial values and algorithm implementations are compared by means of experiments on a PC recording the number of iterations required, and execution time measurements on a real-time embedded microprocessor. Recommendations are provided for engineers tasked with the problem of implementing exact schedulability tests, as part of on-line acceptance tests and spare capacity allocation algorithms, or as part of off-line system design tools.

This paper focuses on priority assignment for realtime systems using fixed priority scheduling. It introduces and defines the concept of a "robust" priority ordering: the most appropriate priority ordering to use in a system subject to variable amounts of additional interference from sources such as interrupts, operating system overheads, exception handling, cycle stealing, and task execution time overruns. The paper describes a robust priority assignment algorithm that can find the robust priority ordering for a wide range of fixed priority system models and additional interference functions. Proofs are given for a number of interesting theorems about robust priority assignment, and the circumstances under which a "deadline minus jitter" monotonic partial ordering forms part of the robust ordering. The paper shows that "deadline minus jitter" monotonic priority ordering is the robust priority ordering for a specific class of system, and that this property holds essentially independent of the additional interference function.

Controller Area Network (CAN) is used extensively in automotive applications, with in excess of 400 million CAN enabled microcontrollers manufactured each year. In 1994 schedulability analysis was developed for CAN, showing how worst-case response times of CAN messages could be calculated and hence guarantees provided that message response times would not exceed their deadlines. This seminal research has been cited in over 200 subsequent papers and transferred to industry in the form of commercial CAN schedulability analysis tools. These tools have been used by a large number of major automotive manufacturers in the design of in-vehicle networks for a wide range of cars, millions of which have been manufactured during the last decade. This paper shows that the original schedulability analysis given for CAN messages is flawed. It may provide guarantees for messages that will in fact miss their deadlines in the worst-case. This paper provides revised analysis resolving the problems with the original approach. Further, it highlights that the priority assignment policy, previously claimed to be optimal for CAN, is not in fact optimal and cites a method of obtaining an optimal priority ordering that is applicable to CAN. The paper discusses the possible impact on commercial CAN systems designed and developed using flawed schedulability analysis and makes recommendations for the revision of CAN schedulability analysis tools.

This paper focuses on resource sharing in hierarchical fixed priority pre-emptive systems where a number of separate applications, each with its own server, reside on a single processor. It defines the hierarchical stack resource policy, an appropriate global resource access policy that bounds priority inversion and also limits interference due to overruns during resource access. The paper provides detailed response time analysis enabling the schedulability of application servers and tasks to be determined for systems with local and global resource access. This analysis is applicable to real-world systems where server-based applications need mutually exclusive access to shared resources such as communications buffers, peripheral devices, operating system calls and data structures shared with interrupt handlers

This paper focuses on the hierarchical scheduling of systems where a number of separate applications reside on a single processor. It addresses the particular case where fixed priority pre-emptive scheduling is used at both global and local levels, with a server associated with each application. Using response time analysis, an exact schedulability test is derived for application tasks. This test improves on previously published work. The analysis is extended to the case of harmonic tasks that can be bound to the release of their server. These tasks exhibit improved schedulability indicating that it is advantageous to choose server periods that enable some tasks to be bound to the release of their server. The use of periodic, sporadic and deferrable servers is considered with the conclusion that the simple periodic server dominates both sporadic and deferrable servers when the metric is application task schedulability

In this paper, we present a new strategy for scheduling tasks with soft deadlines in real-time systems containing periodic, sporadic and adaptive tasks with hard deadlines. In such systems, much of the spare capacity present is due to sporadic and adaptive tasks not arriving at their maximum rate. Offline methods of identifying spare capacity such as the Deferrable Server or Priority Exchange Algorithm are unable to make this spare capacity available as anything other than a background service opportunity for soft tasks. Further, more recent methods such as dynamic Slack Stealing require computationally expensive re-evaluation of the available slack in order to reclaim such spare capacity. By comparison, the Dual Priority approach presented in this paper provides an efficient and effective means of scheduling soft task in this case.

Adaptive and dynamic behaviour is seen as one of the key characteristics of next generation hard real-time systems. Whilst fixed priority pre-emptive scheduling is rapidly becoming a de facto standard in real-time systems engineering, it remains inflexible in its purest form. One method of increasing flexibility is via the incorporation of optional components into processes with hard deadlines. Such components are not guaranteed off-line, but may be accepted at run-time if sufficient spare capacity becomes available. This paper describes new mechanisms which are required to schedule effectively optional components: mechanisms which enable spare capacity to be detected early and on-line guarantees to be given.>

This paper addresses the problem of jointly scheduling tasks with both hard and soft time constraints. We present a new analysis which builds upon previous research into slack stealing algorithms. Our analysis determines the maximum processing time which may be stolen from hard deadline periodic or sporadic tasks, without jeopardising their timing constraints. It extends to tasks with characteristics such as synchronization, release jitter and stochastic execution times, as well as forming the basis for a family of optimal and approximate slack stealing algorithms.>