Search

Reservation-based operating systems provide applications with guaranteed and timely access to system resources. One of their chief benefits is temporal isolation, which prevents the timing mis-behavior of one task from interfering with other tasks. Such a benefit is appealing enough that many systems [2, 8] desire to recursively apply this reservation model to each of their components. This recursive application provides flexible load isolation among applications, users and other high-level resource management entities such as aggregated flows for network bandwith. The hierarchical reservation study can be applied to hierarchical schedulers [5, 6], that support heterogenous scheduling algorithms. We propose and analyze a hierarchical reservation model in the context of fixed-priority scheduling, rate-monotonic and deadline-monotonic, as used in systems such as the Resource Kernel [11]. Detailed schedulability analyses under both deferrable-server and sporadic-server replenishment schemes, including exact completion time tests under hierarchical deadline-monotonic schedulers, are presented. We also derive the least upper scheduling bound for hierarchicalrate-monotonic schedulers. Finally, we describe how to apply multi-reserve PCP [4 ], an extension of the Priority Ceiling Protocol for reservation-based systems, to allow tasks to share non-preemptable resources across the hierarchy.

The resource-sharing problem in priority-driven realtime systems has been studied at length, with the result that some effective and practical solutions are available for both fixed-priority and dynamic-priority systems. In recent years, real-time operating systems have begun to support the resource reservation paradigm, providing a "temporal isolation" abstraction. However the problem of sharing logical resources across reserved applications has not been extensively studied. In this paper we consider both the theoretical and practical implications of such resource-sharing in reservation-based systems. Moreover we provide some experimental results from the implementation of our proposed schemes in Linux/RK, a "resource kernel" that supports reservations.

In many devices, wireless network interfaces consume upwards of 30% of scarce portable system energy. Extending the system lifetime by minimizing communication power consumption has therefore become a priority. Conventional energy management techniques focus independently on minimizing the fixed energy consumption of the transceiver circuit or on scalable transmission control. Fixed energy consumption is reduced by maximizing the transceiver shutdown interval. In contrast, variable transmission rate, coding and power can be leveraged to minimize energy costs. These two energy management approaches present a tradeoff in minimizing the overall system energy. For example, variable energy costs are minimized by transmitting at a lower modulation rate and transmission power, but this also shortens the sleep duration thereby increasing fixed energy consumption. We present a methodology for energy-efficient resource allocation across the physical layer, communications layer and link layer. Our methodology is aimed at providing QoS for multiple users with bursty MPEG-4 video over a time-varying channel. We evaluate our scheme by exploiting control knobs of actual RF components over a modified IEEE 802.11 MAC. Our results indicate that the system lifetime is increased by a factor of 2 to 5 compared to the gains of conventional techniques.

Energy-efficiency is imperative to enable the deployment of sensor networks with satisfactory lifetime. Conventional power management in radio communication primarily focuses independently on the physical layer, medium access control (MAC) or routing and approaches differ depending on the levels of abstraction. At the physical layer, the fundamental trade-off that exists between transmission rate and energy is exploited. This leads to the lazy scheduling approach, which consists of transmitting with the lowest power over the longest feasible duration. At MAC level, power reduction techniques tend to keep the transmission as short as possible to maximize the radio's power-off interval. Those two approaches seem conflicting and it is not clear which one is the most appropriate for a given network scenario. In this paper, we propose a transmission strategy that combines both techniques optimally. We present a cross-layer solution to determine the best transmission strategy taking into account the transceiver power consumption characteristics, the system load and the scenario constraints. Based on this approach, we derive a low complexity, on-line scheduling algorithm that can be used to optimally organize the forwarding of the sensed information from cluster heads to the data sink (uplink) in a hierarchical sensor network. Results, considering Coded Frequency Shift Keying (FSK) modulation, show that depending on the scenario, a 50% extra power reduction is achieved in a realistic uplink data gathering context, compared to the case where only transmission rate scaling or shutdown is considered.

The MEAD system that we are developing employs a synergistic combination of a reactive and a proactive fault-tolerance approach in order to address unanticipated events and hazards in real-time, fault-tolerant distributed systems. The reactive fault-tolerance approach involves active monitoring of the system to adapt the provided QoS and to allocate resources based on current conditions in the system. The proactive approach involves monitoring both the distributed applications and the network to seek pre-cursors to imminent failures, and then to trigger fault-recovery mechanisms in advance of the occurrence of the failure. The underlying ideas of the MEAD system have demonstrated initial promise through our enhanced capabilities to handle failures and unanticipated events, and to reduce jitter under faulty conditions.

In this paper, we present an analytical tool called RETINA for analyzing real-time constraints in complex networks with stochastic traffic. RETINA is based on a statistical method called real-time queueing theory and can predict the fraction of late tasks in networks of queues given traffic conditions and queue protocol specifications. Upon submitting a profile of the network structure and data flow descriptions, the user is able to query certain performance metrics. Currently RETINA supports two types of real-time scheduling algorithms (EDF and FIFO) and three types of performance queries: the deadline miss rate of a designated flow, the minimum feasible deadline for a particular flow, and whether all QoS requirements of all flows met when a new flow is added. Simulation results show excellent agreement with the results predicted by our tool. RETINA has made it possible to analyze larger and more realistic networks and can be used to address network design tradeoffs. This use of RETINA to identify and quantify network bottlenecks is presented in the paper.

An onboard vehicle-to-vehicle multi-hop wireless networking system has been developed to test the realworld performance of telematics applications. The system targets emergency and safety messaging, traffic updates, audio/video streaming and commercial announcements. The test-bed includes a Differential GPS receiver, an IEEE 802.11a radio card modified to emulate the DSRC standard, a 1xRTT cellular-data connection, an onboard computer and audio-visual equipment. Vehicles exchange data directly or via intermediate vehicles using a multi-hop routing protocol. The focus of the test-bed is to (a) evaluate the feasibility of high-speed inter-vehicular networking, (b) characterize 5.8GHz signal propagation within a dynamic mobile ad hoc environment, and (c) develop routing protocols for highly mobile networks. The test-bed has been deployed across five vehicles and tested over 400 miles on the road.

Dynamic real-time systems such as phased-array radars must manage multiple resources, satisfy energy constraints and make frequent on-line scheduling decisions. These systems are hard to manage because task and system requirements change rapidly (e.g. in radar systems, the targets/tasks in the sky are moving continuously) and must satisfy a multitude of constraints. Their highly dynamic nature and stringent time constraints lead to complex cross-layer interactions in these systems. Therefore, the design of such systems has long been a conservative and/or unpredictable mixture of pre-computed schedules, pessimistic resource allocations, cautious energy usage and operator intuition. In this paper, we present an integrated approach that simultaneously maximizes overall system utility, performs task scheduling and satisfies multi-resource constraints. Using a phased-array radar system, we show that our approach can reconfigure settings of 100 tracks at every 0.7 sec in real-time, and performs within 0.1% of the achievable optimal solution.

Many existing and emerging network applications such as voice-over-IP, videoconferencing and online gaming have end-to-end timing requirements. Despite the real-time demands of these applications, they are usually deployed on best-effort networks such as the Internet. This results in unpredictable and often unsatisfactory performance. In this paper we propose a simple and novel task (or packet) scheduling algorithm Diff-EDF (differentiated earliest deadline first) which can meet the real-time needs of these applications while continuing to provide best effort service to nonreal time traffic. In our system we consider each flow as having stochastic traffic characteristics, a stochastic deadline and a maximum allowable miss rate. The Diff-EDF service meets the flow miss rate requirements through the combination of an admission control test and a scheduling algorithm similar to EDF (earliest deadline first). However, unlike standard EDF scheduling each flow receives a deadline bias based on the flow's miss rate requirement. Applying this bias allows the miss rate to be controlled on a flow-by-flow basis. Both the admission control test and the bias selection algorithms can be computed as a linear function of the flow traffic parameters and the logarithms of the miss rate requirements resulting in an efficient implementation. In this paper, we presented the proposed system structure, protocols, algorithms, analysis and experiments. Experiments with randomly generated and real-life data closely match values predicted by the theory.

In this paper, we study the problem of allocating end-to-end bandwidth to each of multiple traffic flows in a large-scale network. We adopt the QoS-based resource allocation model (Q-RAM) (K-S. Lui et al., 2000), whereby each flow derives an utility based on the amount of its allocated bandwidth. Our goal therefore is to maximize the total utility derived across all network flows. The NP-hard nature of the resource allocation problem is compounded by the need to select an appropriate path between each source-destination pair. We propose a hierarchical decomposition scheme that allows the resource allocation problem to be solved in a decentralized and scalable fashion. The hierarchy we use is based on a (natural) partitioning of the network into subnets, with resource allocation decisions made on a subnet-by-subnet basis. A novel distributed transaction scheme is used to ensure that resource allocations are consistent across all the subnets traversed by each flow. We provide both analytical and experimental evidence to show that our scheme is very scalable and yet does not sacrifice the quality of the allocations.

This paper presents operating system abstractions for managing physical memory and paging that can be used to improve both timing predictability and the run-time performance of soft real-time tasks. First, we propose a memory reservation scheme which allows any application to reserve a portion of the total system memory pages for its exclusive use. If the application's memory needs exceed its memory reservation, its pages are swapped within its own reservation, thereby containing the performance effects of its memory access profile to its reservation. Swap space for the application is also reserved. A memory reservation can be shared by multiple threads/applications, and reservations can be used hierarchically, with children using only a portion of their parent's reservation. Next, we propose a novel methodology to determine reservation sizes for an embedded task-set that optimizes the overall performance of the system. We also show how an application can leverage customized predictable page-replacement policies to minimize performance penalties from avoidable page faults ("capacity misses").

We present scalable QoS optimization algorithms for allocating resources to tasks in a multi-processor environment. Given a set of tasks, each of which is capable of running at one of several different QoS levels, the algorithms can select a QoS operating point, the number of replicas for fault-tolerance and the processors on which to run the replicas so as to maximize overall system QoS. The algorithms are extensions of Q-RAM (QoS-based Resource Allocation Model) [5] and fix two deficiencies with the basic algorithm. The first is that the existing algorithm is weak in making resource trade-off decisions such as to which processor to map a task. The second was that it was not scalable to very large numbers of resources such as in a large multi-processor system. In this paper we present two new algorithms which significantly enhance the ability of Q-RAM to make resource tradeoff decisions. We also introduce a hierarchical decomposition scheme which enables QoS optimization to be performed on problems with thousands of resources and thousands of tasks.

In CMOS circuits, power consumption is proportional to the product of the frequency and the square of the supply voltage. Hence, any reductions in the operating frequency of the processor and its supply voltage can lead to significant savings in energy consumption (and heat dissipation) but cause longer execution times. The application of dynamic voltage scaling (DVS) techniques to real-time systems must therefore attempt to minimize energy while guaranteeing the schedulability of the real-time tasks. In this paper we study the effect of limited number of operating frequencies on the performance of voltage-scaling algorithms. The optimal frequency grid which minimizes the effect of discrete operating frequencies is also derived We then propose four alternative voltage-scaling schemes, Sys-Clock, PM-Clock, Opt-Clock and DPM-Clock. Each scheme is suitable for different hardware configuration which may have high or low voltage-scaling overhead and different taskset characteristics. We have implemented our voltage-scaling schemes on CMU's real-time OS, Linux/RK, on the 3700 series Compaq iPAQ and a 733MHz XScale BRH board modified to support voltage-scaling.

Summary form only given. We present an extension to our QoS optimization algorithm, Q-RAM, that can improve optimization time by several orders of magnitude when managing highly configurable tasks. A highly configurable task is one with a large number of QoS dimensions and/or a large number of quality levels on those dimensions. For example, an application that has ten QoS dimensions with ten quality levels each will have 10/sup 10/ setpoints, or ways in which it can be configured. While the existing Q-RAM algorithm has been shown to be a very effective resource management tool, it must still explicitly perform computations on all of the setpoints for each task. For tasks with 10/sup 10/ setpoints or more, this is clearly impractical. The key idea presented here is a new approximation algorithm for the concave majorant step in Q-RAM. By using this algorithm in a filtering step, the best performing subset of the setpoints can be quickly found without explicitly examining all of the setpoints. The idea is validated using a phased array radar system as an example application.

For bursty traffic with a large peak-to-average ratio and a stochastic channel, is it possible to minimize the response time of every flow while maximizing the effective channel utilization and maintain fairness? This is the question we address in this paper. In wireless networks with a single shared channel, channel arbitration is a core issue for flows with throughput and timeliness requirements on the uplink and peer-to-peer links where the instantaneous demand is not known. This paper presents a link layer frame scheduling algorithm for delay-sensitive variable bit rate traffic, such as high-rate multimedia (MPEG-4), over a wireless channel. We evaluate our scheduling algorithm over two Medium Access Control (MAC) architectures and compare it to four scheduling strategies that cover a range of classes: TDMA, proportional share algorithms, real-time scheduling algorithms, and size-based scheduling algorithms. Detailed simulation results, with full-length MPEG-4 movie traces over a fading wireless channel, show that Fair-Shortest Remaining Processing Time (Fair-SRPT) outperforms other algorithms in terms of QoS performance, channel utilization efficiency and response time under all utilization levels and channel error rates. Our Fair-SRPT scheme avoids the classical SRPT problems of preferring small jobs by using normalization to mean reservations. An attractive feature of the proposed approach is that it can be implemented with no modifications to the IEEE 802.11e and IEEE 802.15.3 high-rate personal area network standards.

The quantized earliest deadline first (Q-EDF) scheduling policy assumes a limited number of priority levels available to express task (or packet) deadlines. This situation arises in computer and communication systems in which priority levels must be expressed using a limited number of bits. The range of possible deadlines is partitioned into bins, and a task whose deadline lies within the range of a bin is assigned a quantized deadline equal to the left endpoint of the bin. We assume soft real-time tasks arrive according to a renewal process, have random service requirements, and have random deadlines drawn from a probability distribution. Using real-time queueing theory, a general method for computing the long run fraction of tasks that miss their actual deadlines (or their quantized deadlines) is presented. Results are given for uniform deadline distributions, and the optimal bin partitioning is determined for this distribution. The theoretical results show excellent agreement with simulation results. Finally, assuming only the min, mean, and max task deadlines are specified, we determine the worst-case deadline distribution given any specified priority bin choice, then optimize the priority bin choice to minimize the worst-case lateness relative to EDF. For this Q-EDF partition, we determine the number of bins needed to achieve a given performance relative to EDF. We show that for practical cases with soft deadlines, 3 bits are sufficient to achieve nearly the same performance with Q-EDF as with pure EDF.

A QoS-aware real-time operating system must schedule multiple tasks which have different timing constraints and which access various resources including the CPU, disk and network. These resources, however, are not independent of one another. For example, resources like network bandwidth and disk bandwidth are available on a single node but must be managed by their host OS on the CPU by means of interrupt handlers, device drivers, file-systems and/or protocol services. Hence, in order to obtain guaranteed completion times, an application must therefore obtain both user-mode time on the CPU along with sufficient OS-level time for the network and disk subsystems. In this paper, we investigate the co-scheduling of CPU cycles and network bandwidth. Specifically, we study the problem of obtaining pre-specified network bandwidth received by applications from the external network. Our solution endows (1) direct control over the flow of network packets into the system based on the requirements of specific applications, (2)guaranteed and enforced processing time for the received packets,(3)precise accounting of those processing times, and (4)elimination of scheduling anomalies. We describe and evaluate our system design and implementation in Linux/RK, a QoS-aware real-time version of Linux. We also compare this approach with a commercial implementation we did in TimeSys Linux.

Obtaining simultaneous and timely access to multiple resources is known to be an NP-complete problem. Complete resource decoupling is, therefore, often used for managing end-to-end delays in distributed real-time system where each processor is scheduled independent of the others. This decoupling approach unfortunately fails when multiple resources must be managed within a single node. Resources such as disk bandwidth and network bandwidth are available on a single node but must be managed by their host processor by means of device drivers, filesystem or protocol services. The host processor acting as a controlling resource, therefore, must play multiple roles. One, it is used by applications on that node. Two, it is used to control and manage other (time-shared) controlled resources including disk bandwidth and network bandwidth. These two roles, unfortunately can often be at odds with one another. In this paper we investigate the problem of co-scheduling controlling and controlled resources. We propose the use of a Cooperative Scheduling Server (CS S), which is a dedicated server that manages one specific controlled resource (like disk bandwidth, network bandwidth, inter-process communication, etc.) while using a controlling resource (like the processor). Two core ideas underlie our approach. First, a single (aperiodic) server is created on a controlling resource (such as a CPU) to handle all local requests for a controlled resource (such as disk bandwidth). This implies that conjuctive admission control must be carried out on both the controlling and controlled resources. Secondly, timing constraints at the application level are partitioned into multiple stages, each of which will be guaranteed to complete on a particular resource. RTFS is a real-time filesystem that provides disk bandwidth guarantees under light CPU loads. With a cooperative scheduling server (FS-CSS) for this disk-based filesystem, disk bandwidth guarantees can be obtained under both heavy CPU and disk workloads. We describe the design and implementation of FS-CSS for providing disk bandwidth guarantees. We conclude with a detailed performance evaluation of FS-CSS.

Portable RK is a portable implementation of a resource kernel, a resource-centric approach to build a real-time kernel that provides explicit timely, guaranteed, and enforced access by applications to system resources. Portable RK is designed to work with widely available operating systems with minimal changes. This facilitates experimentation in familiar software environments and helps the faster deployment of research results. Execution in resource kernels is directly based on OS-enforced resource reservation. As a result, an application can request the reservation of a certain amount of a resource, and the kernel can guarantee that the requested amount is available to that application in timely fashion. We describe the design and implementation of Portable RK called Linux/RK that resides within the Linux kernel. The evaluation results show that Portable RK in the form of Linux/RK gives direct control over timely resource utilization by applications and that its overhead costs are small enough to be negligible.

The problem of maximizing system utility by allocating a single finite resource to satisfy discrete Quality of Service (QoS) requirements of multiple applications along multiple QoS dimensions was studied previously. In this paper we consider the more complex problem of apportioning multiple finite resources to satisfy the QoS needs of multiple applications along multiple QoS dimensions. In other words, each application, such as video-conferencing, needs multiple resources to satisfy its QoS requirements. We evaluate and compare three strategies to solve this provably NP-hard problem. We show that dynamic programming and mixed integer programming compute optimal solutions to this problem but exhibit very long running times. We then adapt the mixed integer programming problem to yield near-optimal results with smaller running times. Finally, we present an approximation algorithm based on a local search technique that is less than 5% away from the optimal solution but which is more than two orders of magnitude faster. Perhaps more significantly, the local search technique turns out to be very scalable and robust as the number of resources required by each application increases.

The authors investigate the synchronization problem in the context of priority-driven preemptive scheduling on shared-memory multiprocessors. Unfortunately, a direct application of synchronization mechanisms such as the Ada rendezvous, semaphores, or monitors can lead to uncontrolled priority inversion: a high job being blocked by a lower priority job for an indefinite period of time. A task allocation scheme based on the generalized protocol is outlined. >

A run-time environment for monitoring distributed real-time systems is described. In particular, the authors focus on the problem of detecting violations of timing assertions in an environment in which the real-time tasks run on multiple processors, and timing constraints can be either interprocessor or intraprocessor constraints. Constraint violations are detected at the earliest possible time by deriving and checking intermediate constraints. If the violations must be detected as early as possible, then the problem of minimizing the number of messages to be exchanged between the processors becomes intractable. The authors characterize a subclass of timing constraints that occur commonly in distributed real-time systems and whose message requirements can be minimized. They also take into account the drift among the various processor clocks when detecting a violation of a timing assertion. Finally, an implementation of a distributed run-time monitor is described. >

The specification, design and implementation of a set of protocols to solve the processor group membership problem in distributed systems are presented. These group membership protocols were developed as part of a toolkit for building distributed/parallel applications on a cluster of workstations. The group membership service forms the lowest layer in the toolkit, and is the glue which unifies all other layers. The membership service supports three distinct protocols: weak, strong, and hybrid. These protocols differ significantly in the level of consistency and the number of messages exchanged in reaching agreement. The modular implementation of these protocols and the optimization techniques used to enhance their performance are described. >

The real time publisher/subscriber (RT P/S) communications model has been proposed as a flexible and powerful interprocess communication model for distributed real time systems (R. Rajkumar et al., 1995). It can also be used as the underlying framework for supporting building blocks such as extensible cells and replaceable software units far building evolvable distributed real time systems. However, for the model to be adopted in practice, it must tolerate processor failures and allow repaired processors to rejoin the system on a dynamic basis. Such processor failures and rejoins must also not hurt the efficiency of the steady state publication/subscription of messages by repetitive real time processes. We present extensions to the RT P/S model to support these capabilities. The solution is structured in two layers. First, an efficient processor membership protocol layer, based on F. Cristian's (1988; 1991) periodic broadcast membership protocol, detects processor failures and rejoins. It provides strong semantics and exhibits a finite delay in detecting processor failures. Secondly, idempotence properties, weak interleaving needs and the benign impact of node failures within the RT P/S information structure enable us to transfer consistent state to newly joining daemons and to manage changes to the information elegantly. The changes are orthogonal to the communication programming interface and also maintain very efficient and analyzable steady state real time execution paths. These protocols have been successfully built in the context of both feedback control and multimedia dissemination applications.

Fielded real-time systems including many defense systems, manufacturing plants and commercial aircraft avionics typically have long lifetimes ranging from a few years to even a few decades. Available technologies, system needs and customer goals change over this lifetime, and changes to a deployed system become very desirable. We argue that such evolution must and can be supported with new system abstractions, and that real-time systems designed with these abstractions can be evolved and incrementally tested. We present two possible run-time abstractions which can act as basic building blocks to construct "evolvable real-time systems". These building blocks can be used to evolve deployed systems in general and real-time systems in particular. First, the replaceable unit abstraction alloys an existing software module to be replaced online by another module with similar or enhanced functionality. Such replacement is transparent to the rest of the system. Secondly, the "cell" abstraction represents a protected module which cannot be harmed by other modules. Based on this notion is an "extensible cell", which allows a deployed module to be extended functionally without the fear of hurting its (fully certified) functionality even when the extensions can fail in unexpected ways. These two abstractions have been implemented in a real-time POSIX testbed used in the Simplex architecture and our findings are reported. Both abstractions are built on the Real-Time Publisher/Subscriber communication model with modifications necessitated by safe evolutionary requirements. We conclude that guaranteed enforcement of the semantics of these two building blocks can only be provided using operating system enforced resource reservation and communication rights.

Scheduling of many different kinds of activities takes place in distributed real time and multimedia systems. It includes scheduling of computations, window services, filesystem management, I/O services and communication protocol processing. We investigate the problem of scheduling communication protocol processing in real time systems. Communication protocol processing takes a relatively substantial amount of time and if not structured correctly, unpredictable priority inversion and undesirable timing behavior can result to applications communicating with other processors but are otherwise scheduled correctly. We describe the protocol processing architecture in the RT-Mach operating system, which allows the timing of protocol processing to be under strict application control. An added benefit is also obtained in the form of higher performance. This scheduling architecture is consistent with the: other RT-Mach scheduling mechanisms including fixed priority scheduling and processor reservation. The benefits of this protocol architecture are demonstrated both under synthetic workloads and in a realistic distributed videoconferencing system we have implemented in RT-Mach. End to end delays for both audio and video are as predicted even with other threads competing for the CPU and the network.

To keep systems affordable, there is a trend towards using open standard and commercial off the shelf (COTS) components in the development of dependable real-time systems. However, the use of COTS also introduces the vendor-driven upgrade problem that is relatively new to the dependable real-time computing community. If we refuse to accept the "new and improved" hardware and software components provided by vendors, then the hope that using COTS components will help keep the system modern via market forces will be dashed. If we decide to keep our systems modern, then we have to develop approaches that can introduce new hardware and software components into deployed systems safely, reliably and easily, in spite of the inevitable bugs in some of the new COTS components. In this paper, we give an informal review of the Simplex Architecture, which has been developed to support safe and reliable online upgrade of dependable computing systems. This paper is a revision of the SEI technical report: A Software Architecture for Dependable and Evolvable Industrial Computing Systems. CMU/SEI-95-TR-005.

Real-time systems manipulate data types with inherent timing constraints. Priority-based scheduling is a popular approach to build hard real-time systems, when the timing requirements, supported run-time configurations, and task sets are known a priori. Future real-time systems will need to support these hard real-time constraints but in addition (a) provide friendly user and programming interfaces with audio and video data types (b) be able to communicate with global networks and systems on demand, and (c) support critical command and control services despite potential risks introduced by such added flexibility and dynamics. We argue that temporal protection mechanisms can be as beneficial in these systems as virtual memory protection. The processor reservation mechanism that we have implemented in Real-Time Mach, for example, provides guaranteed timing behavior for critical activities. >

A priority-based synchronization protocol that explicitly uses shared-memory primitives is defined and analyzed. A solution that has been proposed for bounding and minimizing synchronization delays in real-time systems is briefly reviewed. The waiting times introduced by synchronization requirements in multiple-processor environments are identified, and a set of goals for priority-based multiprocessor synchronization protocols is derived. The underlying priority consideration for a shared memory synchronization protocol are studied and priority assignments to be used by the protocol are derived. >

We investigate filesystem support for continuous media on the Java language. We describe a prototype implementation on a Real-Time Java Server, developed as an application level server on the Real-Time Mach microkernel environment. The Java virtual machine has been extended to support filesystem bandwidth reservation facilities existing on Real-Time Mach. Such facilities allow continuous media applications to specify their disk bandwidth usage requirements by creating a disk bandwidth reservation. The operating system, upon acceptance of the requests, internally enforces and guarantees such a share of the disk bandwidth for every active reservation. We present a performance evaluation, including both a synthetic application and real multimedia application based on a QuickTime video player which make use of real time Java threads and filesystem bandwidth reservation facilities. Our experiments conclude that the proposed filesystem extensions to the Java language are suitable for continuous media application requirements.

The authors focus on two practical considerations that arise in the design of a real-time file system. Firstly, disk bandwidth management should be dynamic, which in turn would allow a QoS manager to dynamically reallocate disk bandwidth to running applications based on their changing needs. Secondly, real-time access to file system data structures should be deterministic, in order to avoid unexpected latencies when accessing files from disk. These issues have implications to the design of the file system and to its schedulability analysis. They address both these problems and present an implementation in RTFS (Real-Time Filesystem Server), a real-time file system supporting disk bandwidth reservation running on top of the Real-Time Mach microkernel. Finally, quantitative comparisons of actual achieved file system bandwidth and response times are used to validate the approach.

Quality of service (QoS) has been receiving wide attention in many research communities including networking, multimedia systems, real-time systems and distributed systems. In large distributed systems such as those used in defense systems, on-demand service and inter-networked systems, applications contending for system resources must satisfy timing, reliability and security constraints as well as application-specific quality requirements. Allocating sufficient resources to different applications in order to satisfy various requirements is a fundamental problem in these situations. A basic yet flexible model for performance-driven resource allocations can therefore be useful in making appropriate tradeoffs. We present an analytical model for QoS management in systems which must satisfy application needs along multiple dimensions such as timeliness, reliable delivery schemes, cryptographic security and data quality. We refer to this model as Q-RAM (QoS-based Resource Allocation Model). The model assumes a system with multiple concurrent applications, each of which can operate at different levels of quality based on the system resources available to it. The goal of the model is to be able to allocate resources to the various applications such that the overall system utility is maximized under the constraint that each application can meet its minimum needs. We identify resource profiles of applications which allow such decisions to be made efficiently and in real-time. We also identify application utility functions along different dimensions which are composable to form unique application requirement profiles. We use a video-conferencing system to illustrate the model.

Scalability of operating system kernels is important especially for real-time systems. The existing real-time kernels, however are made scalable by providing only basic functionalities; thus they often sacrifice the capability of hardware platforms. We introduce the separation of abstractions into software functionalities and hardware resources and their implementation by a scalable kernel architecture. The separation of abstractions into software and hardware are parts enables the provision of rich abstractions. Rich abstractions make it possible to exploit the capability of higher-end hardware platforms, and the separation makes it possible that their software functionalities are available also on low-end platforms. Our scalable kernel can scale up its implementation incrementally as the capability of hardware platforms scales up. In this paper, we describe the design and implementation of a scalable real-time kernel based on that architecture model, and show the experimental results of a prototype implementation.

Traditional real-time systems have largely avoided the use of disks due to their relative slow speeds and their unpredictability. However, many real-time applications including multimedia systems and real-time database applications benefit significantly from the use of disks to store and access real-time data. We investigate the problem of obtaining guaranteed timely access to files on a disk in a real-time system. Our study focuses on several aspects of this problem of providing a real-time filesystem. First, we consider the use of two real-time disk scheduling algorithms: earliest deadline scheduling and just-in-time scheduling, a variation of aperiodic servers for the disk. The latter algorithm is designed to improve disk throughput that can be hurt when a real-time scheduling algorithm such as EDF is applied directly. Admission control policies with practically acceptable properties of performance and usability are provided. Next, we design and implement a real-time filesystem on the RT-Mach microkernel-based system running a real-time shell. The new interface we develop is based on RT-Mach's resource reservation paradigm and provides guaranteed and timely access for multiple concurrent applications requiring disk bandwidth with different timing and volume requirements. Finally, we perform a detailed performance evaluation of the real-time filesystem including its raw performance. We show the following positive but rather surprising result: our real-time scheduling filesystem not only provides guaranteed and timely access but also does so at relatively high levels of throughput. Traditional disk scheduling algorithms offer completely unacceptable file access latencies for real-time applications and do so only at slightly higher throughput.

Real-time applications in dynamic systems such as multimedia systems may change their timing characteristics on the fly and may be created and terminated at any time. A priori resource allocation decisions may not hold throughout the lifetime of such applications because of changing user needs and interests. The ability to monitor and control system resources dynamically is fundamental to building flexible and dynamic multimedia systems. In this paper, we describe the mechanisms and tools we have built for monitoring and controlling operating system resource reserves in Real-Time Mach. The system supports a resource reservation abstraction called 'processor capacity reserves', and an interactive tool named 'rmon' uses these mechanisms to display the processor usage for each reserved activity in the system and to allow the user to change the processor reservation dynamically; it can also coordinate the reservation change requests with a separate quality-of-service manager which makes policy decisions regarding which requests are granted.

Resource management has become an important issue for computer systems as QoS-sensitive multimedia applications and hostile acts such as denial of service (DoS) attacks become widespread. Since applications access the processor, network and other subsystems, attacks on any of these subsystems can lead to undesirable behavior. To maintain system integrity even under such attacks, an unprivileged application must not be allowed to intentionally or unintentionally affect the progress of others. The authors present a first-class abstraction called Resource Control Lists (RCLs) to specify and enforce protection policies on time multiplexed resources, similar to access control on files. RCLs put access control on time multiplexed resources such as CPU time and network and disk bandwidth. RCLs are practical, flexible and provide several benefits. Protection policies specified by RCLs can be under administrator control, customized to a site, and can be dynamically adapted. We have built support for RCLs into Linux/RK, a real-time version of Linux that provides resource reservations where applications receive a promised amount of resources by making reservations. Quantitative measurements with limited forms of DoS attacks show that our new features provide flexible functionality while imposing acceptable overhead without modifying the applications. We also demonstrate that resources are protected even in the face of malicious activities. Finally, we show how RCLs can be used to deliver resource protection on multiple Web server configurations including the hosting of multiple logical sites by an ISP and preferential treatment of buyers on e-commerce sites.

Probabilistic bandwidth guarantees on variable bit-rate network flows offer significant improvements in throughput for only modest decreases in guarantee level. We present a probabilistic bandwidth reservation scheme for variable bit-rate flows called resource priority multiplexing (RPM). The RPM algorithm uses packet marking on edge routers and selective dropping on core routers to provide per-flow specification of probabilistic QoS with guarantees ranging from best-effort to hard reservation. RPM also supports multiple metrics for probabilistic level of service specification. All flow tables are managed only by the edge routers enhancing scalability of the approach. Unlike existing statistical multiplexing approaches, RPM uses a time-multiplexed priority tagging algorithm which provides higher control over flows guarantee levels. The algorithm has been implemented in a live system as part of the IP protocol stack and experimental results are presented.

Group communication is a widely studied paradigm which is often used in building real-time and fault-tolerant distributed systems. RTCAST is a real-time group communication protocol which has been designed to work with commercial, non-real-time, off-the-shelf hardware and operating systems, such as Solaris, Linux and Windows NT. RTCAST makes probabilistic real-time guarantees based on assumptions about the performance of the underlying system. Unfortunately, the high variability of the access to system resources that these operating systems provide may limit the predictability of the real-time guarantees provided by RTCAST. By taking advantage of a service that provides resource scheduling and reservation in these operating systems, both the hardness and timing granularity of RTCAST's real-time services can be greatly improved. This paper describes an implementation of RTCAST which makes use of the Resource Kernel to provide highly predictable, real-time communication guarantees.

The authors present Chocolate, a reservation based real time Java run-time environment that runs on Windows NT. We first present a brief overview of the emerging real time Java standard and the Resource Kernel (RK) approach to providing timely, guaranteed and enforced access to system resources. Chocolate is a real time Java Virtual Machine that interfaces the real time Java programming language with the abstractions of a resource kernel. It also supports memory regimes to control allocation time and a protocol to bound priority inversion. This version of Chocolate is implemented on top of NT/RK, an OS environment that includes a "portable resource kernel" within the NT kernel. Our detailed evaluation of Chocolate shows that the overhead introduced by NT/RK is acceptable. A real time Java audio package on Chocolate demonstrates significantly better performance than its non real time counterpart. However, our Hartstone benchmark evaluations also show that our NT/RK implementation does have its drawbacks due to the lack of hard real time capabilities within Windows NT.

Energy efficiency is becoming an increasingly important feature for both mobile and high-performance server systems. Most processors designed today include power management features that provide processor operating points which can be used in power management algorithms. However, existing power management algorithms implicitly assume that lower performance points are more energy efficient than higher performance points. Our empirical observations indicate that for many systems, this assumption is not valid.We introduce a new concept called critical power slope to explain and capture the power-performance characteristics of systems with power management features. We evaluate three systems - a clock throttled Pentium laptop, a frequency scaled PowerPC platform, and a voltage scaled system to demonstrate the benefits of our approach. Our evaluation is based on empirical measurements of the first two systems, and publicly available data for the third. Using critical power slope, we explain why on the Pentium-based system, it is energy efficient to run only at the highest frequency, while on the PowerPC-based system, it is energy efficient to run at the lowest frequency point. We confirm our results by measuring the behavior of a web serving benchmark. Furthermore, we extend the critical power slope concept to understand the benefits of voltage scaling when combined with frequency scaling. We show that in some cases, it may be energy efficient not to reduce voltage below a certain point.

Real-time computing systems are critical to an industrialized nation's technological infrastructure. Modem telecommunication systems, automated factories, sophisticated defense systems, power plants, aircrafts, airports, space stations, and high energy physics experiments cannot operate without them. Indeed, real-time computing systems control the very systems that keep us productive, and enable us to explore new frontiers of science and engineering. In real-time applications, the correctness of a computation depends not only on its results but also on the time at which its outputs are generated. The measures of merit in a real-time system include: predictably fast response to urgent events; high degree of schedulability. Schedulability is the degree of resource utilization at or below which the timing requirements of tasks can be satisfied. It can be thought of as a measure of the number of timely-transactions per second; and stability under transient overload. When the system is overloaded by events and it is impossible to meet all the deadlines, the deadlines of selected critical tasks must still be guaranteed. Generalized rate-monotonic scheduling (GRMS) theory allows developers of real-time systems to meet application timing requirements by managing system concurrency and timing constraints at the level of tasking and message passing. In essence, GRMS theory guarantees that all tasks will meet their deadlines if the total system utilization of these tasks lies below a known bound, and these tasks are scheduled using appropriate algorithms. This analytic, engineering basis makes real-time systems considerably easier to develop, modify and maintain. The rate-monotonic scheduling algorithm with all its extensions is referred to as generalized rate-monotonic scheduling (GRMS). Because of its versatility and ease of use, GRMS has gained rapid acceptance. For example, it is used for developing real-time software in the NASA Space Station Freedom Program, the European Space Agency (ESA), 1990, and is supported by the IEEE Futurebus + Standard 1990 and IEEE POSIX.4. A review of the basic results are described and then these results are illustrated with example applications. Keywords: scheduling; examples; real-time

In this paper, the efects of quantization on EDF (Earliest Deadline first) queues with a stochastic traffic model are presented. In a quantized EDF queue, jobs have limited fidelity in representing their relative deadlines. It is shown that most of the benefits of full EDF can be achieved with relative deadlines expressed in as little as three bits. The implications of this are that QoS networking technologies such as DifServ can be used to implement near EDF performance while still using no more than the standard set of bits in DS/TOS field.

INSERT is a capability package designed to support safe on-line upgrades of software components in real-time systems and the safe insertion of new capabilities into those systems. High reliability is guaranteed through the use of run-time monitoring and switching. The INSERT run-time monitor can detect and overcome semantic, data, and system errors. The run-time system is complemented with tools for off-line analysis and design to support development and implementation of INSERT-protected systems. This report documents the architecture and the associated middleware. In addition, the capability package contains methods for verification of the INSERT switching rules and Analytic Redundancy Component (ARC) based verification methods (which are also referred to as dependency tracking methods). The report documents a major experiment in which the INSERT architecture was implemented in the Lockheed Martin F-16 ground-based simulators. The Automated Maneuvering and Attack System (AMAS) algorithm was then installed. The INSERT architecture successfully protected the system against residual software faults. A Lockheed Martin cost estimation process concluded that the INSERT architecture could result in a reduction of 20% in labor hours in a real-time safety critical system.

We consider the problem of OS resource management for real- time and multimedia systems where multiple activities with different timing constraints must be scheduled concurrently. Time on a particular resource is shared among its users and must be globally managed in real-time and multimedia systems. A resource kernel is meant for use in such systems and is defined to be one which provides timely, guaranteed and protected access to system resources. The resource kernel allows applications to specify only their resource demands leaving the kernel to satisfy those demands using hidden resource management schemes. This separation of resource specification from resource management allows OS-subsystem- specific customization by extending, optimizing or even replacing resource management schemes. As a result, this resource-centric approach can be implemented with any of several different resource management schemes. We identify the specific goals of a resource kernel: applications must be able to explicitly state their timeliness requirements; the kernel must enforce maximum resource usage by applications; the kernel must support high utilization of system resources; and an application must be able to access different system resources simultaneously. Since the same application consumes a different amount of time on different platforms, the resource kernel must allow such resource consumption times to be portable across platforms, and to be automatically calibrated. Our resource management scheme is based on resource reservation and satisfies these goals. The scheme is not only simple but captures a wide range of solutions developed by the real-time systems community over several years. One potentially serious problem that any resource management scheme must address is that of allowing access to multiple resources simultaneously and in timely fashion, a problem which is known to be NP-complete. We show that this problem of simultaneous access to multiple resources can be practically addressed by resource decoupling and resolving critical resource dependencies immediately. Finally, we demonstrate our resource kernel's functionality and flexibility in the context of multimedia applications which need processor cycles and/or disk bandwidth.

This document constitutes the final report to the revised Statement of Work for the Carnegie Mellon University Incremental Software Evolution for Real-Time Systems (INSERT) project under the DARPA Evolutionary Design for Complex Software (EDCS) Program. The INSERT team has completed an initial API definition and ported the existing real-time publication subscription group communication software to LynxOS 2.4, a POSIX.1b compliant OS. The distributed real-time publisher/subscriber communication model is now supported by a processor membership protocol which allows a node in the system to fail, or to rejoin the system later. When a node fails, all the publishers and subscribers on that node have to be deleted from the publisher/subscriber information maintained by the middleware layer. When a node tries to rejoin, the current state information about the publishers/subscribers must be transferred to the node before it can integrate into the system. A twophase protocol is used to ensure that the state information from the requested node is transferred in consistent fashion (since the information can be changing when the transfer happens). The message distribution list for distributed group communication is currently undergoing further evaluation in the context of real-time control experiments.

The two letters in this special issue cover two critical topics for future vehicles: security layers for smartphone-to-vehicle communication and the design of new applications for vehicle sharing.

The four papers in this special section present examples of recent advances in the state-of-the-art of cyber-physical systems and cooperating objects.

Distributed continuous media applications that incorporate digital audio and video require predictable response from the operating system and the network. Much recent research in communication networks focuses on providing predictable service at the network level, but current operating systems do not typically provide end-to-end predictability. Our aim is to offer operating system support for predictability while still maintaining the dynamic, easy-to- use environment of a general purpose operating system. We explore the use of a resource reservation mechanism in the operating system with the idea that this mechanism can be used to support higher level quality of service management policies. We also employ a protocol software structure that uses priorities, preemptive packet servicing, and reservation enforcement to allow the reservation scheduling policy to make fine-grained scheduling, decisions to control the protocol processing activities. By reserving resources such as buffers, computation time for application-level activities, and computation time for protocol processing our system can support predictable behavior for distributed real-time application programs. We implemented our reservation mechanism using the Real-Time Mach operating system as a base, and we present performance results which demonstrate that our approach provides predictable network service to distributed multimedia applications