Adversarial patch attacks inject localized perturbations into images to mislead deep vision models. These attacks can be physically deployed, posing serious risks to real-world applications. In this paper, we propose CertMask, a certifiably robust defense that constructs a provably sufficient set of binary masks to neutralize patch effects with strong theoretical guarantees. While the state-of-the-art approach (PatchCleanser) requires two rounds of masking and incurs O(n^2) inference cost, CertMask performs only a single round of masking with O(n) time complexity, where n is the cardinality of the mask set to cover an input image. Our proposed mask set is computed using a mathematically rigorous coverage strategy that ensures each possible patch location is covered at least k times, providing both efficiency and robustness. We offer a theoretical analysis of the coverage condition and prove its sufficiency for certification. Experiments on ImageNet, ImageNette, and CIFAR-10 show that CertMask improves certified robust accuracy by up to +13.4% over PatchCleanser, while maintaining clean accuracy nearly identical to the vanilla model.

Sensor fusion algorithms combine data from multiple sensors to produce more accurate and reliable results. However, temporal misalignment between sensors, caused by factors such as clock drift, jitter or networking delays, can significantly degrade fusion quality. Prior work on modeling temporal misalignment in sensor fusion algorithms assumes that in the ideal case all samples should be aligned with the same reference time point. We show that this assumption limits its applicability when samples are intentionally taken at different time points, e.g., when a single sensor is sampled multiple times or when sensors operate at different frequencies. In this paper, we introduce alignment sets, which allow system designers to explicitly specify the intended alignment between samples. This flexibility enables more precise temporal misalignment measures that better reflect the actual requirements of sensor fusion scenarios. We prove that alignment sets generalize the prior definitions of temporal misalignment of sensor fusion algorithms. We also provide an evaluation on a camera-LiDAR fusion pipeline for 3D object detection, showing that alignment sets provide more accurate misalignment measures and robustness estimates.

Cyber-physical systems typically have non-functional tasks to infrequently take care of some hardware and software components for maintaining correct functionality. For example, infrequently, sensors must be calibrated and endurance-limited memories must be wear-leveled. We study how a real-time system, consisting of care-taking tasks and sporadic real-time tasks, can be optimized and analyzed. We introduce a novel model to describe such systems and show how to intuitively utilize existing real-time scheduling theory to guarantee timeliness in this scenario. This is, however, very pessimistic since the care-taking tasks are executed infrequently, compared to the sporadic tasks utilizing the same components. We, therefore, examine how to properly handle care-taking tasks by controlling when to release them to avoid unnecessary interference spikes by proposing a low-overhead care-taking-task releaser. We demonstrate the improvements of schedulability using synthetic benchmarks, supported by an implementation for the proposed care-taking-task releaser in FreeRTOS and a case study for non-volatile memory.

In many applications of cyber-physical systems, a sequence of tasks is necessary to perform a certain functionality. For example, from a sensor to an actuator, the first task reads the sensor value (cause), the second task processes the data, and the third task produces an output for the actuator (an effect is triggered). For such scenarios, the end-to-end timing properties (the so-called end-to-end latency) of the sequence of tasks (the so-called cause-effect chain) are of importance. This tutorial recaps different metrics for the end-to-end latency of cause-effect chains, and summarizes fundamental properties and existing analytical results in a systematic manner. To that end, this tutorial has a special focus on the reaction time (how fast can a reaction be in the worst case) and the data age (how old is the data source of an actuation in the worst case). The goal of this tutorial is to provide a systematic view of the fundamental end-to-end timing properties of cause-effect chains and offer an outlook of possible research directions in the near future. Furthermore, we extend the proof of one fundamental property in the literature to comply with the current state-of-the-art definition of end-to-end latencies.

We introduce and study transfer schedulability , a novel concept that describes how properties of a reference schedule derived from a scheduling algorithm \(\mathcal {A}\) are transferred onto another scheduling algorithm \(\mathcal {B}\) for a given task system and fixed arrival times. Specifically, we say schedulability is transferred from \(\mathcal {A}\) to \(\mathcal {B}\) if the task set is schedulable under \(\mathcal {B}\) whenever all deadlines are met in the reference schedule produced by \(\mathcal {A}\) . We identify a sufficient criterion for schedulability to be transferred on uniprocessor systems, which we verify with the Rocq proof assistant, and based on this criterion develop runtime mechanisms that enforce transfer schedulability. We relate transfer schedulability to prior approaches from the literature and demonstrate how the concept can be utilized to avoid timing anomalies and lower runtime scheduling overheads. We demonstrate that transfer schedulability can be utilized to prevent timing anomalies for non-preemptive scheduling, self-suspending tasks, and directed acyclic graph (DAG) tasks where the edges induce delays. Our evaluation on synthesized task sets shows improved schedulability compared to standard scheduling algorithms. We also evaluated the number of interventions necessary to transfer schedulability, and additionally demonstrate that the proposed runtime mechanisms eliminate timing anomalies (like a completely static, fully table-driven approach) while achieving a response-time distribution closely resembling those of classic dynamic, event-driven schedulers like EDF.

Sensor fusion is the process of combining data from multiple sensors for acquiring a more accurate and comprehensive understanding of the observed environment. However, temporal misalignments between sensors can lead to incorrect fusion results, while the temporal robustness of sensor fusion algorithms is still a relatively unexplored research topic. To address this gap, we define three types of temporal robustness for sensor fusion: reference-point-based, strong sample-point-based, and weak sample-point-based temporal robustness. These definitions provide a framework to quantitatively evaluate the temporal robustness of sensor fusion functions. We also investigate the case where only a part of the sensors are misaligned. Furthermore, we consider potential probabilistic aspects for the proposed definitions. We assess the temporal robustness of a state-of-the-art fusion method in the context of 3D object detection, where camera and LiDAR data are fused. Our empirical evaluation shows that the examined fusion methods exhibit moderate robustness against temporal misalignment of images, but are especially sensitive to LiDAR misalignment. Our findings call attention to the necessity of providing robustness guarantees for sensor fusion functions against temporal misalignment.

In many modern safety-critical cyber-physical sys-tems, such as in the automotive or robotic domain, the appli-cation complexity requires the use of multi-core platforms to execute all workloads under strict hard real-time constraints. The sporadic DAG task model is a parallel task model adept at representing tasks comprised of subtasks, which possess internal data flow and precedence constraints induced by synchronization. A significant challenge to the system's performance and its real-time verification stems from the communication-centric nature of applications in these domains. Inter-core communication, required for data sharing among sub tasks across different cores, depends on either a shared bus or a network-on-chip, culminating in significant overhead due to latency, congestion, and synchronization. To improve performance and reduce these overheads, it is advantageous to execute subtasks, those that either exchange large volumes of data or access the same data, on a singular physical processor, thereby utilizing more efficient intra-core communication. In this paper, we tackle this issue by introducing the DAG task model with execution groups, incorporating a constraint that mandates the execution of grouped sub tasks on the same pro-cessor. We provide an analysis of worst-case response times and propose optimizations for our DAG task model with execution groups, subsequently evaluating our approach against existing solutions. The evaluation results demonstrate that our approach, even with the imposition of group execution constraints, remains competitive in comparison to existing approaches that do not take group execution constraints into account. Additionally, we explore implementation strategies and potential extensions for multi-task systems.

Modern robot systems, like autonomous vehicles, are complex, distributed systems that consist of many interacting components. End-to-end timing latency guarantees are key properties of such systems. They upper bound the data processing time and provide a predictable timing behavior. The Robot Operating System 2 (ROS 2) is a widely used and highly configurable set of software libraries for creating and deploying robot systems. It features a custom scheduler to execute time-triggered and event-triggered tasks and uses Data Distribution Services (DDS) for the communication between different system components. The data propagations between ROS 2 system components form cause-effect chains, which can be analyzed to determine the maximum reaction time (longest time between occurrence of an external cause and the earliest time when this external cause is fully processed) and maximum data age (longest time between the moment of a sensor measurement and the latest moment where an effect is based on this sensor measurement). In this paper, we provide an analysis of the end-to-end latencies in multi-executor ROS 2 systems to upper bound the end-to-end latencies of cause-effect chains in ROS 2 systems. Furthermore, we introduce an optimization using constrained programming that determines the optimal system configuration to minimize the end-to-end latencies for ROS 2 systems. We evaluate our upper-bound analysis to determine the end-to-end latencies of cause-effect chains in an autonomous driving-software stack for oval racing used in the Indy Autonomous Challenge and apply our optimization method to reduce the end-to-end latency upper bound, measured maximum, and measured mean by up to 50.2 %, 19.8 %, and 7.2 %, respectively.

Real-time tasks often exhibit correlated execution-time distributions due to common factors such as shared caches, resources, and inputs. Yet state-of-the-art probabilistic analysis still overlooks the impact of correlation, a gap that has been highlighted as a major open problem in the field. This paper responds to the open problem with the first correlation-aware analysis (CAA) of periodic tasks with stochastic execution times. The proposed analysis, which derives response-time distributions to infer upper bounds on deadline-failure probabilities, applies to a novel task model that incorporates information about both intra- and inter-task dependencies. In addition, the paper shows how to statistically infer the two model parameters using confidence intervals obtained via nonparametric bootstrapping. Notably, the inference method described is distribution-agnostic, meaning that it does not assume any particular probability distribution a priori, thereby eliminating a major risk of misclassifying the ground-truth execution behavior. By design, CAA dominates state-of-the-art correlation-tolerant analysis (CTA). The significantly better accuracy of CAA is demonstrated via experiments with synthetically generated workloads, while a case study based on the WATERS’ 17 industrial challenge provides a proof-of-concept of the statistical inference method.

The robot operating system 2 (ROS 2) is a widely used collection of tools and libraries for building robot applications. It is designed to be flexible and easy to use when creating complex robot systems with many interacting components.Since its alpha version release in 2015, ROS 2 provides two options in a multithreading operating system, namely the single-threaded executor and the multithreaded executor. The single-threaded executor is starvation-free by design (i.e., every task is eventually executed) even in over-utilized systems, since the set of eligible task instances (called wait set) is only refilled once all the task instances in the wait set are executed. The multithreaded executor extends this mechanism to multiple threads that manage the wait set collaboratively. While intuitively this extension preserves the starvation-free property, and analyses for the multithreaded executor even build upon this assumption, the multithreaded executor has not been shown to be starvation-free.In this work, we examine the mechanism of the multithreaded executor in ROS 2 and demonstrate that it is prone to starvation, i.e., some tasks may never be executed even in under-utilized systems. This indicates risks for multithreaded executors in the current ROS 2 design and further leads to counterexamples to the state-of-the-art response-time analyses by Jiang et al. (RTSS 2022) and Sobhani et al. (RTAS 2023). We propose a minimal change in the software architecture of the ROS 2 multithreaded executor to enable starvation- and deadlock-free behavior. We empirically test that we prevent starvation in concrete ROS 2 system configurations, and show that our solution incurs a negligible overhead using the autoware reference benchmark. Moreover, we prove that our solution is starvation- and deadlock-free using formal proofs and model checking.

This lightning talk introduces the motivations of the needs of formal properties that can be used modularly to compose safe and tight analysis and optimization for the scheduler design and schedulability test problems for cyber-physical real-time systems. The key challenge is the correct and precise translation from different schedule functions to proper mathematical properties that can be further used for property-based modulable designs.

ROS 2 is a framework consisting of software libraries for developing robot systems, such as autonomous driving systems, that consist of multiple interacting components. In ROS 2, each component is implemented as a node, which contains time-triggered and event-triggered tasks. These tasks communicate with each other via ROS 2 topics or shared memory, and are scheduled by a ROS 2 executor. In ROS 2 systems, the system configuration and callback execution can have a significant impact on system performance, including end-to-end latencies, message loss, and memory usage. In this paper, we provide a bound on the timer period of ROS 2 timers to prevent sensor undersampling, and a subscription buffer size limit to prevent message loss and minimize memory usage. Furthermore, we explain the occurrence of message loss and high end-to-end latencies in ROS 2 systems, which are caused by the system configuration and subscription buffer size choice. Based on our observations, we propose a callback-prioritization heuristic to reduce end-to-end latencies and subscription buffer sizes. We demonstrate our findings using case studies based on Autoware.Universe and provide further evaluation to highlight the benefits of our heuristic.

The concept of a probabilistic worst-case execution time (pWCET) has gradually emerged from the work of many authors over the course of 2–3 decades. Intuitively, pWCET is a simplifying model abstraction that safely over-approximates the ground-truth probabilistic execution time (pET) of a real-time task. In particular, when analyzing the cumulative processor demand of multiple jobs, the pWCET abstraction is intended to allow for the use of techniques from probability theory that require random variables to be independent and identically distributed (IID), even though the underlying ground-truth pET random variables are usually not independent. However, while powerful, the pWCET concept is subtle and difficult to define precisely, and easily misinterpreted. To place the pWCET concept on firm, unambiguous mathematical foundations, this paper proposes the first rigorous, axiomatic definition of pWCET that is suitable for formal proof. In addition, an adequacy property is stated that formally captures the intuitive notion of an “IID upper bound on pET.” The proposed pWCET definition is shown to satisfy this adequacy condition, and thereby is the first notion of pWCET for which the IID guarantee is formally established. All definitions and proofs have been verified with the Coq proof assistant.

Increasing performance needs of modern cyber-physical systems leads to multiprocessor architectures being increasingly utilized. To efficiently exploit their potential parallelism in hard real-time systems, appropriate task models and scheduling algorithms that allow to provide timing guarantees are required. Such scheduling algorithms and the corresponding worst-case response time analyses usually suffer from resource over-provisioning due to pessimistic analyses based on worst-case assumptions. Hence, scheduling algorithms and analyses with high resource efficiency are required. A prominent fine-grained parallel task model is the directed-acyclic-graph (DAG) task model that is composed of precedence constrained subjobs. This paper studies the hierarchical real-time scheduling problem of sporadic arbitrary-deadline DAG tasks. We propose a parallel path progression scheduling property that is implemented with only two distinct subtask priorities, which allows to quantify the parallel execution of a user chosen collection of complete paths in the response time analysis. This novel approach significantly improves the state-of-the-art response time analyses for parallel DAG tasks for highly parallel DAG structures and can provably exhaust large core numbers. Two hierarchical scheduling algorithms are designed based on this property, extending the parallel path progression properties and improve the response time analysis for sporadic arbitrary-deadline DAG task sets.

Real-time systems require the formal guarantee of timing constraints, not only for the individual tasks but also for the end-to-end latency of data flows. The data flow among multiple tasks, e.g., from sensors to actuators, is described by a cause-effect chain, independent from the priority order of the tasks. In this article, we provide an end-to-end timing-analysis for cause-effect chains on asynchronized distributed systems with periodic task activations, considering the maximum reaction time (MRT) (i.e., the duration of data processing) and the maximum data age (MDA) (i.e., the worst-case data freshness). We first provide an analysis of the end-to-end latency on one local electronic control unit (ECU) that has to consider only the jobs in a bounded time interval. We extend our analysis to globally asynchronized systems by exploiting a compositional property to combine the local results. Throughout synthesized data based on an automotive benchmark as well as on randomized parameters, we show that our analytical results improve the state-of-the-art.

In many embedded systems, for instance, in the automotive, avionic, or robotics domain, critical functionalities are implemented via chains of communicating recurrent tasks. To ensure safety and correctness of such systems, guarantees on the reaction time, that is, the delay between a cause (e.g., an external activity or reading of a sensor) and the corresponding effect, must be provided. Current approaches focus on the maximum reaction time, considering the worst-case system behavior. However, in many scenarios, probabilistic guarantees on the reaction time are sufficient. That is, it is sufficient to provide a guarantee that the reaction does not exceed a certain threshold with (at least) a certain probability. This work provides such probabilistic guarantees on the reaction time, considering two types of randomness: response time randomness and failure probabilities. To the best of our knowledge, this is the first work that defines and analyzes probabilistic reaction time for cause-effect chains based on sporadic tasks.

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.

In soft real-time systems, tasks may occasionally miss their deadlines. This possibility has triggered research on probabilistic timing analysis for the execution time of a single program and probabilistic response time analysis of concurrently executed tasks. Under fixed-priority preemptive uniprocessor scheduling, it was shown that the classical critical instant theorem (for deriving the worst-case schedulability or response time) by Liu and Layland (in JACM 1973) can be applied to analyze the worst-case deadline failure probability (WCDFP) and the worst-case response time exceedance probability (WCRTEP). In this work, we present a counterexample for this result, showing that the WCDFP and WCRTEP derived by the classical critical instant theorem is unsound. We further provide two sound methods: one is to account for one additional carry-in job of a higher-priority task and another is to sample and inflate the execution time of certain jobs without adding one additional carry-in job. We show that these two methods do not dominate each other and, in the evaluation, apply them to two well-known approaches based on direct convolution and Chernoff bounds.

In real-time systems, schedulability analyses provide the required timing guarantees. However, current suspension-aware analyses are limited to Task-Level Fixed-Priority (TFP) scheduling or Earliest-Deadline-First (EDF) scheduling of constrained-deadline self-suspending task systems. In this work, we provide a unifying schedulability analysis for uniprocessor Global EDF-Like (GEL) schedulers of arbitrary-deadline task sets. While analyses for EDF-Like schedulers are rare, many widely used scheduling algorithms can be considered as EDF-Like, for example, EDF, First-In-First-Out (FIFO), Earliest-Quasi-Deadline-First (EQDF), and Suspension-Aware EDF (SAEDF). Therefore, the provided analysis is applicable to those algorithms. It can be applied to TFP scheduling as well. Our analysis is the first suspension-aware schedulability analysis for arbitrary-deadline sporadic real-time task systems under Job-Level Fixed-Priority (JFP) scheduling, such as EDF, and the first unifying suspension-aware schedulability analysis framework that covers a wide range of scheduling algorithms. Through numerical simulations, we show that our analysis improves the state of the art for constrained-deadline EDF scenarios.

Modern autonomous vehicle platforms feature many interacting components and sensors, which add to the system complexity and affect their performance. A key aspect for such platforms are end-to-end timing guarantees, which are required for safe and predictable behavior in every situation. One widely used tool to develop such autonomous systems is the Robot Operating System 2 (ROS2), which allows creating robot applications composed of several components that communicate with each other to form complex systems. Furthermore, it guarantees real-time constraints and provides reliable timing behavior using a custom scheduler design that manages the execution of all components. These components and their data propagation form multiple cause-effect chains that can be analyzed to determine two key metrics: maximum reaction time (which is the maximum time for the system to react to an external input) and maximum data age (which equals the maximum time between sampling and the output of the system being based on that sample). However, an end-to-end analysis for cause-effect chains in ROS2 systems has not been provided yet. In this paper, we provide a theoretical upper bound for the end-to-end timing of a ROS2 system on a single electronic control unit (ECU). Additionally, we show how to simulate a ROS2 system to get a lower bound for the timing analysis and introduce an online end-to-end timing measurement method for existing ROS2 systems. We evaluate our methods with a basic autonomous navigation system and determine the timing behavior for different components and sensor configurations.

The performance of multiprocessor synchronization and locking protocols is a key factor to utilize the computation power of multiprocessor systems under real-time constraints. While multiple protocols have been developed in the past decades, their performance highly depends on the task partition and prioritization. The recently proposed Dependency Graph Approach showed its advantages and attracted a lot of interest. It is, however, restricted to task sets where each task has at most one critical section. In this article, we remove this restriction and demonstrate how to utilize algorithms for the classical job shop scheduling problem to construct a dependency graph for tasks with multiple critical sections. To show the applicability, we discuss the implementation in$\text{LITMUS}^{\text{RT}}$and report the overheads. Moreover, we provide extensive numerical evaluations under different configurations, which in many situations show significant improvement compared to the state-of-the-art.

In-memory wear-leveling has become an important research field for emerging non-volatile main memories over the past years. Many approaches in the literature perform wear-leveling by making use of special hardware. Since most non-volatile memories only wear out from write accesses, the proposed approaches in the literature also usually try to spread write accesses widely over the entire memory space. Some non-volatile memories, however, also wear out from read accesses, because every read causes a consecutive write access. Software-based solutions only operate from the application or kernel level, where read and write accesses are realized with different instructions and semantics. Therefore different mechanisms are required to handle reads and writes on the software level. First, we design a method to approximate read and write accesses to the memory to allow aging aware coarse-grained wear-leveling in the absence of special hardware, providing the age information. Second, we provide specific solutions to resolve access hot-spots within the compiled program code (text segment) and on the application stack. In our evaluation, we estimate the cell age by counting the total amount of accesses per cell. The results show that employing all our methods improves the memory lifetime by up to a factor of 955×.

Gang scheduling has long been adopted by the high-performance computing community as a way to reduce the synchronization overhead between related threads. It allows for several threads to execute in lock steps without suffering from long busy-wait periods or be penalized by large context-switch overheads. When combined with non-preemptive execution, gang scheduling significantly reduces the execution time of threads that work on the same data by decreasing the number of memory transactions required to load or store the data. In this work, we focus on two main types of gang tasks: rigid and moldable. A moldable gang task has a presumed known minimum and maximum number of cores on which it can be executed at runtime, while a rigid gang task always executes on the same number of cores. This work presents the first response-time analysis for non-preemptive moldable gang tasks. Our analysis is based on the notion of schedule abstraction; a new approach for response-time analysis with the promise of high accuracy. Our experiments on periodic rigid gang tasks show that our analysis is 4.9 times more successful in identifying schedulable tasks than the existing utilization-based test for rigid gang tasks.

Real-time systems require the formal guarantee of timing-constraints, not only for the individual tasks but also for the data-propagation paths. A cause-effect chain describes the data flow among multiple tasks, e.g., from sensors to actuators, independent from the priority order of the tasks. In this paper, we provide an end-to-end timing-analysis for cause-effect chains on asynchronized distributed systems with periodic task activations, considering the maximum reaction time (duration of data processing) and the maximum data age (worst-case data freshness). On one local electronic control unit (ECU), we present how to compute the exact local (worst-case) end-to-end latencies when the execution time of the periodic tasks is fixed. We further extend our analysis to globally asynchronized systems by combining the local results. Throughout synthesized data based on an automotive benchmark as well as on randomized parameters, we show that our analytical results improve the state-of-the-art for periodic task activations.

Multiprocessor resource synchronization and locking protocols are of great importance to utilize the computation power of multiprocessor real-time systems. Hence, in the past decades a large number of protocols have been developed and analyzed. The recently proposed dependency graph approach has significantly improved the schedulability for frame-based and periodic real-time task systems. However, the dependency graph approach only supports non-nested resource access, i.e., each critical section can only access one shared resource. In this paper, we develop a dependency graph based protocol that allows nested resource access, where a critical section can access multiple shared resources at the same time. First, constraint programming is applied to construct a dependency graph that determines the execution order of critical sections. Afterwards, a schedule is generated based on this order. To show the feasibility of our proposed protocol, we provide extensive numerical evaluations under different configurations. The evaluation results show that our approach has very good performance with respect to schedulability for frame-based and periodic real-time task systems, whereas the existing results applicable for sporadic task systems have worse performance under such a limited setting.

Determining a soft or firm real-time task’s probabilistic worst-case response time is a central goal when quantifying and bounding the probability of deadline misses, but current approaches are either (i) fast, but coarse-grained analytical bounds without precision guarantees, (ii) based on convolution and suffer from high space and time complexity, or (iii) combine convolution with resampling techniques that accrue pessimism in an uncontrolled manner. As a new alternative, this paper provides the first probabilistic response-time analysis method based on Monte Carlo simulation, which provides a controlled trade-off between analysis runtime, the desired degree of accuracy, and the permissible probability of a misestimate. An evaluation shows the proposed Monte Carlo analysis to routinely provide more accurate worst-case deadline failure probability (WCDFP) estimates than prior approaches, especially when considering large task sets (where prior methods struggle). In particular, it is shown to scale to workloads with up to 500 tasks while achieving one to three orders of magnitude better precision than analytical or convolution-based approaches (given an equivalent time budget).

Probabilistic timing guarantees enable a tradeoff between system safety and hardware costs in embedded real-time systems. A key metric for assessing whether timing requirements can be satisfied with sufficiently high probability is the worst-case deadline failure probability (WCDFP). This paper studies the WCDFP under earliest-deadline first (EDF) scheduling for tasks with several probabilistic execution modes (e.g., a low-needs "typical" mode and a resource-intensive "exceptional" mode). Under EDF, no known approach can bound the WCDFP for practically sized workloads since the time complexity of prior approaches is exponential in the number of jobs.This paper examines the structure of the EDF WCDFP problem and establishes a safe, efficiently computable over-approximation by restricting the analysis to a set of specific intervals and providing a criterion to stop the derivation early without risking under-approximation. The analysis first assumes independent jobs and is then extended to handle dependencies (i.e., acyclic task chains). An evaluation shows that (i) even if 99.9999% of the jobs must meet their deadlines, a significantly higher utilization is possible than in the deterministic case, (ii) the analysis is scalable to 30 tasks with more than 1060jobs in the hyperperiod, and (iii) assuming independence in the presence of dependent tasks can severely under-estimate the WCDFP.

Numerical simulations often play an important role when evaluating and comparing the performance of schedulability tests, as they allow to empirically demonstrate their applicability using synthesized task sets under various configurations. In order to provide a fair comparison of various schedulability tests, von der Brüggen et al. presented the first version of an evaluation framework for self-suspending task sets. In this work-in-progress, we further enhance the framework by providing more features to ease the use, e.g., Python 3 support, an improved GUI, multiprocessing, Gurobi optimization, and external task evaluation. In addition, we integrate the state-of-the-arts we are aware of into the framework. Moreover, the documentation is improved significantly to simplify the application in further research and development. To the best of our knowledge, the framework contains all suspension-aware schedulability tests for uniprocessor systems and we aim to keep it up-to-date.

Emerging non-volatile memory (NVM) architectures are considered as a replacement for DRAM and storage in the near future, since NVMs provide low power consumption, fast access speed, and low unit cost. Due to the lower write-endurance of NVMs, several in-memory wear-leveling techniques have been studied over the last years. Since most approaches propose or rely on specialized hardware, the techniques are often evaluated based on assumptions and in-house simulations rather than on real systems. To address this issue, we develop a setup consisting of a gem5 instance and an NVMain2.0 instance, which simulates an entire system (CPU, peripherals, etc.) together with an NVM plugged into the system. Taking a recorded memory access pattern from a low-level simulation into consideration to design and optimize wear-leveling techniques as operating system services allows a cross-layer design of wear-leveling techniques. With the insights gathered by analyzing the recorded memory access patterns, we develop a software-only wear-leveling solution, which does not require special hardware at all. This algorithm is evaluated afterwards by the full system simulation.

For many cyber-physical systems, e.g., IoT systems and autonomous vehicles, offloading workload to auxiliary processing units has become crucial. However, since this approach highly depends on network connectivity and responsiveness, typically only non-critical tasks are offloaded, which have less strict timing requirements than critical tasks. In this work, we provide two protocols allowing to offload critical and non-critical tasks likewise, while providing different service levels for non-critical tasks in the event of an unsuccessful offloading operation, depending on the respective system requirements. We analyze the worst-case timing behavior of the local cyber-physical system and, based on these analyses, we provide a sufficient schedulability test for each of the proposed protocols. In the course of comprehensive experiments, we show that our protocols have reasonable acceptance ratios under the provided schedulability tests. Moreover, we demonstrate that the system behavior under our proposed protocols is strongly dependent on probability of unsuccessful offloading operations, the percentage of critical tasks in the system, and the amount of offloaded workload.

The increasing availability of heterogeneous ambient sensing systems challenges the according information processing systems to analyse and compare a variety of different systems in a single scenario. For instance, localization of objects can be performed by image processing systems as well as by radio based localization. If such systems are utilized to localize the same objects, synergy of the outputs is important to enable comparable and meaningful analysis. This demo showcases the practical deployment and challenges of such an example system.

Inter-core communication is a central challenge in many-core systems for which Network-on-chips (NoCs) have been demonstrated to scale well and to provide good overall performance. However, not only the distributed structure but also the link switching of NoCs have imposed a great challenge in the design and analysis for real-time systems where timing verification is mandatory. NoC protocols like worm-hole switching are designed with scalability and flexibility in mind, thus the existing link switching protocols usually consider each single link to be scheduled independently. The flexibility of such link-based arbitrations allows each packet to be distributed over multiple switches but also increases the number of possible link states (the number of flits in a buffer) that have to be considered in the worst-case timing analysis for real-time systems. To achieve timing predictability by design, we propose a family of less flexible switching protocols, called Simultaneous Progressing Switching Protocols (SP2), in which the links used by a flow either all simultaneously transmit one flit (if it exists) of this flow or none of them transmits any flit of this flow. Based on the all-or-nothing property of Sp2, we reduce the schedulability of the NoC to the uniprocessor self-suspension scheduling problem. Moreover, the proposed approach is not limited to any specific underlying routing protocols, which are usually constructed for deadlock avoidance instead of timing predictability.

While the earliest-deadline-first (EDF) scheduling algorithm has extensively been utilized in real-time systems, there is almost no literature considering EDF for task sets with dynamic self-suspension behavior. To be precise, there is no specialized result for uniprocessor systems, besides the trivial suspension-oblivious approach. The work by Liu and Anderson (in ECRTS 2013) and Dong and Liu (in RTSS 2016) for suspension-aware multiprocessor global EDF can also be applied to uniprocessor systems and therefore be considered the state-of-the-art. In this work, two novel schedulability analyses (one for sporadic and one for periodic task sets) for suspension-aware EDF on uniprocessor systems are proposed, which outperform the state-of-the-art on such systems in empirical and theoretical comparison. We further show that the analysis by Dong and Liu is in fact not suspension-aware for uniprocessor systems.

In soft real-time systems, applications can tolerate rare deadline misses. Therefore, probabilistic arguments and analyses are applicable in the timing analyses for this class of systems, as demonstrated in many existing researches. Convolution-based analyses allow to derive tight deadline-miss probabilities, but suffer from a high time complexity. Among the analytical approaches, which result in a significantly faster runtime than the convolution-based approaches, the Chernoff bounds provide the tightest results. In this paper, we show that calculating the deadline-miss probability using Chernoff bounds can be solved by considering an equivalent convex optimization problem. This allows us to, on the one hand, decrease the runtime of the Chernoff bounds while, on the other hand, ensure a tighter approximation since a larger variable space can be searched more efficiently, i.e., by using binary search techniques over a larger area instead of a sequential search over a smaller area. We evaluate this approach considering synthesized task sets. Our approach is shown to be computationally efficient for large task systems, whilst experimentally suggesting reasonable approximation quality compared to an exact analysis.

In the field of automotive engineering, broadcast buses, e.g., Controller Area Network (CAN), are frequently used to connect multiple electronic control units (ECUs). Each message transmitted on such buses can be received by each single participant, but not all messages are relevant for every ECU. For this purpose, all incoming messages must be filtered in terms of relevance by either hardware or software techniques. We address the issue of designing hardware filter configurations for clients connected to a broadcast bus in order to reduce the cost, i.e., the computation overhead, provoked by undesired but accepted messages. More precisely, we propose an SMT formulation that can be applied to i) retrieve a (minimal) perfect filter configuration, i.e., no undesired messages are received, ii) optimize the filter quality under given hardware restrictions, or iii) minimize the hardware cost for a given type of filter component and a maximum cost threshold.

In computing systems, a job may suspend itself (before it finishes its execution) when it has to wait for certain results from other (usually external) activities. For real-time systems, such self-suspension behavior has been shown to induce performance degradation. Hence, the researchers in the real-time systems community have devoted themselves to the design and analysis of scheduling algorithms that can alleviate the performance penalty due to self-suspension behavior. As self-suspension and delegation of parts of a job to non-bottleneck resources is pretty natural in many applications, researchers in the operations research (OR) community have also explored scheduling algorithms for systems with such suspension behavior, called the master-slave problem in the OR community. This paper first reviews the results for the master-slave problem in the OR literature and explains their impact on several long-standing problems for scheduling self-suspending real-time tasks. For frame-based periodic real-time tasks, in which the periods of all tasks are identical and all jobs related to one frame are released synchronously, we explore different approximation metrics with respect to resource augmentation factors under different scenarios for both uniprocessor and multiprocessor systems, and demonstrate that different approximation metrics can create different levels of difficulty for the approximation. Our experimental results show that such more carefully designed schedules can significantly outperform the state-of-the-art.

When considering recurrent real-time tasks in multiprocessor systems, access to shared resources, via so-called critical sections, can jeopardize the schedulability of the system. The reason is that resource access is mutual exclusive and a task must finish its execution of the critical section before another task can access the same resource. Therefore, the problem of multiprocessor synchronization has been extensively studied since the 1990s, and a large number of multiprocessor resource sharing protocols have been developed and analyzed. Most protocols assume work-conserving scheduling algorithms which make it impossible to schedule task sets where a critical section of one task is longer than the relative deadline of another task that accesses the same resource. The only known exception to the work-conserving paradigm is the recently presented Dependency Graph Approach where the order in which tasks access a shared resource is not determined online, but based on a pre-computed dependency graph. Since the initial work only considers frame-based task systems, this paper extends the Dependency Graph Approach to periodic task systems. We point out the connection to the uniprocessor non-preemptive scheduling problem and exploit the related algorithms to construct dependency graphs for each resource. To schedule the derived dependency graphs, List scheduling is combined with an earliest-deadline-first heuristic. We evaluated the performance considering synthesized task sets under different configurations, where a significant improvement of the acceptance ratio compared to other resource sharing protocols is observed. Furthermore, to show the applicability in real-world systems, we detail the implementation in LITMUSRTand report the resulting scheduling overheads.

Effectively handling precedence constraints and resource synchronization is a challenging problem in the era of multiprocessor systems even with massively parallel computation power. One common approach is to apply list scheduling to a given task graph with precedence constraints. However, in some application scenarios, such as the OpenMP task model and multiprocessor partitioned scheduling for resource synchronization using binary semaphores, several operations can be forced to be tied to the same processor, which invalidates the list scheduling. This paper studies a special case of this challenging scheduling problem, where a task comprised of (at most) three subtasks is executed sequentially on the same processor and the second subtasks of the tasks may have sequential dependencies, e.g., due to synchronization. We demonstrate the limits of existing algorithms and provide effective heuristics considering preemptive execution. The evaluation results show a significant improvement, compared to the existing multiprocessor partitioned scheduling strategies.

In general computing systems, a job (process/task) may suspend itself whilst it is waiting for some activity to complete, e.g., an accelerator to return data. In real-time systems, such self-suspension can cause substantial performance/schedulability degradation. This observation, first made in 1988, has led to the investigation of the impact of self-suspension on timing predictability, and many relevant results have been published since. Unfortunately, as it has recently come to light, a number of the existing results are flawed. To provide a correct platform on which future research can be built, this paper reviews the state of the art in the design and analysis of scheduling algorithms and schedulability tests for self-suspending tasks in real-time systems. We provide (1) a systematic description of how self-suspending tasks can be handled in both soft and hard real-time systems; (2) an explanation of the existing misconceptions and their potential remedies; (3) an assessment of the influence of such flawed analyses on partitioned multiprocessor fixed-priority scheduling when tasks synchronize access to shared resources; and (4) a discussion of the computational complexity of analyses for different self-suspension task models.

A cause-effect chain is used to define the logical order of data dependent tasks, which is independent from the execution order of the jobs of the (periodic/sporadic) tasks. Analyzing the worst-case End-to-End timing behavior, associated to a cause-effect chain, is an important problem in embedded control systems. For example, the detailed timing properties of modern automotive systems are specified in the AUTOSAR Timing Extensions. In this paper, we present a formal End-to-End timing analysis for distributed systems. We consider the two most important End-to-End timing semantics, i.e., the button-to-action delay (termed as the maximum reaction time ) and the worst-case data freshness (termed as the maximum data age ). Our contribution is significant due to the consideration of the sporadic behavior of job activations, whilst the results in the literature have been mostly limited to periodic activations. The proof strategy shows the (previously unexplored) connection between the reaction time (data age, respectively) and immediate forward (backward, respectively) job chains. Our analytical results dominate the state of the art for sporadic task activations in distributed systems and the evaluations show a clear improvement for synthesized task systems as well as for a real world automotive benchmark setting.

This paper explores the probability of deadline misses for a set of constrained-deadline sporadic soft real-time tasks on uniprocessor platforms. We explore two directions to evaluate the probability whether a job of the task under analysis can finish its execution at (or before) a testing time point t. One approach is based on analytical upper bounds that can be efficiently computed in polynomial time at the price of precision loss for each testing point, derived from the well-known Hoeffding's inequality and the well-known Bernstein's inequality. Another approach convolutes the probability efficiently over multinomial distributions, exploiting a series of state space reduction techniques, i.e., pruning without any loss of precision, and approximations via unifying equivalent classes with a bounded loss of precision. We demonstrate the effectiveness of our approaches in a series of evaluations. Distinct from the convolution-based methods in the literature, which suffer from the high computation demand and are applicable only to task sets with a few tasks, our approaches can scale reasonably without losing much precision in terms of the derived probability of deadline misses.

The sporadic task model is often used to analyze recurrent execution of tasks in real-time systems. A sporadic task defines an infinite sequence of task instances, also called jobs, that arrive under the minimum inter-arrival time constraint. To ensure the system safety, timeliness has to be guaranteed in addition to functional correctness, i.e., all jobs of all tasks have to be finished before the job deadlines. We focus on analyzing arbitrary-deadline task sets on a homogeneous (identical) multiprocessor system under any given global fixed-priority scheduling approach and provide a series of schedulability tests with different tradeoffs between their time complexity and their accuracy. Under the arbitrary-deadline setting, the relative deadline of a task can be longer than the minimum inter-arrival time of the jobs of the task. We show that global deadline-monotonic (DM) scheduling has a speedup bound of 3-1/M against any optimal scheduling algorithms, where M is the number of identical processors, and prove that this bound is asymptotically tight.

In real-time systems, in addition to the functional correctness recurrent tasks must fulfill timing constraints to ensure the correct behavior of the system. Partitioned scheduling is widely used in real-time systems, i.e., the tasks are statically assigned onto processors while ensuring that all timing constraints are met. The decision version of the problem, which is to check whether the deadline constraints of tasks can be satisfied on a given number of identical processors, has been known NP-complete in the strong sense. Several studies on this problem are based on approximations involving resource augmentation, i.e., speeding up individual processors. This paper studies another type of resource augmentation by allocating additional processors, a topic that has not been explored until recently. We provide polynomial-time algorithms and analysis, in which the approximation factors are dependent upon the input instances. Specifically, the factors are related to the maximum ratio of the period to the relative deadline of a task in the given task set. We also show that these algorithms unfortunately cannot achieve a constant approximation factor for general cases. Furthermore, we prove that the problem does not admit any asymptotic polynomial-time approximation scheme (APTAS) unless P=NP when the task set has constrained deadlines, i.e., the relative deadline of a task is no more than the period of the task.

Many practical real-time systems must be able to sustain several reliability threats induced by their physical environments that cause short-term abnormal system behavior, such as transient faults. To cope with this change of system behavior, online adaptions, which may introduce a high computation overhead, are performed in many cases to ensure the timeliness of the more important tasks while no guarantees are provided for the less important tasks. In this work, we propose a system model which does not require any online adaption, but, according to the concept of dynamic real-time guarantees, provides full timing guarantees as well as limited timing guarantees, depending on the system behavior. For the normal system behavior, timeliness is guaranteed for all tasks; otherwise, timeliness is guaranteed only for the more important tasks while bounded tardiness is ensured for the less important tasks. Aiming to provide such dynamic timing guarantees, we propose a suitable system model and discuss, how this can be established by means of partitioned as well as semi-partitioned strategies. Moreover, we propose an approach for handling abnormal behavior with a longer duration, such as intermittent faults or overheating of processors, by performing task migration in order to compensate the affected system component and to increase the system's reliability. We show by comprehensive experiments that good acceptance ratios can be achieved under partitioned scheduling, which can be further improved under semi-partitioned strategies. In addition, we demonstrate that the proposed migration techniques lead to a reasonable trade-off between the decrease in schedulability and the gain in robustness of the system. The presented approaches can also be applied to mixed-criticality systems with two criticality levels.

This paper studies the problem of scheduling a set of hard real-time sporadic tasks that may access CPU cores and a shared resource. Motivated by the observation that the CPU resource is often abundant compared to the shared resources in multi-core and many-core systems, we propose to resolve this problem from a counter-intuitive shared-resource-centric perspective, focusing on judiciously prioritizing and scheduling tasks' requests in a limited preemptive manner on the shared resource while viewing the worst-case latency a task may experience on the CPU cores as suspension delays. We develop a rather comprehensive set of task partitioning algorithms that partition tasks onto the shared resource with the objective of guaranteeing schedulability while minimizing the required size of the shared resource, which plays a critical role in reducing the overall cost and complexity of building resource-constrained embedded systems in many application domains. A GPU-based prototype case study and extensive simulation-based experiments have been conducted, which validate both our shared-resource-centric scheduling philosophy and the efficiency of our suspension-based partitioning solutions in practice.

Timeliness is an important feature for many embedded systems. Although soft real-time embedded systems can tolerate and allow certain deadline misses, it is still important to quantify them to justify whether the considered systems are acceptable. In this paper, we provide a way to safely over-approximate the expected deadline miss rate for a specific sporadic real-time task under fixed-priority preemptive scheduling in uniprocessor systems. Our approach is compatible with the existing results in the literature that calculate the probability of deadline misses either based on the convolution-based approaches or analytically. We demonstrate our approach by considering randomly generated task sets with an execution behavior that simulates jobs that are subjected to soft errors incurred by hardware transient faults under a given fault rate. To empirically gather the deadline miss rates, we implemented an event-based simulator with a fault-injection module and release the scripts. With extensive simulations under different fault rates, we evaluate the efficiency and the pessimism of our approach. The evaluation results show that our approach is effective to derive an upper bound of the expected deadline miss rate and efficient with respect to the required computation time.

Self-suspending behavior in real-time embedded systems can have a major and non-trivial negative impact on timing predictability. In this work, we investigate how to analyze the schedulability of segmented self-suspending task systems under a fixed-priority assignment. For this purpose, we introduce the multi-segment workload function as well as the maximum workload function in order to quantify the maximum interference from the higher-priority tasks when constructing our (sufficient) schedulability test. Moreover, we derive an optimal priority assignment with respect to our schedulability test since it is compatible with Audsley's Optimal Priority Assignment (OPA). We show by means of comprehensive evaluations that our approach is highly effective concerning the number of schedulable task sets. Furthermore, one set of results reveals a rather non-intuitive observation, namely, that the worst-case suspension time of a computation segment should also be respected to improve the schedulability even if the suspension may finish earlier.

Over the years, many multiprocessor locking protocols have been designed and analyzed. However, the performance of these protocols highly depends on how the tasks are partitioned and prioritized, and how the resources are shared locally and globally. This paper answers a few fundamental questions when real-time tasks share resources in multiprocessor systems. We explore the fundamental difficulty of the multiprocessor synchronization problem and show that a very simplified version of this problem is NP-hard in the strong sense regardless of the number of processors and the underlying scheduling paradigm. Therefore, the allowance of preemption or migration does not reduce the computational complexity. On the positive side, we develop a dependency-graph approach that is specifically useful for frame-based real-time tasks, i.e., when all tasks have the same period and release their jobs always at the same time. We present a series of algorithms with speedup factors between 2 and 3 under semi-partitioned scheduling. We further explore methodologies for and tradeoffs between preemptive and non-preemptive scheduling algorithms, and partitioned and semi-partitioned scheduling algorithms. Our approach is extended to periodic tasks under certain conditions.

Multicore systems are increasingly utilized in real-time systems in order to address the high computational demands. To fully exploit the advantages of multicore processing, possible intra-task parallelism modeled as a directed acyclic graph (DAG) must be utilized efficiently. This paper considers the scheduling problem for parallel real-time tasks with constrained and arbitrary deadlines. In contrast to prior work in this area, it generalizes federated scheduling and proposes a novel reservation-based approach. Namely, we propose a reservation-based federated scheduling strategy that reduces the problem of scheduling arbitrary-deadline DAG task sets to the problem of scheduling arbitrary-deadline sequential task sets by allocating reservation servers. We provide the general reservation design for sporadic parallel tasks, such that any scheduling algorithm and analysis for sequential tasks with arbitrary deadlines can be used to execute the allocated reservation servers of parallel tasks. Moreover, the proposed reservation-based federated scheduling algorithms provide constant speedup factors with respect to any optimal scheduler for arbitrary-deadline DAG task sets. We demonstrate via numerical and empirical experiments that our algorithms are competitive with the state of the art.

Using Redundant Multithreading (RMT) for error detection and recovery is a prominent technique to mitigate soft-error effects in multi-core systems. Simultaneous Redundant Threading (SRT) on the same core or Chip-level Redundant Multithreading (CRT) on different cores can be adopted to implement RMT. However, only a few previously proposed approaches use adaptive CRT managements on the system level and none of them considers both SRT and CRT on the task level. In this paper, we propose to use a combination of SRT and CRT, called Mixed Redundant Threading (MRT), as an additional option on the task level. In our coarse-grained approach, we consider SRT, CRT, and MRT on the system level simultaneously, while the existing results only apply either SRT or CRT on the system level, but not simultaneously. In addition, we consider further fine-grained task level optimizations to improve the system reliability under hard real-time constraints. To optimize the system reliability, we develop several dynamic programming approaches to select the redundancy levels under Federated Scheduling. The simulation results illustrate that our approaches can significantly improve the system reliability compared to the state-of-the-art techniques.

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.

To tackle the unavoidable self-suspension behavior due to I/O-intensive interactions, multi-core processors, computation offloading systems with coprocessors, etc., the dynamic and the segmented self-suspension sporadic task models have been widely used in the literature. We propose new self-suspension models that are hybrids of the dynamic and the segmented models. Those hybrid models are capable of exploiting knowledge about execution paths, potentially reducing modelling pessimism. In addition, we provide the corresponding schedulability analysis under fixed-relative-deadline (FRD) scheduling and explain how the state-of-the-art FRD scheduling strategy can be applied. Empirically, these hybrid approaches are shown to be effective with regards to the number of schedulable task sets.

In computing systems, a job/process/task/thread may suspend itself when it has to wait for some other internal or external activities, such as computation offloading or memory accesses, to finish before it can continue its execution. In the literature, there are two commonly adopted self-suspending sporadic task models in real-time systems: 1) the dynamic self-suspension model and 2) the segmented self-suspension sporadic task model. A dynamic self-suspending sporadic task is specified with an upper bound on the maximum suspension time for a job (task instance), which allows a job to dynamically suspend itself arbitrary often as long as the suspension time upper bound is not violated. By contrast, a segmented self-suspending sporadic task has a predefined execution and suspension pattern in an interleaving manner. The dynamic self-suspension model is very flexible but inaccurate, whilst the segmented self-suspension model is very restrictive but very accurate. The gap between these two widely-adopted self-suspension task models can be potentially filled by the hybrid self-suspension task model. The investigation of the impact of self-suspension on timing predictability has been started in 1988. This survey paper provides a short summary of the state of the art in the design and analysis of scheduling algorithms and schedulability tests for self-suspending tasks in real-time systems.

In many practical real-time systems, the physical environment and the system platform can impose uncertain execution behaviour to the system. For example, if transient faults are detected, the execution time of a task instance can be increased due to recovery operations. Such fault recovery routines make the system very vulnerable with respect to meeting hard real-time deadlines. In theory and in practical systems, this problem is often handled by aborting not so important tasks to guarantee the response time of the more important tasks. However, for most systems such faults occur rarely and the results of not so important tasks might still be useful, even if they are a bit late. This implicates to not abort these not so important tasks but keep them running even if faults occur, provided that the more important tasks still meet their hard real time properties. In this paper, we present Systems with Dynamic Real-Time Guarantees to model this behaviour and determine if the system can provide full timing guarantees or limited timing guarantees without any online adaptation after a fault occurred. We present a schedulability test, provide an algorithm for optimal priority assignment, determine the maximum interval length until the system will again provide full timing guarantees and explain how we can monitor the system state online. The approaches presented in this paper can also be applied to mixed criticality systems with dual criticality levels.

For real time task sets, allowing preemption is often considered to be important to ensure the schedulability, as it allows high-priority tasks to be allocated to the processor nearly immediately. However, preemptive scheduling also introduces some additional overhead and may not be allowed for some hardware components, which motivates the needs of non-preemptive or limited-preemptive scheduling. We present a safe sufficient schedulability test for non-preemptive (NP) fixed priority scheduling that can verify the schedulability for Deadline Monotonic (DM-NP) and Rate Monotonic (RM-NP) scheduling in linear time, if task orders according to priority and period are given. This test leads to a better upper bound on the speedup factor for DM-NP and RM-NP in comparison to Earliest Deadline First (EDF-NP) than previously known, closing the gab between lower and upper bound. We improve our test, resulting in interesting properties of the blocking time that allow to determine schedulability by only considering the schedulability of the preemptive case if some conditions are met. Furthermore, we present a utilization bound for RM-NP, based on the ratio γ > 0 of the upper bound of the maximum blocking time to the execution time, significantly improving previous results.