***************************************************************************** Paper Abstarcts 1995 Real-Time Systems Symposium Dec. 4-7, Pisa, Italy ***************************************************************************** Session 1: Applications Proving Dynamic Properties in an Aerospace Application Simin Nadjm-Tehrani and Jan-Erik Stromberg Link"oping University, Sweden In this paper we give an exposition to an ongoing research effort in cooperation with aerospace industries in Sweden. We report on an application of formal verification techniques on a landing gear system. This system consists of actuating hydromechanic and electromechanic hardware, and of controlling software components. We emphasize the need for modelling techniques and languages covering the whole spectrum from informal engineering documents, to hybrid mathematical models. In this modelling process we give as much weight to the physical environment as to the controlling software. We show the application of two verification methods for proving safety and timeliness properties of the closed loop system; first, using the proof system of extended duration calculus, and second by symbolic model checking. Modelling a Real Time Control System Based on Distributed Objects Nigel Baker, Wayne Harris, Chris Wallace, Richard McClatchey and Jean-Marie Le Goff University of the West of England, Frenchay Campus The CERN Research and Development project (RD-38), named CICERO [1], aims to identify and design the main building blocks of a generic control information system based on distributed objects. The project is producing an integrating framework (named Cortex [2]) into which user real-time control objects will ultimately be plugged (and played) and a control information system to support its configuration and management. Development of Cortex is following the ESA PSS-05-02 software engineerin standards [3]. Cortex is providing an environment which allows real-time control systems to share information, control and analysis functions; which presents an uniform human interface; which permits upgrades and additions without code modification; and which is sufficiently generic to allow its use both by existing or future control systems at CERN and by industrial real-time control systems. It provides both high level data access, abstracting objects to a level appropriate for online control and low level data access to allow views of experimenta sub-components for detailed real-time control. Additionally, the Cortex system shall enable developers to grow their control systems from a lab-based test system to the complete experimental system and is therefore both scalable and flexible to change. Technical solutions are being identified in CICERO which could later be the major components of a basic turnkey control system for future medium to large scale HEP experiments and accelerators as well as for industrial real-time control systems. This paper outlines the modelling concepts behind Cortex. ------------------------------------------------------------------------------- Session 2: Synchronization and OS A Scalable Real-Time Synchronization Protocol for Distributed Systems Injong Rhee and Graham R. Martin University of Warwick, UK A distributed protocol is proposed for the synchronization of real-time tasks that have variable resource requirements. The protocol is simple to implement and is intended for large-scale distributed or parallel systems in which processes communicate by message passing. Critical sections, even when nested, may be executed on any processor. Thus, given an adequate number of processors, the execution of critical sections can be completely distributed. More significantly, since the protocol enables the distributed allocation of critical sections, the benefits of various allocations can be analyzed and the system optimized to provide minimal blocking. This has important application in global optimization techniques for allocating large numbers of hard real-time tasks in multiprocessor systems. Real-Time Computing with Lock-Free Shared Objects James H. Anderson, Srikanth Ramamurthy, and Kevin Jeffay University of North Carolina This paper considers the use of lock-free shared objects within hard real-time systems. As the name suggests, lock-free shared objects are distinguished by the fact that they are not locked. As such, they do not give rise to priority inversions, a key advantage over conventional, lock-based object-sharing approaches. Despite this advantage, it is not immediately apparent that lock-free shared objects can be employed if tasks must adhere to strict timing constraints. In particular, lock-free object implementations permit concurrent operations to interfere with each other, and repeated interferences can cause a given operation to take an arbitrarily long time to complete. The main contribution of this paper is to show that such interferences can be bounded by judicious scheduling. This work pertains to periodic, hard real-time tasks that share lock-free objects on a uniprocessor. In the first part of the paper, scheduling conditions are derived for such tasks, for both static and dynamic priority schemes. Based on these conditions, it is formally shown that lock-free object-sharing approaches can be expected to incur much less overhead than approaches based on wait-free objects or lock-based schemes. In the last part of the paper, this conclusion is validated experimentally through work involving a real-time desktop videoconferencing system. Kernel-Level Threads for Dynamic, Hard Real-Time Environments Marty Humphrey, Gary Wallace, and John A. Stankovic University of Massachusetts The design of a kernel-level thread package for dynamic, hard real-time environments is presented. A highly integrated design is used to ensure predictability. A system description language and real-time programming language are used to specify key properties of threads and thread groups. For a thread, this includes whether or not the thread spawns other threads at run-time, the type of performance guarantee the thread requires, how the thread interacts with other threads, and what processors the thread may execute on. A predictable kernel uses this information along with on-line dynamic guarantees to ensure predictable execution of threads. The first phase of the thread package has been implemented and performance measurements have indicated a 66% improvement in context switching costs. MiThOS -- A Real-Time Micro-Kernel Threads Operating System Frank Mueller*, Viresh Rustagi** and Ted Baker*** * Humboldt-Universitat zu Berlin ** Microtec Research Inc. *** Florida State University MiThOS (Micro-kernel Threads Operating System) is an experimental operating system for embedded systems. The system kernel is a first implementation of the POSIX ``Minimal Real-Time System Profile''. It is based on prior work of a library implementation of Pthreads (POSIX threads). The system is fully preemptive. It supports multi-threading within a single process environment with shared kernel and user space, {\em i.e.} real-time tasks are mapped onto POSIX threads. It exhibits remarkable timing predictability intended for hard real-time requirements. This is achieved by a careful design of only few device drivers. The system has been implemented and tested on the SPARC VME architecture. The system includes a fast context switching algorithm for the SPARC which outperforms the context switch under SunOS and matches the performance under Solaris. It supports selective enabling and disabling of hardware components (MMU, caches, etc.) since its sources are available. Furthermore, an implementation-defined extension of POSIX threads for deadline scheduling is presented. Overall, the system exhibits slightly faster performance than SunOS 4.x and is considerably more predictable in its timing behavior. Applications of the kernel range from evaluating the overhead of new language features in Ada 95 and its runtime system, verifying static timing predictions on a bare machine, to providing the operating system for small embedded system that require a high timing predictability. ---------------------------------------------------------------------------- Session 3: Formal Methors HyTech: The Next Generation T. Henzinger, P.-H. Ho, and H. Wong-Toi Cornell University We describe a new implementation of \hytech\,---\,a symbolic model-checker for hybrid systems. Given a parametric description of an embedded system as a collection of communicating automata, \hytech\ automatically computes the conditions on the parameters under which the system satisfies its safety and timing requirements. While the original \hytech\ prototype was based on the symbolic algebra tool Mathematica, the new implementation is written in C++ and builds on geometric algorithms instead of formula manipulation. The new \hytech\ offers a cleaner and more expressive input language, greater portability, and dramatically superior performance (typically two to three orders of magnitude). We illustrate the effectiveness of the new implementation by applying \hytech\ to the automatic parametric analysis of the generic railroad crossing (GRC) benchmark problem~\cite{HJL93} and to an active structure control algorithm~\cite{ECB94}. Two Examples of Verification of Multirate Timed Automata with Kronos Conrado Daws and Sergio Yovine VERIMAG, France Multirate timed automata are an extension of timed automata where each clock has its own speed varying between a lower and an upper bound that may change from one control location to another. This formalism is well-suited for specifying hybrid systems where the dynamics of the continuous variables are defined or can be approximated by giving the minimal and maximal rate of change. To avoid the difficulties inherent to the verification of multirate timed automata, we follow the approach suggested in (1). This approach consists in first transforming the multirate timed automata into timed automata and then applying the symbolic techniques implemented in Kronos. We show the practical interest of this approach analyzing two examples recently proposed in the literature and considered to be realistic case studies: the manufacturing plant of (2) and the Philips audio control protocol (3). (1) "Using abstractions for the verification of linear hybrid systems", A. Olivero and J. Sifakis and S. Yovine, LNCS 818, p. 81-94. (2) "Verification of hybrid systems using abstractions" A. Puri and P. Varaiya, Hybrid Systems Workshop, Cornell University, October 1994. (3) "Verification of an audio control protocol" D. Bosscher and I. Polak and F. Vaandrager, LNCS 863, p. 170-192. Compositional and Symbolic Model-Checking of Real-Time Systems Kim G. Larsen, Paul Pettersson, and Wang Yi Uppsala University, Sweden Efficient automatic model--checking algorithms for real-time systems have been obtained in recent years based on the state--region graph technique of Alur, Courcoubetis and Dill. However, these algorithms are faced with two potential types of explosion arising from parallel composition: explosion in the space of control nodes, and explosion in the region space over clock-variables. In this paper we attack these explosion problems by developing and combining compositional and symbolic model--checking techniques. The presented techniques provide the foundation for a new automatic verification tool Uppaal. Experimental results show that Uppaal is not only substantially faster than other real-time verification tools but also able to handle much larger systems. ----------------------------------------------------------------------------- Session 4: Scheduling I Value vs Deadline Scheduling in Overload Conditions Giorgio Buttazzo, Marco Spuri and Fabrizio Sensini Scuola Superiore S. Ann, Italya In this paper we present a comparative study among scheduling algorithms which use different priority assignments and different guarantee mechanisms to improve the performance of a real-time system during overload conditions. In order to increase the information available to the system for enhancing the quality of service, we assume that tasks are characterized not only by a deadline, but also by an importance value. The performance of the scheduling algorithm is then evaluated by computing the cumulative value gained on a task set, i.e. the sum of the values of those tasks that completed by their deadline. The purpose of this simulation study was twofold. Firstly, we wanted to discover which priority assignment is able to achieve the best performance in overload conditions. Secondly, we were interested in understanding how the pessimistic assumptions made in the guarantee test affect the performance of the scheduling algorithms, and how much a reclaiming mechanism can compensate this degradation. To answer these questions, in our study we have considered four classical priority assignments, that we have tested using three different guarantee mechanisms, thus comparing a total number of twelve scheduling algorithms. The results are interesting and provide a useful reference for building robust real-time systems for practical control applications. Dual Priority Scheduling Robert Davis and Andy Wellings University of York In this paper, we present a new strategy for scheduling tasks with soft deadlines in real-time systems containing periodic, sporadic and adaptive tasks with hard deadlines. In such systems, much of the spare capacity present is due to sporadic and adaptive tasks not arriving at their maximum rate. Offline methods of identifying spare capacity such as the Deferrable Server or Priority Exchange Algorithm are unable to make this spare capacity available as anything other than a background service opportunity for soft tasks. Further, more recent methods such as dynamic Slack Stealing require computationally expensive re-evaluation of the available slack in order to reclaim such spare capacity. By comparison, the Dual Priority approach presented in this paper provides an efficient and effective means of scheduling soft task in this case. Skip-Over: Algorithms and Complexity for Overloaded Systems That Allow Skips Gilad Koren and Dennis Shasha Bar-Ilan U., ISRAEL Courant Institute, NYU In applications ranging from video reception to telecommunications and packet communication to aircraft control, tasks enter periodically and have fixed response time constraints, but missing a deadline is acceptable, provided most deadlines are met. We call such tasks ``occasionally skippable.'' We look at the problem of uniprocessor scheduling of occasionally skippable periodic tasks. We show that making optimal use of skips is NP-hard. We then look at algorithms for scheduling such systems. -------------------------------------------------------------------------- Session 5: Fault Tolerance Enhancing Real-Time Schedules to Tolerate Transient Faults Sunondo Ghosh, Rami Mellhem and Daniel Mosse University of Pittsburgh We present a scheme that can be used to guarantee that the execution of real-time tasks can tolerate transient and intermittent faults. The scheme is based on reserving sufficient slack in a schedule such that a task can be re-executed before its deadline without compromising the guarantees given to other tasks. Instead of reducing the schedulability by 50\% by simply leaving enough time in the schedule for each task to re-execute, we take the Mean Time To Failure (MTTF) into account. We leave only enough slack in the schedule to guarantee fault tolerance if at most one fault occurs within a time interval, e.g., a factor of the MTTF. This results in increased schedulability and a very low percentage of deadline misses even if no restriction is placed on the fault separation. We show that this methodology can be applied to any queue-based scheduling technique for real-time tasks, and provide simulation results for some common scheduling policies. We also provide two algorithms to solve the problem of adding fault tolerance to a queue of real-time tasks. The first is a dynamic programming solution to find the optimal placement of backups in the queue which maximizes schedulability while providing fault tolerance. The second is a heuristic which closely approximates the optimal. We also present a comparison between the two algorithms, and a detailed evaluation of one of the two algorithms. A Software Fault Injection Tool on Real-Time Mach Scott Dawson, Farnam Jahanian and Todd Mitton University of Michigan Ensuring that a distributed real-time system with strict dependability constraints meets its prescribed specification is a growing challenge that confronts software developers and system engineers. This paper reports on a software fault injection tool, called sockPFI, for testing the fault tolerance and timing behavior of distributed real-time applications. The sockPFI, developed on Real-Time Mach, can be used to test socket-based distributed real-time applications on this platform without modifying the source code of the target protocol. The sockPFI tool is based on the concept of Script-Driven Probing and Fault Injection \cite{dawson:94b}. It is explicitly designed to address some of the intrusiveness associated with fault injection of distributed systems, and in particular, with real-time protocols. The paper describes the design and implementation of sockPFI on Real Time Mach. This paper also describes a demonstration of the tool on a real-time primary-backup replication protocol. Fault-tolerant Real-Time Communication in FDDI-Based Networks Biao Chen, Sanjay Kamat, and Wei Zhao Texas A&M University In mission-critical systems, messages have hard real-time constraints as well as certain fault-tolerance requirements. Often some critical messages may have to be transmitted by their deadlines even when the system detects certain faults at run-time. FDDI-Based Reconfigurable Networks have an architecture that is suitable for mission-critical systems. This architecture uses multiple FDDI networks to connect hosts and provides for automatic reconfiguration to maintain high network bandwidth in spite of faults. Extensive studies have been carried out on the design of reconfiguration algorithms for this architecture. An important open problem is how resources in such networks should be managed in order to guarantee that the fault-tolerant real-time requirements of messages are met. This paper presents an efficient and practical solution to this problem. Our solution consists of off-line and on-line components. On-line management deals with run-time manipulation of messages and network resources. A message grouping approach simplifies on-line management. Off-line management deals with organizing messages into groups, allocating bandwidth to messages and verifying that all the fault-tolerant real-time requirements are met. Three approaches are investigated: spatial redundancy approach that relies on sending multiple copies of a message, temporal redundancy approach that allows for migration of a message from faulty to nonfaulty rings, and an integrated approach that uses a combination of both. It is shown that the integrated approach has the best performance. Our solution is compatible with the FDDI and SAFENET standards. ------------------------------------------------------------------------------ Session 6: Distributed Systems Joint Scheduling of Distributed Complex Periodic and Hard Aperiodic Tasks in Statically Scheduled Systems Gerhard Fohler University of Massachusetts In this paper we present algorithms for the joint scheduling of periodic and aperiodic tasks in statically scheduled distributed real-time systems. Periodic tasks are precedence constrained, distributed, and communicating over the nodes of the systems. Both soft and hard aperiodic tasks are handled. After a static schedule has been created in a first step, the algorithms determine the amount and distribution of unused resources and leeway in it. These are then used to incorporate aperiodic tasks into the schedule by shifting the periodic tasks' execution, without violating their feasibility. Run-time mechanisms are simple and require only little memory. Processors and communication nodes can be utilized fully. The algorithm performs an optimal online guarantee algorithm for hard aperiodic tasks of O(N). Optimal Combined Task and Message Scheduling in Distributed Real-Time Systems Tarek F. Abdelzaher, and Kang G. Shin University of Michigan In this paper we present an optimal algorithm for {\em combined\/} task and message scheduling in distributed hard real-time systems. The algorithm finds an optimal schedule for a set of communicating tasks with known arrival times, precedence constraints, and resource requirements in conjunction with the assignment and scheduling of intertask messages over communication links. Processing nodes are assumed to be joined by an arbitrary topology point-to-point interconnection network. The algorithm employs a branch-and-bound (B\&B) technique to find an optimal solution for the combined task and message scheduling problem. The solution is ``optimal'' in the sense of minimizing maximum task lateness, defined as the difference between task completion time and deadline. It has the property of generating a complete schedule at each vertex in the search tree, and can be made to produce the first encountered feasible solution if needed. A robotics application is used to illustrate the potential of the algorithm. Results of an extensive simulation study analyzing its performance are reported. The algorithm is shown to find the optimal solution near the root of the search for a large range of systems. The algorithm also scales well with respect to system size, and degree of interaction among system tasks. It has good performance for workloads spanning a large range of CPU utilization and degrees of application concurrency. Distributed Pinwheel Scheduling with End-to-End Timing Constraints Chih-wen Hsueh, Kwei-Jay Lin, and Nong Fan University of California, Irvine Scheduling algorithms for allocating resources and scheduling tasks are important to the success of many real-time systems with end-to-end performance requirements. In this paper, an end-to-end scheduling model based on the pinwheel scheduling algorithms is presented for distributed real-time systems. We discuss how tasks on different nodes may be transformed to have harmonic periods. We also present algorithms to adjust the phases between schedules on neightboring node so that the overall end-to-end delay is reduced. Using the pinwheel approach, schedules on different nodes are closely synchronized and more static. However, the payoff is the more predictable performance with a shorter end-to-end delay. We believe that our work in this paper provides a practical approach to the design of many static real-time systems. The Design of Large Real-Time Systems: The Time-Triggered Approach Hermann Kopetz, Martin Braun, Christian Ebner, Andreas Kruger, Dietmar Millinger, Roman Nossal and Anton Schedl Technische Universit"at Wien, Austria ------------------------------------------------------------------------------ Session 7: Scheduling II Applicability of Simulated Annealing Methods to Real-Time Scheduling and Jitter Control Marco DiNatale & John A. Stankovic University of Massachusetts This paper presents a non-conventional scheduling approach for distributed static systems where tasks are periodic and have arbitrary deadlines, precedence, and exclusion constraints. The solution presented in this work not only creates feasible schedules, but also minimizes jitter for periodic tasks. The problem of scheduling real-time tasks with minimum jitter is particularly important in many control applications, nevertheless, it has been rarely studied in the scientific literature. We present a general framework consisting of an abstract architecture model and a general programming model. We show how to design a surprisingly simple and flexible scheduling method based on simulated annealing and present some experimental results. Fairness in Periodic Real-Time Scheduling Sanjoy K. Baruah New Jersey Institute of Technology The issue of temporal fairness in periodic real-time scheduling is considered. It is argued that such fairness is often a desirable characteristic in real-time schedules. A quantitative measure of temporal fairness --- pfairness --- is described. The Weight-Monotonic scheduling algorithm, a static priority scheduling algorithm for generating pfair schedules, is presented and proven correct. A feasibility test is presented which, if satisfied by a periodic task system, ensures that the Weight-Monotonic scheduling algorithm will schedule the system in a pfair manner. Robust Aperiodic Scheduling Under Dynamic Priority Systems Marco Spuri, Giorgio Buttazzo and Fabrizio Sensini Scuola Superiore S. Ann, Italya When hard periodic and firm aperiodic tasks are jointly scheduled in the same system, the processor workload can vary according to the arrival times of aperiodic requests. In order to guarantee the schedulability of the periodic task set, in overload conditions some aperiodic tasks must be rejected. In this paper we propose a technique that, in overload conditions, adds robustness to the joint scheduling of periodic and aperiodic tasks in systems with dynamic priorities. Our technique is based on an aperiodic server, called Total Bandwidth server, already proven effective in a previous work. Here the algorithm is first extended to efficiently handle firm aperiodic tasks and then integrated with a robust guarantee mechanism that allows to achieve graceful degradation in case of transient overloads. Extensive simulations show that the proposed new algorithm is effective in all workload conditions. ------------------------------------------------------------------------------- Session 8: Communication On Slot Reuse for Isochronous Services in DQDB Networks Ching-Chih Han*, Chao-Ju Hou** and Kang G. Shin* * University of Michigan ** Univerity of Wisconsin-Madison The Distributed Queue Dual Bus (DQDB) protocol has been jointly adopted by IEEE and ANSI as a standard (IEEE802.6) for metropolitan area networks (MANs). As such, DQDB has become the focus of many studies. In addition to the numerous studies performed on the queueing performance [3,6,18] and the fairness issue [2, 12, 13, 26], the issue of how to effectively provide various services in DQDB networks has also received increasing attention [14, 24]. In [14], we devised a slot allocation scheme for allocating pre-arbitrated (PA) slots to isochronous message streams in DQDB networks. We laid a formal basis for guaranteeing the timely delivery of isochronous (real-time) messages with hard deadlines. In this paper, we extend our work in [14] and address on how to improve the performance of the slot allocation scheme (in terms of bandwidth utilization) by using the concept of slot reuse. We devise several slot reuse schemes to assign spatially non-intersecting message streams to share the same virtual connections (i.e., the same set of PA slots identified by the VCI numbers). The slot reuse schemes proposed in this paper are simple, can be easily incorporated into the slot allocation scheme proposed in [14], and requires only a minor change in the current DQDB standards. Dynamic Real-Time Channel Setup and Tear-Down in DQDB Networks Chao-Ju Hou and Kar Shun Tsoi Univerity of Wisconsin-Madison The Distributed Queue Dual Bus (DQDB) protocol has been jointly adopted by IEEE and ANSI as a standard (IEEE802.6) for metropolitan area networks (MAN). As such, how to provide various services in the DQDB protocol has attracted increasing attention. In particular, how to guarantee the timely delivery of isochronous (real-time) messages with hard deadline constraints is one of the open issues yet to be solved. In [12], we laid a formal basis for allocating pre-arbitrated (PA) slots to isochronous message streams in DQDB networks and devised a slot allocation scheme to statically establish a set of isochronous message streams at system initialization. In this paper, we complement our work in [12] and propose a dynamic channel setup and tear-down scheme for DQDB networks. During system operation, we artificially treat the QA slots as slots assigned to a pseudo channel, called an empty channel. In response to a call setup request, the proposed scheme first verifies whether or not the new channel can be feasibly established without jeopardizing the timing constraints of existing channels by checking a certain schedulability condition. If the schedulability condition is satisfied, the channel establishment procedures are invoked to set up this new channel by using the slots originally assigned to the empty channel. In response to a call clear request, the channel termination procedures are invoked to free the slots originally allocated to the terminated channel by marking them as slots allocated to an empty channel. The channel termination procedures then merge this newly freed channel and the existing empty channel into one. The resulting channel establishment and termination procedures are simple, can be easily implemented in DQDB networks, and do not require any changes in the current DQDB standards. Modeling Bus Scheduling Policies for Real-Time Systems Kevin Kettler and Jay Strosnider Carnegie Mellon University This paper introduces formal scheduling models for several common system bus architectures found in PC and workstation systems. The scheduling models are abstractions which enable one to reason about the timing correctness of a bus transferring real-time traffic. The models provide a quantitative means to explore the design space of bus implementations. This paper provides a simple, unambiguous approach for the creation of scheduling models which can be used efficiently by a bus designer or system user to improve real-time bus performance without the need for detailed real-time scheduling knowledge. The step by step process of model development is presented. The utility of the scheduling models is demonstrated by analyzing several common system buses. ------------------------------------------------------------------------------- Session 9: Specification Compiling Modechart Specifications Carlos Puchol, Aloysius K. Mok and Douglas A. Stuart University of Texas at Austin The Modechart specification language is a formalism for the specification of real-time systems. A toolset for specification, analysis and simulation for Modechart specifications exists for supporting the design and construction of real-time systems. This paper introduces a new tool in the the toolset: a compiler for a class of Modechart specifications, namely, that of deterministic system specifications, extended by a subclass of the non-deterministic system specifications. The object code that the compiler generates is in Esterel, a member of the synchronous family of programming languages for real-time systems. We discuss a broad approach to the implementation of timing specifications, providing a range of implementation options, from the basic time step unrolling of states in Esterel, to the use of system timers. The compiler presented herein allows the specifier to obtain a correct implementation of a modechart program, including timing constraints. The Specification and Schedulability Analysis of Real-Time Systems using ACSR J. Choi, I. Lee and H. Xie University of Pennsylvania To engineer reliable real-time systems, it is desirable to detect timing anomalies early in the development process. However, there is little work addressing the problem of accurately predicting timing properties of real-time systems before implementations are developed. This paper describes an approach to the specification and schedulability analysis of real-time systems based on the timed process algebra ACSR-VP, which is an extension of ACSR with value-passing communication and dynamic priorities. Combined with the existing features of ACSR for representing time, synchronization and resource requirements, ACSR-VP is capable of specifying a variety of real-time systems with different scheduling disciplines in a modular fashion. Moreover, we can perform schedulability analysis on real-time systems specified in ACSR-VP automatically by checking for a certain bisimulation relation. A Graphical Language with Formal Semantics for the Specification and Analysis of Real-Time Systems Hanene Ben-Abdallah, Insup Lee, and Jin-Young Choi University of Pennsylvania Graphical Communicating Shared Resources, GCSR, is a formal language for the specification and analysis of real-time systems including their functional and resource requirements. GCSR allows a modular and hierarchical, thus, scalable specification of a real-time system. GCSR supports notions of communication through events, interrupt, concurrency, and time to describe the functional requirements of a real-time system. In addition, GCSR allows the explicit representation of resources and priorities to arbitrate resource contention in a natural way that produces easy to understand and modify specifications. The semantics of GCSR is the Algebra of Communicating Shared Resources, a timed process algebra with operational semantics. The process algebra ACSR provides behavioral equivalence relations which can be used to verify the correctness of one GCSR specification with respect to the other. ------------------------------------------------------------------------------ Session 10: Timing Analysis Integrating the Timing Analysis of Pipelining and Instruction Caching Chris Healy*, Dave Whalley* and Marion Harmon** * Florida State University ** Florida A&M University Recently designed machines contain pipelines and caches. While both features provide significant performance advantages, they also pose problems for predicting execution time of code segments in real-time systems. Pipeline hazards may result in multicycle delays. Instruction or data memory references may not be found in cache and these misses typically require several cycles to resolve. Whether an instruction will stall due to a pipeline hazard or a cache miss depends on the dynamic sequence of previous instructions executed and memory references performed. Furthermore, these penalties are not independent since delays due to pipeline stalls and cache miss penalties may overlap. This paper describes an approach for bounding the worst-case performance of large code segments on machines that exploit both pipelining and instruction caching. First, a method is used to analyze a program's control flow to statically categorize the caching behavior of each instruction. Next, these categorizations are used in the pipeline analysis of sequences of instructions representing paths within the program. A timing analyzer uses the pipeline path analysis to estimate the worst-case execution performance of each loop and function in the program. Finally, a graphical user interface is invoked that allows a user to request timing predictions on portions of the program. Efficient Microarchitecture Modeling and Path Analysis for Real-Time Software Yau-Tsun Steven Li, Sharad Malik, Andrew Wolfe Princeton University Real-time systems are characterized by the presence of timing constraints in which a task must be completed within a specific amount of time interval. This paper examines the problem of determining the bound on the worst case execution time (WCET) of a given program on a given processor. There are two important issues in solving this problem: (i) program path analysis, which determines what sequence of instructions will be executed in the worst case, and (ii) microarchitectural modeling, which models the hardware system and determines the WCET of a known sequence of instructions. To obtain a tight estimate on the bound, both of these issues must be addressed accurately and efficiently. The later is becoming difficult to model for modern processors due to the presence of pipelined instruction execution units and cached memory systems. All existing methods that the authors know of focus only on either one of above issues. They also adopt the path oriented approach to solve the problem, in which an exhaustive search on all feasible program paths is required. These limit the accuracy of the estimated bound and the size of the program that can be analyzed. We present a more effective solution for solving this problem. It addresses both issues and uses an integer linear programming formulation to solve the problem. Explicit program path enumeration is not required. This solution is implemented in the program cinderella, which currently targets the Intel i960KB processor. Some experimental results are presented here. Worst Case Timing Analysis of RISC Processors: R3000/R3010 Case Study Yerang Hur, Young Hyun Bae, Sung-Soo Lim, Sung-Kwan Kim, Byung-Do Rhee, Sang Lyul Min, Chang Yun Park, Heonshik Shin, and Chong Sang Kim Seoul National University This paper presents a case study of worst case timing analysis for a RISC processor. The target machine consists of the R3000 CPU and R3010 FPA (Floating Point Accelerator). This target machine is typical of a RISC system with pipelined execution units and cache memories. Our methodology is an extension of the existing timing schema. The extended timing schema provides means to reason about the execution time variation of a program construct by surrounding program constructs due to pipelined execution and cache memories of RISC processors. The main focus of this paper is on explaining the necessary steps for performing timing analysis of a given target machine within the extended timing schema framework. This paper also gives results from experiments using a timing tool for the target machine built based on the extended timing schema approach. ----------------------------------------------------------------------------- Sessions 11: Real-Time DB and Window Systems Some Performance Issues for Database Transactions with Firm Deadlines Y. C. Tay National University of Singapore We present a performance model for transactions with firm deadlines running on a database system that uses locking, but without priority scheduling. Such a system may be a legacy, or bought off-the-shelf. Excluding priority scheduling is also a way of determining how resource and data contention affect deadline misses. The model is used to (1) define workload --- a number that helps the evaluation of a system design by predicting the stress on it; (2) show that performance is proportional to the cube of transaction length, so it is crucial that transactions request a minimal number of locks; (3) examine how deadlines should vary if transaction length increases, thus demonstrating the crucial role of resource contention; and (4) consider the issue of fairness and show that execution times and multiprogramming levels can cause a bias only though priority scheduling. We also offer an interpretation of ``missed deadlines must be rare'' in terms of abort cost. Managing Contention and Timing Constraints in a Real-Time Database System Matthew R. Lehr, Young-Kuk Kim, and Sang H. Son University of Virginia Previous work in real-time database management systems (RT-DBMS) has primarily focused on simulation. This paper discusses how current real-time technology has been applied to architect an actual RT-DBMS on a real-time microkernel operating system. A real RT-DBMS must confront many practical issues which simulations typically ignore: race conditions, concurrency, and asynchrony. The challenge of constructing a RT-DBMS is divided into three basic problems: dealing with resource contention, dealing with data contention, and enforcing timing constraints. In this paper, we present our approaches to each problem. ARTIFACT: A Platform for Evaluating Real-Time Window System Designs John Sasinowski and Jay Strosnider Carnegie Mellon University Multimedia and advanced real-time systems integrate a variety of applications and media types in one environment, many of which have timing properties which are not supported by current window systems running in multitasking environments. This paper discusses several key aspects to designing window systems which support continuous media and other real-time applications. These design considerations were used to construct ARTIFACT, a window system designed to investigate issues in building real-time window systems. Several of the behaviors of a partial implementation of ARTIFACT are described, along with preliminary scheduling models and avenues for further research. *****************************************************************************