Abstracts:

Marcin Paprzycki
Department of computer Science and Statistics, The University of Southern Mississippi, Hattiesburg, MS 39406-5106, USA; marcin@orca.st.usm.edu
Janusz Zalewski
Department of Computer Science, Embry-Riddle Aeronautical University, Daytona Beach, FL 32114-3900, USA; zalewski@db.erau.edu

The purpose of this Introduction is to present the rationale behind selecting the structure of this Special Issue. It follows the general scheme of real-time systems' development: from requirements specification, to design, to implementation. A bibliography of books on parallel and distributed real-time systems for the last ten years is also included.

Real-Time Systems have two major characteristics: they always interact with the environment other than the human operator, and usually deal with timing constraints, mostly in a form of deadlines on the reaction to external stimuli. Because responsiveness and timeliness are so important in their behavior, real-time systems are almost exclusively concurrent, that is, consist of multiple program units, usually called tasks or processes, running simultaneously to perform required functions. Concurrent execution of tasks on a single processor may be in many respects inadequate for achieving the required level of performance or required level of reliability -- the two primary system requirements. Therefore the tasks are often moved to different interconnected processors, making a real-time system parallel or distributed. Although it is sometimes hard to distinguish between parallel and distributed systems, especially in real-time computing, the principal distinction between the two is that of the communication speed versus processing speed. If the communication time between processing units is negligible with respect to the processing speed, then the system is called parallel; otherwise it is distributed.

Our approach to real-time systems, in general, is based on the system development view: from application requirements, to specification and design, to implementation issues considered on three different levels, that is, programming languages, operating systems, and hardware architectures. From the system development point of view, it does not make any difference whether a system is to be implemented on a single processor or on a parallel or distributed architecture; the development process must proceed in the same way. Therefore the sequence of articles in this special issue resembles the system development process and is structured in that way.

The first article, by McKay and Atkinson, discusses one of the most demanding applications for a real-time system: a part of the NASA's Mission project. Our interest in this paper is not that much in the solutions, which are described on a relatively general level, but in system requirements, which include reliability, safety and security. The major characteristic of an application described in this article is that as systems get more and more complicated, a unified approach to account for critical system properties, such as those listed above, combined with real-time properties is needed. Such systems are usually called high-assurance systems or high-integrity systems.

Because of extremely critical nature of high-assurance systems, whose failure may involve loss of lives, loss of precious property or significant environmental damage, unconventional development methods are needed to ensure their correctness. One very promising, although not fully tested yet, approach to ensure correctness on the high level of development is the use of formal methods. These are the methods that employ proof techniques to ensure that the system is correct. In the article by van Katwijk and Toetenel, one such formal method, named MOSCA, is presented. MOSCA, based on an extension of VDM (Vienna Development Method), is a specification language providing facilities to specify real-time requirements for parallel and distributed applications.

Moving from the specification to the design level, system developers need to be equipped with modern methodology, usually consisting of the rigorous notation, techniques for development, and support tools. One such approach, object-oriented technology received significant attention in the last decade, but not necessarily for real-time systems development. In the article by Lin, Kung and Hsia, an object-oriented approach is presented to designing real-time systems whose critical system properties constitute a dominant part of the requirements and play a significant role in the development.

To convert the system/software design into a running application, the implementor usually faces a problem of dealing with programming language constructs to support design concepts. Of the many constructs that explicitly support real-time, parallel, and distributed programming, one still needs further development: exception handling. Colnaric, Verber and Halang deal with eception handling in their paper. Again, this problem is especially important because of the necessity to meet critical requirements in exceptional situations and the major contribution of this article is in providing exceptions on the language level.

If the implementation is to run according to the specification, the language constructs ought to be adequately mapped onto and supported by the operating system kernel. A real-time kernel, and especially a parallel or ditributed real-time kernel, needs to provide specific functionality which is very different from traditionalunderstanding of an operating system. Corresponding problems are so critical that this special issue includes four articles related to this subject.

The first paper in this group, by Yu and Welch, presents an off-line scheduling approach based on the analysis of tasks' behavior for concurrency enhancement. The second paper, by Davari and Dhall, discusses two heuristic on-line algorithms to solve the allocation problem, that is, the assignment of tasks to processors so they can successfully meet deadlines. The next paper, by Erciyes, Ozkasap and Aktas, describes a dynamic load balancing mechanism for massively parallel processing systems, and finally, a paper by Wojcik and Wojcik presents a universal method of achieving fault tolerance in a distributed system via checkpointing.

As the implementors well know, finding the perfect solutions to the most difficult software problems may be not enough, if the underlying hardware architecture is not functioning properly. From the multitude of problems which can be listed on the architecture level of a parallel or distributed real-time system, only one is tackled here, that of hardware guarantees on communication deadlines. Tchouaffe and Zalewski, in their article, deal with the problem of predictability of Ethernet -- one of the most widely used local area networks.

Although we attempted to provide readers with a comprehensive coverage of problems and their solutions in parallel and distributed real-time systems, certainly no such coverage can be exhaustive. Those readers who are especially interested in this topic and want to pursue further studies may want to look into three other collections of papers or access some of the books on this subject which have been published throughout the last ten years and are listed below.

Keywords: Parallel Computing, Distributed Systems, Real-Time Systems

Charles W. McKay
University of Houston - Clear Lake, 2700 Bay Area Boulevard, Houston, TX. 77058; mckay@cl.uh.edu
Colin Atkinson
University of Houston - Clear Lake, 2700 Bay Area Boulevard, Houston, TX. 77058.

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.
(pp. 7-24)

Keywords: distribution, environments, non-stop, real-time, safety-critical

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

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.(pp. 25-42)

Keywords: MOSCA language, multiple threads, semantic basis

Jyhjong Lin, David Chenho Kung and Pei Hsia
Computer Science Engineering, The University of Texas at Arlington, P.O. BOX 19015, Arlington, TX 76019-001; jlinkunghsia@cse.uta.edu

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.(pp. 43-58)

Keywords: object-oriented conceptual modeling, distributed and parallel real-time system, control flow, safety, failure, analysis

M. Colnaric
University of Maribor, Faculty of Technical Sciences, Smetanova 17, Maribor, Slovenia ; colnaric@uni-mb.si
D. Verber
University of Maribor, Faculty of Technical Sciences, Smetanova 17, Maribor, Slovenia.
W. A. Halang
FernUniversitat Hagen, Faculty of Electrical Engineering, D-58084 Hagen, Germany; wolfgang.halang@fernuni-hagen.de

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.(pp. 59-69)

Keywords: hard real-time systems, high-integrity requirements (safety-related systems), exception handling, real-time programming languages, process run-time estimation

Guohui Yu
Department of Computer and Information Science, New Jersey Institute of Technology, University Heights, Newark, NJ 07102; gray@earth.njit.edu
Lonnie R. Welch
Department of Computer and Information Science, New Jersey Institute of Technology, University Heights, Newark, NJ 07102; welch@vienna.njit.edu

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. (pp. 71-82)

Keywords: real-time, multiprocessor, off-line scheduling, ADTs, replication, concurrency

Sadegh Davari
Department of Computing and Mathematics, University of Houston-Clear Lake, Houston, TX 77058
Sudarshan K. Dhall
School of Computer Science, University of Oklahoma, Norman, Ok 73019.

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. (pp. 83-96)

Keywords: scheduling, multiprocessors, time critical, on-line, heuristic algorithms, real-time

Kayhan Erciyes
Ege University Computer Eng. Dept., 35100 Bornova, Izmir, Turkey; erciyes@baum01.ege.edu.tr
Oznur Ozkasap
Ege University Computer Eng. Dept., 35100 Bornova, Izmir, Turkey; ozkasap@baum01.ege.edu.tr
Nilgun Aktas
Ege University Computer Eng. Dept., 35100 Bornova, Izmir, Turkey; aktas@baum01.ege.edu.tr

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.(pp. 97-109)

Keywords: parallel processing, load balancing, real-time system, deterministic scheduling

Zbigniew M. Wojcik and Barbara E. Wojcik
Smart Machines, 13703 Morningbluff Drive, San Antonio, TX 78216, USA.

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.(pp. 111-122)

Keywords: fault-tolerant computing, distributed processing, real-time systems

Bonaventure Tchouaffe
Department of Computer Science, Embry-Riddle Aeronautical University, Daytona Beach, FL 32114, USA.
Janusz Zalewski
Department of Computer Science, Embry-Riddle Aeronautical University, Daytona Beach, FL 32114, USA; zalewski@db.erau.edu

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.(pp. 123-132)

Keywords: Ethernet, CSMA/CD, real-time communication

Anton P. Zeleznikar
Volariceva ulica 8, 61111 Ljubljana, Slovenia; a.p.zeleznikar@ijs.si

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).(pp. 133-158)

Keywords: axiom, circularity, derivation, functionalism, general informational theory, inclusiveness, inference rule, parallelism, propositional vs. informational, serialism