================================= VOLUME 19 NUMBER 1 FEBRUARY 1995 ================================= With the exception of the last paper this is a special volume Parallel and Distributed Real-Time Systems ------------------------------ Profile: Haneef Fatmi, pp. 1-2 ------------------------------ 0. Parallel and Distributed Real-Time Systems: Introduction to the Special Issue M. Paprzycki, J. Zalewski pp. 3-6 ------------------------------ 1. Supporting the Evolution of Distributed, Non-stop, Mission and Safety Critical Systems Charles W. McKay and Colin Atkinson, University of Houston - Clear Lake, 2700 Bay Area Boulevard, Houston, TX. 77058. Phone: +713 283 3830, Fax: +713 283 3869, E-mail: mckay@cl.uh.edu pp. 7-24 Keywords: distribution, environments, non-stop, real-time, safety-critical Abstract: In coming years embedded systems which are distributed, non-stop and mission and safety critical (MASC) are likely to assume increasing importance. The construction, operation and maintenance of this class of system presents a unique blend of problems which many traditional tools and techniques, targeted to just one problem area, cannot currently address. This paper provides an overview of a promising, model-based framework for supporting such systems that has been developed as part of NASA's MISSION project. Based on well-established research advances in computing, the MISSION approach provides a domain-specific, life-cycle support framework encompassing three separate environments: host, integration and target. Although the individual elements of the framework are not all new, their synergistic packaging within the MISSION project is believed to be unique. This paper focuses upon the systems-level support for applications executing in the target environment. -------------------------------------- 2. Loose Specification of Real Time Systems Jan van Katwijk and Hans Toetenel, Delft University of Technology, Faculty of Technical Mathematics and Informatics, P.O. Box 356, 2600 AJ Delft The Netherlands pp. 25-42 Keywords: MOSCA language, multiple threads, semantic basis Abstract: MOSCA is an experimental language that equips the Vienna Development Method specification language VDM-SL to be applicable in the area ofdeveloping distributed, parallel and real-time systems. As is generally known, plain VDM is not adequate for these application areas since it lacks facilities to specify multiple threads of control and does not allow the use of time within specifications. MOSCA is designed to overcome these restrictions. This paper presents an overview of some of the process specification capabilities of the notation. It highlights the semantic basis and treats in particular the interpretation of loose value specification and loose process specification. -------------------------------------- 3. An Object-Oriented Approach for Modeling and Analysis of Safety-Critical Real-time Systems Jyhjong Lin, David Chenho Kung and Pei Hsia, Computer Science Engineering, The University of Texas at Arlington, P.O. BOX 19015, Arlington, TX 76019-0015, E-mail: jlinkunghsia@cse.uta.edu pp. 43-58 Keywords: object-oriented conceptual modeling, distributed and parallel real-time system, control flow, safety, failure, analysis Abstract: This paper presents an object-oriented approach that deals with modeling and analysis of concurrent real-time systems whose behavior must satisfy certain safety considerations. The approach describes the structural aspect and the time dependent behavioral aspect of objects in one model, and allows formal analysis of the model properties. The description of object behavior also contains a representation of control flow that specifies desirable execution sequences of object activities. For designing for fault tolerance and safety, it also supports modeling of failures to object behavior and their resultant faults. In particular, including the types of faults is useful for modeling and analysis of failures in more general situations. -------------------------------------- 4. Supporting High Integrity and Behavioural Predictability of Hard Real-Time Systems M. Colnaric and D. Verber, University of Maribor, Faculty of Technical Sciences, Smetanova 17, Maribor, Slovenia, E-mail: colnaric@uni-mb.si, and W. A. Halang, FernUniversitat Hagen, Faculty of Electrical Engineering, D-58084 Hagen, Germany, E-mail: wolfgang.halang@fernuni-hagen.de pp. 59-69 Keywords: hard real-time systems, high-integrity requirements (safety-related systems), exception handling, real-time programming languages, process run-time estimation Abstract: The main objective of this paper is to present a method for handling non-preventable and non-avoidable catastrophic exceptions in embedded hard real-time environments in a well-structured and predictable way, and as painlessly as possible. First, apt hardware and software platforms which are pre-requisite for predictable system behaviour are briefly presented. Then, some existing techniques are shown and their suitability for implementation in embedded hard real-time environments is discussed. Further, a classification of exceptions and our own approach for handling them is presented and elaborated. Finally, a method for the estimation of the resulting temporal behaviour is described. -------------------------------------- 5. A Novel Approach to Off-line Scheduling in Real-Time Systems Guohui Yu and Lonnie R. Welch, Department of Computer and Information Science, New Jersey Institute of Technology, University Heights, Newark, NJ 07102, Email: gray@earth.njit.edu, welch@vienna.njit.edu pp. 71-82 Keywords: real-time, multiprocessor, off-line scheduling, ADTs, replication, concurrency Abstract: This paper presents a new off-line scheduling approach for object-based real-time systems using a periodic model of execution. The approach differs from previous off-line scheduling work in that it constructs a feasible schedule by exploiting concurrency. Concurrency is achieved by replication of abstract data type (ADT) module instances to reduce contention caused by multiple accesses to shared ADTs. Concurrency is also achieved by asynchronous remote procedure calls (ARPCs), which allow caller and callee to execute concurrently. By enhancing concurrency, the execution times of processes are reduced, and the chance for finding a feasible schedule is significantly increased. -------------------------------------- 6. On-line Algorithms for Allocating Periodic-time-critical Tasks on Multiprocessor Systems Sadegh Davari, Department of Computing and Mathematics, University of Houston-Clear Lake, Houston, TX 77058 and Sudarshan K. Dhall, School of Computer Science, University of Oklahoma, Norman, Ok 73019 pp. 83-96 Keywords: scheduling, multiprocessors, time critical, on-line, heuristic algorithms, real-time Abstract: The problem of allocating a set of Periodic-Time-Critical (PTC) tasks to processors in a multiprocessor system is considered. A PTC task is a real-time task for which requests are made periodically, at some fixed interval of time, by means of some external signals. Associated with each request there is a computation time and a deadline for the completion of the computation. The Rate-Monotonic algorithm, which is an optimal static priority driven algorithm for scheduling PTC tasks on single processor systems (Liu & Layland 1973, Serlin 1972, Sha Goodenough 1990, Locke 1992), does not perform as well for multiprocessor systems (Dhall 1977, Dhall & Liu 1978, Davari 1985, Davari & Dhall 1986a, 1986b, 1986c, Oh & Son 1994). The allocation problem is to distribute a set of PTC tasks among various processors so that the tasks assigned to each processor can be feasibly scheduled on that processor using the Rate-Monotonic algorithm. Moreover, the aim is to use as few processors as possible. This problem is NP-hard (Davari 1985, Leung & Whitehead 1982). In this paper we present two heuristic on-line algorithms and analyze their complexity and worst case performance. -------------------------------------- 7. A Semi-Distributed Load Balancing Model for Parallel Real-time Systems Kayhan Erciyes, Oznur Ozkasap and Nilgun Aktas, Ege University Computer Eng. Dept., 35100 Bornova, Izmir, Turkey, E-mail: erciyes@baum01.ege.edu.tr, ozkasap@baum01.ege.edu.tr, aktas@baum01.ege.edu.tr pp. 97-109 Keywords: parallel processing, load balancing, real-time system, deterministic scheduling Abstract: We propose static and dynamic load balancing policies for parallel real-time systems. A parallel real-time system in this context is considered as a computational environment consisting of a number of processors where stringent timing requirements of processes should be met. This would encompass massively parallel systems at one end of the spectrum and a group of computers connected by a local network at the other end. The static and dynamic load balancing policies developed are suitable for both types of systems with parameters such as communication costs to be tuned for each environment. For massively parallel processing systems, we introduce the concept of a domain which is a pool of processors and is governed locally for various services such as dynamic load balancing. The dynamic load balancing is implemented by central load balancers per domain whichmake use of the group communication facility for distributed communication with the other load balancers. This semi-distributed approach eliminates the need for maintaining a central node or replicated data by providing local data and control confined to that domain. The distributed data and control transfer is performed among the servers of the domains. The static scheduler however works off line for tasks with known characteristics such as execution time, communication constraints and deadlines prior to their execution which would be the usual case for hard real-time tasks. -------------------------------------- 8. Optimal Algorithm for Real-Time Fault Tolerant Distributed Processing Using Checkpoints Zbigniew M. Wojcik and Barbara E. Wojcik, Smart Machines, 13703 Morningbluff Drive, San Antonio, TX 78216, USA, Phone: (210)496-7287, Fax:(210)496-6218 pp. 111-122 Keywords: fault-tolerant computing, distributed processing, real-time systems Abstract: The paper presents optimal algorithm for a real-time deadlock-free fault-tolerant distributed processing. Our fault tolerant computations do not incur any postponements in the underlying distributed processing and need the minimum number of messages. Both the underlying messages and the messages maintaining fault tolerance do not need to arrive in the order in which they have been sent. The method is based on the asynchronous, atomic checkpointing of the sender and receiver of a message. Messages not balanced in the last permanent checkpoints are recorded in the new checkpoints. The fault recovery is based on: a) The repetition of all messages lost according to a record of unbalanced messages in the last permanent checkpoints; and b) Undoing every message re-sent during the fault recovery, or undoing of a computation repeated according to a record of unbalanced messages in the last permanent checkpoints. Our fault recovery involves only processes which communicated before a failure. Proof of the resilience of the fault recovery algorithm is presented. -------------------------------------- 9. Fully Deterministic Real-Time Protocol for a CSMA/CD Type Local Area Network Bonaventure Tchouaffe and Janusz Zalewski, Dept. of Computer Science, Embry-Riddle Aeronautical University, Daytona Beach, FL 32114, USA Phone: (904)226-7034, Fax: (904)226-6678, E-mail: zalewski@db.erau.edu pp. 123-132 Keywords: Ethernet, CSMA/CD, real-time communication Abstract: This paper presents a new access protocol, based on a simple CSMA/CD extension to improve Ethernet's performance in real-time applications and guarantee predictability. An analysis is given of both the extended protocol and the standard CSMA/CD. Several simulation experiments are conducted to test the two protocols under a meaningful variety of load levels, measuring the time it takes each protocol to transmit a predefined packet. The results allow making the final analysis to judge each access protocol and determine if and how the problem of predictable Ethernet behavior has been solved. ---------------------------- 10. Principles of a Formal Axiomatic Structure of the Informational Anton P. Zeleznikar Volariceva ulica 8, 61111 Ljubljana, Slovenia E-mail: a.p.zeleznikar@ijs.si pp. 133-158 Keywords: axiom, circularity, derivation, functionalism, general informational theory, inclusiveness, inference rule, parallelism, propositional vs. informational, serialism Abstract: The article deals with some basic problems of a formal axiomatic structure pertaining to the phenomenalism of the informational. In this way, solid philosophical and formal foundations of an emerging informational science are set from the strict informational point of view citeprin. A general informational theory conjoins the so-called object theory and its metatheory, in contrariness to a narrower mathematical theory, where the metamathematical theory serves as an exterior means for proving of the object theory. The principles of informational axioms are treated from the dualistic point of view conjoining the axioms of the object theory and inference axioms of the metatheory. Inference rules become regular informational formulas which arise informationally as any other informational operands (entities).