The existing worst-case response time (WCRT) analysis for individual priority classes under credit-based shaping (CBS) in Ethernet AVB based on so-called eligible intervals is both independent and tight. This WCRT analysis does not rely on any assumptions on interfering inter-priority streams other than those enforced by the Ethernet standard. A major advantage of this independent analysis is that CBS may be viewed as resource reservation, where allocated bandwidth is both guaranteed and enforced. Although independent analysis provides inter-priority class robustness, it comes at a cost of over-provisioning bandwidth. We illustrate this cost of inter-priority class robustness by means of an example that requires 7.8 times the amount of bandwidth reservation for a given set of streams compared to a different analysis that takes knowledge of inter-priority streams into account.

Despite their industrial relevance, contemporary textbooks hardly address cyclic executives, if at all. There is therefore a need for analysis techniques for these executives.Earlier work considered exact schedulabilily analysis of basic single-rate cyclic executives for a basic system model. In this paper, we present exact schedulability analysis of a single-rate periodic cyclic executive, for a refined model in which the notion of observable event [1] is taken into account. We compare the single-rate periodic cyclic executive with the single-rate AFAP (as fast as possible) and single-rate time-driven AFAP cyclic executives from a scheduling perspective for this refined model.

In a recent survey of industry practitioners in the field of real-time systems, the majority of the respondents indicated that cyclic executives are (still) in use in their systems. Unfortunately, contemporary text books hardly address cyclic executives, if at all. There is therefore a need for analysis techniques for these executives.In this paper, we consider the multi-rate periodic cyclic executive, scheduling a given sequence of independent hard real-time polling tasks in a single-processor system. We present exact analysis for this cyclic executive, and discuss its relative strengths and weaknesses compared to multi-rate AFAP (as fast as possible) and multi-rate time-driven AFAP cyclic executives in terms of jitter, energy efficiency, schedulability, and implementation overhead. Unlike existing approaches, which typically take periodic tasks as a starting point for cyclic executives and focus on schedulability of tasks, we take the schedulability of the system as a starting point, i.e. whether or not the system meets its deadlines. In particular, we do not assume periods and deadlines for tasks, and our analysis derives feasible cycle times of a multi-rate periodic cyclic executive for a system.

In a recent survey, it was observed that the majority of the respondents to the question which task scheduling policy/policies are used in considered systems answered “static cycle/table driven/time-triggered”. Cyclic executives, though hardly addressed in contemporary text books, if at all, are therefore still in use in practice. Hence, there is a need for analysis techniques for these executives.In earlier work, exact analysis for single-rate AFAP (as fast as possible) and single-rate time-driven AFAP cyclic executives, scheduling a given sequence of independent hard real-time polling tasks in single-processor systems, have been presented. Unlike the analysis for single-rate AFAP cyclic executives, the analysis for single-rate time-driven AFAP cyclic executives depends on the order of the tasks in the cycle. In this paper, we present two optimal order assignment (OOA) algorithms for single-rate time-driven AFAP cyclic executives. The first algorithm yields a schedulable order of tasks if and only if such an order exists. The second algorithm enhances the first by yielding an order that maximizes the cycle time of the executive, effectively maximizing energy efficiency or improving the average response times of background tasks.

Existing papers on worst-case response time analysis for individual classes in Ethernet AVB typically focus on classes under credit-based shaping (CBS). There also exist industrial applications that use the Best-Effort class BE for non-hard real-time traffic with a minimum quality-of-service (QoS) require-ment, however. In this paper, we therefore present a conjecture for worst-case response time analysis for that class BE, stating that the existing analysis based on eligible intervals can be equally well applied to a single (highest-priority) stream without CBS, by simply assuming the remaining bandwidth to be available to that stream. The conjecture is illustrated using a figure.

The academic interest in cyclic executives for multitasking in hard real-time systems decreased significantly during the past decades. Moreover, cyclic executives are hardly addressed in contemporary text books, if at all. Cyclic executives are still in use, however, and there is therefore a need for analysis techniques for these executives. In this document, we consider two basic cyclic executives, i.e. a single-rate AFAP (as fast as possible) and a single-rate time-driven AFAP cyclic executive, scheduling a given sequence of independent hard real-time polling tasks in a single-processor system. We present exact analysis for both cyclic executives and discuss their relative strengths and weaknesses in terms of jitter, energy efficiency, and schedulability. Unlike existing approaches, which typically take periodic tasks as a starting point for cyclic executives and focus on schedulability of tasks, we take the schedulability of the system as a starting point, i.e. whether or not the system meets its deadlines. In particular, we do not assume periods and deadlines for tasks.

In a recent survey, it was observed that the majority of the respondents to the question which task scheduling policy/policies are used in considered systems answered “static cy-cle/table driven/time-triggered”. Cyclic executives, though hardly addressed in contemporary text books, if at all, are therefore still in use in practice. Hence, there is a need for analysis techniques for these executives. In earlier work, exact analysis for single-rate AFAP (as fast as possible) and single-rate time-driven AFAP cyclic executives, scheduling a given sequence of independent hard real-time polling tasks in single-processor systems, has been presented. Unlike the analysis for single-rate AFAP cyclic executives, the analysis for single-rate time-driven AFAP cyclic executives depends on the order of the tasks in the cycle. In this paper, we present a conjecture for an optimal order assignment (OOA) algorithm for single-rate time-driven AFAP cyclic executives.

Although the academic interest in cyclic executives for multitasking in hard real-time systems decreased significantly during the past decades, industry still uses cyclic executives in embedded real-time systems. Unfortunately, contemporary text books hardly address cyclic executives, if at all. There is therefore a need for analysis techniques for these executives.In this document, we consider two basic cyclic executives, i.e. a multi-rate AFAP (as fast as possible) and a multi-rate time-driven AFAP cyclic executive, scheduling a given sequence of independent hard real-time polling tasks in a single-processor system. We present exact analysis for both cyclic executives. Unlike existing approaches, which typically take periodic tasks as a starting point for cyclic executives and focus on schedulability of tasks, we take the schedulability of the system as a starting point, i.e. whether or not the system meets its deadlines. In particular, we do not assume periods and deadlines for tasks.

In this paper, we propose to use Schedule Abstraction Graphs (SAGs) to determine exact worst-case latency of packets at an egress port of an Ethernet TSN switch with Time-aware Shapers (TASs). We briefly sketch how to apply the existing SAG framework in a TSN context and extend the framework with FIFO-queues and TASs.

Flow control is of particular importance in TimeSensitive Networking (TSN), where timeliness of messages is guaranteed through several types of traffic shaping. This has given rise to a number of papers discussing the worst-case response time analysis of, in particular, the credit-based traffic shaping approach. In this work-in-progress paper, we concern ourselves with the possibility that traffic shaping can be applied in different layers of the protocol stack, e.g., the physical layer and link layer, which may give rise to different credit behaviors. We convey our concern that the analysis performed in literature seems to assume application of traffic shaping in the physical layer, and that the analysis therefore cannot be readily used in a context where shaping is applied in a higher layer. In particular, assuming application of credit-based shaping in the link layer, there are different interpretations possible for credit behavior. Depending on the interpretation, some of the basic properties of credit, that are crucial for the analysis, may no longer be valid after overhead is added by the physical layer. As an ongoing effort, we plan to revisit the eligible interval analysis of [1] with an adaptation for a link layer interpretation of the standard concerning application of traffic shaping.

Contact-less vital-sign monitoring is enabling in situations where traditional contact-based vital sign monitoring is prohibitive, such as neonatal and burn care where electrodes and attachments risk patient infection or complications. To make vital-sign monitoring available for the consumer market, these algorithms shall use COTS cameras and run on COTS systems. In this paper, we report upon our experience in improving the performance of a contact-less respiration algorithm on a resource-constrained COTS multi-core system, in our case a Raspberry Pi 3 running Linux. In particular, we describe how, by using a state-of-research tool to visualize the behavior of a system, performance bottlenecks and issues of the system are identified and resolved. The resulting improvements are an increase of the CPU utilization from 72% to almost 94% and an increase of the throughput of the algorithm by more than 45%.

Contact-less vital-sign monitoring is enabling in situations where traditional contact-based vital sign monitoring is prohibitive, such as neonatal and burn care where electrodes and attachments risk patient infection or complications. To make vital-sign monitoring available for the consumer market, these algorithms shall use COTS cameras and run on COTS systems. In this paper, we report upon the results of an experiment to improve the performance of a contact-less respiration algorithm on a resource-constrained COTS multi-core system, in our case a Raspberry Pi 3 running Linux, using a state-of-the-art tool to visualize the behavior of a system. The improvements are an increase of the CPU utilization from 72% to almost 94% and an increase of the throughput of the algorithm by more than 45%.

Commercially available Off The Shelf (COTS) multicores have been assessed as the baseline computing platform even in the most conservative real-time domains. Multicore contention arising on shared hardware resources, with its circular dependence with scheduling, is among the most challenging issues that require urgent attention before multicores can be fully embraced for real-time computing. In the context of static scheduling, still the most used scheduling approach in real-time industries, we propose an ILP formulation for computing the worst-case contention delay suffered by a task due to interference on a shared bus. Our model provides accurate contention delay bounds that avoid unnecessary over-accounting of conflicts between bus requests, by considering contention effects at system-level (i.e., across tasks) rather than at task-level only. This allows precisely capturing the interdependence between timing interference of conflicting requests, issued in parallel by other cores (tasks), and the identification of the particular set of tasks co-running on those cores. We assess our technique both analytically and empirically on a real COTS multicore platform. We show, via extensive evaluation, that jointly accounting for worst-case task overlapping and request distribution scenarios always provides tighter contention bounds when compared to state-of-the-art solutions.

Stack sharing between tasks may significantly reduce the amount of memory required in resource-constrained real-time embedded systems. Existing work on stack sharing mainly focused on stack sharing between tasks that neither leave any data on the stack from one instance to another nor suspend themselves, i.e. tasks with a so-called single-shot execution. In this paper, we consider stack memory requirements of AUTOSAR/OSEK-compliant scheduling policies for a mixed task set, consisting of so-called basic and extended tasks. Unlike basic tasks, that have a single-shot execution, extended tasks are allowed to leave data on the stack from one instance to another and to suspend themselves. We prove that minimizing the shared stack requirement for such a mixed task set is an NP-hard problem. We subsequently provide an heuristic-based algorithm to minimize stack usage of a mixed task set, and evaluate the algorithm through a case study of an implementation of an unmanned aerial vehicle. An extended version of the paper is available as technical report [5].

Stack sharing between tasks may significantly reduce the amount of memory required in resource-constrained real-time embedded systems. On the downside, stack sharing decreases the predictability of a system, e.g. may give rise to a substantial variation in the address space for the memory locations used for the stack of a task. As a result, the precision of execution-time bounds may be reduced, the pessimism in schedulability analysis increased, and optimizations to increase schedulability hampered. In this paper, we present EMPRESS, an Efficient and effective Method for PREdictable Stack Sharing. We assume priority-based scheduled systems, where the binary pre-emption relation on tasks is a strict partial order, and static bounds on each task's stack usage. Both assumptions are common in the embedded real-time domain. For such systems, EMPRESS provides a predictable stack sharing between tasks, i.e. the stack of every task is always located in the very same memory area, even for tasks sharing a stack. It therefore combines the predictability of dedicated stack spaces with the reduced memory need of a shared stack. We exemplify the benefits of EMPRESS using as a case study an implementation of an unmanned aerial vehicle, and explain how EMPRESS can be realized within t.he Erika Enterprise RTOS without additional overheads.

The flexible spin-lock model (FSLM) unifies suspension-based and spin-based resource access protocols for partitioned fixed-priority preemptive scheduling based real-time multi-core platforms. Recent work has been done in defining the protocol for FSLM, providing schedulability analysis, and investigating the practical consequences of the theoretical model. FSLM complies to the AUTOSAR standard for the automotive industry, and prototype implementations of FSLM in the OSEK/VDX-complaint Erika Enterprise Real-Time Operating System have been realized. In this paper, we briefly describe some practical challenges to improve efficiency and generality.

In the high-tech and automotive industry, bandwidth considerations and widely accepted standardization are two important reasons why Ethernet is currently being considered as an alternative solution for real-time communication (compared to traditional fieldbusses). Although Ethernet was originally not intended for this purpose, the development of the Ethernet AVB standard enables its use for transporting high-volume data (e.g. from cameras and entertainment applications) with low-latency guarantees. In complex industrial systems, the network is shared by many applications, developed by different parties. To face this complexity, the development of these applications must be kept as independent as possible. In particular, from a network point of view, progress of all communication streams must be guaranteed, and the performance for individual streams should be predictable using only information regarding the stream under study and the general parameters of the communication standard used by the network. Initial methods to guarantee latency for Ethernet AVB networks rely on the traditional busy-period analysis. Typically, these methods are based on knowledge of the inter-arrival patterns of both the stream under study and the interfering streams that also traverse the network. The desired independence is therefore not achieved. In this paper, we present an independent real-time analysis based on so-called eligible intervals , which does not rely on any assumptions on interfering priority classes other than those enforced in the Ethernet AVB standard. We prove this analysis is tight in case there is only a single higher-priority stream, and no additional information on interference is known. In case there are multiple higher-priority streams, we give conditions under which the analysis is still tight. Furthermore, we compare the results of our approach to the two most recent busy-period analyses, point out sources of pessimism in these earlier works, and argue that assuming more information on the sources of interference (e.g. a minimal inter-arrival time between interfering frames) has only limited advantages.

Cooperative adaptive cruise control and platooning are well-known applications in the field of cooperative automated driving. However, extension toward maneuvering is desired to accommodate common highway maneuvers, such as merging, and to enable urban applications. To this end, a layered control architecture is adopted. In this architecture, the tactical layer hosts the interaction protocols, describing the wireless information exchange to initiate the vehicle maneuvers, supported by a novel wireless message set, whereas the operational layer involves the vehicle controllers to realize the desired maneuvers. This hierarchical approach was the basis for the Grand Cooperative Driving Challenge (GCDC), which was held in May 2016 in The Netherlands. The GCDC provided the opportunity for participating teams to cooperatively execute a highway lane-reduction scenario and an urban intersection-crossing scenario. The GCDC was set up as a competition and, hence, also involving assessment of the teams' individual performance in a cooperative setting. As a result, the hierarchical architecture proved to be a viable approach, whereas the GCDC appeared to be an effective instrument to advance the field of cooperative automated driving.

Fixed-priority preemption threshold scheduling (FPTS) is a limited preemptive scheduling scheme that generalizes both fixed-priority preemptive scheduling (FPPS) and fixed-priority non-preemptive scheduling (FPNS). By increasing the priority of tasks as they start executing it reduces the set of tasks that can preempt any given task. A subset of FPTS task configurations can be implemented natively on any AUTOSAR/OSEK compatible platform by utilizing the platform's native implementation of non-preemptive task groups via so called internal resources. The limiting factor for this implementation is the number of internal resources that can be associated with any individual task. OSEK and consequently AUTOSAR limit this number to one internal resource per task. In this work, we investigate the impact of this limitation on the schedulability of task sets when cache related preemption delays are taken into account. We also consider the impact of this restriction on the stack size when the tasks are executed on a shared-stack system.

Fixed-priority scheduling with preemption thresholds (FPTS) is supported by the AUTOSAR and OSEK standards as a scheduling policy. Since FPTS is a generalization of fixed-priority preemptive scheduling (FPPS) and fixed-priority nonpreemptive scheduling (FPNS), it aims to improve schedulability. In this paper, we prove, as an intermediate step towards the exact best-case response time analysis for FPTS, that the best-case computation time of a non-preemptive task scheduled under FPTS or FPNS is a tight lower bound for its response time. In addition, we illustrate by means of an example that the best-case response time analysis for FPTS is most likely not a straight forward extension of the current best-case analysis for FPPS.

The flexible spin-lock model (FSLM) unifies suspension-based and spin-based resource sharing protocols for partitioned fixed-priority preemptive scheduling based real-time multiprocessor platforms. Recent work has been done in defining the protocol for FSLM and providing a schedulability analysis without accounting for the implementation overheads. In this paper, we extend the analysis for FSLM with implementation overheads. Utilizing an initial implementation of FSLM in the OSEK/VDX-compliant Erika Enterprise RTOS on an Altera Nios II platform using 4 soft-core processors, we present an improved implementation. Given the design of the implementation, the overheads are characterized and incorporated in specific terms of the existing analysis. The paper also supplements the analysis with measurement results, enabling an analytical comparison of FSLM with the natively provided multiprocessor stack resource policy (MSRP), which may serve as a guideline for the choice of FSLM or MSRP for a specific application.

Support for exclusive access to shared (global) resources is instrumental in the context of embedded real-time multi-core systems, and mechanisms for achieving such access must be deterministic and efficient. There exist two traditional approaches for multiprocessors when a task requests a global resource that is locked by a task on a remote core: a spin-based approach, i.e. non-preemptive busy waiting for the resource to become available, and a suspension-based approach, i.e. the task relinquishes the processor. A suspension-based approach can be viewed as a spin-based approach where the lowest priority on a core is used during spinning, similar to a non-preemptive spin-based approach where the highest priority on a core is used. By taking such a view, we previously provided a general model for spinning, where any arbitrary priority can be used for spinning, i.e. from the lowest to the highest priority on a core. Targeting partitioned fixed-priority preemptive scheduled multiprocessors and spin-based approaches that use a fixed priority for spinning per core for all tasks, we aim at increasing the schedulability of multiprocessor systems by using the spin-lock priority per core as parameter. In this paper, we present (i) a generalization of the traditional worst-case response-time analysis for non-preemptive spin-based approaches addressing an arbitrary but fixed spin-lock priority per core, (ii) an optimal spin-lock priority assignment (OSPA) algorithm per core, i.e. an algorithm that will find a fixed spin-lock priority per core that will make the system schedulable, whenever such an assignment exists and, (iii) comparative evaluations of the OSPA algorithm with the spin-based and suspension-based approaches where OSPA showed up to 38% improvement compared to both approaches.

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

Busy period analysis is often used as a basis for worst-case response time analysis of priority based systems. However, when shaping strategies are used to prevent starvation of lower priorities, it becomes difficult to achieve tightness results using this method. The reason for this is that a busy period is defined as the longest interval in which there exists pending load. It is exclusively based on execution time, and does not take the amount of provided bandwidth into account. As a consequence, it is less suitable for the study of idling systems. In particular, we do not yet have tightness results regarding the analysis of the Ethernet AVB standard, in which credit-based shaping is applied. In this paper, we propose an alternative to the use of busy periods. We show that, by defining an eligible interval in such a way that provisioning is taken into account, tight worst-case response time bounds can more easily be obtained for Ethernet AVB, at least in the case of either lower-or higher-priority interference.

For resource-constrained embedded real-time systems, resource-efficient approaches are very important. Such an approach is presented in this paper, targeting systems where a critical application is partitioned on a multi-core platform and the remaining capacity on each core is provided to a noncritical application using resource reservation techniques. To exploit the potential parallelism of the non-critical application, global scheduling is used for its constituent tasks. Previously, we enabled intra-application resource sharing for such a framework, i.e. each application has its own dedicated set of resources. In this paper, we enable inter-application resource sharing, in particular between the critical application and the non-critical application. This effectively enables resource sharing in a hybrid partitioned/global scheduling framework on multiprocessors. For resource sharing, we use a spin-based synchronization protocol. We derive blocking bounds and extend existing schedulability analysis for such a system.

To combine the relative strengths of fully preemptive and non-preemptive fixed priority scheduling, we can use limited preemptive scheduling methods. One such method is fixed-priority threshold scheduling (FPTS). This approach defines dual priorities for every task, a priority assigned to the inactive jobs and an equal or a higher one, called preemption threshold, for the jobs that have already started executing. A task can preempt another task's job if and only if its priority is greater than the other task's preemption threshold. FPTS can be implemented by assigning tasks to non-preemptive groups in a one-to-many manner. That is groups of tasks that are mutually non-preemptive.

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.

In the context of switched Ethernet networks, multi-hop communication is essential as the networks in industrial applications comprise a high amount of nodes, that is far beyond the capability of a single switch. In this paper, we focus on multi-hop communication using HaRTES switches. The HaRTES switch is a modified Ethernet switch that provides real-time traffic scheduling, dynamic Quality-of-Service and temporal isolation between real-time and non-real-time traffic. Herein, we propose a method, called Reduced Buffering Scheme, to conduct the traffic through multiple HaRTES switches in a multi-hop HaRTES architecture. In order to enable the new scheduling method we propose to modify the HaRTES switch structure. Moreover, we develop a response time analysis for the new method. We also compare the proposed method with a method previously proposed, called Distributed Global Scheduling, based on their traffic response times. We show that, the new method forwards all types of traffic including the highest, the medium and the lowest priority, faster than the previous method in most of the cases. Furthermore, we show that the new method performs even better for larger networks compared with the previous one.

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.

Multi-mode embedded real-time systems exhibit a specific behaviour for each mode, and upon a mode-change request the task-set and timing interfaces of the system need to be changed. This paper presents the implementation of a MultiMode Adaptive Hierarchical Scheduling Framework (MMAHSF) and provides a generic skeleton (framework) for a two-level adaptive hierarchical scheduling supporting multiple modes and multiple mode-change mechanisms on an open source real-time operating system (FreeRTOS). The MMAHSF enable application-specific implementations of mode-change protocols using a set of predefined mode-change mechanisms. The paper addresses different mode-change mechanisms at both global and local scheduling levels. It presents examples of mode-change protocols that are developed by composing together these mechanisms in multiple ways and provide the initial results of executing these protocols in the MMAHSF implementation on an AVR 32-bit board EVK1100.

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.

This paper addresses the problem of scheduling periodic parallel tasks on a multi-resource platform, where tasks have real-time constraints. The goal is to exploit the inherent parallelism of a platform comprised of multiple heterogeneous resources. A resource model is proposed, which abstracts the key properties of any heterogeneous resource from a scheduling perspective. A new scheduling algorithm called PSRP is presented, which refines MSRP. The schedulability analysis for PSRP is presented. The benefits of PSRP are demonstrated by means of an example application showing that PSRP indeed exploits the available concurrency in heterogeneous real-time systems.

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.

Recent trends towards adopting hypervisors, hierarchical scheduling, and other virtualization technologies that achieve partitioned access to the CPU and other resources impose significant impact with respect to jitter performance in embedded real-time systems. In this paper we make a first step towards characterization, modeling and calculation of this jitter.

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.

In this paper, we show that both global as well as local schedulability analysis of synchronization protocols based on the stack resource policy (SRP) and overrun without payback for hierarchical scheduling frameworks based on fixed-priority preemptive scheduling (FPPS) are pessimistic. We present tighter global and local schedulability analysis, illustrate the improvements of the new analysis by means of examples, and show that the improved global analysis is both uniform and sustainable. We evaluate the new global and local schedulability analysis based on an extensive simulation study and compare the results with the existing analysis.

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.

In this paper, we consider multimedia Quality-of-Service (QoS) in resource constrained embedded systems, where scalable applications are structured as directed acyclic graphs of tasks, which communicate via shared buffers. Scalable multimedia applications allow to trade quality for resource usage during run-time. We present two QoS problems: (i) temporal dependencies between subchains of tasks due to a common predecessor, and (ii) mode change latency in applications. These problems are addressed through advanced memory management techniques. For the first problem, it is shown how additional access to the buffer, in particular the support for dropping selected frames, allows to guarantee the Quality of Service of the application during overload conditions, preventing congestion in one buffer to propagate across the whole application. For the latter problem, the approach of in-buffer scaling is applied to reduce the mode change latency in scalable multimedia processing applications, which can adapt their memory requirements during runtime according to a set of predefined modes. The latter approach is validated with simulation results.

Fixed-priority preemption-threshold scheduling (FPTS) has been proposed as a generalization of fixed-priority preemptive scheduling (FPPS) and fixed-priority non-preemptive scheduling (FPNS) with the aim to improve schedulability and reduce run-time overheads. In this paper, we show that the existing worst-case response time (WCRT) analysis for FPTS is pessimistic and present an exact WCRT analysis. Moreover, we refine the task model for FPTS, making FPTS also a generalization of fixed-priority scheduling with deferred preemption (FPDS). Finally, we present exact analysis for FPTS for this refined task model and an example showing that FPTS can improve on FPPS and FPDS.

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.

Proposed safety applications for vehicle-to-vehicle (V2V) communication rely mostly on periodic broadcasting. In this work we analyze the performance and fairness aspects of such an one-hop periodic broadcast communication. We show that communication reliability is greatly dependent on the random relative phasing of the communicating vehicles and on the impact of hidden nodes. For a random initial phasing some vehicles suffer from consecutive packet losses thereby becoming invisible to neighboring vehicles for a long time, whereas some other vehicles have no packet loss at all. We propose a simple and effective approach to provide fair transmission opportunities and show the improvements through simulations.

This paper presents a new schedulability analysis for hierarchically scheduled real-time systems executing on a single processor using SIRAP, a synchronization protocol for inter subsystem task synchronization. We show that it is possible to bound the number of self-blocking occurrences that should be taken into consideration in the schedulability analysis of subsystems. Correspondingly, we present two novel schedulability analysis approaches with proof of correctness for SIRAP. An evaluation suggests that this new schedulability analysis can decrease the analytical subsystem utilization significantly.

In recent years, several synchronization protocols for resource sharing have been presented for use in a Hierarchical Scheduling Framework (HSF). An initial comparative assessment of existing protocols revealed that none of the protocols is superior to the others and that the performance of a protocol heavily depends on system parameters. In this paper, we aim at efficiency improvements of the synchronization protocol SIRAP [5] and its associated schedulability analysis, where efficiency refers to calculated CPU resource needs. The contribution of the paper is threefold. Firstly, we present an improvement of the schedulability analysis for SIRAP, which makes SIRAP more efficient. Secondly, we generalize SIRAP by distinguishing separate resource ceilings for self-blocking and resource access. Using a separate resource ceiling for self-blocking enables a reduction of the interference from lower priority tasks, which can result in efficiency improvements. The efficiency improvement depends on both subsystem characteristics and the value selected for the resource ceiling for self-blocking, however. The third contribution of this paper is therefore an algorithm that given a subsystem selects for each globally shared resource an optimal value in terms of efficiency for its resource ceiling for self-blocking. The efficiency improvement gained by the algorithm compared to the original SIRAP approach is evaluated by means of simulation.

We present our ongoing work on synchronization in hierarchical scheduled real-time systems, where tasks are scheduled using fixed-priority pre-emptive scheduling. In this paper, we show that the original local schedulability analysis of the synchronization protocol SIRAP [4] is very pessimistic when tasks of a subsystem access many global shared resources. The analysis therefore suggests that a subsystem requires more CPU resources than necessary. A new way to perform the schedulability analysis is presented which can make the SIRAP protocol more efficient in terms of calculated CPU resource needs.

This paper presents the design and implementation of RELTEQ, a timed event management algorithm based on relative event times, supporting long event interarrival time, long lifetime of the event queue, no drift and low overhead. It is targeted at embedded operating systems. RELTEQ has been conceived to replace and improve the existing timed event management approach in ¿C/OS II, a real-time operating system used by one of our industrial partners. Experimental results confirm a lower overhead of the proposed method in terms of processor requirements compared to the existing approach.

In the multi-core and multiprocessor domain, there has been considerable work done on scheduling techniques assuming that real-time tasks are independent. In practice a typical real-time system usually share logical resources among tasks. However, synchronization in the multiprocessor area has not received enough attention. In this paper we investigate the possibilities of extending multiprocessor hierarchical scheduling to support an existing synchronization protocol (FMLP) in multiprocessor systems. We discuss problems regarding implementation of the synchronization protocol under the multiprocessor hierarchical scheduling.

Recently, two SRP-based synchronization protocols for hierarchically scheduled real-time systems based on fixed priority preemptive scheduling (FPPS) have been presented, i.e., HSRP and SIRAP. Preventing depletion of budget during global resource access, the former implements an overrun mechanism, while the later exploits a skipping mechanism. A theoretical comparison of the performance of these mechanisms revealed that none of them was superior to the other, as their performance is heavily dependent on the system's parameters. To better understand the relative strengths and weaknesses of these mechanisms, this paper presents a comparative evaluation of the depletion prevention mechanisms overrun (with or without payback) and skipping. These mechanisms are investigated in detail and the corresponding system load imposed by these mechanisms is explored in a simulation study. The mechanisms are evaluated assuming FPPS and a periodic resource model. The periodic resource model is selected as it supports locality of schedulability analysis, allowing for a truthful comparison of the mechanisms. Given system characteristics, guiding the design of hierarchically scheduled real-time systems, the results of this paper indicate when one mechanism is better than the other and how a system should be configured in order to operate efficiently.

Fixed-priority scheduling with deferred preemption (FPDS) has been proposed in the literature as a viable alternative to fixed-priority pre-emptive scheduling (FPPS), that obviates the need for non-trivial resource access protocols and reduces the cost of arbitrary preemptions. This paper shows that existing worst-case response time analysis of hard real-time tasks under FPDS, arbitrary phasing and relative deadlines at most equal to periods is pessimistic and/or optimistic. The same problem also arises for fixed-priority non-pre-emptive scheduling (FPNS), being a special case of FPDS. This paper provides a revised analysis, resolving the problems with the existing approaches. The analysis is based on known concepts of critical instant and busy period for FPPS. To accommodate for our scheduling model for FPDS, we need to slightly modify existing definitions of these concepts. The analysis assumes a continuous scheduling model, which is based on a partitioning of the timeline in a set of non-empty, right semi-open intervals. It is shown that the critical instant, longest busy period, and worst-case response time for a task are suprema rather than maxima for all tasks, except for the lowest priority task. Hence, that instant, period, and response time cannot be assumed for any task, except for the lowest priority task. Moreover, it is shown that the analysis is not uniform for all tasks, i.e. the analysis for the lowest priority task differs from the analysis of the other tasks. These anomalies for the lowest priority task are an immediate consequence of the fact that only the lowest priority task cannot be blocked. To build on earlier work, the worst-case response time analysis for FPDS is expressed in terms of known worst-case analysis results for FPPS. The paper includes pessimistic variants of the analysis, which are uniform for all tasks, illustrates the revised analysis for an advanced model for FPDS, where tasks are structured as flow graphs of subjobs rather than sequences, and shows that our analysis is sustainable.

Fixed-priority scheduling with deferred preemption (FPDS) has been proposed in the literature as a viable alternative to fixed-priority preemptive scheduling (FPPS), that both reduces the cost of arbitrary preemptions and removes the need for non-trivial resource access protocols. This paper shows that existing worst-case response time analysis of hard real-time tasks under FPDS, arbitrary phasing and relative deadlines at most equal to periods is both pessimistic and optimistic. This paper provides a revised analysis, resolving the problems with the existing approaches. The analysis assumes a continuous scheduling model. It is shown that the critical instant, longest busy period, and worst-case response time for a task are suprema rather than maxima for all tasks, except for the lowest priority task. Moreover, it is shown that the analysis is not uniform for all tasks, i.e. the analysis for the lowest priority task differs from the analysis of the other tasks, because only the lowest priority task cannot be blocked. To build on earlier work, the worst-case response time analysis for FPDS is expressed in terms of known worst-case analysis results for FPPS. The paper includes pessimistic variants of the analysis, which are uniform for all tasks.

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.

To analyse the schedulability of conditionally guaranteed budgets (CGBs) in the context of fixed-priority preemptive scheduling (FPPS), we present a so-called cognac-glass algorithm (CGA). CGBs have been conceived in the context of software video processing for consumer terminals to exploit the relative importance of applications. CGBs are similar to normal budgets, but are only conditionally guaranteed. This paper presents the schedulability analysis of CGBs under FPPS, based on both best-case and worst-case analysis techniques. We show that because both techniques are used, it is not straightforward to base the analysis on a critical instant. We therefore have to investigate multiple phasings of budgets during the analysis, for which we present a so-called cognac-glass algorithm. We derive that it suffices to consider only a subset of so-called dominating values for the phasing, which improves the efficiency of our algorithm. Given our analysis, we evaluate the effectiveness of CGBs, and conclude that CGBs are particularly useful for software video processing. Finally, we briefly compare our approach for CGBs with existing analysis techniques for hierarchical FPPS, and illustrate that best-case analysis techniques and a CGA can reduce the inherent pessimism in these existing techniques

Inconsistencies between software views are a source of errors for software systems. In this paper we present a general approach that aids in finding inconsistencies between different views. This approach supports both intra phase consistency checking and inter phase consistency checking. The approach is suitable for detecting consistency problems between, for example, multiple diagrams in a UML design as well as between a design and an implementation. The approach is based on verification of rules using relation partition algebra. In this paper, we present two types of rules: obligations and the more commonly used constraints, which can be viewed as lower bounds and upper bounds, respectively. To check consistency between views, rules are derived from one view, the so-called prevailing view, and imposed on another view, the so-called subordinate view. Because our approach does not prescribe which views are prevailing, it can be used in any arbitrary process. Violations to rules can be expressed in terms of either the prevailing view or the subordinate view. Exceptions to rules are easiliy embedded in our general approach to consistency checking.

Abstract Software architecture plays a vital role in the development (and hence maintenance) of large complex systems (containing millions of lines of code) with a long lifetime. It is therefore required that the software architecture is also maintained, i.e., sufficiently documented, clearly communicated, and explicitly controlled during its life‐cycle. In our experience, these requirements cannot be met without appropriate support. Commercial‐off‐the‐shelf support for architectural maintenance is still scarcely available, if at all, implying the need to develop appropriate proprietary means. In this paper, we reflect upon software architecture maintenance taken within three organizations within Philips that develop professional systems. We extensively describe the experience gained with introducing and embedding of architectural support in these three organizations. We focus on architectural support in the area of software architecture recovery, visualization, analysis, and verification. In our experience, the support must be carried by a number of pillars of software development, and all of these pillars have to go through a change process to ensure sustainable embedding. Managing these changes requires several key roles to be fulfilled in the organization: a champion, a company angel, a change agent, and a target. We call our reflection model C‐POSH, which is an acronym for Change management of the four identified pillars of software development: Process, Organization, Software development environment, and Humans. Our experiences will be presented in terms of the C‐POSH model. Copyright © 2005 John Wiley & Sons, Ltd.

Many real-time systems needing an online schedulability test requires exact schedulability analysis. In this paper we evaluate standard initial values for the iterative procedure to calculate worst-case response times of periodic tasks under fixed priority preemptive scheduling and arbitrary phasing. For discrete scheduling, we show that the number of iterations needed to determine the worst-case response time of a task using standard initial values increases logarithmically for an increasing worst-case computation time of that task. We present a new initial value, and prove that the number of iterations for that value is bounded. The costs of using the standard and new initial values are compared by means of an experiment. We briefly discuss the applicability of the initial value in other contexts, such as best-case response time analysis and jitter analysis.

Software architecture plays a vital role in the development (and hence maintenance) of large complex systems with a long lifetime. It is therefore required that the software architecture is also maintained, i.e. sufficiently documented, clearly communicated, and explicitly controlled. In our experience, these requirements cannot be met without appropriate support. Commercial-off-the-shelf support for architectural maintenance is still scarcely available, if at all, implying the need to develop appropriate proprietary means. In this paper, we briefly report upon an overall approach taken within three organizations within Philips that develop professional systems. We extensively describe the experience gained with the embedding of architectural support in these three organizations. We focus on architectural support in the area of software architecture recovery, visualization, analysis, and verification. In our experience, the support must be carried by a number of elements of software development, and all of these elements have to go through a change process to ensure sustainable embedding. We distinguish four of these elements, i.e. process, organization, software development environment, and humans, and present our experience in terms of those elements.

In this paper, we present how scalable 3D graphics fits into a quality-of-service resource management approach for high volume electronics consumer terminals. Resource management is based on guaranteed and enforced resource budgets, which are allocated by a global quality manager. A specific 3D QoS manager makes sure that a 3D graphics service performs acceptably within the limitations of its budget. Based on models that estimate the quality and workload of functional tasks, such as rendering and decoding, for 3D objects, the scaling parameters of these tasks are adapted to guarantee real-time operation, possibly at a slightly degraded perceived quality. The validity of the approach is demonstrated with a 3D graphics application running in conjunction with video decoding on a Philips set-top box containing a TriMedia/spl trade/ processor.

Increasingly, media processing in high volume electronics (HVE) consumer multimedia terminals, such as digital TV sets and set-top boxes, is performed by powerful programmable components. These programmable components enable media processing in software, allowing the terminals to become open and flexible. HVE consumer terminals are heavily resource constrained, and therefore demand for a minimal dimensioning of these terminals. This paper presents the dynamic behavior of HVE consumer multimedia terminals, and describes the implications for the system in general and resource management in particular.

Consumer multimedia devices are becoming more open allowing media applications in software. Programmable components, however, are expensive and the consumer expects the devices to remain robust. A novel approach uses media applications that allow a trade-off between resource usage and output quality in a QoS environment. In this paper we focus on video applications and we take a look on the type of changes they may undergo at run-time. We use this information to define the parameters that describe the state of the applications in a QoS manner. We further provide the implications of state changes to the functionality and QoS control of the video processing modules.

An organization that develops large, software intensive systems with a long lifetime will encounter major changes in the market requirements, the software development environment, including its platform, and the target platform. In order to meet the challenges associated with these changes, software development has to undergo major changes as well. Especially when these systems are successful, and hence become an asset, particular care shall be taken to maintain this legacy; large systems with a long lifetime tend to become very complex and difficult to understand. Software architecture plays a vital role in the development of large software systems. For the purpose of maintenance, an up-to-date explicit description of the software architecture of a system supports understanding and comprehension of it, amongst other things. However, many large complex systems do not have an up-to-date documented softwarearchitecture. Particularly in cases where these systems have a long lifetime, the (natural) turnover of personnel will make it very likely that many employees contributing to previous generations of the system are no longer available. A need to ‘recover’ the software architecture of the system may become prevalent, facilitating the understanding of the system, providing ways to improve its maintainability and quality and to control architectural changes. This paper gives an overview of an on-going effort to improve the maintainability and quality of a legacy system, and describes the recent introduction of support at the architectural level for program understanding and complexity control. Copyright © 2000 John Wiley & Sons, Ltd.