Search

This report develops a queueing-theoretic solution to predict, for a real-time system, the average-case latency of aperiodic tasks managed by a sporadic server. The report applies this theory to a model problem drawn in the domain of industrial robot control. In this model problem, a controller with hard periodic deadlines is "open" to third-party plug-in extensions. The sporadic server is used to limit the invasiveness of aperiodic tasks on the controller's hard deadlines. The theory developed in this report is used to predict the average- case latency of a plug-in managed by a sporadic server.

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 in 6. 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 exhibits very high 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.

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.

This research project is developing a new approach to software fault tolerance called analytic redundancy. It has been widely acknowledged that software failures are the most important issue in large computer system reliability. The failure rate of software has risen to 9.4 times the failure rate of hardware, and software failures have captured substantial media attention in recent years. The problem of software reliability is especially difficult because the major recognized approaches (recovery blocks and n-version programming) are known to have serious drawbacks. Analytic redundance is an approach which uses simplicity (in the form of software which is relatively simple, well understood and well tested but whose performance is merely adequate) to control complexity (in the form of software which has high performance but is complex and, therefore, not reliable). Rather than trying to combine the two algorithms (which would create an even less reliable system), we allow the complex software to control the system as long as it is behaving properly (as judged by the simple software). If it is determined that the complex software is behaving incorrectly, then the simple software takes over. The simple software will guarantee a baseline, if not optimal, performance.

The ART (Advanced Real-Time Technology) Project of Carnegie Mellon University is engaged in wide ranging research on hard real-time systems. The project has as its overall goal the development and demonstration of predictable and fault tolerant hard real-time computer systems. To achieve this goal, research is being conducted in three interrelated areas: (1) The development of a theory of hard real-time resource management including scheduling and synchronization. In addition, this theory is being applied in a wide range of contexts including databases, communication networks and operating systems; (2) The design and construction of an operating system (ARTS 2.0) that supports predictable and fault tolerant real-time computer systems and demonstration and testing in the ARTS testbed to provide proof of concept and to gain understanding into aspects of the theory needing further refinement. (3) Development of hardware architectures and approaches to fault tolerance that can support predictable hard real-time computer systems.

The ART (Advanced Real-Time Technology) Project is engaged in wide ranging research on hard real-time systems. The project has as its overall goal the development and demonstration of predictable and fault tolerant hard real- time computer systems. To achieve this goal, research is being conducted in three interrelated areas: The development of a theory of hard real-time resource management including scheduling and synchronization. In addition, this theory is being applied in a wide range of contexts including databases, communication networks, operating systems and artificial intelligence. The design and construction of an operating system (ARTS) that supports predictable and fault tolerant real-time computer systems and demonstration and testing in the ARTS testbed to provide proof of concept and to gain understanding into aspects of the theory needing further refinement. A real-time version of the Mach operating system, RT-Mach, is also being developed as a part of the project. Development of hardware architectures and approaches to fault tolerance that can support predictable hard real-time computer systems.