Title: Proceedings of the Real-Time Systems Symposium WIP Session Author: Azer Bestavros (Editor) Date: December 4, 1996 Abstract: This technical report includes 14 short papers presented during the WIP session of the 17th Real-Time Systems Symposium, held in Washington DC on December 4-6, 1996. The title and authors are included below. ------ (1) A Specialized Specification and Verification System for Timed Automata Myla Archer and Constance Heitmeyer Naval Research Laboratory, USA Abstract: Assuring the correctness of specifications of real-time systems can involve significant human effort. The use of a mechanical theorem prover to encode such specifications and to verify their properties could significantly reduce this effort. A barrier to routinely encoding and mechanically verifying specifications has been the need first to master the specification language and logic of a general theorem proving system. Our approach to overcoming this barrier is to provide mechanical support for producing specifications and verifying proofs, specialized for particular mathematical models and proof techniques. We are currently developing a mechanical verification system called TAME (Timed Automata Modeling Environment), which provides this specialized support using SRI's Prototype Verification System (PVS). Our system is intended to permit steps in reasoning similar to those in hand proofs that use model-specific techniques. TAME has recently been used to detect errors in a realistic example. ------ (2) Scheduling Slack in MetaH Pam Binns Honeywell Technology Center, USA Abstract: A real-time implementation for allocating slack to aperiodic proceesses in MetaH is nearing completion. The slack scheduling algorithm is based on the slack stealer originally proposed in "An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed-Priority Preemptive Systems" with practical extensions to allow for support of process criticalities, multiple process streams (of different criticalities) competing for pooled slack and inclusion of run-time overheads in the slack functions. Areas in need of future work are also identified. ------ (3) AFTER: A case tool to assist in Fine-tuning of embedded real-time systems Gaurav Arora and David Stewart University of Maryland, USA Abstract: AFTER (Assist in Fine-Tuning of Embedded Real-time systems) is an interactive analysis and predictor tool for embedded systems. It helps designers quickly identify timing problems and systematically fine-tune an application during and after the implementation phase of a product's lifecycle. The tool begins with raw timing data collected from an embedded system. It analyzes the data to provide a temporal image of the current implementation, highlighting actual and potential problems. The user then interacts with AFTER to obtain predictions on what overall effect can be expected if small adjustments are made to configuration parameters or to the timing properties of specific software components. The tool integrates and extends prior research in scheduling, task monitoring, and operating system design for real-time systems. ------ (4) Genericity and Upgradability in Ultra-Dependable Real-Time Architectures Andy Wellings, Ljerka Beus-Dukis, Alan Burns, and David Powell LAAS-CNRS, France and University of York, UK Abstract: We report on the ideas currently being developed within the European GUARDS project to develop a generic upgradable architecture for real-time dependable systems. After a brief introduction and overview of the architecture, we outline the GUARDS approach for scheduling real-time replicated computation. ------ (5) Challenges in Engineering Distributed Shipboard Control System L.Welch, B.Ravindran, R.Harrison, L.Madden, M.W.Masters and W.Mills Naval Surface Warfare Center and University of Texas at Arlington, USA Abstract: In response to the need to develop high capacity, scalable computer systems for shipboard use, a program called the High Performance Distributed Computing Program (HiPer-D), was created. HiPer-D is intended to provide the technical design concepts and engineering data needed to enable the Navy to capitalize on commercial computing products. The program, conducted jointly by the Defense Advanced Research Projects Agency (DARPA) and the Aegis Shipbuilding Program, consists of simultaneous top down engineering studies and large-scale critical experiments using new computer technology. ------ (6) Issues for realizing a scalable Real Time Kernel for function-distributed Multiprocessors Hiroaki Takada, Cai-Dong Wang, and ken Sakamura University of Tokyo, Japan Abstract: In multiprocessor systems, the worst-case execution time of a task that exclusively accesses a shared resource is unavoidably prolonged as the number of contending processors is increased. In case of function-distributed multiprocessors, because many of the tasks can be processed within a processor, it is advantageous that their worst-case behavior are independent of the number of processors in the system. This paper summarizes the required properties on scalable real-time kernels and discusses their realization techniques. What we have solved so far are described, and the remaining problem to be solved is presented. ------ (7) The design and implementation of the CPU power regulator for multimedia operating systems Giun-Haur Huang, Shie-Kai Ni, and Tei-Wei Kuo National Chung Cheng University, Taiwan Abstract: This paper describes a Windows NT/95 utility, the CPU Power Regulator (CPR), which improves the capability of Windows NT/95 in servicing time-critical applications. CPR considers a distance model [4] to service time-critical applications such as multimedia softwares and electronic games in a timely fashion. Distinct from the past work [7, 8, 9], CPR adopts a user-level control mechanism to manage the resource allocations on Windows NT/95 and makes no modifications to the operating system and application softwares. The performance of CPR was verified by a collection of simulation experiments of randomly generated and realistic workloads. CPR not only introduces very low system overheads but also largely reduces the phenomenon of non-timely resource allocation for applications. The experimental results also demonstrate the capability and flexibility of CPR in multiplexing CPU cycles to provide different degrees of quality-of-service to time-critical applications. The results of this work present a low-cost software solution to transform an ordinary operating system into a multimedia operating system. ------ (8) An approach for monitoring intrusion removal in Real Time Systems Vishal Jain, Madalene Spezialetti, and Rajiv Gupta University of Pittsburgh and Trinity College, USA Abstract: To assist in the development of a real-time application, monitoring is used to collect execution timing information for the application. In this paper we propose a strategy that accurately reports timing information by accounting for intrusion introduced by monitoring. In addition, by allowing processes that miss deadlines to run to completion, our approach provides the user with times by which the execution of these processes exceeds their deadlines. This information can be used to guide the user in restructuring the application to meet timing requirements. ------ (9) Empirical Evaluation of Task and Resource Scheduling in Dynamic Real-Time Systems Ken Tew and Panos Chrysantis and Daniel Mosse University of Pittsburgh, USA Abstract: This work-in-progress reports on our on-going empirical evaluation of a two-tiered resource allocation scheme assuming independent jobs, that is, jobs have no precedence constraints. The first tier extends the temporal density approach, while the second tier uses an Earliest Deadline First (EDF) approach to schedule jobs at a site. However, job scheduling at sites is constrained by the precedence relation between the loading and execution of a job. In addition to CPU scheduling, we also take care of the time it takes to load a task onto memory from a disk (or from another processor over the network). We assume that loading (i.e., disk scheduling) follows an EDF non-preemptive discipline whereas the execution (i.e., CPU scheduling) follows a preemptive EDF. ------ (10) Scalability based admission control of real-time channels Ramesh Yerraballi and Ravi Mukkamala Midwestern State University and Old Dominion University, USA Abstract: This paper reports our continuing efforts and initial results with the problem of admission control in real-time networks. This problem was first addressed by the Tenet group, and, their approach was based on the assumption that the link level scheduling was EDD (Earliest Due Date) based. Our work departs from this assumption by addressing the problem in the context of any arbitrary dynamic/fixed priority link level scheduling. Our approach is based on extending a result we have derived in a different context, viz., Task Scalability. It involves assessing the current capacity of a link in terms of its ability to accommodate (scale to) new channels. This assessment (called the admittance measure) is then heuristically compared against the traffic requirements of the newly requested channel to decide its admissibility. A simulation study was performed to study the effectiveness of our approach in improving both utilization of the link and admissibility of channels. Further, we demonstrate the relevance of our heuristic by observing that it reduces to the Tenet schedulability test, for the case of EDD. ------ (11) Optimization of scheduling on real-time parallel computer systems Leyuan Shi and Philip Q. Hwang University of Wisconsin and Defence Mapping Agency, USA Abstract: We describe our ongoing work in the field of optimal scheduling for real-time systems. We are primarily concerned with optimal task allocation and job scheduling for parallel computer systems. Many real-time task allocation and job scheduling problems are proven to be NP-hard. Recently, we proposed a randomized optimization framework for efficiently solving such NP-hard problems. The proposed method, the Nested Partitions (NP) method, has been proved to converge to global optimal solutions and it is also highly matched to emerging massively parallel processing capabilities. ------ (12) Dynamic Scheduling of Hard Real-Time Applications in Open System Environment Z. Deng, J. W.-S. Liu, and J. Sun University of Illinois at Urbana Champaign, USA Abstract: This paper focuses on the problem of providing run-time support to real-time applications and non-real-time applications in an open system. It describes a two-level hierarchical priority-driven scheme for scheduling independently developed applications. The scheme allows the developer of each real-time application to validate the schedulability of the application independently of other applications. Once a real-time application is created and accepted by the open system, its schedulability is guaranteed regardless of the behaviors of other applications that execute concurrently in the system. ------ (13) In Search for an efficient Real-Time Atomic Commit Protocol Yousef Al-Houmaily and Panos Chrysantis University of Pittsburgh, USA Abstract: The purpose of this paper is to report on the first step in our quest for an efficient atomic commit protocol in real-time databases. This includes the development of RT-IYV (real-time implicit yes-vote), a new real-time atomic commit protocol. In contrast to other real-time commit protocols that provide for semantic atomicity, RT-IYV is designed to ensure the traditional notion of transaction atomicity. RT-IYV (1) eliminates the voting phase from 2PC hence, reducing the number of sequential coordination messages and forced log writes during normal processing, and (2) supports transactions' forward recovery hence, enabling partially executed transactions to resume their execution after a failure. To illustrate its performance advantages, we compare RT-IYV with the recently proposed OPT (optimistic commit protocol) which is also designed to support the standard transaction atomicity in real-time databases. ------ (14) Distributed Real-Time Dataflow: An Execution Paradigm for Image Processing and Anti-Submarine Warfare Applications Steve Goddard and Kevin Jeffay University of North Carolina, USA Abstract: The purpose of this paper is to report on the first step in our quest for an efficient atomic commit protocol in real-time databases. This includes the development of RT-IYV (real-time implicit yes-vote), a new real-time atomic commit protocol. In contrast to other real-time commit protocols that provide for semantic atomicity, RT-IYV is designed to ensure the traditional notion of transaction atomicity. RT-IYV (1) eliminates the voting phase from 2PC hence, reducing the number of sequential coordination messages and forced log writes during normal processing, and (2) supports transactions' forward recovery hence, enabling partially executed transactions to resume their execution after a failure. To illustrate its performance advantages, we compare RT-IYV with the recently proposed OPT (optimistic commit protocol) which is also designed to support the standard transaction atomicity in real-time databases.