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 .]

This work investigates the composition of interdependent software components on a shared platform from a timing perspective. Because we consider software components for vehicular systems, which are often sensitive to timing, the individual components and the composed system require timing analysis. In order to support independent development of components, the real-time systems community proposed hierarchical scheduling frameworks (HSFs). HSFs in essence provide a virtual platform to individual components, including well-defined protocols for their synchronization. In this paper, we give an overview of recent research for applying HSFs into in-vehicle technology standards and we look ahead to some future challenges regarding the safety certification of such systems.

In this paper, we compare and survey different ways to model the scheduling delays corresponding to non-preemptive critical sections being executed by the tasks of different components that ultimately need to share one processor. We focus on the performance of compositional timing analyses for systems and we compare different protocols for the arbitration of tasks that wish to execute critical sections. Such analysis methods support timing predictable composition of independently validated components. This validation consists of analyzing the worst-case impact of critical sections on the schedules of the component's tasks. Finally, we evaluate the performance of the analysis methods by means of a simulation study.

Simulations are often used to improve the development and test time of industrial embedded systems in different domains, such as healthcare, railway, automobile and aerospace. This paper introduces a general framework capable of simulating real components simultaneously with simulated ones, in real-time, and with a low impact on the performance of the overall system. Our framework is loosely dependent on the application and the domain where the application is developed in. More importantly, it enhances interoperability and reuse, because it paves the way to reuse existing simulating tools and models and to integrate separately developed models from earlier stages in the design into a single coherent simulation.

In this paper we consider various flavors of the stack resource policy (SRP) for arbitrating access to shared resources in a hierarchical scheduling framework (HSF) upon a uni-processor. We propose algorithms for exploring and selecting the (local) resource ceilings within components, such that it results in an optimal composition of resource-sharing components in an HSF. Existing methods are non-optimal, because (i) they optimize just the length of global non-preemptive execution of tasks and (ii) they do not detect whether or not resources are shared globally (i.e., between tasks of different components). Lifting these limitations leads to an exponential growth of the design space. This paper contributes a fast three-step methodology which lifts these limitations, i.e., we apply the SRP at each level of the HSF to just the resources being shared. Our algorithm selects those component interfaces (i.e., by fixing the local resource ceilings of each component) that minimize the system load.

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.

Many embedded systems have complex timing constraints and, at the same time, have flexibility requirements which prohibit offline planning of the entire system. To support a mixture of time-triggered and event-triggered tasks, some industrial systems deploy a table-driven dispatcher for time-triggered tasks complemented with a preemptive scheduler to allocate the free time slots to event-driven tasks. Contrary to fully preemptive scheduling, limiting the preemptions of tasks to fixed preemptions points may reduce memory requirements and it alleviates the preemption costs in the system. We revisit slotshifting, which at run time mixes time-triggered and event-triggered tasks in a preemptive EDF schedule. In this paper, we extend slotshifting with limited-preemptive execution of event-triggered tasks. We present a synchronization protocol to arbitrate the executions of non-preemptive regions, so that time-triggered tasks keep meeting their timing constraints implicitly. Furthermore, we investigate how to disable preemptions of event-triggered tasks during the execution of the offline-scheduled time-triggered tasks, while keeping the feature of slotshifting to reallocate their slots of execution dynamically at run time.

Fixed-priority scheduling with deferred preemption(FPDS) and fixed-priority scheduling with preemption thresholds(FPTS) have been proposed in the literature as viable alternatives to fixed-priority preemptive scheduling (FPPS), that reduce memory requirements, reduce the cost of arbitrary preemptions, and may improve the feasibility of a task set even when preemption overheads are neglected. This paper aims at advancing the relative strength of limited preemptive schedulers by combining FPDS and FPTS. In particular, we present a refinement of FPDS with preemption thresholds for both jobs and sub-jobs, termed FPGS. We provide an exact schedulability analysis for FPGS, and show how to maximize the feasibility of a set of sporadic tasks under FPGS for given priorities, computation times, periods, and deadlines of tasks. We evaluate the effectiveness of FPGS by comparing the feasibility of task sets under FPGS with other fixed-priority scheduling algorithms by means of a simulation. Our experiments show that FPGS allows an increase of the number of task sets that are schedulable under fixed-priority scheduling.

Many embedded systems have complex timing constraints and, at the same time, have flexibility requirements which prohibit offline planning of the entire system. To support a mixture of time-triggered and event-triggered tasks, some industrial systems deploy a real-time operating system (RTOS) with a table-driven dispatcher complemented with a preemptive scheduler to allocate free time slots to event-driven tasks. Rather than allocating dedicated time-slots to time-triggered tasks, we propose to dynamically re-allocate time-slots of time-triggered tasks within a pre-computed time range to maximize the available processing capacity for event-triggered tasks. Although the concept - called slotshifting - is not new, we are unaware of a commercial RTOS with such support. After identifying the mechanisms for an RTOS implementation of slotshifting, we discuss the run-time overheads for admitting aperiodic requests into the system1.

Hierarchical scheduling frameworks (HSFs) provide means for composing complex real-time systems from well-defined, independently analyzed components. To support resource sharing in two-level HSFs, three synchronization protocols based on the stack resource policy (SRP) have recently been presented for single-processor execution platforms, i.e., HSRP, SIRAP, and BROE. This paper presents a transparent implementation of these three protocols side-by-side in an HSF-enabled real-time operating system. Transparent synchronization interfaces make it possible to select a protocol during integration time based on its relative strengths. A timing interface describes the required budget to execute a component on a shared platform and an accessor's maximum critical-section execution time to global shared resources. These resources are arbitrated based on the available budget of the accessing task. We enable this explicit synchronization of virtual time with global time by means of a novel virtual-timer mechanism. Moreover, we investigate system overheads caused by each synchronization protocol, so that these can be included in the system analysis. Based on the analytical and implementation overheads of each protocol, we present guidelines for the selection of a synchronization protocol during system integration. Finally, we show that unknown task-arrival times considerably complicate an efficient implementation of SIRAP's self-suspension mechanism. We briefly discuss the implementation complexity caused by these arrivals for bandwidth-preserving servers, e.g., deferrable servers and BROE.

Hierarchical scheduling frameworks (HSFs) have been extensively investigated as a paradigm for facilitating temporal isolation between components that need to be integrated on a single shared processor. In the presence of shared resources, however, temporal isolation may break when one of the accessing components executes longer than specified during global resource access. The ability to confine such temporal faults makes the HSF more dependable. As a solution we propose a stack-resource-policy (SRP)-based synchronization protocol for HSFs, named Hierarchical Synchronization protocol with Temporal Protection (HSTP). When a component exceeds its specified critical-section length, HSTP enforces a component to self-donate its own budget to accelerate the resource release. In addition, a component that blocks on a locked resource may donate budget. The schedulability of those components that are independent of the locked resource is unaffected. HSTP efficiently limits the propagation of temporal faults to resource-sharing components by disabling local preemptions in a component during resource access. We finally show that HSTP is SRP-compliant and applies to existing synchronization protocols for HSFs.

Hierarchical scheduling frameworks (HSFs) provide means for composing complex real-time systems from well-defined, independently analyzed subsystems. To support resource sharing within two-level HSFs, three synchronization protocols based on the stack resource policy (SRP) have recently been presented, i.e. HSRP, SIRAP and BROE. This paper describes the first implementation presenting these three SRP-based synchronization protocols side-by-side in a HSF-enabled real-time operating system. We base our implementations on the commercially available real-time operating system μC/OS-II, extended with proprietary support for periodic tasks, idling periodic servers and two-level preemptive scheduling. Moreover, we investigate the system overhead of the synchronization primitives of each protocol. Transparent interfaces allow a protocol to be selected during integration time based on its relative strengths.

Hard real-time embedded systems need to guarantee that tasks always meet their deadlines. Exact schedulability tests can guarantee this for fixed-priority, preemptively scheduled systems even under the tightest resource constraints. However, these tests are pseudo-polynomial in complexity. This can become a limiting factor in open systems where it might be necessary to have run-time admission tests. A linear-time sufficient test has therefore been developed to estimate response-time upper bounds. In line with utilization-based sufficient tests, we propose to improve this test for task sets with harmonically related task periods. Moreover, we make it possible to reuse this test in the context of hierarchically scheduled (partitioned) resources. In such systems several applications are given a virtual share (budget) of the processor. By modeling the unavailability of processor resources to an application as two fictive tasks, we can also use a budget's period to improve response-time bounds1.