Artificial-intelligence-powered real-time systems typically consist of numerous gang tasks, such as computations on graphics processing units (GPUs), that are interconnected by data-flow dependencies. Despite their relevance in many applications, scheduling processing graphs of gang tasks has received limited attention. This paper presents scheduling techniques and response-time analysis for such systems on heterogeneous computing platforms. Response-time bounds of a graph of gang tasks are presented when scheduled under a work-conserving or semi-work-conserving scheduler. Techniques to support multiple graphs using federated scheduling techniques are also presented. Experimental evaluations and a case study on a computer vision application are presented to demonstrate the effectiveness of the proposed approach.

Modern real-time workloads are often expressed as processing graphs that have complex dataflow dependencies. No scheduling algorithm with a holistic analysis of graph-based tasks is known that can provide bounded response times without utilization loss, thus ensuring soft-real-time optimality, when a node instance depends on some of its prior instances and multiple invocations of the same graph can be active simultaneously. This paper presents a scheduling policy for such a graph-based task and provides a response-time analysis that guarantees bounded response times without utilization loss. Experimental evaluations show that our scheduler yields significantly tighter response-time bounds than existing soft-real-time optimal schedulers.

The Robot Operating System 2 (ROS) is heavily used in autonomous systems due to its large ecosystem and modular design. However, ROS remains problematic for real-time applications despite prior efforts to improve its real-time capabilities. Many of these problems are rooted in the implementation of the ROS executor, which does not support preemption or userspecified priorities. These properties are fundamental to real-time scheduling and desirable for general systems to reduce latency. ROS variants in prior work have separately supported the preemption and prioritization of callbacks but place restrictions on the application, preventing their adoption in a real-world workload. This paper addresses these deficiencies with a novel executor framework,$\operatorname{ROS}^{\text{RT}}$, which is compatible with any type of ROS application while supporting preemptive, priority-driven scheduling. Additionally, to support flexible EDF scheduling in ROS${ }^{\text {RT }}$, a custom EDF scheduler implementation is proposed using the new Linux scheduling class SCHED_EXT. ROS${ }^{\text {RT }}$s flexibility and real-time compatibility do not come at the cost of overheads: it achieves a significant decrease in publisher-tosubscriber overhead from the native ROS executor. Finally, this paper concludes with a case study performed on the Autoware Reference System, which simulates the execution of the LiDAR module in an autonomous driving application, demonstrating the ability of$\operatorname{ROS}^{\text{RT}}$at real-time scheduling in real-world scenarios.

Due to the emergence of parallel architectures and parallel programming frameworks, modern real-time applications are often composed of parallel tasks that can occupy multiple processors at the same time. Among parallel task models, gang scheduling has received much attention in recent years due to its performance efficiency and applicability to parallel architectures such as graphics processing units. Despite this attention, the soft real-time (SRT) scheduling of gang tasks has received little attention. This paper, for the first time, considers the SRT-feasibility problem for gang tasks. Necessary and sufficient feasibility conditions are presented that relate the SRT-feasibility problem to the HRT-feasibility problem of "equivalent" task systems. Based on these conditions, intractability results for SRT gang scheduling are derived. This paper also presents server-based scheduling policies, corresponding schedulability tests, and an improved schedulability condition for the global-earliest-deadline-first (GEDF) scheduling of gang tasks. Moreover, GEDF is shown to be non-optimal in scheduling SRT gang tasks.

To certify the schedulability of a system, valid per-task worst-case execution-time (WCET) estimates are almost always required. Unfortunately, on multicore machines, deriving WCET estimates through static analysis that is not highly pessimistic may never be a practical reality. The alternative is to determine WCETs via a measurement process, but such a process cannot correctly produce accurate WCET estimates with certainty. This lack of certainty necessitates the use of overrun-handling mechanisms, such as budget-enforcement techniques, to preserve temporal correctness at runtime. In many systems of interest today, tasks are interconnected to form processing graphs, which can be quite large. The simplest (and perhaps most common) approach to budget enforcement in this case is to abort an entire graph invocation whenever any node (task) overruns its budget. However, such an approach can result in a high abort rate at the graph level even when the per-node abort rate is low. To remedy this situation, this paper presents a holistic budget-management strategy for directed acyclic graphs (DAGs) that involves reallocating per-node budgets to overrunning nodes to avoid DAG-Ievel aborts. To enable the effects of aborts to be studied analytically, a probabilistic analysis is presented to derive a DAG's abort rate under the proposed budget-management strategy. Experimental results are also presented to demonstrate the utility of budgeting graphs holistically.

Artificial-intelligence (AI) techniques are revolutionizing modern safety-critical real-time systems by enabling autonomous features never seen before. However, AI-based workloads are typically expressed as processing graphs that are subject to complex tradeoffs involving parallelism and dataflow dependencies. Due to such complexities, exact analysis of graph-based tasks is challenging under most (if not all) schedulers. This paper presents a periodic server-based scheduling policy for periodic graph-based task systems and provides an exact response-time analysis under this policy. This analysis entails pseudo-polynomial time complexity for pseudo-harmonic periodic graph-based tasks, which are commonly used in practice.

The global earliest-deadline-first (GEDF) scheduler and its variants are soft-real-time (SRT) optimal for periodic/sporadic tasks, meaning they provide bounded tardiness so long as the underlying platform is not over-utilized. Although their SRT-optimality has long been known, tight tardiness bounds for these schedulers have remained elusive. In this paper, a tardiness bound, that does not depend on the processor or task count, is derived for pseudo-harmonic periodic tasks, which are commonly used in practice, under global-EDF-like (GEL) schedulers. This class of schedulers includes both GEDF and first-in-first-out (FIFO). This bound is shown to be generally tight via an example. Furthermore, it is shown that exact tardiness bounds for GEL-scheduled pseudo-harmonic periodic tasks can be computed in pseudo-polynomial time.

Simultaneous multithreading (SMT) enables enhanced computing capacity by allowing multiple tasks to execute concurrently on the same computing core. Despite its benefits, its use has been largely eschewed in work on real-time systems due to concerns that tasks running on the same core may adversely interfere with each other. In this paper, the safety of using SMT in a mixed-criticality multicore context is considered in detail. To this end, a prior open-source framework called MC2(mixedcriticality on multicore), which provides features for mitigating cache and memory interference, was re-implemented to support SMT on an SMT-capable multicore platform. The creation of this new, configurable MC2variant entailed producing the first operating-system implementations of several recently proposed real-time SMT schedulers and tying them together within a mixed-criticality context. These schedulers introduce new spatialisolation challenges, which required introducing isolation at both the L2 and L3 cache levels. The efficacy of the resulting MC2variant is demonstrated via three experimental efforts. The first involved obtaining execution data using a wide range of benchmark suites, including TACLeBench, DIS, SD-VBS, and synthetic microbenchmarks. The second involved conducting a large-scale overhead-aware schedulability study, parameterized by the collected benchmark data, to elucidate schedulability tradeoffs. The third involved experiments involving case-study task systems. In the schedulability study, the use of SMT proved capable of increasing platform capacity by an average factor of 1.32. In the case-study experiments, deadline misses of highly critical tasks were never observed.

Different global and semi-partitioned schedulers have been proposed that are soft-real-time (SRT) optimal for sporadic task systems, meaning they can guarantee bounded deadline tardiness. However, under known analyses, tardiness bounds increase with respect to the number of processors, which reduces the applicability of these schedulers in systems with a large number of processors. In this paper, a semi-clustered scheduler, SC-EDF, is presented that has a constant tardiness bound. SC-EDF partitions tasks into clusters, each of which may include one fractional processor. Each cluster is scheduled by G-EDF, and the fractional processors are realized using Pfair scheduling techniques.

Simultaneous multithreading (SMT) has the ability to dramatically improve real-time scheduling, but existing methods are cumbersome, frequently need specialized hardware, or are limited to producing table-based schedules. Here, an easily portable method for quickly applying SMT to priority-driven hard real-time systems is given. Using a combination of integer linear programming and heuristic bin-packing, a partitioned earliest-deadline-first (EDF) scheduler that takes advantage of SMT is produced. The integer linear programming and partitioning are done offline, but generally require only a few seconds, even given over a hundred tasks. A large-scale schedulability study is conducted, showing that compared to partitioned scheduling without SMT, the schedulable utilization for the considered hardware platform is nearly doubled in the best cases.