Experimental evaluation of software development tools for safety-critical real-time systems

Since the early years of computing, programmers, systems analysts, and software engineers have sought ways to improve development process efficiency. Software development tools are programs that help developers create other programs and automate mundane operations while bringing the level of abstraction closer to the application engineer. In practice, software development tools have been in wide use among safety-critical system developers. Typical application areas include space, aviation, automotive, nuclear, railroad, medical, and military. While their use is widespread in safety-critical systems, the tools do not always assure the safe behavior of their respective products. This study examines the assumptions, practices, and criteria for assessing software development tools for building safety-critical real-time systems. Experiments were designed for an avionics testbed and conducted on six industry-strength tools to assess their functionality, usability, efficiency, and traceability. The results some light on possible improvements in the tool evaluation process that can lead to potential tool qualification for safety-critical real-time systems.     

Phase clocks for transient fault repair

Phase clocks are synchronization tools that implement a form of logical time in distributed systems. For systems tolerating transient faults by self-repair of damaged data, phase clocks can enable reasoning about the progress of distributed repair procedures. This paper presents a phase clock algorithm suited to the model of transient memory faults in asynchronous systems with read/write registers. The algorithm is self-stabilizing and guarantees accuracy of phase clocks within O(k) time following an initial state that is.     

Logical time: capturing causality in distributed systems

Causality is vital in distributed computations. Distributed systems can determine causality using logical clocks. Human beings use the concept of causality to plan, schedule, and execute an enterprise, or to determine a plan's feasibility. In daily life, we use global time to deduce causality from loosely synchronized clocks such as wrist watches and wall clocks. But in distributed computing systems, the rate of event occurrence is several magnitudes higher, and the event-execution time several magnitudes smaller. If the physical clocks in these systems are not synchronized precisely the causality relation between events cannot be captured accurately. However, distributed systems have no built-in physical time and can only approximate it. This article presents a general framework of a system of logical clocks in distributed systems and discusses three methods: scalar, vector and matrix, for implementing logical time in these systems     

An environment for distributed prototyping of real time systems

Designing and reasoning about real-time systems are difficult activities, in which timing and reactive behaviour requirements add significant complexity to system validation. In this paper, a new technique for distributed prototyping of real-time systems is presented. It enables system prototypes to be concurrently developed and tested by a geographically distributed team, in such a way that each developer can validate his or her part of the system against the other parts which are being built in other development sites. A set of tools has been implemented that supports validation of functional and time behaviour through distributed animation of graphical prototypes with a consistent vision of simulated time.     

Timing analysis of MRL: A real-time rule-based system

This paper examines issues on how to predict timing behavior of rule-based decision systems for real-time applications. In particular, we focus on the analysis of response time of rule-based programs written in the production system language MRL. The design goal of MRL is to allow programmers to write OPS5-like rule-based programs in a language that is more amenable to formal analysis based on the semantic foundation underlying the language Unity. The language MRL, its analysis algorithms, and its execution system form a package of design tools for programming real-time rule-based decision systems.This project is partly supported by research grants from Office of Naval Research under ONR contract number N00014-89-J-1472 as well as ONR contract number N000014-89-J-1913, by a grant from Texas Advance Technology Program, and also by a grant from Texas Instruments Corporation.     

A flexible software for real-time control in nuclear fusion experiments

JETRT is a software framework particularly suited for implementation of both real-time control and data acquisition systems. It is especially designed to work in a complex experimental environment such as the JET nuclear fusion facility. This new architecture maximizes the software reusability. The project-specific algorithm is compiled into a separate software component, in order to achieve a separation from the plant interface code. JETRT provides a set of tools to perform most of the validation phase on a Windows running desktop PC. Thanks to these design choices, both the development costs and the commissioning time have been reduced and even non-specialist programmers can easily contribute to the deployment of a new real-time system.     

Logical time in distributed computing systems

The partial ordering of events as defined by their causal relationships, that is, the ability of one event to directly, or transitively, affect another is defined. Its generalized and practical implementations in terms of partially ordered logical clocks are described. Such clocks can provide a decentralized definition of time for distributed computing systems, which lack a common time base. In their full generality, partially ordered logical clocks may be impractically expensive for long-lived computations. Several possible optimizations, depending on the application environment in which the clocks will be used, are described. Some applications are summarized     

Calculating the maximum execution time of real-time programs

In real-time systems, the timing behavior is an important property of each task. It has to be guaranteed that the execution of a task does not take longer than the specified amount of time. Thus, a knowledge about the maximum execution time of programs is of utmost importance.This paper discusses the problems for the calculation of the maximum execution time (MAXT... MAximum eXecution Time). It shows the preconditions which have to be met before the MAXT of a task can be calculated. Rules for the MAXT calculation are described. Triggered by the observation that in most cases the calculated MAXT far exceeds the actual execution time, new language constructs are introduced. These constructs allow programmers to put into their programs more information about the behavior of the algorithms implemented and help to improve the self checking property of programs. As a consequence, the quality of MAXT calculations is improved significantly. In a realistic example, an improvement fator of 11 has been achieved.     

Interoperable Run-Time Tools for Distributed Systems—A Case Study

Tools that observe and manipulate the run-time behavior of parallel and distributed systems are essential for developing and maintaining these systems. Sometimes users would even need to use several tools at the same time in order to have a higher functionality at their disposal. Today, tools developed independently by different vendors are, however, not able to interoperate. Interoperability not only allows concurrent use of tools, but also can lead to an added value for the user. A debugger interoperating with a checkpointing system, for example, can provide a debugging environment where the debugged program can be reset to any previous state, thus speeding up cyclic debugging for long running programs.Using this example scenario, we derive requirements that should be met by the tools' software infrastructure in order to enable interoperability. A review of existing infrastructures shows that these requirements are only partially met today. In an ongoing research effort, support for all of the requirements is built into the OMIS compliant on-line monitoring system OCM.     

基于线性时序逻辑的实时系统模型检查

模型检查是一种用于并发系统的性质验证的算法技术.LTLC(linear temporal logic with clocks)是一种连续时间时序逻辑,它是线性时序逻辑LTL的一种实时扩充.讨论实时系统关于LTLC公式的模型检查问题,将实时系统关于LTLC公式的模型检查化归为有穷状态转换系统关于LTL公式的模型检查,从而可以利用LTL的模型检查工具来对LTLC进行模型检查.由于LTLC既能表示实时系统的性质,又能表示实时系统的实现,这就使得时序逻辑LTLC的模型检查过程既能用于实时系统的性质验证,又能用于实时系统之间的一致性验证.     

APIs for real-time distributed object programming

Ideally, according to the author, a real-time distributed programming method should be based on a general high-level style that could be easily accommodated by application programmers using C++ and Java. If such a method were to exist, these programmers could specify the interactions among distributed components and the timing requirements of various actions without expending much effort. Facilitating high-level, high precision, real-time object programming by establishing some form of language tools has consequently become a subject of great interest to the embedded systems community. This article focuses on application programming interfaces (APIs) that take the form of C++ and Java class libraries and support high-level, high precision, real-time object programming without requiring new language translators. These APIs wrap the services of the real-time object execution engines, which consist of hardware, node OSs, and middleware; they enable convenient high-level programming almost to the extent that a new real-time object language can. The author explains the API's fundamental features, how they interact among real-time objects, and how multicast channels and real-time multicast APIs contribute     

Replication Management in Reliable Real-Time Systems

Building reliable real-time applications on top of commercial off-the-shelf (COTS) components is not a straightforward task. Thus, it is essential to provide a simple and transparent programming model, in order to abstract programmers from the low-level implementation details of distribution and replication. However, the recent trend for incorporating pre-emptive multitasking applications in reliable real-time systems inherently increases its complexity. It is therefore important to provide a transparent programming model, enabling pre-emptive multitasking applications to be implemented without resorting to simultaneously dealing with both system requirements and distribution and replication issues. The distributed embedded architecture using COTS components (DEAR-COTS) architecture has been previously proposed as an architecture to support real-time and reliable distributed computer-controlled systems (DCCS) using COTS components. Within the DEAR-COTS architecture, the hard real-time subsystem provides a framework for the development of reliable real-time applications, which are the core of DCCS applications. This paper presents the proposed framework, and demonstrates how it can be used to support the transparent replication of software components.     

Data race avoidance and replay scheme for developing and debugging parallel programs on distributed shared memory systems

Distributed shared memory (DSM) allows parallel programs to run on distributed computers by simulating a global virtual shared memory, but data racing bugs may easily occur when the threads of a multi-threaded process concurrently access the physically distributed memory. Earlier tools to help programmers locate data racing bugs in non-DSM parallel programs are not easily applied to DSM systems. This study presents the data race avoidance and replay scheme (DRARS) to assist debugging parallel programs on DSM or multi-core systems. DRARS is a novel tool which controls the consistency protocol of the target program, automatically preventing a large class of data racing bugs when the parallel program is subsequently run, obviating much of the need for manual debugging. For data racing bugs that cannot be avoided automatically, DRARS performs a deterministic replay-type function on DSM systems, faithfully reproducing the behavior of the parallel program during run time. Because one class of data racing bugs has already been eliminated, the remaining manual debugging task is greatly simplified. Unlike previous debugging methods, DRARS does not require that the parallel program be written in a specific style or programming language. Moreover, DRARS can be implemented in most consistency protocols. In this paper, DRARS is realized and verified in real experiments using the eager release consistency protocol on a DSM system with various applications.     

Criticality: static profiling for real-time programs

With the increasing performance demand in real-time systems it becomes more and more important to provide feedback to programmers and software development tools on the performance-relevant code parts of a real-time program. So far, this information was limited to an estimation of the worst-case execution time (WCET) and its associated worst-case execution path (WCEP) only. However, both, the WCET and the WCEP, only provide partial information. Only code parts that are on one of the WCEPs are indicated to the programmer. No information is provided for all other code parts. To give a comprehensive view covering the entire code base, tools in the spirit of program profiling are required. This work proposes an efficient approach to compute worst-case timing information for all code parts of a program using a complementary metric, called criticality. Every statement of a program is assigned a criticality value, expressing how critical the code is with respect to the global WCET. This gives valuable information how close the worst execution path passing through a specific program part is to the global WCEP. We formally define the criticality metric and investigate some of its properties with respect to dominance in control-flow graphs. Exploiting some of those properties, we propose an algorithm that reduces the overhead of computing the metric to cover complete programs. We also investigate ways to efficiently find only those code parts whose criticality is above a given threshold. Experiments using well-established real-time benchmark programs show an interesting distribution of the criticality values, revealing considerable amounts of highly critical as well as uncritical code. The metric thus provides ideal information to programmers and software development tools to optimize the worst-case execution time of these programs.     

Probabilistic clock synchronization

A probabilistic method is proposed for reading remote clocks in distributed systems subject to unbounded random communication delays. The method can achieve clock synchronization precisions superior to those attainable by previously published clock synchronization algorithms. Its use is illustrated by presenting a time service which maintains externally (and hence, internally) synchronized clocks in the presence of process, communication and clock failures. Flaviu Cristian is a computer scientist at the IBM Almaden Research Center in San Jose, California. He received his PhD from the University of Grenoble, France, in 1979. After carrying out research in operating systems and programming methodology in France, and working on the specification, design, and verification of fault-tolerant programs in England, he joined IBM in 1982. Since then he has worked in the area of fault-tolerant distributed protocols and systems. He has participated in the design and implementation of a highly available system prototype at the Almaden Research Center and has reviewed and consulted for several fault-tolerant distributed system designs, both in Europe and in the American divisions of IBM. He is now a technical leader in the design of a new U.S. Air Traffic Control System which must satisfy very stringent availability requirements.     

HADES—A command environment that supports structure

HADES is a command program designed to aid programmers and authors involved in writing systems with an inherently high degree of structuring. It presents the system being developed in a hierarchical fashion, encouraging a top down approach to its design, and alleviates many of the problems experienced with traditional filing systems. Unlike other programming environment systems, the utility programs and tools do not have to be ‘integrated’ into the system, which means that new and existing tools can be quickly and easily added. This results in a rich set of operations implemented at very low cost. The paper outlines some of the problems that arise with traditional filing systems from the point of view of software development, and then presents the approach adopted by HADES. This is followed by a discussion of the strengths and weaknesses of the result and some reflections on the lessons that have been learnt.     

Programming and compiling strategies for paging systems

Designers of paging systems have tended to believe that programmers can influence system performance, but usually for the worse, rather than for the better. Their efforts to find operating system solutions to poorly styled programs may have discouraged efforts to produce paging-oriented compilers, to educate programmers in techniques to use under paging, and to open communication channels between the programmer and the paging system—all of which now promise to give increased satisfaction with paging systems.     

Building flexible real-time systems using the Flex language

The design and implementation of a real-time programming language called Flex, which is a derivative of C++, are presented. It is shown how different types of timing requirements might be expressed and enforced in Flex, how they might be fulfilled in a flexible way using different program models, and how the programming environment can help in making binding and scheduling decisions. The timing constraint primitives in Flex are easy to use yet powerful enough to define both independent and relative timing constraints. Program models like imprecise computation and performance polymorphism can carry out flexible real-time programs. In addition, programmers can use a performance measurement tool that produces statistically correct timing models to predict the expected execution time of a program and to help make binding decisions. A real-time programming environment is also presented