Robot autonomy is driving an ever-increasing demand for computational power, including on-board multi-core CPUs and accelerators such as GPUs, to enable fast perception, planning, control, and more. Careful scheduling of these computational tasks on the CPU cores and GPUs is important to prevent locking up the finite computational capacity in ways that hinder other critical workloads; delays in computing time-critical tasks like obstacle detection and control can have huge negative consequences for autonomous robots, potentially resulting in damage, substantial financial loss, or even loss of life. In this paper, we leverage recent advances from real-time systems research. We apply TimeWall, a component-based real-time framework, to the computational components of an autonomous drone and experimentally show that the timeliness and safe operation properties of a drone are preserved even in the presence of increasing interfering computational processes.

Fourier transforms are vital for a broad range of signal-processing applications. Accelerating FFTs with GPUs offers an orders-of-magnitude improvement vs. CPU-only FFT computation. However, two problems arise when executing FFT tasks with other GPU work. First, concurrent GPU use introduces unpredictability in the form of lengthy response times. Second, it is unclear how to best parameterize and schedule FFT tasks to meet the throughput and timeliness constraints of real-time signal processing. This work investigates how FFT and other GPU-using tasks can concurrently access a GPU while maintaining bounded response-time guarantees without sacrificing throughput. In our experiments, the techniques proposed by this work result in an up to 17% improvement in worst-case FFT response times.

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.

GPUs are increasingly needed to run a variety of tasks in embedded systems, from object recognition to conver-sational chat. Some of these tasks are safety-critical, real-time tasks, where completing each by its deadline is essential for system safety. To meet the practical constraints of real-world systems, these tasks much also be run efficiently. Unfortunately, current techniques to schedule GPU-using tasks onto a single GPU while respecting deadlines impart high overheads, leading to inefficiency and substantial capacity loss during formal analysis. We address this problem by moving GPU scheduling from the CPU to the GPU. Our approach limits overheads, increasing the proportion of CPU tasks which can meet their deadlines by as much as 12.1% while increasing available GPU capacity.

In prior work, a number of asymptotically optimal suspension-based real-time locking protocols have been presented for job-level fixed priority (JLFP) schedulers, where job priorities do not change. However, the optimality proofs for these locking protocols break down under non-JLFP scheduling, where job priorities can vary. In fact, the problem of designing an asymptotically optimal real-time locking protocol for general non-JLFP scheduling has remained open. This paper closes this problem by presenting the non-JLFP locking protocol (NJLP), the first asymptotically optimal suspension-based real-time locking protocol for non-JLFP schedulers.

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.

As GPU-dependent artificial intelligence and ma-chine learning workloads increasingly come to embedded, safety-critical systems-such as self-driving cars-real-time predictabil-ity for GPU-using tasks becomes essential. This paper identifies flaws in three different real-time GPU management approaches that are largely the result of incomplete information about NVIDIA GPU internals. Details concerning this missing information are elucidated via experiments. Based on this information, key rules of GPU scheduling are identified and shown necessary for safe GPU management.

The increasing complexity and parallelization of hardware and applications in embedded systems have brought unavoidable uncertainty in determining the worst-case execution times (WCETs) of real-time tasks. While budget enforcement can address this uncertainty by limiting an overrunning task from affecting the rest of the system, less explored is how to determine the rate and pattern of failures resulting from budget overruns. For analysis using probabilistic techniques, one must first consider potential dependence relations across different tasks or jobs of the same task. As a result, prior work on probabilistic WCET (pWCET) distributions seeking to enable independence assumptions has suffered from excessive pessimism and intricate derivation processes. In contrast, industry designs have opted for relatively simple heuristics such as “fudge factors,” budgets set by scaling mean or observed worst-case execution times by a constant factor. However, such heuristics do not have a strong analytical foundation. This paper addresses this gap in theory and practice, presenting analysis of a budgeted real-time system’s failure rate not reliant on extensive knowledge of a task’s execution behavior or independence assumptions, only requiring approximations of the mean execution time and standard deviation. This analysis bounds the rate of deadline failures, particularly those which would violate weakly-hard robustness specifications, to efficiently and optimally allocate budget and to evaluate industry heuristics.

It is common practice today to design complex safety-critical systems by repurposing hardware and software components originally designed for other contexts and using such components in a "black-box" fashion. However, if a black box’s inner workings are not fully understood, then this can be unsafe. This paper reports on an investigation pertaining to a black box that is important for autonomous systems, namely NVIDIA’s CUDA GPU framework. This investigation was motivated by certain timing glitches in CUDA kernels reported in the literature. After extensive tracing and testing efforts, the culprit causing these glitches was surprisingly found to be not CUDA-related at all, but rather delays due to system management interrupts (SMIs), a known source of timing unpredictability on x86 machines that is rarely if ever mentioned in work on real-time GPU usage. The effects of these SMIs are invisible to the operating system and can cause all cores on an x86 machine to become unavailable for over 20ms! This paper describes the methods used to uncover this timing-glitch source. It also discusses some lessons learned when trying to validate the timing behavior of black-box components.

Embedded and autonomous systems are increasingly integrating AI/ML features, often enabled by a hardware accelerator such as a GPU. As these workloads become increasingly demanding, but size, weight, power, and cost constraints remain unyielding, ways to increase GPU capacity are an urgent need. In this work, we provide a means by which to spatially partition the computing units of NVIDIA GPUs transparently, allowing of tidled capacity to be reclaimed via safe and efficient GPU sharing. Our approach works on any NVIDIA GPU since 2013, and can be applied via our easy-to-use, user-space library titled libsmctrl. We back the design of our system with deep investigations into the hardware scheduling pipeline of NVIDIA GPUs. We provide guidelines for the use of our system, and demonstrate it via an object detection case study using YOLOv2.

The fixed preemption point (FPP) model has been studied as an alternative to fully preemptive and non-preemptive models, as restricting preemptions to specific, predictable locations within a task's execution can simplify overhead analysis without disallowing preemptions entirely. Prior work has produced response-time analyses for global Earliest Deadline First (G-EDF) scheduling under the FPP model. However, scheduling decisions based solely on task deadlines may be too coarse-grained and may not lead to the lowest response times. In this paper, we propose global FPP EDF-like (G-FPP-EL) scheduling, which assigns a priority point in time for each non-preemptive region of a task. We adapt compliant-vector analysis (CVA) to our model and present general response-time bounds for G-FPP-EL schedulers. We then demonstrate that it is possible to design G-FPP-EL schedulers acheiving response-time bounds optimal under CVA and argue that such schedulers should replace global FPP EDF.

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.

Parallel workloads are commonly modeled as directed acyclic graphs (DAGs). While DAG scheduling is an important tool, it is plagued by capacity loss; it is not uncommon to see half of a platform go unused. Here this loss is attacked from a new direction: reducing per-DAG utilization prior to assigning computing cores to a DAG. Specifically, simultaneous multithreading (SMT) is used to schedule individual nodes of a DAG task in parallel on the same physical computing core. An optimization program is given that applies SMT to a DAG in a way that minimizes total utilization without compromising correctness. Results for both individual DAGs and systems of DAGs are evaluated using both a large-scale study of synthetic DAGs and a case study. Optimal use of the program can reduce DAG utilization and required core counts by over 40% in the best cases and by 25% in nearly half of cases. Runtime requirements for the optimization program are considered, and a tunable parameter is provided to make tradeoffs between runtime and optimality, allowing even DAGs with 500 nodes to benefit.

Software in autonomous systems, owing to performance requirements, is deployed on heterogeneous hardware comprising task specific accelerators, graphical processing units, and multicore processors. But performing timing analysis for safety critical control software tasks with such heterogeneous hardware is becoming increasingly challenging. Consequently, a number of recent papers have addressed the problem of stability analysis of feedback control loops in the presence of timing uncertainties (cf., deadline misses). In this paper, we address a different class of safety properties, viz., whether the system trajectory deviates too much from the nominal trajectory, with the latter computed for the ideal timing behavior. Verifying such quantitative safety properties involves performing a reachability analysis that is computationally intractable, or is too conservative. To alleviate these problems we propose to provide statistical guarantees over behavior of control systems with timing uncertainties. More specifically, we present a Bayesian hypothesis testing method based on Jeffreys’s Bayes factor test that estimates deviations from a nominal or ideal behavior. We show that our analysis can provide, with high confidence, tighter estimates of the deviation from nominal behavior than using known reachability based methods. We also illustrate the scalability of our techniques by obtaining bounds in cases where reachability analysis fails to converge, thereby establishing the former’s practicality.

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.

Safety-critical embedded systems are experiencing increasing computational and memory demands as edge-computing and autonomous systems gain adoption. Main memory (DRAM) is often scarce, and existing mechanisms to support DRAM oversubscription, such as demand paging or compile-time transformations, either imply serious CPU capacity loss, or put unacceptable constraints on program structure. This work proposes an alternative: paging GPU rather than CPU memory buffers directly to permanent storage to enable efficient and predictable memory oversubscription. This paper focuses on why GPU paging is useful and how it can be efficiently implemented. Specifically, a GPU paging implementation is proposed as an extension to NVIDIA's embedded Linux GPU drivers. In experiments reported herein, this implementation was seen to be three times faster end-to-end than demand paging, with 81% lower overheads. It also achieved speeds above the fastest prexisting Linux userspace I/O APIs with low DRAM and bus interference to CPU tasks—at most a 17% slowdown.

Graphics Processing Units (GPUs) are widely used in safety-critical real-time systems such as autonomous vehicles due to their high performance on artificial intelligence (AI) work-loads. As the computing power of recent GPUs keeps growing, it becomes increasingly possible to allow multiple independent programs to access the GPU concurrently. This complicates timing analysis, as contention for shared GPU resources renders execution times less predictable and worst-case execution times (WCETs) difficult to estimate. This paper provides a method for producing enemy programs that intentionally contend for GPU resources in order to enable more confident measurement-based WCET estimations. This paper provides an experiment-driven method to design effective enemy programs for several different interference channels—specific shared resources within the GPU through which concurrent computations may impact others' execution times. The method is flexible and can be applied to different GPU sharing mechanisms. The enemies are evaluated against a large number of real GPU applications, and the results indicate that these enemies cause higher slowdowns for GPU tasks than other baseline resource-stressing methods.

Vision processing for autonomous systems today involves implementing machine learning algorithms and vision processing libraries on embedded platforms consisting of CPUs, GPUs and FPGAs. Because many of these use closed-source proprietary components, it is very difficult to perform any timing analysis on them. Even measuring or tracing their timing behavior is challenging, although it is the first step towards reasoning about the impact of different algorithmic and implementation choices on the end-to-end timing of the vision processing pipeline. In this paper we discuss some recent progress in developing tracing, measurement and analysis infrastructure for determining the timing behavior of vision processing pipelines implemented on state-of-the-art FPGA and GPU platforms.

Feedback control loops are ubiquitous in any autonomous system. The design flow for any controller starts by determining a control strategy, while abstracting away all implementation details. However, when designing controllers for autonomous systems, there is significant computation associated with the perception modules. For example, this involves vision processing using deep neural networks on multicore CPU+accelerator platforms. Such computation can be organized in many different ways, with each choice resulting in very different sensor-to-actuator delays and tradeoffs between cost, delay, and accuracy. Further, each of these choices requires the control strategy to be designed accordingly. It is not possible for a control designer to enumerate and account for all of these choices manually, or abstract them away as “implementation details” as done in traditional controller design. In this paper we outline this problem and discuss how automated controller-synthesis techniques could help in addressing it.

This paper is concerned with the following question: Given a set of control tasks that are not schedulable, i.e., their required timing properties cannot be satisfied, what should be changed? While the real-time systems literature proposes many different schedulability analysis techniques, it surprisingly provides almost no guidelines on what should be changed to make a task set schedulable, when it is not. We show that when the tasks in question are control tasks, this timing debugging question in the context of cyber-physical systems (CPS) may be answered by exploiting the dynamics of the physical systems that these control tasks are expected to influence. Towards this, we study a very simple setup, viz., when a set of periodic tasks with implicit deadlines is not schedulable, by how much should the periods be changed in order to make the task set schedulable? Among the many ways in which the periods can be modified, our proposed strategy is to change the periods in a manner such that while the task set becomes schedulable, the poles of the closed-loop system experience the minimal shift. Since the poles influence the closed loop dynamics of the system, we thereby ensure that we obtain a system with the desired timing properties whose dynamics is very similar to the dynamics of the original (non-schedulable) system. We formulate this CPS timing debugging strategy as an optimization problem and illustrate it with a concrete example.

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.

This paper is directed at reader/writer locking for read-dominant real-time workloads. It is shown that state-of-the-art real-time reader/writer locking protocols are subject to performance limitations when reads dominate, and that existing schedulability analysis fails to leverage the sparsity of writes in this case. A new reader/writer locking-protocol implementation and new inflation-free schedulability analysis are proposed to address these problems. Overhead evaluations of the new implementation show a decrease in overheads of up to 70% over previous implementations, leading to throughput for read operations increasing by up to 450%. Schedulability experiments are presented that show that the analysis results in schedulability improvements of up to 156.8% compared to the existing state-of-the-art approach.

Computer-vision applications typically rely on graphics processing units (GPUs) to accelerate computations. However, prior work has shown that care must be taken when using GPUs in real-time systems subject to strict timing constraints; without such care, GPU use can easily lead to unexpected delays not only on the GPU device but also on the host CPU. In this paper, a software library is presented that can detect the improper use of GPUs for safety-critical computer-vision applications. This library was used to analyze several GPU-using sample applications available as part of OpenCV, a popular computer-vision library, revealing the presence of issues in all ten applications considered. Additionally, a case study is presented, detailing the response-time improvements to one of the applications when such issues are corrected.

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.

Across a range of safety-critical domains, an evolution is underway to endow embedded systems with "thinking" capabilities by using artificial-intelligence (AI) techniques. This evolution is being fueled by the availability of high-performance embedded hardware, typically multicore machines augmented with accelerators. Unfortunately, existing software certification processes rely on time partitioning to isolate system components, and this sense of isolation can be broken by accelerator usage. To address this issue, this paper presents TimeWall, a time-partitioning framework for multicore+accelerator platforms. When applied alongside existing methods for alleviating spatial interference, TimeWall can help enable component-wise certification on multicore+accelerator platforms. The challenges in realizing a TimeWall implementation are discussed in detail in this paper. Additionally, the temporal isolation TimeWall affords is examined experimentally, including via a case study of a computer-vision perception application, on a real platform.

Software transactional memory (STM) is a synchronization paradigm originally proposed for throughput-oriented computing to facilitate producing performant concurrent code that is free of synchronization bugs. With STM, programmers merely annotate code sections requiring synchronization; the underlying STM framework automatically resolves how synchronization is done. Today, the programming issues that motivated STM are becoming a concern in embedded computing, where ever more sophisticated systems are being produced that require highly parallel implementations. These implementations are often produced by engineers and control experts who may not be well versed in concurrency-related issues. In this context, a real-time STM framework would be useful in ensuring that the synchronization aspects of a system pass real-time certification. However, all prior STM approaches fundamentally rely on retries to resolve conflicts, and such retries can yield high worst-case synchronization costs compared to lock-based approaches. This paper presents a new STM class called Retry-Free Real-Time STM (R2STM), which is designed for worst-case real-time performance. The benefit of a retry-free approach for use in a real-time system is demonstrated by a schedulability study, in which it improved overall schedulability across all considered task systems by an average of 95.3% over a retry-based approach. This paper also presents TORTIS, the first R2STM implementation for real-time systems. Throughput-oriented benchmarks are presented to highlight the tradeoffs between throughput and schedulability for TORTIS.

Though recent work has established the soft real-time (SRT)-optimality of Earliest-Deadline-First (EDF) variants on multiprocessor models with limited heterogeneity (e.g., uniform speeds or affinity masks), such models are insufficient to describe modern multiprocessors, which have grown increasingly heterogeneous. This fact highlights the need to extend theoretical results to more asymmetric models, such as the unrelated multiprocessor model. This paper presents an EDF variant tailored for this model and proves that it is at least nearly SRT-optimal. Simulation results for random task systems are also presented that suggest that the proposed EDF variant may actually be SRT-optimal.

Artificial-intelligence algorithms are enabling ever more sophisticated autonomous features in safety-critical application domains. These algorithms can be quite complex—consisting of many tasks interconnected in processing graphs—and often must execute on complex heterogeneous hardware—typically multicore machines augmented with one or more hardware accelerators. To further complicate matters, these processing graphs often must be supported in contexts where a large system is broken into smaller components. With this confluence of factors, existing response-time analysis for processing graphs is not applicable. In this paper, such analysis is extended to address these complexities in systems where components are isolated via time partitioning. Additionally, graph restructuring methods are presented that enable response-time bounds to be reduced.

The applicability of Simultaneous Multithreading (SMT) to real-time systems has been hampered by the difficulty of obtaining reliable execution costs in an SMT-enabled system. This problem is addressed by introducing a scheduling framework, called CERT-MT, that combines scheduling-aware timing analysis with a cyclic-executive scheduler in a way that minimizes SMT-related timing variations. The proposed scheduling-aware timing analysis is based on maximum observed execution times and accounts for the uncertainty inherent in measurement-based timing analysis. The timing analysis is found to work for tasks with and without SMT, though some adjustments are required in the former case. A large-scale schedulability study is presented that shows CERT-MT can schedule systems with total utilizations approaching 1.4 times the core count, without sacrificing safety.

Graphics processing units (GPUs) manufactured by NVIDIA continue to dominate many fields of research, including real-time GPU-management. NVIDIA’s status as a key enabling technology for deep learning and image processing makes this unsurprising, especially when combined with the company’s push into embedded, safety-critical domains like autonomous driving. NVIDIA’s primary competitor, AMD, has received comparatively little attention, due in part to few embedded offerings and a lack of support from popular deep-learning toolkits. Recently, however, AMD’s ROCm (Radeon Open Compute) software platform was made available to address at least the second of these two issues, but is ROCm worth the attention of safety-critical software developers? In order to answer this question, this paper explores the features and pitfalls of AMD GPUs, focusing on contrasting details with NVIDIA’s GPU hardware and software. We argue that an open software stack such as ROCm may be able to provide much-needed flexibility and reproducibility in the context of real-time GPU research, where new algorithmic or analysis techniques should typically remain agnostic to the underlying GPU architecture. In support of this claim, we summarize how closed-source platforms have obstructed prior research using NVIDIA GPUs, and then demonstrate that AMD may be a viable alternative by modifying components of the ROCm software stack to implement spatial partitioning. Finally, we present a case study using the PyTorch deep-learning framework that demonstrates the impact such modifications can have on complex real-world software.

Autonomous vehicles often employ computer-vision (CV) algorithms that track the movements of pedestrians and other vehicles to maintain safe distances from them. These algorithms are usually expressed as real-time processing graphs that have cycles due to back edges that provide history information. If immediate back history is required, then such a cycle must execute sequentially. Due to this requirement, any graph that contains a cycle with utilization exceeding 1.0 is categorically unschedulable, i.e., bounded graph response times cannot be guaranteed. Unfortunately, such cycles can occur in practice, particularly if conservative execution-time assumptions are made, as befits a safety-critical system. This dilemma can be obviated by allowing older back history, which enables parallelism in cycle execution at the expense of possibly affecting the accuracy of tracking. However, the efficacy of this solution hinges on the resulting history-vs.-accuracy trade-off that it exposes. In this paper, this trade-off is explored in depth through an experimental study conducted using the open-source CARLA autonomous-driving simulator. Somewhat surprisingly, easing away from always requiring immediate back history proved to have only a marginal impact on accuracy in this study.

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.

A gap exists between the theory of EDF scheduling on identical multiprocessors with arbitrary processor affinities (APA) and practical EDF scheduling as embodied by the SCHED_DEADLINE (SD) scheduler in Linux. This is because the EDF variant proposed in theory for APA, called Strong APA EDF, introduces affinity-related complexities that are not applicable under global EDF, the original target of SD. SD instead treats affinities as a secondary concern. It is shown herein that this treatment comes at the price of causing SD to be fundamentally broken with regard to soft real-time (SRT)-optimality with APA. This result resolves a longstanding open question regarding this matter. It also suggests that Strong APA EDF, which has been proven to be SRT-optimal, is necessary for practical EDF scheduling with APA. However, non-preemptive sections are typically required in practice, and prior work on Strong APA EDF is limited to fully preemptive systems. In this paper, this prior work is extended for the first time to deal with non-preemptivity, which introduces non-trivial nuances with APA. As a byproduct of considering non-preemptivity, it is shown that the SRT-optimality of EDF in this context carries over to a significantly expanded class of schedulers.

A central challenge in designing embedded control systems or cyber-physical systems (CPS) is that of translating high-level models of control algorithms into efficient implementations, while ensuring that model-level semantics are preserved. While a large body of techniques for designing provably correct control strategies exist in the control theory literature, when it comes to transforming mathematical descriptions of these strategies to an efficient implementation, the available means are surprisingly ad hoc in nature. Among other reasons, this is because of (i) implementation platform details not sufficiently being accounted for in controller models, (ii) side effects introduced in the code generation process, (iii) various compiler optimizations whose impact on the dynamics of the plant being controlled not being properly understood, (iv) the presence of analog components on the implementation platform whose behavior is difficult to model, (v) computation and communication delays that exist in an implementation but were not accounted for in the model, and (vi) also the effects of image/video processing whose accuracy and timing behavior are difficult to model. As we move towards designing autonomous systems, these issues become biting problems on the path to certification, and striking a balance between performance and certification. In this position paper, we discuss some of these challenges - that we formulate as the need for modeling the interactions between various implementation layers in a CPS - and potential research directions to address them.

Existing models used in real-time scheduling are inadequate to take advantage of simultaneous multithreading (SMT), which has been shown to improve performance in many areas of computing, but has seen little application to real-time systems. The SMART task model, which allows for combining SMT and real time by accounting for the variable task execution costs caused by SMT, is introduced, along with methods and conditions for scheduling SMT tasks under global earliest-deadline-first scheduling. The benefits of using SMT are demonstrated through a large-scale schedulability study in which we show that task systems with utilizations 30% larger than what would be schedulable without SMT can be correctly scheduled.

Prior work has shown that the global earliest-deadline-first (GEDF) scheduler is soft real-time (SRT)-optimal for sporadic task systems in a variety of contexts, meaning that bounded deadline tardiness can be guaranteed under it for any task system that does not cause platform overutilization. However, one particularly compelling context has remained elusive: multiprocessor platforms in which tasks have affinity masks that determine the processors where they may execute. Actual GEDF implementations, such as the SCHED_DEADLINE class in Linux, have dealt with this unresolved question by foregoing SRT guarantees once affinity masks are set. This unresolved question, as it pertains to SCHED_DEADLINE, was included by Peter Zijlstra in a list of important open problems affecting Linux in his keynote talk at ECRTS 2017. In this paper, this question is resolved along with another open problem that at first blush seems unrelated but actually is. Specifically, both problems are closed by establishing two results. First, a proof strategy used previously to establish GEDF tardiness bounds that are exponential in size on heterogeneous uniform multiprocessors is generalized to show that polynomial bounds exist on a wider class of platforms. Second, both uniform multiprocessors and identical multiprocessors with affinities are shown to be within this class. These results yield the first polynomial GEDF tardiness bounds for the uniform case and the first such bounds of any kind for the identical-with-affinities case.

Vision-based perception systems are crucial for profitable autonomous-driving vehicle products. High accuracy in such perception systems is being enabled by rapidly evolving convolution neural networks (CNNs). To achieve a better understanding of its surrounding environment, a vehicle must be provided with full coverage via multiple cameras. However, when processing multiple video streams, existing CNN frameworks often fail to provide enough inference performance, particularly on embedded hardware constrained by size, weight, and power limits. This paper presents the results of an industrial case study that was conducted to re-think the design of CNN software to better utilize available hardware resources. In this study, techniques such as parallelism, pipelining, and the merging of per-camera images into a single composite image were considered in the context of a Drive PX2 embedded hardware platform. The study identifies a combination of techniques that can be applied to increase throughput (number of simultaneous camera streams) without significantly increasing per-frame latency (camera to CNN output) or reducing per-stream accuracy.

Many computer-vision (CV) applications used in autonomous vehicles rely on historical results, which introduce cycles in processing graphs. However, existing response-time analysis breaks down in the presence of cycles, either by failing completely or by drastically sacrificing parallelism or CV accuracy. To address this situation, this paper presents a new graph-based task model, based on the recently ratified OpenVX standard, that includes historical requirements and their induced cycles as first-class concepts. Using this model, response-time bounds for graphs that may contain cycles are derived. These bounds expose a tradeoff between responsiveness and CV accuracy that hinges on the extent of allowed parallelism. This tradeoff is illustrated via a CV case study involving pedestrian tracking. In this case study, the methods proposed in this paper enabled significant improvements in both analytical and observed response times, with acceptable CV accuracy, compared to prior methods.

During the past decade, parallelism-related issues have been at the forefront of real-time systems research due to the advent of multicore technologies. In the coming years, such issues will loom ever larger due to increasing core counts. Having more cores means a greater potential exists for platform capacity loss when the available parallelism cannot be fully exploited. In this paper, such capacity loss is considered in the context of real-time locking protocols. In this context, lock nesting becomes a key concern as it can result in transitive blocking chains that force tasks to execute sequentially unnecessarily. Such chains can be quite long on a larger machine. Contention-sensitive real-time locking protocols have been proposed as a means of "breaking" transitive blocking chains, but such protocols tend to have high overhead due to more complicated lock/unlock logic. To ease such overhead, the usage of lock servers is considered herein. In particular, four specific lock-server paradigms are proposed and many nuances concerning their deployment are explored. Experiments are presented that show that, by executing cache hot, lock servers can enable reductions in lock/unlock overhead of up to 86%. Such reductions make contention-sensitive protocols a viable approach in practice.

NVIDIA's CUDA API has enabled GPUs to be used as computing accelerators across a wide range of applications. This has resulted in performance gains in many application domains, but the underlying GPU hardware and software are subject to many non-obvious pitfalls. This is particularly problematic for safety-critical systems, where worst-case behaviors must be taken into account. While such behaviors were not a key concern for earlier CUDA users, the usage of GPUs in autonomous vehicles has taken CUDA programs out of the sole domain of computer-vision and machine-learning experts and into safety-critical processing pipelines. Certification is necessary in this new domain, which is problematic because GPU software may have been developed without any regard for worst-case behaviors. Pitfalls when using CUDA in real-time autonomous systems can result from the lack of specifics in official documentation, and developers of GPU software not being aware of the implications of their design choices with regards to real-time requirements. This paper focuses on the particular challenges facing the real-time community when utilizing CUDA-enabled GPUs for autonomous applications, and best practices for applying real-time safety-critical principles.

We propose a method for designing software transactional memory that relies on the use of locking protocols to ensure that transactions will never be forced to retry. We discuss our approaches to implementing this method and tunable parameters that may be able to improve schedulability on an application-specific basis.

The existing sporadic task model is inadequate for real-time systems to take advantage of Simultaneous Multithreading (SMT), which has been shown to improve performance in many areas of computing, but has seen little application to real-time systems. A new family of task models, collectively referred to as SMART, is introduced. SMART models allow for combining SMT and real time by accounting for the variable task execution costs caused by SMT.

Modern operating systems allow task migrations to be restricted by specifying per-task processor affinity masks. Such a mask specifies the set of processor cores upon which a task can be scheduled. In this paper, a semi-partitioned scheduler, AM-Red (affinity mask reduction), is presented for scheduling implicit-deadline sporadic tasks with arbitrary affinity masks on an identical multiprocessor. AM-Red is obtained by applying an affinity-mask-reduction method that produces affinities in accordance with those specified, without compromising feasibility, but with only a linear number of migrating tasks. It functions by employing a tunable frame of size |F|. For any choice of |F|, AM-Red is soft-real-time optimal, with tardiness bounded by |F|, but the frequency of task migrations is proportional to |F|. If |F| divides all task periods, then AM-Red is also hard-real-time-optimal (tardiness is zero). AM-Red is the first optimal scheduler proposed for arbitrary affinity masks without future knowledge of all job releases. Experiments are presented that show that AM-Red is implementable with low overhead and yields reasonable tardiness and task-migration frequency.

OpenVX is a recently ratified standard that was expressly proposed to facilitate the design of computer-vision (CV) applications used in real-time embedded systems. Despite its real-time focus, OpenVX presents several challenges when validating real-time constraints. Many of these challenges are rooted in the fact that OpenVX only implicitly defines any notion of a schedulable entity. Under OpenVX, CV applications are specified in the form of processing graphs that are inherently considered to execute monolithically end-to-end. This monolithic execution hinders parallelism and can lead to significant processing-capacity loss. Prior work partially addressed this problem by treating graph nodes as schedulable entities, but under OpenVX, these nodes represent rather coarse-grained CV functions, so the available parallelism that can be obtained in this way is quite limited. In this paper, a much more fine-grained approach for scheduling OpenVX graphs is proposed. This approach was designed to enable additional parallelism and to eliminate schedulability-related processing-capacity loss that arises when programs execute on both CPUs and graphics processing units (GPUs). Response-time analysis for this new approach is presented and its efficacy is evaluated via a case study involving an actual CV application.

Heterogeneous computing platforms with multiple types of computing resources have been widely used in many industrial systems to process dataflow tasks with pre-defined affinity of tasks to subgroups of resources. For many dataflow workloads with soft real-time requirements, guaranteeing fast and bounded response times is often the objective. This paper presents a new set of analysis techniques showing that a classical real-time scheduler, namely earliest-deadline first (EDF), is able to support dataflow tasks scheduled on such heterogeneous platforms with provably bounded response times while incurring no resource capacity loss, thus proving EDF to be an optimal solution for this scheduling problem. Experiments using synthetic workloads with widely varied parameters also demonstrate that the magnitude of the response time bounds yielded under the proposed analysis is reasonably small under all scenarios. Compared to the state-of-the-art soft real-time analysis techniques, our test yields a 68% reduction on response time bounds on average. This work demonstrates the potential of applying EDF into practical industrial systems containing dataflow-based workloads that desire guaranteed bounded response times.

The desire to support real-time applications on multicore platforms has led to intense recent interest in techniques for reducing memory-related hardware interference. These techniques typically rely on mechanisms that ensure per-task isolation properties with respect to cache and memory accesses. In most prior work on such techniques, any sharing of memory pages by different tasks is defined away, as sharing breaks isolation. In reality, however, sharing is common. In this paper, one source of sharing is considered, namely, the usage of shared libraries. Such sharing can be obviated by statically linking libraries, but this solution can degrade schedulability by exhausting memory capacity. An alternative approach is proposed herein that allows library pages to be shared while preserving isolation properties. This approach is presented in the context of the MC2 framework and a schedulability-based evaluation of it is presented. Such an evaluation must necessarily consider memory-capacity limits. As a secondary contribution, this paper considers such limits for the first time in the context of MC2.

Autonomous vehicles are an exemplar for forward-looking safety-critical real-time systems where significant computing capacity must be provided within strict size, weight, and power (SWaP) limits. A promising way forward in meeting these needs is to leverage multicore platforms augmented with graphics processing units (GPUs) as accelerators. Such an approach is being strongly advocated by NVIDIA, whose Jetson TX1 board is currently a leading multicore+GPU solution marketed for autonomous systems. Unfortunately, no study has ever been published that expressly evaluates the effectiveness of the TX1, or any other comparable platform, in hosting safety-critical real-time workloads. In this paper, such a study is presented. Specifically, the TX1 is evaluated via benchmarking efforts, blackbox evaluations of GPU behavior, and case-study evaluations involving computer-vision workloads inspired by autonomousdriving use cases. Autonomous vehicles are an exemplar for forward-looking safety-critical real-time systems where significant computing capacity must be provided within strict size, weight, and power (SWaP) limits. A promising way forward in meeting these needs is to leverage multicore platforms augmented with graphics processing units (GPUs) as accelerators. Such an approach is being strongly advocated by NVIDIA, whose Jetson TX1 board is currently a leading multicore+GPU solution marketed for autonomous systems. Unfortunately, no study has ever been published that expressly evaluates the effectiveness of the TX1, or any other comparable platform, in hosting safety-critical real-time workloads. In this paper, such a study is presented. Specifically, the TX1 is evaluated via benchmarking efforts, blackbox evaluations of GPU behavior, and case-study evaluations involving computer-vision workloads inspired by autonomous-driving use cases.

The push towards fielding autonomous-driving capabilities in vehicles is happening at breakneck speed. Semi-autonomous features are becoming increasingly common, and fully autonomous vehicles are optimistically forecast to be widely available in just a few years. Today, graphics processing units (GPUs) are seen as a key technology in this push towards greater autonomy. However, realizing full autonomy in mass-production vehicles will necessitate the use of stringent certification processes. Currently available GPUs pose challenges in this regard, as they tend to be closed-source “black boxes” that have features that are not publicly disclosed. For certification to be tenable, such features must be documented. This paper reports on such a documentation effort. This effort was directed at the NVIDIA TX2, which is one of the most prominent GPU-enabled platforms marketed today for autonomous systems. In this paper, important aspects of the TX2's GPU scheduler are revealed as discerned through experimental testing and validation.

It has long been known that the global earliest-deadlinefirst (GEDF) scheduler is soft real-time (SRT) optimal for sporadic task systems executing on identical multiprocessor platforms, regardless of whether task execution is preemptive or non-preemptive. This notion of optimality requires deadline tardiness to be provably bounded for any feasible task system. In recent years, there has been interest in extending these SRT optimality results to apply to uniform heterogeneous platforms, in which processors may have different speeds. However, it was recently shown that nonpreemptive GEDF is not SRT optimal on such platforms. The remaining case, preemptive GEDF, has turned out to be quite difficult to tackle and has remained open for a number of years. In this paper, this case is resolved by showing that preemptive GEDF is indeed SRT optimal on uniform platforms, provided a certain job migration policy is used.

A real-time multiprocessor synchronization problem is studied herein that has not be extensively studied before, namely, the management of replicated resources where tasks may require multiple replicas to execute. In prior work on replicated resources, k-exclusion locks have been used, but this restricts tasks to lock only one replica at a time. To motivate the need for unrestricted replica sharing, two use cases are discussed that reveal an interesting tradeoff: in one of the use cases, blocking is the dominant lock-related factor impacting schedulability, while in the other, lock/unlock overheads are. Motivated by these use cases, three replica-allocation protocols are presented. In the first two, the lock/unlock logic is very simple, yielding low overheads, but blocking is not optimal. In the third, blocking is optimal (ignoring constant factors), but additional lock/unlock overhead is incurred to properly order lock requests. Experiments are presented that examine the overhead/blocking tradeoff motivated by these protocols in some detail.

The multicore revolution is having limited impact in safety-critical application domains. A key reason is the "one-out-of-m" problem: when validating real-time constraints on an m-core platform, excessive analysis pessimism can effectively negate the processing capacity of the additional m-1 cores so that only "one core's worth" of capacity is available. Two approaches have been investigated previously to address this problem: mixed-criticality allocation techniques, which provision less-critical software components less pessimistically, and hardware-management techniques, which make the underlying platform itself more predictable. A better way forward may be to combine both approaches, but to show this, fundamentally new criticality-cognizant hardware-management tradeoffs must be explored. Such tradeoffs are investigated herein in the context of a large-scale, overhead-aware schedulability study. This study was guided by extensive trace data obtained by executing benchmark tasks on a new variant of the MC^2 framework that supports configurable criticality-based hardware management. This study shows that the two approaches mentioned above can be much more effective when applied together instead of alone.

Recent work involving a mixed-criticality framework called MC2 has shown that, by combining hardware-management techniques and criticality-aware task provisioning, capacity loss can be significantly reduced when supporting real-time workloads on multicore platforms. However, as in most other prior research on multicore hardware management, tasks were assumed in that work to not share data. Data sharing is problematic in the context of hardware management because it can violate the isolation properties hardware-management techniques seek to ensure. Clearly, for research on such techniques to have any practical impact, data sharing must be permitted. Towards this goal, this paper presents a new version of MC2 that permits tasks to share data within and across criticality levels through shared memory. Several techniques are presented for mitigating capacity loss due to data sharing. The effectiveness of these techniques is demonstrated by means of a large-scale, overhead-aware schedulability study driven by micro-benchmark data.

Many approaches have been proposed to enable disparate real-time software components to share a physical multiprocessor platform by giving each component the "illusion" of executing on a dedicated virtual platform. Such an illusion is supported by specifying a supply interface that indicates how computation time is made available to a component over time. A number of approaches for defining such interfaces have been proposed: so many that sifting through them all can be confusing for the practitioner. In the case of soft real-time applications, one particular proposed interface-minimum-parallelism (MP) supply-has been shown to enable the co-scheduling of different components with no utilization loss. In the case of hard real-time applications, it follows from prior work that MP supply easily dominates other choices if the simplifying assumption is made that supply is allocated on different processors using a common, synchronized allocation period. The main contribution of this paper is to show that the dominance of MP supply is retained if this simplifying assumption is removed, provided the period of allocation is defined properly. This result suggests that MP supply should be the focus in future work on real-time multiprocessor virtualization.

A semi-partitioned scheduler called EDF-tu is presented that is the first such scheduler to be optimal on uniform heterogeneous multiprocessors. EDF-tu utilizes an adjustable allocation parameter called a frame to schedule tasks that migrate. The frame size F must divide all task periods to ensure hard real-time optimality, but for any choice of F, maximum deadline tardiness is at most F. Thus, the proper selection of F hinges on runtime overheads (which are higher when F is smaller) and the strength of the real-time guarantee desired. When determining which tasks must migrate, new issues specific to heterogeneous platforms arise that have not been explored before. It is shown via counterexamples that resolving such issues differently from EDF-tu can render feasible task systems unschedulable.

The multicourse revolution is having limited impact on safety-critical cyber-physical systems. The key reason is the "one out of m" problem: certifying the real-time correctness of a system running on m cores can necessitate pessimistic analysis that easily negates the processing capacity of the "additional" m -- 1 cores. In safety-critical domains such as avionics, this has led to the common practice of simply disabling all but one core. In this paper, the usage of mixed-criticality (MC) scheduling and analysis techniques is considered to alleviate such analysis pessimism. Under MC analysis, a single system with components of different criticality levels is viewed as a set of different per-criticality-level systems. More optimistic analysis assumptions are made when certifying lower criticality levels. Unfortunately, this can lead to transient overloads at these levels, compromising real-time guarantees. This paper presents the first multicourse MC framework that addresses this problem. This framework makes scheduling decisions in a virtual time domain that can be "stretched" until the effects of a transient overload have abated. Such effects dissipate more quickly if virtual time is "stretched" more aggressively, but this may reduce the quality of the work performed. This trade off is analyzed experimentally herein.

Under the definition of soft real-time (SRT) correctness that requires deadline tardiness to be bounded, both the pre-emptive and non-pre-emptive global EDF (GEDF) schedulers are known to be SRT-optimal on identical multiprocessors. This paper considers the potential extension of these results to uniform heterogeneous multiprocessors. In the pre-emptive case, it is shown that such an extension is possible for two-processor platforms but unlikely for platforms of more than two processors, unless fundamentally new proof techniques are developed. In the non-pre-emptive case, it is shown that no work-conserving scheduler, including GEDF, can be SRT-optimal on uniform multiprocessors, even if the number of processors is limited to two.

In mixed-critical applications, tension exists between sharing and isolation with respect to hardware resources: while strong isolation might be required for highly critical tasks, somewhat permissive sharing might be reasonable for less critical tasks to improve throughput or average-case performance. In this paper, this tension is examined as it pertains to shared last-level caches (LLCs) on multicore platforms. In particular, criticality-aware optimization techniques based on linear programming are presented for allocating LLC areas in the context of the previously proposed MC2 (mixed-criticality on multicore) framework. Experiments are also presented that show that these techniques can result in significant schedulability improvements.

In the automotive industry, there is currently great interest in supporting driver-assist and autonomouscontrol features that utilize vision-based sensing through cameras. The usage of graphics processing units (GPUs) can potentially enable such features to be supported in a cost-effective way, within an acceptable size, weight, and power envelope. OpenVX is an emerging standard for supporting computer vision workloads. OpenVX uses a graph-based software architecture designed to enable efficient computation on heterogeneous platforms, including those that use accelerators like GPUs. Unfortunately, in settings where real-time constraints exist, the usage of OpenVX poses certain challenges. For example, pipelining is difficult to support and processing graphs may have cycles. In this paper, graph transformation techniques are presented that enable these issues to be circumvented. Additionally, a case-study evaluation is presented involving an OpenVX implementation in which these techniques are applied. This OpenVX implementation runs atop a previously developed GPU-management framework called GPUSync. In this case study, the usage of GPUSync's GPU management techniques along with the proposed graph transformations enabled computer vision workloads specified using OpenVX to be supported in a predictable way.

A fine-grained locking protocol permits multiple locks to be held simultaneously by the same task. In the case of real-time multiprocessor systems, prior work on such protocols has considered only mutex constraints. This unacceptably limits concurrency in systems in which some resource accesses are read-only. To remedy this situation, a variant of a recently proposed fine-grained protocol called the real-time nested locking protocol (RNLP) is presented that enables concurrent reads. This variant is shown to have worst-case blocking no worse (and often better) than existing coarse-grained real-time reader/writer locking protocols, while allowing for additional parallelism. Experimental evaluations of the proposed protocol are presented that consider both schedulability (i.e., the ability to validate timing constraints) and implementation-related overheads. These evaluations demonstrate that the RNLP (both the mutex and the proposed reader/writer variant) provides improved schedulability over existing coarse-grained locking protocols, and is practically implementable.

On behalf of the IEEE Technical Committee on Real-Time Systems, it is our pleasure to welcome you to the 20th IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS 2014), held in Berlin, Germany, as part of the Cyber-Physical Systems Week!

Semi-partitioned real-time scheduling algorithms extend partitioned ones by allowing a (usually small) subset of tasks to migrate. The first such algorithm to be proposed was directed at soft real-time (SRT) sporadic task systems where bounded deadline tardiness is acceptable. That algorithm, called EDF-fm, has the desirable property that migrations are boundary-limited, i.e., they can only occur at job boundaries. However, it is not optimal because per-task utilization restrictions are required. In this paper, a new optimal semi-partitioned scheduling algorithm for SRT sporadic task systems is proposed that eliminates such restrictions. This algorithm, called EDF-os, preserves the boundary-limited property. In overhead-aware schedulability experiments presented herein, EDF-os proved to be better than all other tested alternatives in terms of schedulability in almost all considered scenarios. It also proved capable of ensuring very low tardiness bounds, which were near zero in most considered scenarios.

Dataflow software architectures are prevalent in prototypes of advanced automotive systems, for both driver-assisted and autonomous driving. Safety constraints of these systems necessitate real-time performance guarantees. Automotive prototypes often ensure such constraints through over-provisioning and dedicated hardware; however, a commercially viable system must utilize as few low-cost multicore processors as possible to meet size, weight, and power constraints. In short, these platforms must do more with less. To this end, we develop cache-aware and overhead-cognizant scheduling techniques that lessen guaranteed response times without unnecessarily constraining platform utilization. We implement these techniques in PGMRT, a portable middleware framework for managing real-time dataflow applications on multicore platforms. The efficacy of our techniques is demonstrated through overhead-aware schedulability experiments and runtime observations. Results for our test platform show that cache-aware clustered scheduling outperforms naïve partitioned and global approaches in terms of schedulability and end-to-end response times of dataflows.

Motivated by computational capacity and power efficiency, techniques for integrating graphics processing units (GPUs) into real-time systems have become an active area of research. While much of this work has focused on single-GPU systems, multiple GPUs may be used for further benefits. Similar to CPUs in multiprocessor systems, GPUs in multi-GPU systems may be managed using partitioned, clustered, or global methods, independent of CPU organization. This gives rise to many combinations of CPU/GPU organizational methods that, when combined with additional GPU management options, results in thousands of "reasonable" configuration choices. In this paper, we explore real-time schedulability of several categories of configurations for multiprocessor, multi-GPU systems that are possible under GPUSync, a recently proposed highly configurable real-time GPU management framework. Our analysis includes the careful consideration of GPU-related overheads. We show system configuration strongly affects real time schedulability. We also identify which configurations offer the best schedulability in order to guide the implementation of GPU-based real-time systems and future research.

The issue of stochastic response-time analysis is considered in the context of soft real-time multiprocessor schedulers. For such analysis to yield tractable, closed-form results, it is inevitably necessary to assume that execution times are probabilistically independent. However, stochastic dependencies among tasks are often common in actual systems. To enable closed-form analysis results to be applied to such systems, the concept of an independence threshold is introduced. Such a threshold is a "tunable" per-task parameter that can be adjusted to control the extent of dependency in task execution times as assumed in analysis, such thresholds can even be applied in settings where explicit dependencies exist among tasks through resource sharing. A method is presented for setting independence thresholds in which measured task execution times are subjected to known statistical independence tests. This method is applied in a case study involving MPEG decoding. In this case study, the usage of independence thresholds enabled up to a 3.5-fold reduction in provisioned task execution times compared to a worst-case provisioning without compromising analysis assumptions.

Under current analysis, soft real-time tardiness bounds applicable to global earliest-deadline-first scheduling and related policies depend on per-task worst-case execution times. By splitting job budgets to create sub jobs with shorter periods and worst-case execution times, such bounds can be reduced to near zero for implicit-deadline sporadic task systems. However, doing so could potentially cause more preemptions and create problems for synchronization protocols. This paper analyzes this tradeoff between theory and practice by presenting an overhead-aware schedulability study pertaining to job splitting. In this study, real overhead data from a scheduler implementation in LITMUSRTwas factored into schedulability analysis. This study shows that despite practical issues affecting job splitting, it can still yield substantial reductions in tardiness bounds for soft real-time systems.

In many real-time systems, tasks may experience suspension delays when accessing external devices. The problem of analyzing task systems with such suspensions on multiprocessors has been relatively unexplored. The commonly used suspension-oblivious approach of treating all suspensions as computation can be quite pessimistic. As an alternative, this paper presents the first suspension-aware hard real-time multiprocessor schedulability analysis for task systems with suspensions, under both global fixed-priority and global EDF scheduling. In experiments presented herein, the proposed schedulability tests proved to be superior to suspension-oblivious tests. Moreover, when applied to ordinary arbitrary-deadline sporadic task systems with no suspensions, the proposed analysis for fixed-priority scheduling improves upon prior analysis.

In safety-critical cyber-physical systems, the usage of multicore platforms has been hampered by problems due to interactions across cores through shared hardware. The inability to precisely characterize such interactions can lead to worst-case execution time pessimism that is so great, the extra processing capacity of additional cores is entirely negated. In this paper, several techniques are proposed and analyzed for dealing with such interactions in the context of shared caches. These techniques are applied in a mixed-criticality scheduling framework motivated by the needs of next-generation unmanned air vehicles.

As multicore computing hardware has become more ubiquitous, real-time scheduling theory aimed at multicore systems has become increasingly sophisticated and diverse. Real-time operating systems (RTOSs) are ill-suited for this kind of rapid change, and the slow-moving RTOS ecosystem is falling further and further behind advances in real-time scheduling theory. Thus, supporting new functionality in a layer of middleware software running in userspace (i.e., outside the RTOS kernel) has been proposed. In this paper, we describe the first userspace scheduler that supports preemptive, dynamic-priority, migrating real-time tasks on multicore hardware, and report empirical latency and overhead measurements. On an eight-core Intel Xeon platform, these measurements are in the range of ones to tens of microseconds under most tested configurations. We believe that this approach may prove superior to a kernel-based approach for supporting a subset of future real-world realtime applications.

This paper describes GPUSync, which is a framework for managing graphics processing units (GPUs) in multi-GPU multicore real-time systems. GPUSync was designed with flexibility, predictability, and parallelism in mind. Specifically, it can be applied under either static-or dynamic priority CPU scheduling, can allocate CPUs/GPUs on a partitioned, clustered, or global basis, provides flexible mechanisms for allocating GPUs to tasks, enables task state to be migrated among different GPUs, with the potential of breaking such state into smaller "chunks", provides migration cost predictors that determine when migrations can be effective, enables a single GPU's different engines to be accessed in parallel, properly supports GPU-related interrupt and worker threads according to the sporadic task model, even when GPU drivers are closed-source, and provides budget policing to the extent possible, given that GPU access is non-preemptive. No prior real-time GPU management framework provides a comparable range of features.

Architectures in which multicore chips are augmented with graphics processing units (GPUs) have great potential in many domains in which computationally intensive real-time workloads must be supported. However, unlike standard CPUs, GPUs are treated as I/O devices and require the use of interrupts to facilitate communication with CPUs. Given their disruptive nature, interrupts must be dealt with carefully in real-time systems. With GPU-driven interrupts, such disruptiveness is further compounded by the closed-source nature of GPU drivers. In this paper, such problems are considered and a solution is presented in the form of an extension to LITMUS^RT called klmirqd. The design of klmirqd targets systems with multiple CPUs and GPUs. In such settings, interrupt-related issues arise that have not been previously addressed.

Existing research in soft real-time scheduling has focused on determining tardiness bounds given a scheduling algorithm. In this paper, we study lateness bounds, which are related to tardiness bounds, and propose a scheduling algorithm to minimize lateness bounds, namely the global fair lateness (G-FL) algorithm. G-FL is a G-EDF-like scheduler, but has lower maximum lateness bounds than GEDF. Due to its G-EDF-like nature, it can be used within existing systems that implement arbitrary-deadline G-EDF, and with existing synchronization protocols. Therefore, we argue that G-FL should replace G-EDF for SRT applications.

This paper presents the first real-time multiprocessor locking protocol that supports fine-grained nested resource requests. This locking protocol relies on a novel technique for ordering the satisfaction of resource requests to ensure a bounded duration of priority inversions for nested requests. This technique can be applied on partitioned, clustered, and globally scheduled systems in which waiting is realized by either spinning or suspending. Furthermore, this technique can be used to construct fine-grained nested locking protocols that are efficient under spin-based, suspension-oblivious or suspension-aware analysis of priority inversions. Locking protocols built upon this technique perform no worse than coarse-grained locking mechanisms, while allowing for increased parallelism in the average case (and, depending upon the task set, better worst-case performance).

Google Earth is a virtual globe that allows users to explore satellite imagery, terrain, 3D buildings, and geo-spatial content. It is available on a wide variety of desktop and mobile platforms, including Windows, Mac OS X, Linux, iOS, and Android. To preserve the sense of fluid motion through a 3D environment, the application must render at 60Hz. In this paper, we discuss the scheduling constraints of this application as a soft real-time scheduling problem where missed deadlines disrupt this motion. We describe a new scheduling implementation that addresses these problems. The diversity of hardware and software platforms on which Google Earth runs makes offline execution time analysis infeasible, so we discuss ways to predict execution time using on line measurement. We provide experimental results comparing different methods for predicting execution time. This new implementation is slated for inclusion in a future release of Google Earth.

Mixed-criticality scheduling algorithms, which attempt to reclaim system capacity lost to worst-case execution time pessimism, seem to hold great promise for multi core real-time systems, where such loss is particularly severe. However, the unique nature of these algorithms gives rise to a number of major challenges for the would-be implementer. This paper describes the first implementation of a mixed-criticality scheduling framework on a multi core system. We experimentally evaluate design trade offs that arise when seeking to isolate tasks of different criticalities and to maintain overheads commensurate with a standard RTOS. We also evaluate a key property needed for such a system to be practical: that the system be robust to breaches of the optimistic execution-time assumptions used in mixed-criticality analysis.

The prevalence of multicore processors has resulted in the wider applicability of parallel programming models such as Open MP and MapReduce. A common goal of running parallel applications implemented under such models is to guarantee bounded response times while maximizing system utilization. Unfortunately, little previous work has been done that can provide such performance guarantees. In this paper, this problem is addressed by applying soft real-time scheduling analysis techniques. Analysis and conditions are presented for guaranteeing bounded response times for parallel applications under global EDF multiprocessor scheduling.

Real-time locking protocols employ progress mechanism(s) to ensure that resource-holding jobs are scheduled. These mechanisms are required to bound the duration of priority-inversion blocking (pi-blocking) for jobs sharing resources. Examples of such progress mechanisms include priority inheritance and priority donation. Unfortunately, some progress mechanisms can cause any job, including those that never request shared resources, to be blocked upon job release. This paper presents a variant of priority donation for globally-scheduled systems that only causes blocking for jobs waiting for shared resources. Additionally, this variant of priority donation is employed to construct a new suspension-based locking protocol called the replica-request donation global locking protocol (R2DGLP), which is asymptotically optimal for both mutex and k-exclusion (i.e., multi-unit) resources. This work is motivated by multicore systems where tasks may share I/O devices (e.g., GPUs) where critical sections can be long. In such applications, progress mechanisms that cause jobs that do not access I/O devices to be blocked to ensure progress can be detrimental from a schedulability perspective.

In many real-time and embedded systems, suspension delays may occur when tasks block to access shared resources or interact with external devices. Unfortunately, prior analysis methods for dealing with suspensions are quite pessimistic. In this paper, a novel technique is presented for analyzing soft real-time sporadic self-suspending task systems, for which bounded deadline tardiness is required, scheduled under global schedulers such as global EDF on multiprocessors (or EDF on uniprocessors). This technique is used to derive a new schedulability test that results in only O(m) suspension-related utilization loss, where m is the number of processors. The derived test theoretically dominates prior tests with respect to schedulability. Furthermore, experiments presented herein show that the improvement over prior tests is often quite significant.

Semi-partitioned schedulers are -- in theory -- a particularly promising category of multiprocessor real-time scheduling algorithms. Unfortunately, issues pertaining to their implementation have not been investigated in detail, so their practical viability remains unclear. In this paper, the practical merit of three EDF-based semi-partitioned algorithms is assessed via an experimental comparison based on real-time schedulability under consideration of real, measured overheads. The presented results indicate that semi-partitioning is indeed a sound and practical idea. However, several problematic design choices are identified as well. These shortcomings and other implementation concerns are discussed in detail.

This paper presents the first suspension-based real-time locking protocols for clustered schedulers. Such schedulers pose challenges from a locking perspective because they exhibit aspects of both partitioned and global scheduling, which seem to necessitate fundamentally different means for bounding priority inversions. A new mechanism to bound such inversions, termed priority donation, is presented and used to derive protocols for mutual exclusion, reader-writer exclusion, and k-exclusion. Each protocol has asymptotically optimal blocking bounds under certain analysis assumptions. The latter two protocols are also the first of their kind for the special cases of global and partitioned scheduling.

Graphics processing units (GPUs) are becoming increasingly important in today's platforms as their increased generality allows for them to be used as powerful coprocessors. In this paper, we explore possible applications for GPUs in real-time systems, discuss the limitations and constraints imposed by current GPU technology, and present a summary of our research addressing many such constraints.

The processing graph method (PGM) is a widely used framework for modeling applications with producer/consumer precedence constraints. PGM was originally developed by the U.S. Navy to model signal-processing applications where data communications exist among connected tasks. Prior work has shown how to schedule PGM-specified systems on uniprocessors and globally-scheduled multiprocessors. In this paper, this work is extended to enable such systems to be supported in a distributed collection of multicore machines. In such a context, pure global and partitioned scheduling approaches are problematic. Moreover, data communication costs must be considered. In this paper, a clustered scheduling algorithm is proposed for soft real-time PGM-specified distributed task systems for which bounded deadline tardiness is acceptable. This algorithm is effective in reducing data communication costs with little utilization loss. This is shown both analytically and via experiments conducted to compare it with an optimal integer linear programming solution.

We utilize a multiprocessor server-based approach to schedule a general class of soft real-time systems with stochastic execution demands, when bounded average-case tardiness is sufficient for schedulability. A key feature of the task model considered here is that the stochastic execution-time demands can have arbitrary amounts of dependence within pre-specified time intervals of bounded length. This is an important practical step forward from requiring complete independence of execution times between successive jobs of the same task. Our main result does not require the scheduler to know the execution time of each job in advance, and requires only average-case utilization to be bounded by the number of processors. This constraint is mild compared to constraints on worst-case utilization because in multiprocessor systems, worst-case execution times may be orders of magnitude higher than average-case execution times.

The evolution of multicore platforms has led to much recent work on multiprocessor scheduling techniques for soft real-time workloads. However, end users routinely run such workloads atop general-purpose operating systems with seemingly good results, albeit typically on over-provisioned systems. This raises the question: when, if ever, is the use of an analysis-based scheduler actually warranted? In this paper, this question is addressed via a video-decoding case study in which a scheme based on the global earliest-deadline-first (GEDF) algorithm was compared against Linux's CFS scheduler. In this study, the GEDF-based scheme proved to be superior under heavy workloads in terms of several timing metrics, including jitter and deadline tardiness. Prior to discussing these results, an explanation of how existing GEDF-related scheduling theory was applied to provision the studied system is given and various "mismatches" between theoretical assumptions and practice that were faced are discussed.

While most prior work on multiprocessor real-time scheduling focuses on independent tasks, dependencies due to non-preemptive sections, suspensions, and pipeline-based precedence constraints are common in practice. In this paper, such complexities are considered in the context of the global earliest-deadline-first scheduling algorithm. It is shown that any periodic task system with such dependencies can be transformed into one with only suspensions in a way that preserves maximum per-task response times. This result enables analysis directed at systems with suspensions to be applied if non-preemptive sections and/or pipelines are present as well.

Prior work has shown that the global earliest-deadline-first (GEDF) scheduling algorithm ensures bounded deadline tardiness on multiprocessors with no utilization loss; therefore, GEDF may be a good candidate scheduling algorithm for soft real-time workloads. However, such workloads are often implemented assuming an average-case provisioning, and in prior tardiness-bound derivations for GEDF, worst-case execution costs are assumed. As worst-case costs can be orders of magnitude higher than average-case costs, using a worst-case provisioning may result in significant wasted processing capacity. In this paper, prior tardiness-bound derivations for GEDF are generalized so that execution times are probabilistic, and a bound on expected (mean) tardiness is derived. It is shown that, as long as the total expected utilization is strictly less than the number of available processors, the expected tardiness of every task is bounded under GEDF. The result also implies that any quantile of the tardiness distribution is also bounded.

In work on globally-scheduled soft real-time multiprocessor systems, analysis has been presented for dealing with self-suspensions, but this analysis can be pessimistic. In this paper, we present an approach that is designed to improve the schedulability of such systems. In experimental results that are presented, the proposed approach significantly improved schedulability in most considered scenarios.

As multicore platforms become ever larger, overhead-related factors play a greater role in determining which real-time scheduling algorithms are preferable. In this paper, such factors are investigated through an empirical comparison of global, partitioned, and clustered EDF scheduling algorithms on a 24-core Intel system. On this platform, global EDF proved to be a non-viable choice for hard real time systems, while clusters of size six practically approximated global approaches. For soft real-time systems, clustered EDF scheduling algorithms proved to be particularly effective. This study suggests that future global scheduling research should focus on small-to-medium multicore platforms rather than large platforms.

When locking protocols are used in real-time systems, bounds on blocking times are required when ensuring timing constraints. While the term “blocking” is well-understood in the context of uniprocessor real-time systems, the same is not true in the multiprocessor case. In this paper, two definitions of blocking are presented that are applicable to suspension-based multiprocessor locking protocols. The need for two definitions arises because of differences in how suspensions are handled in existing schedulability analysis. For each definition, locking protocols are presented that have asymptotically optimal blocking behavior. In particular, protocols are presented for any job-level static-priority global or partitioned scheduling algorithm.

In work on globally-scheduled real-time multiprocessor systems, analysis is lacking for supporting real-time applications developed using general processing graph models. In this paper, it is shown that bounded deadline tardiness can be ensured for such applications on a multiprocessor with no utilization loss. This result is general: it is applicable to periodic, sporadic, and rate-based directed-acyclic-graph (DAG) models and allows sophisticated notions of precedence to be supported (particularly, notions allowed by the processing graph method). This paper is the first to show that bounded tardiness can be ensured for globally-scheduled DAG-based applications without utilization loss.

Reader preference, writer preference, and task-fair reader writer locks are shown to cause undue blocking in multiprocessor real-time systems. A new phase-fair reader-writer lock is proposed as an alternative that significantly reduces worst case blocking for readers and an efficient local-spin implementation is provided. Both task- and phase-fair locks are evaluated and contrasted to mutex locks in terms of hard and soft real-time schedulability under consideration of runtime overheads on a multicore computer.

Multicore architectures, which have multiple processing units on a single chip, have been adopted by most chip manufacturers. Most such chips contain on-chip caches that are shared by some or all of the cores on the chip. Prior work has presented methods for improving the performance of such caches when scheduling soft real-time workloads. Given these methods, two additional research issues arise: (1) how to automatically profile the cache behavior of real-time tasks within the scheduler; and (2) how to implement scheduling methods efficiently, so that scheduling overheads do not offset any cache-related performance gains. This paper addresses these two issues in an implementation of a cache-aware soft real-time scheduler within Linux, and shows that the use of this scheduler can result in performance improvements that directly result from a decrease in shared cache miss rates.

In work on multiprocessor real-time systems, processing pipelines have received little attention. In this paper, soft real-time periodic task systems are considered that include such pipelines. Conditions are presented for guaranteeing bounded deadline tardiness in such systems under global EDF or FIFO multiprocessor scheduling.

The importance of accounting for interrupts in multiprocessor real-time schedulability analysis is discussed. Three interrupt accounting methods, two of which are newly described here, are analyzed and compared.

Soft real-time sporadic multiprocessor task systems are considered that include processing pipelines. Conditions are presented for guaranteeing bounded deadline tardiness in such systems under global EDF or FIFO scheduling. "Early-releasing" is applied to make pipeline scheduling work-conserving. This lessens job response times in lightly-loaded systems.

An empirical study of implementation tradeoffs (choice of ready queue implementation, quantum-driven vs. event-driven scheduling, and interrupt handling strategy) affecting global real-time schedulers, and in particular global EDF, is presented. This study, conducted using UNC's Linux-based LITMUSRTon Sun's Niagara platform, suggests that implementation tradeoffs can impact schedulability as profoundly as scheduling-theoretic tradeoffs. For most of the considered workloads, implementation scalability proved to not be a key limitation of global EDF on the considered platform. Further, a combination of a parallel heap, event-driven scheduling, and dedicated interrupt handling performed best for most workloads.

Many embedded platforms consist of a heterogeneous collection of processing elements, memory modules, and communication subsystems. These components often implement different scheduling/arbitration policies, have different interfaces, and are supplied by different vendors. Hence, compositional techniques for modeling and analyzing such platforms are of interest. In prior work, the real-time calculus framework has proven to be very effective in this regard. However, real-time calculus has heretofore been limited to systems with uniprocessor processing elements, which is a serious impediment given the advent of multicore technologies. In this paper, a two-step approach is proposed that allows the power of real-time calculus to be applied in globally-scheduled multiprocessor systems: first, assuming that job response-time bounds are given, determine whether these bounds are met; second, using these bounds, determine the resulting residual processor supply and streams of job completion events using formalisms from real-time calculus. For this methodology to be applied in settings where response-time bounds are not specified, such bounds must be determined. Though this is an issue that warrants further investigation, a method is discussed for calculating such bounds that is applicable to a large family of fixed job-priority schedulers. The utility of the proposed analysis framework is demonstrated using a case study.

In work on multiprocessor real-time systems, task scheduling with self-suspensions is a relatively unexplored topic. In this paper, soft real-time sporadic task systems are considered that include self-suspending tasks. Conditions are presented for guaranteeing bounded deadline tardiness in such systems under global EDF or FIFO multiprocessor scheduling. These conditions enable many soft real-time task systems with self-suspending tasks to be scheduled with little or no utilization loss.

In this paper, we develop an adaptive scheduling framework for changing the processor shares of tasks - a process called reweighting - on real-time multiprocessor platforms. Our particular focus is adaptive frameworks that are deployed in environments in which tasks may frequently require significant share changes. Prior work on enabling real-time adaptivity on multiprocessors has focused exclusively on scheduling algorithms that can enact needed adaptations. The algorithm proposed in this paper uses both feedback and optimization techniques to determine at runtime which adaptations are needed.

Multicore architectures, which have multiple processing units on a single chip, have been adopted by most chip manufacturers. Most such chips contain on-chip caches that are shared by some or all of the cores on the chip. To effectively use the available processing resources on such platforms,scheduling methods must be aware of these caches. In this paper, we explore various heuristics that attempt to improve cache performance when scheduling real-time workloads. Such heuristics are applicable when multiple multithreaded applications exist with large working sets. In addition, we present a case study that shows how our best-performing heuristics can improve the end-user performance of video encoding applications.

A multiprocessor scheduling scheme is presented for supporting hierarchical containers that encapsulate sporadic soft and hard real-time tasks. In this scheme, each container is allocated a specified bandwidth, which it uses to schedule its children (some of which may also be containers). This scheme is novel in that, with only soft realtime tasks, no utilization loss is incurred when provisioning containers, even in arbitrarily deep hierarchies. Presented experiments show that the proposed scheme performs well compared to conventional real-time scheduling techniques that do not provide container isolation.

In the domain of multiprocessor real-time systems, there has been a wealth of recent work on scheduling, but relatively little work on the equally-important topic of synchronization. When synchronizing accesses to shared resources, four basic options exist: lock-free execution, wait-free execution, spin- based locking, and suspension-based locking. To our knowledge, no empirical multiprocessor-based evaluation of these basic techniques that focuses on real-time systems has ever been conducted before. In this paper, we present such an evaluation and report on our efforts to incorporate synchronization support in the testbed used in this effort.

We extend the FMLP to partitioned static-priority scheduling and derive corresponding worst-case blocking bounds. Further, we present the first implementation of the PCP, SRP, D-PCP, M-PCP, and FMLP synchronization protocols in a unified framework in a general-purpose OS and discuss design issues that were beyond the scope of prior algorithmic-oriented work on real-time synchronization.

Multicore platforms are predicted to become significantly larger in the coming years. Given that real-time workloads will inevitably be deployed on such platforms, the scalability of the scheduling algorithms used to support such workloads warrants investigation. In this paper, this issue is consideredand an empirical evaluation of several global and partitioned scheduling algorithms is presented. This evaluation was conducted using a Sun Niagara multicore platformwith 32 logical CPUs (eight cores, four hardware threads per core). In this study, each tested algorithm proved to be a viable choice for some subset of the workload categories considered.

The issue of deadline tardiness is considered under earliest-deadline-first (GEDF) multiprocessor scheduling. New schedulability tests are presented for determining whether a set of sporadic tasks with arbitrary relative deadlines can be scheduled under either preemptive or non-preemptive GEDF so that pre-defined tardiness bounds are met. These tests are of pseudo-polynomial time complexity, and can be used in hard real-time, soft real-time, and mixed contexts.

We present a multiprocessor scheduling framework for integrating hard and soft real-time tasks and best-effort jobs. This framework allows for full system utilization, and ensures that hard real-time deadlines are met and that deadline tardiness is bounded for soft real-time tasks. Dynamic slack reclamation is employed to reduce tardiness and to improve the response time of best-effort jobs. The approach is validated using an implementation within the Linux kernel.

We propose a hybrid approach for scheduling real-time tasks on large-scale multicore platforms with hierarchical shared caches. In this approach, a multicore platform is partitioned into clusters. Tasks are statically assigned to these clusters, and scheduled within each cluster using the preemptive global EDF scheduling algorithm. We show that this hybrid of partitioning and global scheduling performs better on large-scale platforms than either approach alone. We also determine the appropriate cluster size to achieve the best performance possible, given the characteristics of the task set to be supported.

FIFO scheduling is often considered to be inappropriate for scheduling workloads that are subject to timing constraints. However, FIFO is implemented in many general-purpose OSs, and is more widely supported than other priority-based scheduling methods. In this paper, we show that, when the global FIFO scheduling algorithm is used to schedule sporadic real-time tasks on a multiprocessor, deadline tardiness is bounded. This result shows that global FIFO may in fact be useful for scheduling soft real-time workloads.

This paper discusses an approach for supporting soft real-time periodic tasks in Linux on performance asymmetric multicore platforms (AMPs). Such architectures consist of a large number of processing units on one or several chips, where each processing unit is capable of executing the same instruction set at a different performance level. We discuss deficiencies of Linux in supporting periodic real-time tasks, particularly when cores are asymmetric, and how such deficiencies were overcome. We also investigate how to provide good performance for non-real-time tasks in the presence of a real-time workload. We show that this can be done by using deferrable servers to explicitly reserve a share of each core for non-real-time tasks. This allows non-real-time tasks to have priority over real-time tasks when doing so will not cause timing requirements to be violated, thus improving non-real-time response times. Experiments show that even small deferrable servers can have a dramatic impact on non-real-time task performance

Real-time scheduling algorithms for multiprocessor systems have been the subject of considerable recent interest. For such an algorithm to be truly useful in practice, support for semaphore-based locking must be provided. However, for many global scheduling algorithms, no such mechanisms have been proposed. Furthermore, in the partitioned case, most prior semaphore schemes are either inefficient or restrict critical sections considerably. In this paper, a new flexible multiprocessor locking scheme is presented that can be applied under both partitioning and global scheduling. This scheme allows unrestricted critical-section nesting, but has been designed to deal with the common case of short non-nested accesses efficiently.

Multicore platforms, which include several processing cores on a single chip, are being widely touted as a solution to heat and energy problems that are impediments to single-core chip designs. To accommodate both parallelizable and inherently-sequential applications on the same platform, heterogeneous multicore designs with faster and slower cores have been proposed. In this paper, we consider the problem of scheduling soft real-time workloads on such a platform.

We consider the issue of deadline tardiness under global multiprocessor scheduling algorithms. We present a general tardiness-bound derivation that is applicable to a wide variety of such algorithms (including some whose tardiness behavior has not been analyzed before). Our derivation is very general: job priorities may change rather arbitrarily at runtime, arbitrary non-preemptive regions are allowed, and capacity restrictions may exist on certain processors. Our results show that, with the exception of static-priority algorithms, most global algorithms considered previously have bounded tardiness. In addition, our results provide a simple means for checking whether tardiness is bounded under newly-developed algorithms.

We consider schemes for enacting task share changes - a process called reweighting - on real-time multiprocessor platforms. Our particular focus is reweighting schemes that are deployed in environments in which tasks may frequently request significant share changes. Prior work has shown that fair scheduling algorithms are capable of reweighting tasks with minimal allocation error and that partitioning-based scheduling algorithms can reweight tasks with better average-case performance, but greater error. However, preemption and migration overheads can be high in fair schemes. In this paper, we consider the question of whether global scheduling techniques can improve the accuracy of reweighting relative to partitioning-based schemes and provide improved average-case performance relative to fair-scheduled systems. Our conclusion is that, for soft real-time systems, global scheduling techniques provide a good mix of accuracy and average-case performance.

We consider coordinating accesses to shared data structures in multiprocessor real-time systems scheduled under preemptive global EDF. To our knowledge, prior work on global EDF has focused only on systems of independent tasks. We take an initial step here towards a generic resource-sharing framework by considering simple shared objects, such as queues, stacks, and linked lists. In many applications, the predominate use of synchronization constructs is for sharing such simple objects. We analyze two synchronization methods for such objects, one based on queue-based spin locks and a second based on lock-free algorithms

A straight line needle trajectory is typically used in medical needle insertion for percutaneous intervention. Flexible needle steering may be able to avoid obstacles, and reach regions that are currently inaccessible using straight line trajectory. The success of flexible needle insertion in clinical application, for example, biopsy to obtain a tissue sample from human liver organ is dependent on how accurate the motion path can be planned and simulated. We developed a motion planning algorithm for flexible needle insertion with an integrative model of human liver organ, and finite element models of needle and needle-tissue interaction. The aim of image based integrative modeling is to have a unified organ model of patient comprising finite element and implicit surface models of blood vessels, normal and pathological tissues. The trajectory path can be determined in an interactive manner. The generated trajectory for flexible needles avoids obstacles (vessels) to reach target (tumor) inaccessible to rigid needles. The algorithm can also be used to simulate needle bending due to dynamic contact with tumor

The earliest-deadline-first (EDF) scheduling of a sporadic real-time task system on a multiprocessor may require that the total utilization of the task system, U/sub sum/, not exceed (m + 1)/2 on m processors if every deadline needs to be met. In recent work, we considered the alleviation of this under-utilization for task systems that can tolerate deadline misses by bounded amounts (i.e., bounded tardiness). We showed that if U/sub sum/ /spl les/ m and tasks are not pinned to processors, then the tardiness of each task is bounded under both preemptive and non-preemptive EDF. However, the tardiness bounds derived are applicable to every task in the task system, i.e., any task may incur maximum tardiness. In this paper, we consider supporting tasks whose tolerances to tardiness are less than that known to be possible under EDF. We propose a new scheduling policy, called EDF-hl, which is a variant of EDF, and show that under EDF-hl, any tardiness, including zero tardiness, can be ensured for a limited number of privileged tasks, and that bounded tardiness can be guaranteed to the remaining tasks if their utilizations are restricted. EDF-hl reduces to EDF in the absence of privileged tasks. The tardiness bound that we derive is a function of U/sub sum/, in addition to individual task parameters. Hence, tardiness for all tasks can be lowered by lowering U/sub sum/. A simulation-based evaluation of the tardiness bounds that are possible is provided.

We propose a scheduling method for real-time systems implemented on multicore platforms that encourages individual threads of multithreaded real-time tasks to be scheduled together. When such threads are cooperative and share a common working set, this method enables more effective use of on-chip shared caches

We present a real-time, Linux-based testbed called LITMUS, which we have developed for empirically evaluating multiprocessor real-time scheduling algorithms. We also present the results from such an evaluation, in which partitioned earliest-deadline-first (EDF) scheduling, preemptive and nonpreemptive global EDF scheduling, and two variants of the global PD2 Pfair algorithm were considered. The tested algorithms were compared based on both raw performance and schedulability (with real overheads considered) assuming either hard- or soft-real-time constraints. To our knowledge, this paper is the first attempt by anyone to compare partitioned and global real-time scheduling approaches using empirical data

We present several locking synchronization protocols for Pfair-scheduled multiprocessor systems. We focus on two classes of protocols. The first class is only applicable in systems in which all critical sections are short relative to the length of the scheduling quantum. In this case, efficient synchronization can be achieved by ensuring that all locks have been released before tasks are preempted. This is accomplished by exploiting the quantum-based nature of Pfair scheduling, which provides a priori knowledge of all possible preemption points. The second and more general protocol class is applicable to any system. For this class, we consider the use of a client-server model. We also discuss the viability of inheritance-based protocols in Pfair-scheduled systems.

In hard real-time systems, a significant disparity in schedulability exists between EDF-based scheduling algorithms and Pfair scheduling, which is the only known way of optimally scheduling recurrent real-time tasks on multiprocessors. This is unfortunate because EDF-based algorithms entail lower scheduling and task-migration overheads. In work on hard real-time systems, it has been shown that the disparity in schedulability can be lessened by placing caps on per-task utilizations. In this paper, we show that it can also be lessened by easing the requirement that all deadlines be met. Our main contribution is a new EDF-based scheme that ensures bounded deadline tardiness. In this scheme, per-task utilizations must be capped, but overall utilization need not be restricted. The required cap is quite liberal. Hence, our scheme should enable a wide range of soft real-time applications to be scheduled with no constraints on total utilization. We also propose techniques and heuristics that can be used to reduce tardiness.

We consider the problem of task reweighting in fair-scheduled multiprocessor systems wherein each task's processor share is specified as a weight. Task reweighting can be used as a means for consuming (or making available) spare processing capacity. In this paper, we propose a multiprocessor reweighting scheme that can change a task's processor share with "minimal" error per share change.

Most prior theoretical research on partitioning algorithms for real-time multiprocessor platforms has focused on ensuring that the cumulative computing requirements of the tasks assigned to each processor does not exceed the processor's processing power. However, many multiprocessor platforms have only limited amounts of local per-processor memory; if the memory limitation of a processor is not respected, thrashing between "main" memory and the processor's local memory may occur during run-time and may result in performance degradation. We formalize the problem of task partitioning in a manner that is cognizant of both memory and processing capacity constraints as the memory constrained multiprocessor partitioning problem, prove that this problem is intractable, and present efficient algorithms for solving it under certain well-defined conditions.

This paper considers the scheduling of soft real-time sporadic task systems under global EDF on an identical multiprocessor. Prior research on global EDF has focused mostly on hard real-time systems, where, to ensure that all deadlines are met, approximately 50% of the available processing capacity will have to be sacrificed in the worst case. This may be overkill for soft real-time systems that can tolerate bounded tardiness. In this paper, we derive tardiness bounds under preemptive and non-preemptive global EDF on multiprocessors when the total utilization of a task system is not restricted and may equal the number of processors. Our tardiness bounds depend on per-task utilizations and execution costs - the lower these values, the lower the tardiness bounds. As a final remark, we note that global EDF may be superior to partitioned EDF for multiprocessor-based soft real-time systems in that the latter does not offer any scope to improve system utilization even if bounded tardiness can be tolerated

Multiprocessor implementations of real-time systems tend to be more energy-efficient than uniprocessor implementations. However several factors, including the nonexistence of optimal multiprocessor scheduling algorithms, combine to prevent all the computing capacity of a multiprocessor platform from being guaranteed available for executing the real-time workload. In this paper, this tradeoff - that while increasing the number of processors results in lower energy consumption for a given computing capacity, the fraction of the capacity of a multiprocessor platform that is guaranteed available for executing real-time work decreases as the number of processors increases - is explored in detail. Algorithms are presented for synthesizing multiprocessor implementations of hard-real-time systems comprised of independent periodic tasks in such a manner that the energy consumed by the synthesized system is minimized.

Summary form only given. The earliest-pseudo-deadline-first (EPDF) Pfair algorithm is more efficient than other known Pfair scheduling algorithms, but is not optimal on more than two processors. Srinivasan and Anderson established a sufficient per-task utilization restriction for ensuring a tardiness of at most one quantum under EPDF. They also conjectured that a tardiness bound of one quantum applies to systems that are not restricted in any way. We present counterexamples that show that this conjecture is false. We also present sufficient utilization restrictions that are more liberal than theirs.

Prior work on Pfair scheduling has resulted in three optimal multiprocessor scheduling algorithms, and one algorithm, EPDF, that is less expensive but not optimal. EPDF is still of interest in soft real-time systems, however, due to its ability to guarantee bounded tardiness. In particular, it has been shown that a tardiness bound of t quanta is possible under EPDF if all task weights (i.e., shares or utilizations) are restricted to a value specified as a function of t. In an actual system, however, different tasks may be subject to different tardiness bounds. If such a system is scheduled under EPDF, then the tardiness of a task with a higher bound may cause the tardiness bound of a task with a lower bound to be violated; that is, temporal isolation among the various tardiness classes may not be guaranteed. In this paper, we propose an algortihm based on EPDF for scheduling task classes with different tardiness bounds on a multiprocessor. Our algorithm provides temporal isolation among classes, allows the available processing capacity to be fully utilized, and does not require that previously established per-task weight restrictions be made more stringent.

We consider the implementation of a Pfair scheduler on a symmetric multiprocessor (SMP). Simulations presented herein suggest that bus contention resulting from simultaneous scheduling decisions can substantially degrade performance. To correct this problem, we propose a staggered model for Pfair scheduling under which scheduling points are uniformly distributed over time.

We revisit the problem of supertasking in Pfair-scheduled multiprocessor systems by presenting a generalized "reweighting" algorithm. The generalized algorithm we present breaks new ground by permitting tasks to have noninteger execution costs, by incorporating blocking terms into the analysis, and by assuming a more flexible global-scheduling model. To demonstrate the efficacy of the supertasking approach, we present an experimental evaluation of our algorithm that suggests that reweighting may often result in almost no schedulability loss in practice.

In this paper, we consider fair scheduling of soft real-time applications on multiprocessors using the earliest pseudo deadline first (EPDF) Pfair algorithm. Our main contributions are twofold. First, we establish a condition for ensuring a tardiness of at most one quantum under EPDF. This condition is very liberal and should often hold in practice. Second, we present simulation results involving randomly-generated task sets, including those that do not satisfy our condition. In these experiments, deadline misses were rare, and no misses by more than one quantum ever occurred.

We present a generic fetch-and-/spl phi/-based local-spin mutual exclusion algorithm with O(1) time complexity under the RMR (remote-memory-reference) measure. This algorithm is "generic" in the sense that it can be implemented using any fetch-and-/spl phi/ primitive of rank 2N, where N is the number of processes. The rank of a fetch-and-/spl phi/ primitive expresses the extent to which processes may "order themselves" using that primitive. By using an arbitration tree, a /spl otimes/(log/sub r/ N) algorithm can be constructed using any primitive of rank r, where 2 /spl les/ r < N. For primitives that meet a certain additional condition, we present a O(log N/log log N) algorithm, which is time-optimal for certain primitives of constant rank.

In prior work on multiprocessor fairness, efficient techniques with provable properties for reallocating spare processing capacity have been elusive. In this paper, we address this shortcoming by proposing a new notion of multiprocessor fairness, called quick-release fair (QRfair) scheduling. Under QRfair scheduling, each task is specified by giving both a minimum and a maximum weight (i.e., processor share). The goal is to schedule each task (as the spare capacity changes) at a rate that is (i) at least that implied by its minimum weight and (ii) at most that implied by its maximum weight. We present a quick-release variant of the PD/sup 2/ Pfair scheduling algorithm called PD/sup Q/ and prove that the allocations of PD/sup Q/ always satisfy (i) and (ii). Also, we present results from simulation experiments that show the efficacy of PD/sup Q/.

We consider the problem of object sharing in Pfair-scheduled multiprocessor systems. We primarily focus on systems that use lock-free shared objects, although some lock-based alternatives are briefly considered as well. Our work demonstrates that the tight synchrony that exists in Pfair-scheduled systems can be exploited to reduce object-sharing overheads when lock-free objects are used.

We propose two server implementations for multiplexing aperiodic and recurrent real-time tasks in fair-scheduled multiprocessor systems. We also provide admission-control tests for scheduling hard aperiodic tasks. Further, we consider several complexities, most of which arise because of the parallelism available in multiprocessor systems, and present techniques to handle them. Finally, we present experimental results that demonstrate the effectiveness of our implementations.

We present an N-process local-spin mutual exclusion algorithm, based on nonatomic reads and writes, in which each process performs Θ(log N) remote memory references to enter and exit its critical section. No atomic read/write algorithm with better asymptotic worst-case time complexity is currently known. This suggests that atomic memory is not fundamentally required if one is interested in worst-case time complexity. The same cannot be said if one is interested in fast-path or adaptive algorithms. We show that such algorithms fundamentally require memory accesses to be atomic. In particular, we show that for any N-process nonatomic algorithm, there exists a single-process execution in which the lone competing process executes Ω(log N/log log N) remote operations to enter its critical section. Moreover, these operations must access Ω(√log N/log log N) distinct variables.

We consider two classes of locking synchronization protocols for pfair-scheduled multiprocessor systems: short critical-section protocols and long critical-section protocols. For the former class, we demonstrate that efficient synchronization can be achieved by ensuring that all locks have been released before tasks are preempted. For the latter class, we propose the use of statically-weighted resource servers. We also discuss several inheritance-based protocols as possible alternatives.

The PD2 Pfair/ERfair scheduling algorithm is the most efficient known algorithm for optimally scheduling periodic tasks on multiprocessors. In this paper, we prove that PD2 is also optimal for scheduling "rate-based" tasks whose processing steps may be highly jittered. The rate-based task model we consider generalizes the widely-studied sporadic task model.

In this paper, we prove that a simplified variant of the PD Pfair algorithm, called PD/sup 2/, is optimal for scheduling any mix of early-release and non-early-release asynchronous tasks on a multiprocessor. This result breaks new ground by incorporating both early-release and non-early-release tasks under a common framework. In addition, all prior work on optimal multiprocessor Pfair scheduling algorithms has been limited to synchronous periodic task systems.

Mutual exclusion is a topic that Leslie Lamport has returned to many times throughout his career. This article, which is being written in celebration of Lamport's sixtieth birthday, is an attempt to survey some of his many contributions to research on this topic.

We establish a lower bound of 23 N= log log N) remote memory references for N-process mutual exclusion algorithms based on reads, writes, or comparison primitives such as test-and-set and compareand -swap. Our bound improves an earlier lower bound of 34 log N= log log log N) established by Cypher. Our lower bound is of importance for two reasons. First, it almost matches the (log N) time complexity of the best known algorithms based on reads, writes, or comparison primitives. Second, our lower bound suggests that it is likely that, from an asymptotic standpoint, comparison primitives are no better than reads and writes when implementing local-spin mutual exclusion algorithms. Thus, comparison primitives may not be the best choice to provide in hardware if one is interested in scalable synchronization.

We reconsider the "supertask" approach, in which a set of Pfair tasks is scheduled as a single task. We define a "safe" weight threshold for a given supertask in a multiprocessor system with either hard or soft deadlines and either strict or relaxed rate constraints.

Presents a variant of Pfair scheduling (S. Baruah et al., 1995, 1996), which we call early-release fair (ERfair) scheduling. Like conventional Pfair scheduling, ERfair scheduling algorithms can be applied to optimally schedule periodic tasks on a multiprocessor system in polynomial time. However, ERfair scheduling differs from Pfair scheduling in that it is work-conserving. As a result, average job response times may be much lower under ERfair scheduling than under Pfair scheduling, particularly in lightly loaded systems. In addition, run-time costs are lower under ERfair scheduling.

We consider wait-free synchronization in multipro grammed uniprocessor and multiprocessor systems in which "hybrid" schedulers are employed that use both priority information and a scheduling quantum in making scheduling decisions.The main contribution of this paper is to show that, in any hybrid-scheduled system, any object with consensus number C 2 P in Herlihy's wait-free hierarchy is universal for any number of processes executing on P processors, provided the scheduling quantum is of a certain size.We also show that if a C-consensus object must be "hard-wired" to the processors that access it, then our characterization of the required quantum is asymptotically tight.If C = P or if C 2 2P, then this characterization is asymptotically tight regardless of whether objects must be "hard-wired".

Packet switching in connection-oriented networks that may have multiple parallel links between pairs of switches is considered. An efficient packet scheduling algorithm that guarantees a deterministic quality of service to connections with real time constraints is proposed; this algorithm is a generalization of some recent multiprocessor scheduling algorithms, and offers real time performance guarantees similar to those offered by earlier fair scheduling strategies, such as Weighted Fair Queueing and proportional share schemes.

We have been studying brachytherapy planning with the objective of minimizing the maximum deviation of the delivered dose from prescribed dose bounds for treatment volumes. A general framework for optimal treatment planning is presented and the minmax optimization is formulated as a linear program. Dose rate calculations are based on the dosimetry formulation of the American Association of Physicists in Medicine, Task Group 43. We apply the technique to optimal planning for intravascular brachytherapy of intimal hyperplasia using ultrasound data and 192Ir seeds. The planning includes determination of an optimal dwell-time sequence for a train of seeds that deliver radiation while stepping through the vessel lesion. The results illustrate the advantage of this strategy over the common approach of delivering radiation by positioning a single train of seeds along the whole lesion.

We present lock-free and wait-free universal constructions for implementing large shared objects. Most previous universal constructions require processes to copy the entire object state, which is impractical for large objects. Previous attempts to address this problem require programmers to explicitly fragment large objects into smaller, more manageable pieces, paying particular attention to how such pieces are copied. In contrast, our constructions are designed to largely shield programmers from this fragmentation. Furthermore, for many objects, our constructions result in lower copying overhead than previous ones. Fragmentation is achieved in our constructions through the use of load-linked, store-conditional, and validate operations on a "large" multiword shared variable. Before presenting our constructions, we show how these operations can be efficiently implemented from similar one-word primitives.

We consider the problem of implementing shared objects in uniprocessor and multiprocessor real-time systems in which tasks are executed using a scheduling quantum. In most quantum-based systems, the size of the quantum is quite large in comparison to the length of an object call. As a result, most object calls can be expected to execute without preemption. A good object-sharing scheme should optimize for this expected case, while achieving low overhead when preemptions do occur. In this paper, we present several new shared-object algorithms for uniprocessors and multiprocessors that were designed based upon this principle. We also present scheduling analysis results that can be used in conjunction with these algorithms.

While there is currently great interest in the problem of providing real time services in general purpose operating systems, the issue of real time scheduling of internal operating system activities has received relatively little attention. Without such real time scheduling, the system is susceptible to conditions such as receive livelock-a situation in which an operating system spends all its time processing arriving network packets, and application processes, even if scheduled with a real time scheduler, are starved. We investigate the problem of scheduling operating system activities such as network protocol processing in a proportional share manner. We describe a proportional share implementation of the FreeBSD operating system and demonstrate that it solves the receive livelock problem. Packets are processed within the operating system only at the cumulative rate at which the destination applications are prepared to receive them. If packets arrive at a faster rate then they are discarded after consuming minimal system resources. In this manner the performance of "well behaved" applications is unaffected by "misbehaving" applications. We demonstrate this effect by running a set of multimedia applications under a variety of network conditions on a set of increasingly sophisticated proportional share implementations of FreeBSD and comparing their performance. This work contributes to our knowledge of the engineering of proportional share real time systems.

Wait-free objects are often implemented through the use of a "helping scheme", whereby one process "helps" one or more other processes to complete an operation. This paper presents several new helping schemes that can be generally applied to efficiently implement a variety of different objects on priority-based uniprocessor and multiprocessor systems. Examples of such systems include lock-free multiprocessor kernels and real-time systems. Our helping schemes reduce overhead by exploiting the way in which processes are scheduled in priority-based systems. We illustrate the use of these schemes by presenting wait-free implementations of linked lists and a multi-word compare-and-swap primitive. 1 Introduction We consider the implementation of wait-free shared objects on multiprogrammed systems in which processes are scheduled for execution based on priority. We assume that processes are scheduled on a per-processor basis and do not migrate between processors during object accesses. Our ...

Several new wait-free object-sharing schemes for real-time uniprocessors and multiprocessors are presented. These schemes have characteristics in common with the priority inheritance and priority ceiling protocols, but are nonblocking and implemented at the user level. In total, six new object-sharing schemes are proposed: two for uniprocessors and four for multiprocessors. Breakdown utilization experiments are presented that show that the multiprocessor schemes entail less overhead than lock-based schemes.

This article considers the use of lock-free shared objects within hard real-time systems. As the name suggests,lock-freeshared objects are distinguished by the fact that they are accessed without locking. As such, they do not give rise to priority inversions, a key advantage over conventional, lock-based object-sharing approaches. Despite this advantage, it is not immediately apparent that lock-free shared objects can be employed if tasks must adhere to strict timing constraints. In particular, lock-free object implementations permit concurrent operations to interfere with each other, and repeated interferences can cause a given operation to take an arbitrarily long time to complete. The main contribution of this article is to show that such interferences can be bounded by judicious scheduling. This work pertains to periodic, hard real-time tasks that share lock-free objects on a uniprocessor. In the first part of the article, scheduling conditions are derived for such tasks, for both static and dynamic priority schemes. Based on these conditions, it is formally shown that lock-free shared objects often incur less overhead than object implementations based on wait-free algorithms or lock-based schemes. In the last part of the article, this conclusion is validated experimentally through work involving a real-time desktop videoconferencing system.

We present an integrated framework for developing real time systems in which lock-free algorithms are employed to implement shared objects. There are two key objectives of our work. The first is to enable functionality for object sharing in lock-free real time systems that is comparable to that in lock based systems. Our main contribution toward this objective is an efficient approach for implementing multiobject lock-free operations and transactions. A second key objective of our work is to improve upon previously proposed scheduling conditions for tasks that share lock-free objects. When developing such conditions, the key issue is to bound the cost of operation "interferences". We present a general approach for doing this, based on linear programming.

We present wait-free and lock-free universal constructions that allow operations to access multiple objects atomically. Such constructions provide functionality similar to nested critical sections in conventional, lockbased systems. In such a system, two critical sections might be nested, for example, to swap the contents of two shared bu ers. Using our constructions, such a transfer can be done in a wait-free or a lock-free manner. Our universal constructions are based upon multiword synchronization primitives. In the rst part of the paper, we present wait-free implementations of such primitives from one-word primitives. These implementations allow processes that access disjoint words to execute in parallel. Previous implementations of multi-word primitives either overly restrict parallelism, or provide only lock-free execution. We also present several implementations involving one-word universal primitives that allow our constructions to be applied with greater exibility. In particular, we present timeoptimal, wait-free implementations of Load-Linked and Store-Conditional from Read and Compare-And-Swap, and vice versa, and implementations that eliminate the need to deal with spurious Store-Conditional failures. 1

No abstract available.

This paper considers the use of lock-free shared objects within hard real-time systems. As the name suggests, lock-free shared objects are distinguished by the fact that they are not locked. As such, they do not give rise to priority inversions, a key advantage over conventional, lock-based object-sharing approaches. Despite this advantage, it is not immediately apparent that lock-free shared objects can be employed if tasks must adhere to strict timing constraints. In particular, lock-free object implementations permit concurrent operations to interfere with each other, and repeated interferences can cause a given operation to take an arbitrarily long time to complete. The main contribution of this paper is to show that such interferences can be bounded by judicious scheduling. This work pertains to periodic, hard real-time tasks that share lock-free objects on a uniprocessor. In the first part of the paper, scheduling conditions are derived for such tasks, for both static and dynamic priority schemes. Based on these conditions, it is formally shown that lock-free object-sharing approaches can be expected to incur much less overhead than approaches based on wait-free objects or lock-based schemes. In the last part of the paper, this conclusion is validated experimentally through work involving a real time desktop videoconferencing system.

We present a methodology for the implementation of atomic operations or perform badly.Our k-exclusion algorithms are also the first algorithms based on localspin techniques that tolerate process failures.

We establish trade-o s between time complexity and write- and access-contention for solutions to the mutual exclusion problem. The write-contention (accesscontention) of a concurrent program is the number of processes that may be simultaneously enabled to write (access) the same shared variable. Our notion of time complexity distinguishes between local and remote references to shared memory. We show that, for any N-process mutual exclusion algorithm with write-contention w, there exists an execution involving only one process in which that process executes (log w N) remote memory references for entry into its critical section. We further show that among these remote references, ( p log w N) distinct remote variables are accessed. For algorithms with access-contention c, we show that the latter bound can be improved to (log c N). The last two of these results imply that a trade-o between contention and time complexity exists even if coherent caching techniques are employed. Because the execution that establishes these bounds involves only one process, our results show that \\fast mutual exclusion " requires arbitrarily high writecontention. We show that these bounds hold when using any ofavariety of synchronization primitives, including read, write, test-and-set, load-and-store, compare-andswap, and fetch-and-add, and that they can be generalized to apply when using even stronger primitives. Our results can be extended to apply to a class of decision problems that includes the leader-election problem. The time bounds that we establish are the rst of their kind

We present a construction of a single-writer, multiple-reader atomic register from single-writer, single-reader atomic registers. The complexity of our construction is asymptotically optimal; O(M 2 + MN) shared single-writer, single-reader safe bits are required to construct a single-writer, M-reader, N-bit atomic register.

This paper concerns synchronization under read/write atomicity in shared memory multiprocessors.We present a new algorithm for N-process mutual exclusion that requires only read and write operations and that has 0(log2 IV) time complexity, where "time" is measured by counting remote memory references.The time complexity of this algorithm is better than that of all prior solutions to the mutual exclusion problem that are based upon atomic read and write instructions; in fact, the time complexity of most prior solutions is unbounded.Performance studies are presented that show that our mutual exclusion algorithm exhibits scalable performance under heavy contention.In the second part of the paper, we discuss two extensions of our mutual exclusion algorithm.In the first extension, we modify the algorithm so that in the absence of contention only 0(1) memory references are required.In the second extension, the technique of software combining is introduced for the purpose of increasing concurrency when using the algorithm to implement combinable read-modifywrite operations.

Abstract Most proof methods for reasoning about concurrent programs are based upon the interleaving semantics of concurrent computation: a concurrent program is executed in a stepwise fashion, with only one enabled action being executed at each step. Interleaving semantics, in effect, requires that a concurrent program be executed as a nondeterministic sequential program. This is clearly an abstraction of the way in which concurrent programs are actually executed. To ensure that this is a reasonable abstraction, interleaving semantics should only be used to reason about programs with “simple” actions; we call such programs “atomic”. In this paper, we formally characterise the class of atomic programs. We adopt the criterion that a program is atomic if it can be implemented in a wait-free, serialisable manner by a primitive program. A program is primitive if each of its actions has at most one occurrence of a shared bit, and each shared bit is read by at most one process and written by at most one process. It follows from our results that the traditionally accepted atomicity criterion, which allows each action to have at most one occurrence of a shared variable, can be relaxed, allowing programs to have more powerful actions. For example, according to our criterion, an action can read any finite number of shared variables, provided it writes no shared variable.

We introduce a shared data object, called a composite register, that generalizes the notion of an atomic register.A composite register is an array-like variable that is partitioned into a number of components.An operation of such a register either writes a value to one of the components or reads the values of all of the components.A composite register reduces to an ordinary atomic register when there is only one component.We give two composite register constructions, which together show that atomic registers can be used to implement composite registers.In the first construction, atomic registers are used to implement a composite register in which there is only one writer per component.In the second construction, a composite register with one writer per component is used to implement a composite register with multiple writers per component.These two construct,ions show that it, is possible for a process of a concurrent program to take an atomic snapshot of an entire shared memory without using mutual exclusion.

A new construction of a l-writer/m-reader/nbit atomic register using O(m2 + mn) lwriter/l-reader/I-bit atomic registers is presented.This construction is more efficient, i.e, uses less registers, than previous constructions. IntroductionThe currently accepted theory of concurrent computing is deeply rooted in the concept of