Software reusability and system modularity are key features of modern autonomous systems. As a consequence, there is a rapid shift towards hierarchical and compositional architecture, as evidenced by AUTOSAR in automobiles and ROS2 in robotics. The resource-budget supply model is widely applied in the real-time analysis of such systems. Meanwhile, real-time systems with multiple critical levels have received significant attention from the research community and industry. These systems are designed with multiple execution budgets for multiple system-critical levels. Existing studies on mixedcriticality systems consider a dedicated resource supply. This paper considers a novel generalized system model with multiple execution estimations and resource-budget supplies for compositional systems. An analytical model and a demand-bound function-based schedulability test are presented for the EDFbased scheduler in the proposed compositional mixed-criticality system. A range for setting the resource supply period is derived to ensure the schedulability of workloads when supply budgets are known. The general performance of the scheduling framework and its wider applicability is further demonstrated and evaluated using synthetic workloads and resource models, where synthetic workload parameters are derived through a case study on an autonomous driving system.

Real-time systems are characterized by strict timing constraints represented by deadlines. Some systems are tight, such that jobs finish their execution right at the deadlines in the worst case, while others may not be so tight. Static slack is a concept that captures such non-tightness, and it can often be “stolen” to handle additional aperiodic job requests, task suspensions, and occasional task overruns. This paper identifies an interesting and direct correlation between worst-case response time (WCRT) and static slack in a deadline-driven uniprocessor system. We propose a systematic approach for safely constructing a set of Sporadic P-Servers to tightly capture the available static slack, given any feasible task set under a preemptive earliest deadline first. These P-Servers are special in that each task has only a unit-length execution budget and runs in a discrete manner. To leverage these P-Servers and “steal” the slack, we propose a novel consume-replenish algorithm to handle online hard aperiodic jobs. We also extend the theory for other applications, such as dealing with early and arbitrary self-suspensions and servicing job overruns in mixed-criticality systems without triggering a mode switch. Experiments demonstrate that the proposed theory can provide new and better schedulability in some subcases for each application.

While traditional real-time systems analysis requires single pessimistic estimates to represent system parameters, the mixed-criticality (MC) design proposes to use multiple estimates of system parameters with different levels of pessimism, resulting in low critical workloads sacrificed at run-time in order to provide guarantees to high critical workloads. Shortcomings of the MC design were improved recently by the precise MC scheduling technique in which the processor speed is increased at run-time to provide guarantees to both low and high critical workloads. Aiming to extend the precise MC scheduling to multiprocessor computing platforms, this paper proposes three novel scheduling algorithms that are based on virtual-deadline and fluid-scheduling approaches. We prove the correctness of our proposed algorithms through schedulability analysis and also present their theoretical effectiveness via speedup bounds and approximation factor calculations. Finally, we evaluate their performance experimentally via randomly generated task sets and demonstrate that the fluid-scheduling algorithms outperform the virtual-deadline algorithm.

Robot Operating System (ROS) is the most popular framework for developing robotics software. Typically, robotics software is safety-critical and employed in real-time systems requiring timing guarantees. Since the first generation of ROS provides no timing guarantee, the recent release of its second generation, ROS2, is necessary and timely, and has since received immense attention from practitioners and researchers. Unfortunately, the existing analysis of ROS2 showed the peculiar scheduling strategy of ROS2 executor, which severely affects the response time of ROS2 applications. This paper proposes a deadline-based scheduling strategy for the ROS2 executor. It further presents an analysis for an end-to-end response time of ROS2 workload (processing chain) and an evaluation of the proposed scheduling strategy for real workloads.

Many safety-critical real-time systems are considered certified when they meet failure probability requirements with respect to the maximum permitted incidences of failure per hour. In this article, the mixed-criticality task model with multiple worst case execution time (WCET) estimations is extended to incorporate such system-level certification restrictions. A new parameter is added to each task, characterizing the distribution of WCET estimations—the likelihood of all jobs of a task finishing their executions within the less pessimistic WCET estimates. Efficient algorithms are derived for scheduling mixed-criticality systems represented using this model for both uniprocessor and multiprocessor platforms for independent tasks. Furthermore, a 0/1 covariance matrix is introduced to represent the failure dependency between tasks. An efficient algorithm is proposed to schedule such failure-dependent tasks. Experimental analyses show our new model and algorithm outperform current state-of-the-art mixed-criticality scheduling algorithms.

This work studies the hard-real-time routing problem in graphs: one needs to travel from a given vertex to another within a hard deadline. For each edge in the network, the worst-case delay that may be encountered across that edge is bounded. As far as this given bound is trustworthy at a very high level of assurance, it must be guaranteed that one will meet the specified deadline. The actual delays across edges are uncertain and the goal is to minimize the total expected delay while meeting the deadline. We propose a comprehensive solution to this problem. Specifically, if the precise a priori estimates of the delay probability distributions are available, we develop an optimal table-driven algorithm that identifies the route with the minimum expected delay. If those estimates are not precise (i.e., unknown or dynamic), we develop an efficient Q-Learning approach that leverages the table-driven algorithm to track the true distributions rapidly, while ensuring to meet the specified hard deadline. The proposed solution suggests a promising direction towards incorporating probabilistic information and learning-based approaches into safety-critical systems without compromising safety guarantees, when it is not feasible to establish the trustworthiness of the probabilistic information at the high assurance levels required for verification purposes.

The scheduling of mixed-criticality (MC) systems with graceful degradation is considered, where LO-criticality tasks are guaranteed some service in HI mode in the form of minimum cumulative completion rates. First, we present an easy to implement admission-control procedure to determine which LO-criticality jobs to complete in HI mode. Then, we propose a demand-bound-function-based MC schedulability test that runs in pseudo-polynomial time for such systems under EDF-VD scheduling, wherein two virtual deadline setting heuristics are considered. Furthermore, we discuss a mechanism for the system to switch back from HI to LO mode and quantify the maximum time duration such recovery process would take. Finally, we show the effectiveness of our proposed method by experimental evaluation in comparison to state-of-the-art MC schedulers.