In recent years, multiple data copies become popular in heterogeneous computing architectures. They enable parallel data transfer among diverse processing units. Tasks executed on such heterogeneous architectures often exhibit heightened re-source competitions and intricate task dependencies, posing challenges in meeting strict timing constraints. Due to the dominant roles of data copies in the heterogeneous architecture, effective scheduling and tight response time analysis could contribute to the timing performance of the entire heterogeneous computing system. In this work, we introduce MATCH, which offers realtime scheduling and end-to-end response time analysis for the multiple parallel data copies that are popular in mainstream heterogeneous architectures. We first identify the aggravated resource competition and task dependency from multiple data copies and comprehensive task execution patterns. Then, we provide a real-time scheduling strategy and cross-granularity schedulability analysis to deal with resource competition and task dependency. Extensive evaluation demonstrates that efficient scheduling and analysis on multiple parallel data copies can significantly improve the schedulability by 55.5%-144.4%. Additionally, experiments conducted on various scales of heterogeneous systems demonstrate that MATCH can significantly reduce pessimism in response time analysis by up to 22.8%-57.5%. Importantly, the proposed approach is compatible with existing scheduling approaches that do not consider multiple parallel data copies and are readily applied to off-the-shelf heterogeneous computing systems.

Cyber-physical systems (CPS) must interact with varying environments at fine-grained time-scales, assuring control safety and stability while optimizing application-specific performance objectives. To address those requirements, co-design of real-time control and scheduling has received considerable attention over multiple decades, to allow rigorous assurance of system properties while enabling diverse forms of adaptation to changing operating conditions. In this paper, we present a new formalization of the periodicity requirements for control inputs to (1) guarantee reachability of safe (and avoidance of unsafe) portions of the system state space, (2) adaptively manage dynamic periodicity constraints that may change as the state space is traversed, and (3) express minimum periods to enable safe hand-offs between high-performance controllers and more conservative backup controllers. Our evaluations of this approach confirm that it is able to maintain system safety and stability while optimizing system performance.

The Robot Operating System 2 (ROS 2) is a widely used middleware that provides software libraries and tools for developing robotic systems. In these systems, tasks are scheduled by ROS 2 executors. Since the scheduling behavior of the default ROS 2 executor is inherently different from classical real-time scheduling theory, dedicated analyses or alternative executors requiring substantial changes to ROS 2 have been developed. In 2023, the events executor was introduced into ROS 2. It features an events queue and allows the possibility to make scheduling decisions immediately after a job is completed. In this paper, we show that with minor modifications of the events executor, a large body of research results from classical real-time scheduling theory becomes directly applicable to ROS 2. This enables analytical bounds on the worst-case response time and the end-to-end latency, outperforming bounds for the default ROS 2 executor in many scenarios. Our solution is easy to integrate into existing ROS 2 systems since it requires only minor modifications of the events executor, which is natively included in ROS 2. The evaluation results show that our ROS 2 events executor with minor modifications can have significant improvement in terms of dropped jobs, worst-case response time, end-to-end latency, and performance compared to the default ROS 2 executor.

Elastic scheduling is a framework to reduce task utilizations (often by increasing periods) in response to system overload. This paper extends elastic scheduling to uniprocessor scheduling of implicit-deadline task sets for which periods must remain harmonic. We argue that for tasks with periods constrained to continuous intervals, the problem of selecting harmonic periods from those intervals is unlikely to have a polynomial time solution. However, we outline an approach that is pseudo-polynomial in the range of acceptable periods. We then show that the problem of elastic scheduling is NP-hard with harmonic constraints. Nonetheless, if a total order is imposed on task periods (a natural restriction in many applications with execution pipelines that synchronize input data sources), the problem can be reduced offline to a lookup table, enabling polynomial-time online adaptation if available CPU bandwidth changes. We implement the proposed algorithm in two real-world applications: the Fast Integrated Mobility Spectrometer (FIMS) and ORB-SLAM3. We demonstrate that elastic scheduling allows FIMS to adjust its execution to avoid missing deadlines on a SWaP-constrained computational platform, and that it improves ORB-SLAM3's localization results by as much as lO.4x when available CPU bandwidth changes dynamically during runtime.

Buttazzo et al.’s elastic scheduling model allows task utilizations to be “compressed” to ensure schedulability atop limited resources. Each task is assigned a range of acceptable utilizations and an “elastic constant” representing the relative adaptability of its utilization. In this paper, we consider federated scheduling, under which each high-utilization parallel task is assigned dedicated processor cores. We propose a new model of elastic workload compression for parallel DAG tasks that assigns each subtask its own elastic constant and continuous range of acceptable workloads. We show that the problem can be solved offline as a mixed-integer quadratic program, or online using a pseudo-polynomial dynamic programming algorithm. We also consider joint core allocation and compression of low-utilization sequential tasks and present a mixed-integer linear program for optimal elastic compression of tasks under partitioned EDF scheduling. We show empirical improvements in schedulability over the prior work and present a case study for the Fast Integrated Mobility Spectrometer (FIMS).

It is witnessed that heterogeneous architectures, such as GPUs, TPUs, and FPGAs, have made complex algorithms practical in the last decade. Despite multiple efforts to study the scheduling of these parallel and complex tasks on heterogeneous architectures, the power and energy consumption of the platforms have yet to be well managed under real-time task deadlines. To establish high schedulability in heterogeneous architectures, many scheduling strategies and models, such as multi-segment selfsuspension (MSSS), have been proposed by pioneer researchers. However, directly applying this model to heterogeneous architectures with multiple CPUs and many processing elements (PEs) suffers aggravated power consumption due to the pessimism in the scheduling algorithm and the tolerance margin in the worst-case execution time (WCET) model. Therefore, this paper presents an energy-efficient real-time scheduling approach called EESchedule, which works on heterogeneous architectures with guaranteed schedulability and improved power efficiency. In EESchedule, we build a general task execution model for the general heterogeneous architectures integrating multiple CPUs and many PEs. Then, an energy-efficient real-time scheduling strategy is introduced. Next, the response time and corresponding schedulability analysis are presented for EESchedule. Finally, extensive experiments on heterogeneous NVIDIA Jetson TX2 embedded systems and GPU servers with the Intel i9-10900x CPU and RTX 3080 GPU demonstrate that the EESchedule could achieve the same schedulability with 16.8%-40.7% and 39.0%-48.2% reduced power and energy consumption in comparison with state-of-the-art scheduling algorithms.

Elastic scheduling provides a model for systems in which individual task utilizations can adapt to guarantee schedulability despite limited resources. Each task is characterized by a range of acceptable utilizations and an “elastic constant” representing its flexibility to reduce or “compress” its utilization from the desired maximum. Utilization compression is realized by either extending task periods or reducing workloads. This paper extends the model to address period compression for fixed-priority constrained-deadline task systems scheduled on a uniprocessor. We propose two approximate algorithms and one optimal algorithm for determining compression under the model. We then compare the execution times and accuracies of all three, demonstrating that even for large task sets, online compression can be performed feasibly on low-powered embedded systems.

The ROS2 software framework is increasingly prevalent in component-based applications for robots and other autonomous systems. Recently added ROS2 features to support zero-copy semantics may significantly reduce latency and latency variation when passing data from one component to another. Additionally, there is a growing trend of developing autonomous robotic systems on heterogeneous computing platforms to exploit hardware acceleration. However, support for portable and reusable zero-copy semantics on heterogeneous compute systems is limited. Such systems thus must either use low-level techniques to manage memory operations directly, which may be tedious and error-prone, or they may not adequately address substantial memory overheads that can arise from repeatedly copying messages and data into and out of device memory associated with GPUs and FPGAs. Towards addressing that limitation of the current state of the art, this paper introduces Hazcat, a new zero-copy framework that automatically performs device memory operations when needed, and avoids copying and other costly operations otherwise. Hazcat is integrated specifically with ROS2 but is also designed for portability to other component-based software frameworks.

Many real-time systems run in dynamic environments where exogenous factors inform task workloads and deadlines, which may not be known prior to job release. A job of a task that would otherwise miss its deadline may adapt to remain schedulable by executing in a degraded state that reduces its workload. We suggest that such a task should adjust parameters of its computation over multiple dimensions to maintain schedulability while minimizing loss of utility, which we discuss for highly parallel fork-join tasks executing on a fixed number of dedicated processors. We identify the parameterized degrees of freedom over which workload can be adjusted, then characterize the impact of workload reduction on response time and utility. From this, we generate a Pareto-optimal surface over which efficient search, interpolation, and extrapolation enable online selection of task parameters at time of job release. We apply this approach to the Advanced Particle-astrophysics Telescope, a planned mission to perform real-time gamma-ray burst (GRB) localization using SWaP-constrained embedded hardware aboard an orbiting platform. Due to GRBs' dynamic and uncertain nature, the workload and deadline may not be known prior to job release. Nonetheless, even for bright GRBs that may otherwise take longer than a second to localize on candidate embedded hardware, our approach often enables sub-degree accuracy while meeting a 33 ms imposed deadline.

Over the last two decades, as microprocessors have evolved to achieve higher computational performance, their power density has also increased at an accelerated rate. Improving energy efficiency and reducing power consumption are therefore critically important to modern computing systems. One effective technique for improving energy efficiency is dynamic voltage and frequency scaling (DVFS). With the emergence of integrated voltage regulators (IVRs), the speed of DVFS can reach microsecond ($\mu \text{s}$) timescales. However, a practical and effective strategy to guide fast DVFS remains a challenge. In this article, we propose F-LEMMA: a fast, learning-based, hierarchical DVFS framework consisting of a global power allocator in the kernel space, a reinforcement learning-based power management scheme at the architecture level, and a swift controller at the digital circuit level. This hierarchical approach leverages computation at the system and architecture levels with the short response time of the swift controller to achieve effective and rapid$\mu \text{s}$-level power management supported by the IVR. Our experimental results demonstrate that F-LEMMA can achieve significant energy savings (35.2%) across a broad range of workloads. Conservatively compared with existing state-of-the-art DVFS-based power management schemes that can only operate at millisecond timescales, F-LEMMA can provide notable (up to 11%) energy-delay product (EDP) improvements across benchmarks. Compared with state-of-the-art nonlearning-based power management, our method has a universally positive effect on evaluated benchmarks, proving its adaptability.

Many emerging cyber-physical systems, such as autonomous vehicles and robots, rely heavily on artificial intelligence and machine learning algorithms to perform important system operations. Since these highly parallel applications are computationally intensive, they need to be accelerated by graphics processing units (GPUs) to meet stringent timing constraints. However, despite the wide adoption of GPUs, efficiently scheduling multiple GPU applications while providing rigorous real-time guarantees remains challenging. Each GPU application has multiple CPU execution and memory copy segments, with GPU kernels running on different hardware resources. Because of the complicated interactions between heterogeneous segments of parallel tasks, high schedulability is hard to achieve with conventional approaches. This paper proposes RTGPU, which combines fine-grain GPU partitioning on the system-side with a novel scheduling algorithm on the theory-side. We start by building a model for CPU and memory copy segments. Leveraging persistent threads, we then implement fine-grained GPU partitioning with improved performance through interleaved execution. To reap the benefits of fine-grained GPU partitioning and schedule multiple parallel GPU applications, we propose a novel real-time scheduling algorithm based on federated scheduling and grid search with uniprocessor fixed-priority scheduling. Our approach provides real-time guarantees to meet hard deadlines and achieves over 11% improvement in system throughput and up to 57% schedulability improvement compared with previous work. We validate and evaluate RTGPU on NVIDIA GPU systems. Our system-side techniques can be applied on mainstream GPUs, and the proposed scheduling theory can be used in general heterogeneous computing platforms which have a similar task execution pattern.

Component-based design can encapsulate and isolate state and the operations on it, but timing semantics crosscut these boundaries when a real-time task’s control flow spans multiple components. Under priority-based scheduling, inter-component control flow should be coupled with priority information, so that task execution can be prioritized appropriately end-to-end. However, the CAmkES component architecture for the seL4 microkernel does not adequately support priority propagation across intercomponent requests: component interfaces are bound to threads that execute at fixed priorities provided at compile-time in the component specification. In this paper, we present a new library for CAmkES with a thread model that supports (1) multiple concurrent requests to the same component endpoint; (2) propagation and enforcement of priority metadata, such that those requests are appropriately prioritized; and (3) implementations of Non-Preemptive Critical Sections, the Immediate Priority Ceiling Protocol and the Priority Inheritance Protocol for components encapsulating critical sections of exclusive access to a shared resource. We measure overheads and blocking times for these new features and use existing theory to perform schedulability analysis. Evaluations on both Intel x86 and ARM platforms show that our new library allows CAmkES to provide suitable end-to-end timing for real-time systems.

As cyber-physical systems have become increasingly complex, rising computational demand has led to the ubiquitous use of multicore processors in embedded environments. Size, Weight, Power, and Cost (SWaP-C) constraints have pushed more processes onto shared platforms, including real-time tasks with deadline requirements. To prevent temporal interference among tasks running concurrently or in parallel in such systems, many operating systems provide priority-based scheduling and enforce processor reservations based on Worst-Case Execution Time (WCET) estimates. However, shared resources (both architectural components and data structures within the operating system) provide channels through which these constraints can be broken. Prior work has demonstrated that malicious execution by one or more processes can cause significant delays, leading to potential deadline misses in victim tasks. In this paper, we introduce PolyRhythm, a three-phase attack template that combines primitives across multiple architectural and kernel-based channels: (1) it uses an offline genetic algorithm to tune attack parameters based on the target hardware and OS platform; then (2) it performs an online search for regions of the attack parameter space where contention is most likely; and finally (3) it runs the attack primitives, using online reinforcement learning to adapt to dynamic execution patterns in the victim task. On a representative platform (Raspberry Pi 3B) Poly Rhythm outperforms prior work, achieving significantly more slowdown. As we show for several hardware/software platforms, Poly Rhythm also allows us to characterize the extent to which interference can occur; this helps to inform better estimates of execution times and overheads, towards preventing deadline misses in real-time systems.

As the role of virtualization technology becomes more prevalent, the range of applications deployed in virtualized systems is steadily growing. This increasingly includes applications with soft real-time requirements that benefit from low and predictable latency, even when co-located with other virtualized hosts with arbitrary traffic patterns. In this paper, we examine the policies and mechanisms affecting communication latency between virtual machines based on the Xen platform, and identify limitations that can result in long or unpredictable network stack latency for virtual machines deployed on this platform. To address these limitations, we propose and implementVATC, aVirtualization-Aware Traffic Controlframework that supports differentiation (via rate-limited prioritization) of outbound and inbound network traffic from co-located virtualized hosts. Results of our experiments show how and why VATC can offer predictable (soft) latency guarantees to applications running on virtualized hosts with minimum overhead.

The cloud's flexibility and promise of seamless auto-scaling notwithstanding, its ability to meet service level objectives (SLOs) typically calls for some form of control in resource usage. This seemingly traditional problem gives rise to new challenges in a cloud setting, and in particular a subtle yet significant trade-off involving load-distribution decisions (the distribution of workload across available cloud resources to optimize performance), and rate limiting (the capping of individual workloads to prevent global over-commitment). This paper investigates that trade-off through the design and implementation of a real-time messaging system motivated by Internet-of- Things (IoT) applications, and demonstrates a solution capable of realizing an effective compromise. The paper's contributions are in both explicating the source of this trade-off, and in demonstrating a possible solution.

Fault-tolerant coordination services have been widely used in distributed applications in cloud environments. Recent years have witnessed the emergence of time-sensitive applications deployed in edge computing environments, which introduces both challenges and opportunities for coordination services. On one hand, coordination services must recover from failures in a timely manner. On the other hand, edge computing employs local networked platforms that can be exploited to achieve timely recovery. In this work, we first identify the limitations of the leader election and recovery protocols underlying Apache ZooKeeper, the prevailing open-source coordination service. To reduce recovery latency from leader failures, we then design RT-Zookeeper with a set of novel features including a fast-convergence election protocol, a quorum channel notification mechanism, and a distributed epoch persistence protocol. We have implemented RT-Zookeeper based on ZooKeeper version 3.5.8. Empirical evaluation shows that RT-ZooKeeper achieves 91% reduction in maximum recovery latency in comparison to ZooKeeper. Furthermore, a case study demonstrates that fast failure recovery in RT-ZooKeeper can benefit a common messaging service like Kafka in terms of message latency.

Federated scheduling is a generalization of partitioned scheduling for parallel tasks on multiprocessors, and has been shown to be a competitive scheduling approach. However, federated scheduling may waste resources due to its dedicated allocation of processors to parallel tasks. In this work we introduce a novel algorithm for scheduling parallel tasks that require more than one processor to meet their deadlines (i.e., heavy tasks). The proposed algorithm computes a deterministic schedule for each heavy task based on its internal graph structure. It efficiently exploits the processors allocated to each task and thus reduces the number of processors required by the task. Experimental evaluation shows that our new federated scheduling algorithm significantly outperforms other state-of-the-art federated-based scheduling approaches, including semi-federated scheduling and reservation-based federated scheduling, that were developed to tackle resource waste in federated scheduling, and a stretching algorithm that also uses the tasks' graph structures.

In today's manycore processors, the energy loss of more than 20% may result from inherent inefficiencies of conventional power delivery system (PDS) design. By stacking multiple voltage domains in series to lower the step-down conversion ratio of the off-chip voltage regulator module (VRM) and reduce the energy loss along the path of the power delivery network (PDN), voltage stacking (VS) offers a novel alternative power delivery technique to fundamentally improve power delivery efficiency (PDE). However, VS suffers from aggravated supply voltage noise from the current imbalance, which hinders its adoption. In this article, we investigate practical VS implementation in manycore processors to improve PDE and achieve reliable performance, while maintaining compatibility with advanced power management techniques. We first present the system configuration of a voltage-stacked manycore processor. We then systematically characterize supply voltage noise in VS, identify global, and residual differential currents as its dominant contributors, and calculate the possible worst supply voltage noise. We next propose a hybrid voltage regulation solution, based on a charge-recycling off-chip voltage regulator and distributed integrated voltage regulators, to mitigate supply voltage noise effectively. We also study the compatibility of VS with higher-level power management techniques. Finally, the performance of a voltage-stacked GPU system is comprehensively evaluated. The simulation results show that our approach can achieve 93.5% PDE, reducing the power loss by 13.6% compared to conventional single-layer PDS.

Programming time-critical systems is notoriously difficult. In this paper we propose an actor-oriented programming model with a semantic notion of time and a deterministic coordination semantics based on discrete events to exercise precise control over both the computational and timing aspects of the system behavior.

Edge computing systems for Industrial Internet of Things (IIoT) applications require reliable and timely message delivery. Both latency discrepancies within edge clouds, and heterogeneous loss-tolerance and latency requirements pose new challenges for proper quality of service differentiation. Efficient differentiated edge computing architectures are also needed, especially when common fault-tolerant mechanisms tend to introduce additional latency, and when cloud traffic may impede local, time-sensitive message delivery. In this paper, we introduce FRAME, a fault-tolerant real-time messaging architecture. We first develop timing bounds that capture the relation between traffic/service parameters and loss-tolerance/latency requirements, and then illustrate how such bounds can support proper differentiation in a representative IIoT scenario. Specifically, FRAME leverages those timing bounds to schedule message delivery and replication actions to meet needed levels of assurance. FRAME is implemented on top of the TAO real-time event service, and we present empirical evaluations in a local edge computing test-bed and an Amazon Virtual Private Cloud. The results of those evaluations show that FRAME can efficiently meet different levels of message loss-tolerance requirements, mitigate latency penalties caused by fault recovery, and meet end-to-end soft deadlines during normal, fault-free operation.

There is increasing interest in supporting time-critical services in cloud computing environments. Those cloud services differ from traditional hard real-time systems in three aspects. First, cloud services usually involve latency requirements in terms of probabilistic tail latency instead of hard deadlines. Second, some cloud services need to handle aperiodic requests for stochastic arrival processes instead of traditional periodic or sporadic models. Finally, the computing platform must provide performance isolation between time-critical services and other workloads. It is therefore essential to provision resources to meet different tail latency requirements. As a step towards cloud services with stochastic latency guarantees, this paper presents a stochastic response time analysis for aperiodic services following a Poisson arrival process on computing platforms that schedue time-critical services as deferrable servers. The stochastic analysis enables a service operator to provision CPU resources for aperiodic services to achieve a desired tail latency. We evaluated the method in two case studies, one involving a synthetic service and another involving a Redis service, both on a testbed based on Xen 4.10. The results demonstrate the validity and efficacy of our method in a practical setting.

Cyber-physical systems (CPS) involve tight integration of cyber (computation) and physical domains, and both the effectiveness and correctness of a cyber-physical system application may rely on successful enforcement of constraints such as bounded latency and temporal validity subject to physical conditions. For many such systems (e.g., edge computing in the Industrial Internet of Things), it is desirable to enforce such constraints within a common middleware service (e.g., during event processing). In this article, we introduce CPEP, a new real-time middleware for cyber-physical event processing, with (1) extensible support for complex event processing operations, (2) execution prioritization and sharing, (3) enforcement of time consistency with load shedding, and (4) efficient memory management and concurrent data processing. We present the design, implementation, and empirical evaluation of CPEP and show that it can (1) support complex operations needed by many applications, (2) schedule data processing according to consumers’ priority levels, (3) enforce temporal validity, and (4) reduce processing delay and improve throughput of time-consistent events.

The control of a catoptric (mirror-based) surface is decomposed hierarchically. The positioning control of individual mirrors is handled by low-level controllers for each drive motor, and the overall control decisions are guided by a Markov decision process.

More than 20% of the available energy is lost in "the last centimeter" from the PCB board to the microprocessor chip due to inherent inefficiencies of power delivery subsystems (PDSs) in today's computing systems. By series-stacking multiple voltage domains to eliminate explicit voltage conversion and reduce loss along the power delivery path, voltage stacking (VS) is a novel configuration that can improve power delivery efficiency (PDE). However, VS suffers from aggravated levels of supply noise caused by current imbalance between the stacking layers, preventing its practical adoption in mainstream computing systems. Throughput-centric manycore architectures such as GPUs intrinsically exhibit more balanced workloads, yet suffer from lower PDE, making them ideal platforms to implement voltage stacking. In this paper, we present a cross-layer approach to practical voltage stacking implementation in GPUs. It combines circuit-level voltage regulation using distributed charge-recycling integrated voltage regulators (CR-IVRs) with architecture-level voltage smoothing guided by control theory. Our proposed voltage-stacked GPUs can eliminate 61.5% of total PDS energy loss and achieve 92.3% system-level power delivery efficiency, a 12.3% improvement over the conventional single-layer based PDS. Compared to the circuit-only solution, the cross-layer approach significantly reduces the implementation cost of voltage stacking (88% reduction in area overhead) without compromising supply reliability under worst-case scenarios and across a wide range of real-world benchmarks. In addition, we demonstrate that the cross-layer solution not only complements on-chip CR-IVRs to transparently manage current imbalance and restore stable layer voltages, but also serves as a seamless interface to accommodate higher-level power optimization techniques, traditionally thought to be incompatible with a VS configuration.

Real-time virtualization is an emerging technology for embedded systems integration and latency-sensitive cloud applications. Earlier real-time virtualization platforms require offline configuration of the scheduling parameters of virtual machines (VMs) based on their worst-case workloads, but this static approach results in pessimistic resource allocation when the workloads in the VMs change dynamically. Here, we present Multi-Mode-Xen (M2-Xen), a real-time virtualization platform for dynamic real-time systems where VMs can operate in modes with different CPU resource requirements at run-time. M2-Xen has three salient capabilities: (1) dynamic allocation of CPU resources among VMs in response to their mode changes, (2) overload avoidance at both the VM and host levels during mode transitions, and (3) fast mode transitions between different modes. M2-Xen has been implemented within Xen 4.8 using the real-time deferrable server (RTDS) scheduler. Experimental results show that M2-Xen maintains real-time performance in different modes, avoids overload during mode changes, and performs fast mode transitions.

In recent years, there has been significant interest in developing real-time schedulers for parallel tasks. Most of that research has concentrated on idealized task models where tasks do not access any shared resources protected with locks. In this paper, we consider the problem of scheduling parallel tasks which experience contention due to shared resources. In particular, we provide a schedulability test for federated scheduling by deriving blocking time analyses for parallel tasks that access shared resources protected by FIFO-ordered and priority-ordered spin locks. Our numerical evaluation on randomly generated task sets indicates that priority-ordered locks generally provide better schedulability results than FIFO-ordered locks. We also incorporated both FIFO-ordered and priority-ordered spin lock implementations into a federated scheduling platform, which is able to schedule parallel tasks written with OpenMP. Via empirical evaluations, we found that priority-ordered locks also have better performance than FIFO-ordered locks in practice.

Cyber-physical applications are subject to temporal validity constraints, which must be enforced in addition to traditional QoS requirements such as bounded latency. For many such systems (e.g., automotive and edge computing in the Industrial Internet of Things) it is desirable to enforce such constraints within a common middleware service (e.g., during event processing). In this paper, we introduce CPEP, a new real-time middleware for cyber-physical event processing, with (1) extensible support for complex data processing operations, (2) execution prioritization and sharing, (3) enforcement of absolute time consistency with load shedding, and (4) efficient memory management and concurrent data processing. We present the design, implementation, and empirical evaluation of CPEP and show that it can (1) support complex operations needed by many applications, (2) schedule data processing according to consumers' QoS requirements, (3) enforce temporal validity, and (4) reduce processing delay and improve throughput of temporally valid events.

The AMC-IA mixed-criticality scheduling analysis was proposed as an improvement to the AMC-MAX adaptive mixed-criticality scheduling analysis. However, we have identified several necessary corrections to the AMC-IA analysis. In this article, we motivate and describe those corrections, and discuss and illustrate why the corrected AMC-IA analysis cannot be shown to outperform AMC-MAX.

Wireless communication is increasingly being used to federate embedded devices in a variety of distributed systems application domains, ranging from wireless sensor networks to the emerging "Internet of Things (IoT)." Since such embedded devices are tightly coupled both with their environments and with each other through their wireless communication channels, both variations in their environments and the system's need to respond (sometimes rapidly) to those variations may produce (1) the need for such devices to communicate and (2) with it the potential for channel contention to arise, dynamically at run-time. Thus, how wireless channels among the embedded devices are allocated and managed in these systems may significantly influence both communication-specific quality-of-service (QoS) properties (such as message throughput) and broader QoS properties (such as timeliness of system responsiveness) that depend on them. A growing body of research has focused on managing different aspects of wireless communication, but has done so mainly in an ad hoc manner, with respect to individual aspects rather than multiple aspects and their potential interactions. Even less attention has been paid to formal methods for assessing how combinations of aspects may influence communication performance, and how to characterize, adapt to, and exploit their combined effects, which is essential to address the challenges noted above. To overcome these limitations of the current state of the art, this paper makes three main contributions to wireless communication for distributed embedded systems with QoS constraints. First, it shows how a basic but fundamental set of channel admission and modulation decisions can be combined within a single Markov decision process (MDP) model to optimize (in expectation) objectives such as message throughput, even with stochastic arrival and interference characteristics. Second, it identifies regular structure in the value-optimal policies generated off-line from these models, which forms the basis for efficient and accurate heuristics suitable for on-line use. Third, it shows how single-and multi-variable regression techniques can be used to characterize key parameters that govern such regular structure, which then are used to instantiate those heuristics.

A mixed-criticality system comprises safety-critical and non-safety-critical tasks sharing a computational platform. Thus, different levels of assurance are required by different tasks in terms of real-time performance. In addition, as the computational demands of real-time tasks are increasing, tasks may require internal parallelism in order to complete within stringent deadlines. In this paper, we consider the problem of mixed-criticality scheduling of parallel real-time tasks and propose a novel mixed-criticality federated scheduling (MCFS) algorithm for parallel real-time tasks based on the directed acyclic graph model. MCFS is based on federated intuition for scheduling parallel real-time tasks. It strategically assigns cores and virtual deadlines to tasks in order to achieve good schedulability. For task sets with only high-utilization tasks (utilization >= 1), we prove that MCFS provides a capacity augmentation bound of 3.41 and 3.73 for dual-criticality and multi- criticality, respectively. We also show that MCFS have capacity augmentation bounds of 3.67m/(m-1) for a dual-criticality system with both high- and low-utilization tasks, which to our knowledge is the first such performance bound for parallel mixed-criticality tasks. We also present an implementation of an MCFS runtime system in Linux that supports parallel programs written in OpenMP. We conduct both numerical and empirical experiments to demonstrate the practicality of our MCFS approach.

Recent years have witnessed the convergence of two important trends in real-time systems: growing computational demand of applications and the adoption of processors with more cores. As real-time applications now need to exploit parallelism to meet their real-time requirements, they face a new challenge of scaling up computations on a large number of cores. Randomized work stealing has been adopted as a highly scalable scheduling approach for general-purpose computing. In work stealing, each core steals work from a randomly chosen core in a decentralized manner. Compared to centralized greedy schedulers, work stealing may seem unsuitable for real-time computing due to the non-predictable nature of random stealing. Surprisingly, our experiments with benchmark programs found that random work stealing (in Cilk Plus) delivers tighter distributions in task execution times than a centralized greedy scheduler (in GNU OpenMP).To support scalable soft real-time computing, we develop Real-Time Work-Stealing platform (RTWS), a real-time extension to the widely used Cilk Plus concurrency platform. RTWS employs federated scheduling to allocate cores to multiple parallel real-time tasks offline, while leveraging the work stealing scheduler to schedule each task on its dedicated cores online. RTWS supports parallel programs written in Cilk Plus and requires only task parameters that can be readily measured using existing Cilk Plus tools. Experimental results show that RTWS outperforms Real-Time OpenMP in term of deadline miss ratio, relative response time and resource efficiency on a 32-core system.

Clouds have become appealing platforms for not only general-purpose applications, but also real-time ones. However, current clouds cannot provide real-time performance to virtual machines (VMs). We observe the demand and the advantage of co-hosting real-time (RT) VMs with non-real-time (regular) VMs in a same cloud. RT VMs can benefit from the easily deployed, elastic resource provisioning provided by the cloud, while regular VMs effectively utilize remaining resources without affecting the performance of RT VMs through proper resource management at both the cloud and the hyper visor levels. This paper presents RT-Open Stack, a cloud CPU resource management system for co-hosting real-time and regular VMs. RT-Open Stack entails three main contributions: (1) integration of a real-time hyper visor (RT-Xen) and a cloud management system (Open Stack) through a real-time resource interface, (2) a real-time VM scheduler to allow regular VMs to share hosts with RT VMs without interfering the real-time performance of RT VMs, and (3) a VM-to-host mapping strategy that provisions real-time performance to RT VMs while allowing effective resource sharing with regular VMs. Experimental results demonstrate that RT-Open Stack can effectively improve the real-time performance of RT VMs while allowing regular VMs to fully utilize the remaining CPU resources.

As virtualization technology becomes ever more capable, large-scale distributed applications are increasingly deployed in virtualized environments such as data centers and computational clouds. Many large-scale applications have soft real-time requirements and benefit from low and predictable latency, even in the presence of diverse traffic patterns between virtualized hosts. In this paper, we examine the policies and mechanisms affecting communication latency between virtual machines based on the Xen platform, and identify limitations that could result in long or unpredictable network traffic latencies. To address these limitations, we propose VATC, aVirtualization-Aware Traffic Controlframework for prioritizing network traffic in virtualized hosts. Results of our experiments show how and why VATC can improve predictability and reduce delay for latency sensitive applications, while introducing limited overhead.

This paper considers the scheduling of parallel real-time tasks with implicit deadlines. Each parallel task is characterized as a general directed acyclic graph (DAG). We analyze three different real-time scheduling strategies: two well known algorithms, namely global earliest-deadline-first and global rate-monotonic, and one new algorithm, namely federated scheduling. The federated scheduling algorithm proposed in this paper is a generalization of partitioned scheduling to parallel tasks. In this strategy, each high-utilization task (utilization ≥ 1) is assigned a set of dedicated cores and the remaining low-utilization tasks share the remaining cores. We prove capacity augmentation bounds for all three schedulers. In particular, we show that if on unit-speed cores, a task set has total utilization of at most m and the critical-path length of each task is smaller than its deadline, then federated scheduling can schedule that task set on m cores of speed 2, G-EDF can schedule it with speed 3 + v5/2 2.618, and G-RM can schedule it with speed 2 + v3 3.732. We also provide lower bounds on the speedup and show that the bounds are tight for federated scheduling and G-EDF when m is sufficiently large.

Real-time hybrid simulation (RTHS) is an important tool in the design and testing of civil and mechanical structures when engineers and scientists wish to understand the performance of an isolated component within the context of a larger structure. Performing full-scale physical experimentation with a large structure can be prohibitively expensive. Instead, a hybrid testing framework connects part of a physical structure within a closed loop (through sensors and actuators) to a numerical simulation of the rest of the structure. If we wish to understand the dynamic response of the combined structure, this testing must be done in real-time, which significantly restricts both the size of the simulation and the rate at which it can be conducted.

Recent years have witnessed two major trends in the development of complex real-time embedded systems. First, to reduce cost and enhance flexibility, multiple systems are sharing common computing platforms via virtualization technology, instead of being deployed separately on physically isolated hosts. Second, multicore processors are increasingly being used in real-time systems. The integration of real-time systems as virtual machines (VMs) atop common multicore platforms raises significant new research challenges in meeting the real-time performance requirements of multiple systems. This paper advances the state of the art in real-time virtualization by designing and implementing RT-Xen 2.0, a new real-time multicore VM scheduling framework in the popular Xen virtual machine monitor (VMM). RT-Xen 2.0 realizes a suite of real-time VM scheduling policies spanning the design space. We implement both global and partitioned VM schedulers; each scheduler can be configured to support dynamic or static priorities and to run VMs as periodic or deferrable servers. We present a comprehensive experimental evaluation that provides important insights into real-time scheduling on virtualized multicore platforms: (1) both global and partitioned VM scheduling can be implemented in the VMM at moderate overhead; (2) at the VMM level, while compositional scheduling theory shows partitioned EDF (pEDF) is better than global EDF (gEDF) in providing schedulability guarantees, in our experiments their performance is reversed in terms of the fraction of workloads that meet their deadlines on virtualized multi-core platforms; (3) at the guest OS level, pEDF requests a smaller total VCPU bandwidth than gEDF based on compositional scheduling analysis, and therefore using pEDF at the guest OS level leads to more schedulable workloads in our experiments; (4) a combination of pEDF in the guest OS and gEDF in the VMM -- configured with deferrable server -- leads to the highest fraction of schedulable task sets compared to other real-time VM scheduling policies; and (5) on a platform with a shared last-level cache, the benefits of global scheduling outweigh the cache penalty incurred by VM migration.

Shared caches in mixed criticality systems are a source of interference for safety critical tasks. Shared memory not only leads to worst-case execution time (WCET) pessimism, but also affects the response time of safety critical tasks. In this paper, we present a criticality aware cache design which implements a Least Critical (LC) cache replacement policy, where a least recently used non-critical cache line is replaced during a cache miss. The cache acts as a Least Recently Used (LRU) cache if there are no critical lines or if all cache lines are critical in a set. In our design, data within a certain address space is given higher preference in the cache. These critical address spaces are configured using critical address range (CAR) registers. The new cache design was implemented in a Leon3 processor core, a 32bit processor compliant with the SPARC V8 architecture. Experimental results are presented that illustrate the impact of the Least Critical cache replacement policy on the response time of critical tasks, and on overall application performance as compared to a conventional LRU cache policy.

Large-scale cyber-physical systems (CPS) in mission-critical areas such as transportation, health care, energy, agriculture, defense, homeland security, and manufacturing, are becoming increasingly interconnected and interdependent. These types of CPS are unique in their need to combine rigorous control over timing and physical properties, as well as functional ones, while operating dynamically, reliably and affordably over significant scales of distribution, resource consumption, and utilization. As large-scale CPS continue to evolve-and grow in scale and complexity-they will impose significant and novel requirements for a new kind of cloud computing that is not supported by conventional technologies To meet these requirements, cloud computing advances are needed to establish real-time computing, communication, and control foundations rigorously at scale. Likewise, advances are needed to apply these foundations in a flexible and scalable manner to different real-world large-scale CPS challenge problems. To support both foundational and experimental R&D, a new generation of elastic infrastructure must be designed, developed, and evaluated. This paper identifies challenges, opportunities, and benefits for this work and for the largescale CPS it targets.

Federated scheduling is a strategy to schedule parallel real-time tasks: It allocates a dedicated cluster of cores to each high-utilization task (utilization ≥ 1); It uses a multiprocessor scheduling algorithm to schedule and execute all low-utilization tasks sequentially, on a shared cluster of the remaining cores. Prior work has shown that federated scheduling has the best known capacity augmentation bound of 2 for parallel tasks with implicit deadlines. In this paper, we explore the soft real-time performance of federated scheduling and address average-case workloads instead of worst-case ones. In particular, we consider stochastic tasks — tasks for which execution time and critical-path length are random variables. In this case, we use bounded expected tardiness as the schedulability criterion. We define a stochastic capacity augmentation bound and prove that federated scheduling algorithms guarantee the same bound of 2 for stochastic tasks. We present three federated mapping algorithms with different complexities for core allocation. All of them guarantee bounded expected tardiness and provide the same capacity augmentation bound. In practice, however, we expect them to provide different performance, both in terms of the task sets they can schedule and the actual tardiness they guarantee. Therefore, we present numerical evaluations using randomly generated task sets to examine the practical differences between the three algorithms.

No abstract available.

Traditional fixed-priority scheduling analysis for periodic and sporadic task sets is based on the assumption that all tasks are equally critical to the correct operation of the system. Therefore, every task has to be schedulable under the chosen scheduling policy, and estimates of tasks' worst-case execution times must be conservative in case a task runs longer than is usual. To address the significant underutilization of a system's resources under normal operating conditions that can arise from these assumptions, several mixed-criticality scheduling approaches have been proposed. However, to date, there have been few quantitative comparisons of system schedulability or runtime overhead for the different approaches. In this article, we present a side-by-side implementation and evaluation of the known mixed-criticality scheduling approaches, for periodic and sporadic mixed-criticality tasks on uniprocessor systems, under a mixed-criticality scheduling model that is common to all these approaches. To make a fair evaluation of mixed-criticality scheduling, we also address previously open issues and propose modifications to improve particular approaches. Our empirical evaluations demonstrate that user-space implementations of mechanisms to enforce different mixed-criticality scheduling approaches can be achieved atop Linux without kernel modification, with reasonably low (but in some cases nontrivial) overhead for mixed-criticality real-time task sets.

Recently, multi-core processors have become mainstream in processor design. To take full advantage of multi-core processing, computation-intensive real-time systems must exploit intra-task parallelism. In this paper, we address the problem of real-time scheduling for a general model of deterministic parallel tasks, where each task is represented as a directed acyclic graph (DAG) with nodes having arbitrary execution requirements. We prove processor-speed augmentation bounds for both preemptive and non-preemptive real-time scheduling for general DAG tasks on multi-core processors. We first decompose each DAG into sequential tasks with their own release times and deadlines. Then we prove that these decomposed tasks can be scheduled using preemptive global EDF with a resource augmentation bound of$4$. This bound is as good as the best known bound for more restrictive models, and is the first for a general DAG model. We also prove that the decomposition has a resource augmentation bound of$4$plus a constant non-preemption overhead for non-preemptive global EDF scheduling. To our knowledge, this is the first resource augmentation bound for non-preemptive scheduling of parallel tasks. Finally, we evaluate our analytical results through simulations that demonstrate that the derived resource augmentation bounds are safe in practice.

As multicore processors become ever more prevalent, it is important for real-time programs to take advantage of intra-task parallelism in order to support computation-intensive applications with tight deadlines. We prove that a Global Earliest Deadline First (GEDF) scheduling policy provides a capacity augmentation bound of 4-2/m and a resource augmentation bound of 2-1/m for parallel tasks in the general directed a cyclic graph model. For the proposed capacity augmentation bound of 4-2/m for implicit deadline tasks under GEDF, we prove that if a task set has a total utilization of at most m/(4-2/m) and each task's critical path length is no more than 1/(4-2/m) of its deadline, it can be scheduled on a machine with m processors under GEDF. Our capacity augmentation bound therefore can be used as a straightforward schedulability test. For the standard resource augmentation bound of 2-1/m for arbitrary deadline tasks under GEDF, we prove that if an ideal optimal scheduler can schedule a task set on m unit-speed processors, then GEDF can schedule the same task set on m processors of speed 2-1/m. However, this bound does not lead to a schedulabilty test since the ideal optimal scheduler is only hypothetical and is not known. Simulations confirm that the GEDF is not only safe under the capacity augmentation bound for various randomly generated task sets, but also performs surprisingly well and usually outperforms an existing scheduling technique that involves task decomposition.

As computer hardware becomes increasingly powerful, there is an ongoing trend towards integrating QoS-critical systems as virtual machines (domains) on a common, virtualized computing platform. Given the lower latency of local inter-domain communication (IDC) on the same host (compared to inter-host communication), system administrators may preferably colocate domains so that they can communicate locally. When multiple IDC flows contend on the same host, it is important to properly prioritize IDC flows among domains to meet their respective QoS requirements. This paper examines the limitations of IDC in Xen, a widely used open-source virtual machine monitor (VMM) that recently has been extended to support real-time domain scheduling. We find that both the VMM scheduler and the manager domain can significantly impact IDC QoS under different conditions, and show that improving the VMM scheduler alone cannot effectively prevent priority inversion for local IDC. To address those limitations, we present RTCA, a Real-Time Communication Architecture within the manager domain in Xen, along with experimental results that demonstrate the latency of high-priority IDC can be improved dramatically from ms to μs by a combination of the RTCA and a real-time VMM scheduler.

The stochastic nature of wireless communication suggests a Markov Decision Process (MDP) as a formalism for identifying and evaluating spectrum control policies. However, in practice numerous factors influence the success or failure of a transmission, so that the applicability of particular MDP models to real spectrum management problems must itself be examined. This paper presents a series of model validation studies in which correspondence between an MDP model and a discrete-event simulation (DES) model is evaluated. We test several hypotheses that together provide a foundation and an exemplar for the idea of using MDPs to guide management of shared spectrum. We conclude that there is sufficient similarity between the performance predictions made by the MDP model and the DES model that MDPs can be used effectively to determine spectrum control policies.

The multi-core revolution presents both opportunities and challenges for real-time systems. Parallel computing can yield significant speedup for individual tasks (enabling shorter deadlines, or more computation within the same deadline), but unless managed carefully may add complexity and overhead that could potentially wreck real-time performance. There is little experience to date with the design and implementation of realtime systems that allow parallel tasks, yet the state of the art cannot progress without the construction of such systems. In this work we describe the design and implementation of a scheduler and runtime dispatcher for a new concurrency platform, RT-OpenMP, whose goal is the execution of real-time workloads with intra-task parallelism.

Welcome to Taipei, Taiwan, and the IEEE 19th International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA 2013). RTCSA has been a prestigious technical conference sponsored by the IEEE Technical Committee on Real-Time Systems for years. The objective of the conference is to bring together academic researchers and industry developers for intensive discussion of recent advances in the field of embedded systems, real-time systems, and cyber-physical systems.

Multicore processors are becoming ubiquitous, and it is becoming increasingly common to run multiple real-time systems on a shared multicore platform. While this trend helps to reduce cost and to increase performance, it also makes it more challenging to achieve timing guarantees and functional isolation. One approach to achieving functional isolation is to use virtualization. However, virtualization also introduces many challenges to the multicore timing analysis, for instance, the overhead due to cache misses becomes harder to predict, since it depends not only on the direct interference between tasks but also on the indirect interference between virtual processors and the tasks executing on them. In this paper, we present a cache-aware compositional analysis technique that can be used to ensure timing guarantees of components scheduled on a multicore virtualization platform. Our technique improves on previous multicore compositional analyses by accounting for the cache-related overhead in the components' interfaces, and it addresses the new virtualization-specific challenges in the overhead analysis. To demonstrate the utility of our technique, we report results from an extensive evaluation based on randomly generated workloads.

The field of modern control theory and the systems used to implement these controls have shown rapid development over the last 50 years. It was often the case that those developing control algorithms could assume the computing medium was solely dedicated to the task of controlling a plant, for example, the control algorithm being implemented in software on a dedicated Digital Signal Processor (DSP), or implemented in hardware using a simple dedicated Programmable Logic Device (PLD). As time progressed, the drive to place more system functionality in a single component (reducing power, cost, and increasing reliability) has made this assumption less often true. Thus, it has been pointed out by some experts in the field of control theory (e.g., Astrom) that those developing control algorithms must take into account the effects of running their algorithms on systems that will be shared with other tasks. One aspect of the work presented in this article is a hardware architecture that allows control developers to maintain this simplifying assumption. We focus specifically on the Proportional-Integral-Derivative (PID) controller. An on-chip coprocessor has been implemented that can scale to support servicing hundreds of plants, while maintaining microsecond-level response times, tight deterministic control loop timing, and allowing the main processor to service noncontrol tasks. In order to control a plant, the controller needs information about the plant's state. Typically this information is obtained from sensors with which the plant has been instrumented. There are a number of common computations that may be performed on this sensor data before being presented to the controller (e.g., averaging and thresholding). Thus in addition to supporting PID algorithms, we have developed a Sensor Processing Unit (SPU) that off-loads these common sensor processing tasks from the main processor. We have prototyped our ideas using Field Programmable Gate Array (FPGA) technology. Through our experimental results, we show our PID execution unit gives orders of magnitude improvement in response time when servicing many plants, as compared to a standard general software implementation. We also show that the SPU scales much better than a general software implementation. In addition, these execution units allow the simplifying assumption of dedicated computing medium to hold for control algorithm development.

Traditional fixed-priority scheduling analysis for periodic task sets is based on the assumption that all tasks are equally critical to the correct operation of the system. Therefore, every task has to be schedulable under the scheduling policy, and estimates of tasks' worst case execution times must be conservative in case a task runs longer than is usual. To address the significant under-utilization of a system's resources under normal operating conditions that can arise from these assumptions, three main approaches have been proposed: priority assignment, period transformation, and zero-slack scheduling. However, to date there has been no quantitative comparison of system schedulability or run-time overhead for the different approaches. In this paper, we present what is to our knowledge the first side-by-side evaluation of those approaches, for periodic mixed-criticality tasks on uniprocessor systems, under a mixed-criticality scheduling model that is common to all three approaches. To make a fair evaluation of zero-slack scheduling, we also address two previously open issues: how to accommodate execution of a task after its deadline, and how to account for previously unidentified forms of interference between mixed-criticality tasks. Our simulations show that while priority assignment and period transformation are most likely to be able to schedule a randomly selected task set, a small fraction of the task sets are schedulable only under the zero-slack approach. Our empirical evaluation demonstrates that user-space implementations of mechanisms to enforce period transformation and zero-slack scheduling can be achieved on Linux without kernel modification, with suitably low overhead for mixed-criticality real-time task sets.

We present a co-designed scheduling framework and platform architecture that together support compositional scheduling of real-time systems. The architecture is built on the Xen virtualization platform, and relies on compositional scheduling theory that uses periodic resource models as component interfaces. We implement resource models as periodic servers and consider enhancements to periodic server design that significantly improve response times of tasks and resource utilization in the system while preserving theoretical schedulability results. We present an extensive evaluation of our implementation using workloads from an avionics case study as well as synthetic ones.

Driven by the evolution of modern computer architectures from uni-processor to multi-core platforms, there is an increasing need to provide light-weight, efficient, and predictable support for fine-grained parallel and distributed execution of soft real-time tasks with end-to-end timing constraints, modeled as directed a cyclic graphs whose edges capture dependences among their subtasks. At the same time, there is a need to support state of the art programming models such as distributed components, whose ability to encapsulate functionality and allow context-specific optimizations is essential to manage the increasing complexity of modern distributed real-time and embedded systems and systems-of-systems. Real-time distributed middleware such as RT-CORBA has not kept pace with these developments, and a new generation of middleware is needed that can map these dependent subtask graphs onto distributed hosts with multi-core architectures, efficiently and within a simple, lightweight, and intuitive component programming model. To overcome these limitations, we have designed and implemented MC Flow, a novel distributed real-time component middleware for dependent subtask graphs running on multi-core platforms. MC Flow provides three new contributions to the state of the art in real-time component middleware: (1) a very lightweight component model that facilitates system integration and deployment through automatic code generation at compile time from a deployment plan specification, (2) transparent optimization of inter-component communication, and (3) the use of interface polymorphism to separate functional correctness from data copying and other performance constraints so that they can be configured and enforced independently but in a type-safe manner. Empirical evaluations of our approach in comparison to the widely used TAO real-time middleware show that MC Flow performs comparably to TAO when only one core is used and outperforms TAO when multiple cores are involved.

Modern embedded systems are increasingly likely to be distributed across multiple devices and platforms that must interact with high precision across wireless networks. Traditional ways of managing the wireless radio spectrum suffer from two fundamental limitations, which the research presented in this paper addresses: (1) spectrum is divided a priori into static coarse-grained partitions without reference to details of particular applications, and (2) partitions are non-overlapping, which although beneficial to reduce interference prevents a much greater utilization of the spectrum through carefully allowing overlap of spectrum allocations. To overcome these limitations, we propose an approach to spectrum allocation based on dynamic allocation of diverse portions of the overall spectrum and overlapping allocations to increase utilization. This paper makes three main contributions to the state of the art in spectrum management for embedded systems: (1) it examines how memory management techniques such as Knuth's buddy algorithm can be applied to spectrum management, in the face of transmission failures that may arise from the physical environment, (2) it extends that approach to consider transmission failures resulting from interference, when overlapping regions of spectrum are allocated to increase utilization, and (3) it presents results of simulation experiments we conducted to evaluate those approaches, which demonstrate their efficacy and suggest future extensions based on them.

Time utility functions can describe the complex timing constraints of real-time and cyber-physical systems. However, utility aware scheduling policy design is an open research problem. Previously we solved a Markov Decision Process formulation of the scheduling problem to derive value-optimal scheduling policies for systems with periodic real-time task sets and stochastic non-preemptive execution intervals. However, the complexity of computing solutions and their policy storage requirements necessitate the exploration of scalable solutions. In this paper we generalize the Utility Accrual Packet Scheduling Algorithm. We compare several heuristics to Markov Decision Process policy evaluation under soft and hard real-time conditions, different load conditions, and different classes of time utility functions. Based on these evaluations we present guidelines for which heuristics are best suited to particular scheduling criteria.

As system integration becomes an increasingly important challenge for complex real-time systems, there has been a significant demand for supporting real-time systems in virtualized environments. This paper presents RT-Xen, the first real-time hypervisor scheduling framework for Xen, the most widely used open-source virtual machine monitor (VMM). RT-Xen bridges the gap between real-time scheduling theory and Xen, whose wide-spread adoption makes it an attractive platform for integrating a broad range of real-time and embedded systems. Moreover, RT-Xen provides an open-source platform for researchers and integrators to develop and evaluate real-time scheduling techniques, which to date have been studied predominantly via analysis and simulations.

Multi-core processors offer a significant performance increase over single core processors. Therefore, they have the potential to enable computation-intensive real-time applications with stringent timing constraints that cannot be met on traditional single-core processors. However, most results in traditional multiprocessor real-time scheduling are limited to sequential programming models and ignore intra-task parallelism. In this paper, we address the problem of scheduling periodic parallel tasks with implicit deadlines on multi-core processors. We first consider a synchronous task model where each task consists of segments, each segment having an arbitrary number of parallel threads that synchronize at the end of the segment. We propose a new task decomposition method that decomposes each parallel task into a set of sequential tasks. We prove that our task decomposition achieves a resource augmentation bound of 2.62 and 3.42 when the decomposed tasks are scheduled using global EDF and partitioned deadline monotonic scheduling, respectively. Finally, we extend our analysis to directed a cyclic graph tasks. We show how these tasks can be converted into synchronous tasks such that the same transformation can be applied and the same augmentation bounds hold.

Developing large-scale distributed real-time and embedded (DRE) systems is hard in part due to complex deployment and configuration issues involved in satisfying multiple quality for service (QoS) properties, such as real-timeliness and fault tolerance. This paper makes three contributions to the study of deployment and configuration middleware for DRE systems that satisfy multiple QoS properties. First, it describes a novel task allocation algorithm for passively replicated DRE systems to meet their real-time and fault-tolerance QoS properties while consuming significantly less resources. Second, it presents the design of a strategizable allocation engine that enables application developers to evaluate different allocation algorithms. Third, it presents the design of a middleware agnostic configuration framework that uses allocation decisions to deploy application components/replicas and configure the underlying middleware automatically on the chosen nodes. These contributions are realized in the DeCoRAM (Deployment and Configuration Reasoning and Analysis via Modeling) middleware. Empirical results on a distributed testbed demonstrate DeCoRAM’s ability to handle multiple failures and provide efficient and predictable real-time performance.

Open soft real-time systems, such as mobile robots, must respond adaptively to varying operating conditions, while balancing the need to perform multiple mission specific tasks against the requirement that those tasks complete in a timely manner. Setting and enforcing a utilization target for shared resources is a key mechanism for achieving this behavior. However, because of the uncertainty and non-preempt ability of some tasks, key assumptions of classical scheduling approaches do not hold. In previous work we presented foundational methods for generating task scheduling policies to enforce proportional resource utilization for open soft real-time systems with these properties. However, these methods scale exponentially in the number of tasks, limiting their practical applicability.In this paper, we present a novel parameterized scheduling policy that scales our technique to a much wider range of systems. These policies can represent geometric features of the scheduling policies produced by our earlier methods, but only require a number of parameters that is quadratic in the number of tasks. We provide empirical evidence that the best of these policies are competitive with exact solution methods in small problems, and significantly outperform heuristic methods in larger ones.

Abstract—Classical scheduling abstractions such as deadlines and priorities do not readily capture the complex timing semantics found in many real-time cyber-physical systems. Time utility functions provide a necessarily richer description of timing semantics, but designing utility-aware scheduling policies using them is an open research problem. In particular, scheduling design that optimizes expected utility accrual is needed for realtime cyber-physical domains. In this paper we design scheduling policies that optimize expected utility accrual for cyber-physical systems with periodic, non-preemptable tasks that run with stochastic duration. These policies are derived by solving a Markov Decision Process formulation of the scheduling problem. We use this formulation to demonstrate that our technique improves on existing heuristic utility accrual scheduling policies. I.

Different distributed real-time systems (DRS) must handle aperiodic and periodic events under diverse sets of requirements. While existing middleware such as Real-Time CORBA has shown promise as a platform for distributed systems with time constraints, it lacks flexible configuration mechanisms needed to manage end-to-end timing easily for a wide range of different DRS with both aperiodic and periodic events. The primary contribution of this work is the design, implementation, and performance evaluation of the first configurable component middleware services for admission control and load balancing of aperiodic and periodic event handling in DRS. Empirical results demonstrate the need for, and the effectiveness of, our configurable component middleware approach in supporting different applications with aperiodic and periodic events, and providing a flexible software platform for DRS with end-to-end timing constraints.

Real-time hybrid testing of civil structures represents agrand challenge in the emerging area of cyber-physical systems. Hybrid testing improves significantly on either purely numerical or purely empirical approaches by integrating physical structural components and computational models. Actuator dynamics, complex interactions among computers and physical components, and computation and communication delays all hamper the ability to conduct accurate tests. To address these challenges, this paper presents initial work towards a Cyber-physical Instrument for Real-time hybrid Structural Testing (CIRST). CIRST aims to provide two salient features: a highly configurable architecture for integrating computers and physical components; and system support for real-time operations in distributed hybrid testing. This paper presents the motivation of the CIRST architectureand preliminary test results from a proof-of-concept implementation that integrates a simple structural element and simulation model. CIRST will have broad impacts on thefields of both civil engineering and real-time computing.It will enable high-fidelity real-time hybrid testing of awide range of civil infrastructures, and will also providea high-impact cyber-physical application for the study andevaluation of real-time middleware.

Supporting uninterrupted services for distributed soft real-time applications is hard in resource-constrained and dynamic environments, where processor or process failures and system workload changes are common. Fault-tolerant middleware for these applications must achieve high service availability and satisfactory response times for client applications. Although passive replication is a promising fault tolerance strategy for resource-constrained systems, conventional client failover approaches are non-adaptive and load-agnostic, which can cause system overloads and significantly increase response times after failure recovery.This paper presents four contributions to the study of passive replication for distributed soft real-time applications. First, it describes how our Fault-tolerant Load-aware and Adaptive middlewaRe (FLARe) dynamically adjusts failover targets at runtime in response to system load fluctuations and resource availability. Second, it describes how FLARe's overload management strategy proactively enforces desired CPU utilization bounds by redirecting clients from overloaded processors. Third, it presents the design and implementation of FLARe's lightweight middleware architecture that manages failures and overloads transparently to clients. Finally, it presents experimental results on a distributed Linux testbed that demonstrate how FLARe adaptively maintains soft real-time performance for clients operating in the presence of failures and overloads with negligible runtime overhead.

An increasing number of distributed real-time applications are running on multicore platforms. However, existing real-time middleware (e.g., Real-Time CORBA) lacks adequate support for ensuring the timing constraints of soft real-time tasks on multicore platforms, and thus is dependent on (potentially inadequate) support from the underlying operating system. This paper makes three contributions to the state of the art in real-time system software for multicore platforms. First, it offers what is to our knowledge the first experimental analysis of real-time performance of vanilla Linux primitives on multicore platforms. Second, it presents MC-ORB, the first real-time object request broker (ORB) designed to address the nuances of multiprocessor (and especially multicore) platforms with a novel core-aware middleware thread architecture and allocation service for soft real-time tasks. Third, it evaluates MC-ORB's performance on a Linux multicore testbed, the results of which demonstrate its efficiency and effectiveness.

Existing off-line schedulability analysis for real-time systems can only handle periodic or sporadic tasks with known minimum inter-arrival times. Modeling sporadic tasks with fixed minimum inter-arrival times is a poor approximation for systems in which tasks arrive in bursts, but have longer intervals between the bursts. In such cases, schedulability analysis based on the existing sporadic task model is pessimistic and seriously overestimates the task's time demand. In this paper, we propose a generalized sporadic task model that characterizes arrival times more precisely than the traditional sporadic task model, and we develop a corresponding schedulability analysis that computes tighter bounds on worst-case response times. Experimental results show that when arrival time jitter increases, the new analysis more effectively guarantees schedulability of sporadic tasks.

Different distributed cyber-physical systems must handle a periodic and periodic events with diverse requirements. While existing real-time middleware such as Real-Time CORBA has shown promise as a platform for distributed systems with time constraints, it lacks flexible configuration mechanisms needed to manage end-to-end timing easily for a wide range of different cyber-physical systems with both aperiodic and periodic events. The primary contribution of this work is the design, implementation and performance evaluation of the first configurable component middleware services for admission control and load balancing of a periodic and periodic event handling in distributed cyber-physical systems. Empirical results demonstrate the need for, and the effectiveness of, our configurable component middleware approach in supporting different applications with a periodic and periodic events, and providing a flexible software platform for distributed cyber-physical systems with end-to-end timing constraints.

Modern embedded system designers face challenges of unprecedented scales, creating systems that integrate functionality spanning disparate scientific domains, with increasing computation demands and ever-stricter power requirements. Meeting the constraints of these systems requires practical design flows that reduce development time without sacrificing design efficiency. Novel design description methodologies coupled with automated and semi-automated synthesis paths greatly accelerate the design of modern hardware systems. In the software space, however, synthesis methods are far from producing co-designs with the necessary efficiency. This is particularly evident at the hardware/software boundary, where the tight coupling of low-level firmware routines and hardware protocols require designers to have deep design knowledge in both domains. To address this issue, we propose a latency-insensitive software execution model that allows direct connection to elastic hardware control topologies.

Open soft real-time systems, such as mobile robots, experience unpredictable interactions with their environments and yet must respond both adaptively and with reasonable temporal predictability. New scheduling approaches are needed to address the demands of such systems, in which many of the assumptions made by traditional real-time scheduling theory do not hold. In previous work we established foundations for a scheduling policy design and verification approach for open soft real-time systems, that can use different decision models, e.g., a Markov decision process (MDP), to capture the nuances of their scheduling semantics.However, several important refinements to the preliminary techniques developed in that work are needed to make the approach applicable in practice. This paper makes three main contributions to the state of the art in scheduling open soft real-time systems: (1) it defines a novel representation of the scheduling state space that is both more compact and more expressive than the model defined in our previous work; (2) it exploits regular structure of that representation to allow efficient verification of properties involving both discrete and continuous system state variables under specific scheduling policies; and (3) it removes the unnecessary use of a time horizon in our previous approach, thus allowing the more precise specification and enforcement of a wider range of scheduling policies for open soft real-time systems.

Real-time image transmission is crucial to an emerging class of distributed embedded systems operating in open network environments. Examples include avionics mission re-planning over Link-16, security systems based on wireless camera networks, and online collaboration using camera phones. Meeting image transmission deadlines is a key challenge in such systems due to unpredictable network conditions. In this paper, we present CAMRIT, a Control-based Adaptive Middleware framework for Real-time Image Transmission in distributed real-time embedded systems. CAMRIT features a distributed feedback control loop that meets image transmission deadlines by dynamically adjusting the quality of image tiles. We derive an analytic model that captures the dynamics of a distributed middleware architecture. A control theoretic methodology is applied to systematically design a control algorithm with analytic assurance of system stability and performance, despite uncertainties in network bandwidth. Experimental results demonstrate that CAMRIT can provide robust real-time guarantees for a representative application scenario.

Many mission-critical distributed real-time applications must handle aperiodic tasks with end-to-end deadlines. However, existing middleware (e.g., RT-CORBA) lacks schedulability analysis and run-time enforcement mechanisms needed to give online real-time guarantees for aperiodic tasks. The primary contribution of this work is the design, implementation, and performance evaluation of the first realization of deferrable server and admission control mechanisms for aperiodic tasks in middleware. Empirical results on a KURT-Linux testbed demonstrate the efficiency and effectiveness of our deferrable server and admission control mechanisms in TAO's federated event service.

The decoupled nature of computing in mobile ad hoc networks (MANETs) can result in disconnections at inopportune times during an interaction between a pair of hosts. We introduce the notion of a priori selection of partner hosts to reduce the likelihood of disconnection during such interactions. An application may specify the times when and the physical locations where it requires interactions with peer applications on partner hosts. A knowledge base of the physical motion profiles of various hosts maintained on each mobile host is used to select partner hosts that are co-located with the reference host at the required time and are least likely to disconnect. In this paper, we present a formal model for such knowledge management, along with an algorithm used to determine suitable partner hosts. We also provide details of our implementation of partner selection, which has been used in the context of a service-oriented computing middleware for MANETs, developed previously by our group. Finally, we present simulation results of our approach.

As real-time and embedded systems become increasingly large and complex, the traditional strictly static approach to memory management begins to prove untenable. The challenge is to provide a dynamic memory model that guarantees tight and bounded time and space requirements without overburdening the developer with memory concerns. This paper provides an analysis of memory management approaches in order to characterise the tradeoffs across three semantic domains: space, time and a characterisation of memory usage information such as the lifetime of objects. A unified approach to distinguishing the merits of each memory model highlights the relationship across these three domains, thereby identifying the class of applications that benefit from targeting a particular model. Crucially, an initial investigation of this relationship identifies the direction future research must take in order to address the requirements of the next generation of complex embedded systems. Some initial suggestions are made in this regard and the memory model proposed in the real-time specification for Java is evaluated in this context

Developing distributed real-time and embedded (DRE) systems in which multiple quality-of-service (QoS) dimensions must be managed is an important and challenging problem. This paper makes three contributions to research on multi-dimensional QoS for DRE systems. First, it describes the design and implementation of a fault-tolerant real-time CORBA event service for the ACE ORB (TAO). Second, it describes our enhancements and extensions to features in TAO, to integrate real-time and fault tolerance properties. Third, it presents an empirical evaluation of our approach. Our results show that with some refinements, real-time and fault-tolerance features can be integrated effectively and efficiently in a CORBA event service.

We present a deadlock avoidance algorithm for distributed systems that guarantees liveness. Deadlock avoidance in distributed systems is a hard problem and general solutions are considered impractical due to the high communication overhead. In previous work, however, we showed that practical solutions exist when all possible sequences of resource requests are known a priori in the form of call graphs; in this case protocols can be constructed that perform safe resource allocation based on local data only, that is, no communication between components is required. While avoiding deadlock, those protocols, however, did not avoid starvation: they guaranteed that some process could always make progress, but did not guarantee that every individual process would always eventually terminate. In this paper we present a resource allocation mechanism that avoids deadlock and guarantees absence of starvation, without undue loss of concurrency. The only assumption we make is that the local scheduler is fair. We prove the correctness of the algorithm and show how it can be implemented efficiently.

Distributed real-time and embedded (DRE) systems have stringent constraints on timeliness and other properties whose assurance is crucial to correct system behavior. Formal tools and techniques play a key role in verifying and validating system properties. However, many DRE systems are built using middleware frameworks that have grown increasingly complex to address the diverse requirements of a wide range of applications. How to apply formal tools and techniques effectively to these systems, given the range of middleware configuration options available, is therefore an important research problem.This paper makes three contributions to research on formal verification and validation of middleware-based DRE systems. First, it presents a reusable library of formal models we have developed to capture essential timing and concurrency semantics of foundational middleware building blocks provided by the ACE framework. Second, it describes domain-specific techniques to reduce the cost of checking those models while ensuring they remain valid with respect to the semantics of the middleware itself. Third, it presents a verification and validation case study involving a gateway service, using our models.

Thread allocation is an important problem in distributed real-time and embedded (DRE) systems. A thread allocation policy that is too liberal may cause deadlock, while a policy that is too conservative limits potential parallelism, thus wasting resources. However, achieving (globally) optimal thread utilization, while avoiding deadlock, has been proven impractical in distributed systems: it requires too much communication between components. In previous work we showed that efficient local thread allocation protocols are possible if the protocols are parameterized by global static data, in particular by an annotation of the global call graph of all tasks to be performed by the system. We proved that absence of cyclic dependencies in this annotation guarantees absence of deadlock. In this paper we present an algorithm to compute optimal annotations, that is annotations that maximize parallelism while satisfying the condition of acyclicity. Moreover, we show that the condition of acyclicity is in fact tight and exhibits a rather surprising anomaly: if a cyclic dependency is present in the annotation of the call graph and a certain minimum number of threads is provided, deadlock is reachable. Thus, in the presence of cyclic dependencies, increasing the number of threads may introduce the possibility of deadlock in an originally deadlock free system.

This paper describes a scheduling abstraction, called group scheduling, that emphasizes fine grain configurability of system scheduling semantics. The group scheduling approach described and evaluated in this paper provides an extremely flexible framework within which a wide range of scheduling semantics can be expressed, including familiar priority and deadline based algorithms. The paper describes both OS and middleware based implementations of the framework, and shows through evaluation that they can produce the same behavior for a nontrivial set of application computations. We also show that the framework can support application-specific scheduling constraints such as progress, to improve performance of applications whose scheduling semantics do not match those of traditional scheduling algorithms.

Integration of middleware scheduling and resource management services enables open distributed real-time embedded (DRE) applications to meet end-to-end quality of service (QoS) requirements in highly variable operating environments. This paper describes our research on integrating CORBA scheduling and resource management services, and presents experiments we conducted to validate and quantify the benefits of this integration. Our experimental results show that integrating distributed scheduling and resource management in middleware for open DRE systems can offer significant improvements in predictability. Specifically, integrating our stand-alone resource management service with a previously unmanaged experimental baseline application reduced the ratio of missed deadlines from 26% to 10%, and the same application performed even better under the control of integrated scheduling and resource management services, with a missed deadline ratio of only 1%.

No one middleware communication model completely solves the problem of ensuring schedulability in every DRE system. Furthermore, there have been few studies to date of the trade-offs between alternative middleware communication models under different application scenarios. This paper makes three contributions to the state of the art in middleware for distributed real-time and embedded systems. First, it describes what we believe is the first example of integrating release guards directly with CORBA distributable threads to ensure appropriate release times for sub-tasks along an end-to-end computation. Second, it presents empirical results in which release guards improve schedulability of distributable threads compared to a greedy protocol in which arriving tasks simply begin to run as soon as they can. Third, we offer the first empirical comparisons of the distributable thread and event channel models under three different communication scenarios and then using a randomized workload.

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degree of coverage and connectivity in order to support different applications and environments with diverse requirements. This article presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways. (1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. (2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity within a unified framework; in sharp contrast to several existing approaches that address the two problems in isolation. (3) We integrate CCP with SPAN to provide both coverage and connectivity guarantees. (4) We propose a probabilistic coverage model and extend CCP to provide probabilistic coverage guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations through both geometric analysis and extensive simulations.

Summary form only given. Previous system scheduling approaches have focused primarily on system-level abstractions for scheduling decision functions and the mechanisms used to implement them. We introduce a new abstraction called group scheduling that focuses primarily on the progress of application-level computations and on organizing system-level scheduling abstractions to ensure that progress. We make three contributions to system scheduling research. First, it defines a model for group scheduling that augments and complements hierarchical scheduling models. Second, it describes how a computation's progress semantics can be mapped to scheduling mechanisms at the operating system and middleware levels. Third, it presents preliminary empirical studies of the performance of group scheduling in a realistic system environment.

Distributed real-time and embedded (DRE) systems in which application requirements and environmental conditions may not be known a priori-or which may vary at run-time-can benefit from an adaptive approach to management of quality-of-service (QoS) to meet key constraints, such as end-to-end timeliness. Moreover, coordinated management of multiple QoS capabilities across multiple layers of applications and their supporting middleware can help to achieve necessary assurances of meeting these constraints. We offer two contributions to the study of adaptive DRE computing systems: (1) a case study of our integration of multiple middleware QoS management technologies to manage quality and timeliness of imagery adoptively within a representative DRE avionics system and (2) empirical results and analysis of the impact of that integration on key tradeoffs between timeliness and image quality in that system.

Many distributed real-time and embedded (DRE) applications require a scalable event-driven communication model that decouples suppliers from consumers and simultaneously supports advanced quality of service (QoS) properties and event filtering mechanisms. The CORBA notification service provides publisher/subscriber capabilities designed to support scalable event-driven communication by routing events efficiently between suppliers and consumers, enforcing QoS properties (such as reliability, priority, ordering, and timeliness), and filtering events at multiple points in a distributed system. The standard CORBA notification service is insufficient, however, to enforce predictable communication needed by DRE applications and does not leverage real-time CORBA capabilities, such as end-to-end priority assignment or scheduling services. We make three contributions to the study of scalable real-time notification services for DRE applications. First, we describe the requirements of the OMG request for proposals (RFP) on real-time notification, which seeks solutions to the problem of enforcing real-time properties by enhancing the standard CORBA notification service. Second, we explain how we have addressed key design challenges faced when implementing a real-time notification service for TAO, which is our CORBA-compliant real-time object request broker (ORB). We discuss how we integrate real-time CORBA features (such as thread pools, thread lanes, and priority models) to provide real-time event communication. Finally, we analyze the results of empirical benchmarks of the performance and predictability of TAO's real-time notification service. These results show that the static real-time assurances provided by real-time CORBA are maintained within the more flexible context of TAO's real-time notification service.

In an emerging class of open distributed real-time and embedded (DRE) systems with stringent but dynamic QoS requirements, there is a need to propagate QoS parameters and enforce task QoS requirements across multiple endsystems in a way that is simultaneously efficient and adaptable. The object management group's (OMG) real-time CORBA 2.0 specification (RTC2) defines a dynamic scheduling framework for propagating and enforcing QoS parameters dynamically in standard CORBA middleware. We make two contributions to research on middleware for open DRE systems. First, it describes the design and capabilities of the RTC2 dynamic scheduling framework provided by TAO, which is our open-source CORBA standards-based object request broker (ORB). Second, it describes and summarize the results of empirical studies we have conducted to validate our RTC2 framework in the context of open DRE systems. The results of those experiments show that a range of policies for adaptive scheduling and management of distributable threads can be enforced efficiently in standard middleware for open DRE systems.

General purpose middleware has been shown to be effective off-the-shelf, in meeting diverse functional requirements for a wide range of distributed systems. However, middleware customization is necessary for many networked embedded systems because of the resource constraints in the networked nodes. We demonstrate that reduced middleware footprint can be achieved while maintaining real-time properties of applications running on such systems. We also give evidence that empirical measurement using a representative application is crucial to guide (1) selection of feature subsets from general purpose middleware and (2) trade-offs among different dimensions of design metrics including real-time, footprint, and portability.

Real-time image transmission is crucial to an emerging class of distributed embedded systems operating in open network environments. Examples include avionics mission re-planning over Link-16, security systems based on wireless camera networks, and online collaboration using camera phones. Meeting image transmission deadlines is a key challenge in such systems due to unpredictable network conditions. In this paper, we present CAMRIT, a control-based adaptive middleware framework for real-time image transmission in distributed real-time embedded systems. CAMRIT features a distributed feedback control loop that meets image transmission deadlines by dynamically adjusting the quality of image tiles. We derive an analytic model that captures the dynamics of a distributed middleware architecture. A control theoretic methodology is applied to systematically design a control algorithm with analytic assurance of system stability and performance, despite uncertainties in network bandwidth. Experimental results demonstrate that CAMRIT can provide robust real-time guarantees for a representative application scenario.

QoS-enabled component middleware solutions can help reduce the programming complexity of configuring real-time aspects, such as priorities and rates of invocation. However, few empirical studies have been conducted to guide distributed real-time and embedded (DRE) system developers in choosing among alternative configuration mechanisms and performance optimization techniques in practice. This paper makes three contributions to research on QoS-enabled component middleware for DRE systems in the context of the component-integrated ACE ORB (CIAO). First, it describes the design of CIAO's static component configuration mechanisms, which enhance configurability by avoiding features that are not supported by key real-time platforms, while reducing run-time overhead and footprint. Second, it compares the performance of dynamic and static configuration mechanisms in CIAO to help guide the selection of suitable configuration mechanisms based on specific requirements of each DRE system. Third, it presents an empirical comparison of CIAO's static configuration mechanisms to the static configuration mechanisms in Boeing's PRISM avionics component middleware solution.

An effective approach for energy conservation in wireless sensor networks is scheduling sleep intervals for extraneous nodes, while the remaining nodes stay active to provide continuous service. For the sensor network to operate successfully, the active nodes must maintain both sensing coverage and network connectivity. Furthermore, the network must be able to configure itself to any feasible degrees of coverage and connectivity in order to support different applications and environments with diverse requirements. This paper presents the design and analysis of novel protocols that can dynamically configure a network to achieve guaranteed degrees of coverage and connectivity. This work differs from existing connectivity or coverage maintenance protocols in several key ways: 1) We present a Coverage Configuration Protocol (CCP) that can provide different degrees of coverage requested by applications. This flexibility allows the network to self-configure for a wide range of applications and (possibly dynamic) environments. 2) We provide a geometric analysis of the relationship between coverage and connectivity. This analysis yields key insights for treating coverage and connectivity in a unified framework: this is in sharp contrast to several existing approaches that address the two problems in isolation. 3) Finally, we integrate CCP with SPAN to provide both coverage and connectivity guarantees. We demonstrate the capability of our protocols to provide guaranteed coverage and connectivity configurations, through both geometric analysis and extensive simulations.

Increasingly complex requirements, coupled with tighter economic and organizational constraints, are making it hard to build complex distributed real-time embedded (DRE) systems entirely from scratch. Therefore, the proportion of DRE systems made up of commercial-off-the-shelf (COTS) hardware and software is increasing significantly. There are relatively few systematic empirical studies, however, that illustrate how suitable COTS-based hardware and software have become for mission-critical DRE systems. This paper provides the following contributions to the study of real-time quality-of-service (QoS) assurance and performance in COTS-based DRE systems: it presents evidence that flexible configuration of COTS middleware mechanisms, and the operating system (OS) settings they use, allows DRE systems to meet critical QoS requirements over a wider range of load and jitter conditions than statically configured systems; it shows that in addition to making critical QoS assurances, noncritical QoS performance can be improved through flexible support for alternative scheduling strategies; and it presents an empirical study of three canonical scheduling strategies; specifically the conditions that predict success of a strategy for a production-quality DRE avionics mission computing system. Our results show that applying a flexible scheduling framework to COTS hardware, OSs, and middleware improves real-time QoS assurance and performance for mission-critical DRE systems.

The Quality Objects (QuO) middleware is a set of extensions to standard distributed object computing middleware that is used to control and adapt the quality of service in a number of distributed application environments, from wide-area to embedded distributed applications. This paper compares and contrasts the characteristics of key use cases and the variations in QuO implementations that have emerged to support them. We present these variations in the context of several actual applications being developed using the QuO middleware.