Title: Proceedings of the 18th Real-Time Systems Symposium WIP Session Author: Bestavros, Azer (Editor) Date: December 1, 1997 Abstract: This technical report includes 10 short papers presented during the WIP session of the 18th Real-Time Systems Symposium, held in Washington DC on December 3-5, 1997. The title and authors are included below. ------ (1) CPU Reservations and Time Constraints: Efficient, Predictable Scheduling of Independent Activities Michael B. Jones, Microsoft Research, Microsoft Corporation Daniela Rosu and Marcel-Catalin Rosu, Georgia Institute of Technology Abstract: Workstations and personal computers are increasingly being used for applications with real-time characteristics such as speech understanding and synthesis, media computations and I/O, and animation, often concurrently executed with traditional non-real-time workloads. This paper presents a system that can schedule multiple independent activities so that: - activities can obtain minimum guaranteed execution rates with application-specified reservation granularities via CPU Reservations, - CPU Reservations, which are of the form "reserve X units of time out of every Y units", provide not just an average case execution rate of X/Y over long periods of time, but the stronger guarantee that from any instant of time, by Y time units later, the activity will have executed for at least X time units, - applications can use Time Constraints to schedule tasks by deadlines, with on-time completion guaranteed for tasks with accepted constraints, and - both CPU Reservations and Time Constraints are implemented very efficiently. In particular, - CPU scheduling overhead is bounded by a constant and is not a function of the number of schedulable tasks. Other key scheduler properties are: - activities cannot violate other activities' guarantees, - time constraints and CPU reservations may be used together, separately, or not at all (which gives a round-robin schedule), with well-defined interactions between all combinations, and - spare CPU time is fairly shared among all activities. The Rialto operating system, developed at Microsoft Research, achieves these goals by using a precomputed schedule, which is the fundamental basis of this work. ------ (2) Characterizing Group Communication Middleware for a Real-time Distributed System L. M. Feeney, P. Bernadat, F. Travostino The Open Group Research Institute Abstract: This paper presents our current work in characterizing the behavior of a real-time dependable distributed system, which must exhibit predictable behavior under load and in the presence of partial failures. We focus on measuring the end-to-end properties of the middleware which implements the real-time process group service, specifically its membership and message latency. The paper also describes the tools and techniques we have developed, along with some of the practical issues that arise in instrumenting a real-time distributed system. ------ (3) Real-Time Monitoring of the EIVIS Distributed Video-Server on Windows NT M. Gergeleit and M. Mock GMD - German National Research Center for Information Technology Abstract: JewelNT is a fine-grained, trace-based real-time monitoring tool for Windows NT. It hooks into the NT kernel and provides full information about NT?s thread scheduling combined with application-level timing information. JewelNT allows monitoring a number of NT machines remotely controlled from one central desktop. JewelNT has been initially developed for the evaluation and performance tuning of the distributed EIVIS video server, a European ESPRIT project. ------ (4) Achieving Predictability and Responsiveness of Fault Recovery Operations in Real-Time Systems. Pedro Mejia-Alvarez, CINVESTAV-IPN, Seccion de Computacion, Mexico Juan A. de la Puente, Universidad Politecnica de Madrid, Spain. Abstract: The dependability of real-time software can be improved by enhancing the robustness of the scheduler in predicting and controlling the occurrence of timing failures during recovery. This may be achieved by developing strategies which allow the scheduler to dynamically control the manner in which real-time applications tasks and its time-critical recovery operations are handled in time. In this paper, an scheme is presented to provide scheduling guarantees for a variety of fault tolerant techniques. Bounds of execution are developed and an study case examined to analyze these techniques in its ability to recover from transient faulty situations. A criterion for providing responsiveness for fault-tolerant scheduler is discussed and some approaches were developed. A responsiveness table RTAB, has been developed for assisting the scheduler during recovery of transient faults. This table is based on different criterion for responsiveness of recovery. An analytical characterization of the table, for supporting on-line scheduling has been developed. Some of the issues involved in using this table to support run-time scheduling decisions are illustrated with a hypothetical application example. The advantages of the RTAB approach over previously proposed scheduling policies for aperiodic tasks include the support for run-time customization and guaranteed scheduling stability during recovery. ------ (5) Compositional Reasoning about Real-Time Asynchronous Communication with Time-Outs D. Peticolas and F.A. Stomp, University of California, Davis Abstract: This paper describes ongoing work in developing a compositional trace-based semantics and proof system for a real-time language. The semantics models distributed processes communicating over asynchronous FIFO communication channels. Sending processes can specify time-out periods for individual messages. Messages not received within their time-out period are `lost'. Program behavior is modeled as traces of events, including events (such as asynchronous messages) which occur after termination. The proof system uses specification triples with explicit variables for time and program traces. ------ (6) Exploring Consistency of Read-Only Transactions in Real-Time Systems Kwok-Wa Lam, Sang H. Son* and Sheung-Lun Hung City University of Hong Kong, Hong Kong. University of Virginia, U.S.A. Abstract: In this paper, we describe our current work on exploring the consistency of read-only transactions (ROT) in real-time systems. A ROT is a transaction that only reads, but does not update any data items. Since there is a significant proportion of ROTs in several real-time systems, it is important to investigate how to process ROTs efficiently with separate algorithms. We identify three different consistency requirements for ROTs. Particularly, we define a weaker form of consistency, view consistency, which allows ROTs to perceive different serialization order of update transactions, thus permitting non-serializable execution of transactions. However, ROTs are still ensured to see consistent data. Based on view consistency, we present two algorithms which let ROTs read the most recent and consistent data without interfering with update transactions. The recency of data read by a ROT could be important in some real-time applications. ------ (7) Dynamic Timing Constraints - Relaxing Overconstraining Specifications of Real-Time Systems Gerhard Fohler Malardalens University, S-72123 Vasteras, Sweden Abstract: Standard timing constraints, such as deadlines and periods can overconstrain specifications and lack expressive power. Only few tasks have "natural" periods and deadlines. Most are artifacts, derived during system design. Knowledge of more flexibility is abandoned in the process, thus overconstraining the specification. In this paper, we propose dynamic timing constraints, which represent conditions for the temporal correctness rather than fixed values for constraints such as period and deadline. This is achieved by so-called timing entities, which combine a functional unit, such as a task, with a feasibility function for testing the feasibility of the timing of the unit. This representation allows the system specification to provide information about feasibility and various options of time related design decisions. We outline how dynamic timing constraints can be used with standard scheduling algorithms, indicate modifications to these algorithms, and novel approaches fully utilizing the benefits of dynamic timing constraints. ------ (8) Exploring the Importance of Preprocessing Operations in Real-Time Multiprocessor Scheduling Jan Jonsson, Chalmers University of Technology, Sweden Abstract: Recent real-time scheduling research has mainly been focused on generating mature scheduling theories. Therefore, the important field of preprocessing operations has been left fairly unexplored. Most real-time scheduling techniques in use today assume that the constraints (e.g. local task deadlines, degree of task replication, or task clustering) on the constituent tasks are entirely known beforehand. In such cases, no preprocessing is typically applied. However, when the constraints are relaxed, preprocessing operations can be applied for increasing the likelihood of succeeding with a scheduling attempt. In addition, preprocessing operations are vital in quality-of-service negotiations for adaptive real-time systems since changing some of the task constraints may result in a higher system reward. In this paper, we define a set of preprocessing operations that we believe is representative for real-time multiprocessor scheduling. We also give a rationale for using these operations, and present results from some preliminary work that corroborate our conjecture. In conjunction to this, we present an evaluation framework for objective studies of different preprocessing operations. ------ (9) Compiler Support for Non-intrusive Monitoring and Debugging of Real-Time Systems in the CRL Environment P. V. Petrov, A. D. Stoyen New Jersey Institute of Technology Abstract: In this work we approach the problem of monitoring and debugging real-time distributed systems by performing static analysis and transformations to eliminate obtrusion to the monitored system. Our work extends the CRL testbed compiler and run-time environment to support monitoring and logging for the purpose of post-mortem debugging. The main contribution of this work is the innovative use of compiler transformations and idle slots for monitoring and logging. ------ (10) Optimization of Real-Time MRL Rule-Based Systems with the EQL Optimizer Albert Mo Kim Cheng University of Houston--University Park Houston, Texas, USA Abstract: In our earlier work, we developed an efficient algorithm for optimizing a class of EQL rule-based systems so that they can meet specified response time constraints. In this paper, we show that this EQL optimizer with minor modifications can be used to optimize a class of real-time MRL rule-based systems. As a more expressive superset of EQL, MRL allows existentially quantified as well as universally quantified variables (simple or macro), making it comparable in expressive power to that of OPS5 and CLIPS (two of the most popular commercially available rule-based system languages) while maintaining predictable response time behavior.