https://www.mdu.se/

IEEE Time-Sensitive Networking (TSN) is one of the main solutions considered by the industry to support time-sensitive communication in data-intensive safety-critical and mission-critical applications such as autonomous driving and smart manufacturing. IEEE TSN standardizes several mechanisms to support real-time traffic on Ethernet networks. Time-Aware Shapers (TAS) (IEEE 802.1Qbv) is the standardized mechanisms of TSN that is usually considered to provide the most deterministic behavior for packet forwarding. TAS regulates when traffic classes may forward incoming packets to the egress of a TSN switch using gates that are opened and closed according to a time-triggered schedule. State-of-the-art solutions to configure or analyze TAS do not allow for multiple traffic classes to have their TAS gates opened at the same time according to any arbitrary schedule. In this paper, we present the first response-time analysis for traffic shaped with TAS where no restriction is enforced on the gate schedule. The proposed analysis is exact. It is a non-trivial variant of the schedule abstraction graph analysis framework [18]. Experiments confirm the usefulness of the proposed analysis and show that it is promising for doing design-space exploration where non-conventional TAS gates configurations are investigated to, for instance, improve average-case performance without degrading the worst-case.

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 interpriority streams into account.

Ethernet TSN is an upcoming communication standard for industrial distributed embedded systems with high demands on bandwidth and traffic delay. In this paper, we present and prove an improved analysis to determine bandwidth reservations for credit based shapers in a single Ethernet TSN switch. We compare this new analysis, which is based on eligible intervals, to the state-of-the-art bandwidth reservation analysis based on busy periods through experiments. Despite its low complexity and the independence of the knowledge of the interfering traffic, the results show an improvement of efficiency, i.e., a decrease of the required bandwidth, for the new analysis.

Fixed-priority preemption-threshold scheduling (FPTS) is a generalization of fixed-priority preemptive scheduling (FPPS) and fixed-priority non-preemptive scheduling (FPNS). Since FPPS and FPNS are incomparable in terms of potential schedulability, FPTS has the advantage that it can schedule any task set schedulable by FPPS or FPNS and some that are not schedulable by either. FPTS is based on the idea that each task is assigned a priority and a preemption threshold. While tasks are admitted into the system according to their priorities, they can only be preempted by tasks that have priority higher than the preemption threshold.

This paper presents a new optimal priority and preemption threshold assignment (OPTA) algorithm for FPTS which in general outperforms the existing algorithms in terms of the size of the explored state-space and the total number of worst case response time calculations performed. The algorithm is based on back-tracking, i.e. it traverses the space of potential priorities and preemption thresholds, while pruning infeasible paths, and returns the first assignment deemed schedulable.

We present the evaluation results where we compare the complexity of the new algorithm with the existing one. We show that the new algorithm significantly reduces the time needed to find a solution. Through a comparative evaluation, we show the improvements that can be achieved in terms of schedulability ratio by our OPTA compared to a deadline monotonic priority assignment.

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. 

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

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.

Two traditional approaches exist for a task that is blocked on a global resource; a task either performs a non-preemptive busy wait, i.e., spins, or suspends and releases the processor. Previously, we have shown that both approaches can be viewed as spinning either at the highest priority HP or at the lowest priority on the processor LP, respectively. Based on this view, previously we have generalized a task's blocking behavioral model, as spinning at any arbitrary priority level. In this paper, we focus on a particular class of spin-lock protocols from the introduced flexible spin-lock model where spinning is performed at a priority equal to or higher than the highest local ceiling of the global resources accessed on a processor referred to as CP spin-lock approach. In this paper, we assume that all tasks of a specific processor are spinning on the same priority level. Given this class and assumption, we show that there exists a spin-lock protocol in this range that dominates the classic spin-lock protocol which tasks spin on highest priority level (HP). However we show that this new approach is incomparable with the CP spin-lock approach. Moreover, we show that there may exist an intermediate spin-lock approach between the priority used by CP spin-lock approach and the new introduced spin-lock approach that can make a task set schedulable when those two cannot. We provide an extensive evaluation results comparing the HP, CP and the new proposed approach.

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.