An Approach to Platform Independent Real-Time Programming: (1) Formal Description

A method for extending programming languages with timing constructs is proposed. It enables the specification of timing constraints in programs. The approach is not language specific and the extension can be included in many existing programming languages. With the extension it is possible to write real-time program components that can be proven correct independently of the properties of the machine that is used for their execution. It therefore provides a similar abstraction from the execution platform as is normal in non-real-time programming. The presented approach distinguishes two phases in system construction: (1) a platform-independent programming phase that includes the expression of timing requirements, and (2) an implementation phase where all platform dependencies are addressed. The latter only differs from a normal compilation in the sense that a feasible schedule must be found to execute the program.     

The Variety of Variables in Automated Real-Time Refinement

The refinement calculus is a well-established theory for deriving program code from specifications. Recent research has extended the theory to handle timing requirements, as well as functional ones, and we have developed an interactive programming tool based on these extensions. Through a number of case studies completed using the tool, this paper explains how the tool helps the programmer by supporting the many forms of variables needed in the theory. These include simple state variables as in the untimed calculus, trace variables that model the evolution of properties over time, auxiliary variables that exist only to support formal reasoning, subroutine parameters, and variables shared between parallel processes.     

Computer-aided development of a real-time program

The refinement calculus is a well-established theory for formal development of imperative program code and is supported by a number of automated tools. Via a detailed case study, this article shows how refinement theory and tool support can be extended for a program with real-time constraints. The approach adapts a timed variant of the refinement calculus and makes corresponding enhancements to a theorem-prover based refinement tool.     

Real-time refinement in Manna and Pnueli's temporal logic

A refinement calculus for the development of real-time systems is presented. The calculus is based upon a wide-spectrum language called TAM (the Temporal Agent Model), within which both functional and timing properties can be expressed in either abstract or concrete terms. A specification oriented semantics is given for the language. Program development is considered as a refinement process i.e. thecalculation of a structured program from an unstructured specification. An example program is developed.     

一种面向嵌入式实时软件的需求建模语言

针对嵌入式实时系统复杂动态交互行为和严格实时的领域特征,提出了一种软件需求规约语言RTRSM。该语言以扩充的层次并发有穷状态机HCA为核心,以支持合成的模板为基本组成单元．利用转换有效期和事件预定机制来描述时间限制,既具有较强的时间限制描述能力,又能自然而直接地支持交互行为的建模,可执行且具有良好的形式语义。给出了该语言的形式化语法,举例说明了其时间描述机制,并通过执行步算法和基于HCA项的结构化操作规则定义了该语言的形式化操作语义。     

Compiling real-time programs with timing constraint refinement andstructural code motion

We present a programming language called TCEL (Time-Constrained Event Language), whose semantics are based on time-constrained relationships between observable events. Such a semantics infers only those timing constraints necessary to achieve real-time correctness, without overconstraining the system. Moreover, an optimizing compiler can exploit this looser semantics to help tune the code, so that its worst-case execution time is consistent with its real-time requirements. In this paper we describe such a transformation system, which works in two phases. First, the TCEL source code is translated into an intermediate representation. Then an instruction-scheduling algorithm rearranges selected unobservable operations and synthesizes tasks guaranteed to respect the original event-based constraints     

A Modular Approach to Programming Distributed Real-Time Systems

Conventional real-time programs associate real-time requirements with individual commands in a program. This approach has three weaknesses. First, it intermixes two different design concerns: functional correctness and temporal correctness. Second, by mixing real-time requirements with program statements it makes it harder, and in some cases infeasible, to specify constraints between objects. Third, it limits the ability to independently modify either the timing constraints or the representations of objects. We describe a new approach that separates real-time constraints from functional aspects of an application; real-time constraints are described by synchronization code between the interfaces of objects. Objects in our system are defined using a real-time variant of the Actor model. We define a high-level programming language construct calledRTsynchronizer, which specifies a collection of temporal constraints between actors. Thus, our approach separates what an object does from when it does it. Such separation also facilitates the ability to dynamically modify real-time constraints. We illustrate the use of RTsynchronizers by a number of examples and then describe a meta-architecture that can be used to implement RTsynchronizers.     

Real-Time Execution Monitoring

Today's programming methodology emphasizes the study of static aspects of programs. In practice, however, monitoring a program in execution, i.e., monitoring a process, is routinely done by any programmer whose task it is to produce a reliable piece of software. There are two reasons why one might want to examine the dynamic aspects of a program: first, to evaluate the performance of a program, and hence to assess its overall behavior; and second, to demonstrate the presence of programming errors, isolate erroneous program code, and correct it. This latter task is commonly called ``debugging a program' and requires a detailed insight into the innards of a program being executed. Today, many computer systems are being used to measure and control real-world processes. The pace of execution of these systems and their control programs is therefore bound to timing constraints imposed by the real-world process. As a step towards solving the problems associated with execution monitoring of real-time programs, we develop a set of appropriate concepts and define the basic requirements for a real-time monitoring facility. As a test case for the theoretical treatment of the topic, we design hardware and software for an experimental real-time monitoring system and describe its implementation.     

The Variety of Variables in Computer-Aided Real-Time Programming

The refinement calculus is a well-established theory for translating specifications to program code. Recent research has extended the calculus to handle real-time requirements and we have developed an interactive support tool based on these extensions. Via a case study, this paper shows how the tool helps the programmer by supporting the many forms of variables used in the theory. These include simple state variables as in the untimed calculus, timed-trace variables that model the evolution of properties over time, and auxiliary variables that exist to support formal reasoning only.     

Real-time Concurrent C: A language for programming dynamic real-time systems

Concurrent C, is a parallel superset of C (and of C++) that provides facilities such as specifying timeouts during process interactions, delaying program execution, accepting messages in a user-specified order, and asynchronous messages that can be used for writing real-time programs. However, Concurrent C does not provide facilities for specifying strict timing constraints, e.g., Concurrent C only ensures that the lower bounds on the specified delay and timeout periods are satisfied. Real-Time Concurrent C extends Concurrent C by providing facilities to specify periodicity or deadline constraints, to seek guarantees that timing constraints will be met, and to perform alternative actions when either the timing constraints cannot be met or the guarantees are not available.In this paper, we will discuss requirements for a real-time programming language, briefly summarize Concurrent C, and motivate and describe the real-time extensions to Concurrent C. We also discuss scheduling and other run-time facilities that have been incorporated to support the real-time extensions. A prototype implementation of Real-Time Concurrent C is nearing completion.     

Separate compilation of hierarchical real-time programs into linear-bounded Embedded Machine code

Hierarchical Timing Language (HTL) is a coordination language for distributed, hard real-time applications. HTL is a hierarchical extension of Giotto and, like its predecessor, based on the logical execution time (LET) paradigm of real-time programming. Giotto is compiled into code for a virtual machine, called the Embedded Machine (or E machine). If HTL is targeted to the E machine, then the hierarchical program structure needs to be flattened; the flattening makes separate compilation difficult, and may result in E machine code of exponential size. In this paper, we propose a generalization of the E machine, which supports a hierarchical program structure at runtime through real-time trigger mechanisms that are arranged in a tree. We present the generalized E machine, and a modular compiler for HTL that generates code of linear size. The compiler may generate code for any part of a given HTL program separately in any order.     

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     

Complete worst-case execution time analysis of straight-line hard real-time programs

In this article, the problem of finding a tight estimate on the worst-case execution time (WCET) of a hard real-time program is addressed. The analysis is focused on straight-line code (without loops and recursive function calls) which is quite commonly found in synthesised code for embedded systems. A comprehensive timing analysis system covering both low-level (assembler instruction level) as well as high-level aspects (programming language level) is presented. The low-level analysis covers all speed-up mechanisms used for modern superscalar processors: pipelining, instruction-level parallelism and caching. The high-level analysis uses the results from the low-level to compute the final estimate on the WCET. This is done by a heuristic for searching the longest really executable path in the control flow, based on the functional dependencies between various program parts.     

An Approach to Platform Independent Real-Time Programming: (2) Practical Application

In a previously published companion paper a method for extending programming languages with timing constructs was proposed. It was shown that the extension enables the construction of real-time programs that can be proven correct independently of the properties of the machine that is used for their execution. It also yields a strict division of system construction into two phases: (1) a platform-independent programming phase that includes the expression of timing requirements, and (2) an implementation phase where all platform dependencies are addressed. In this second paper the approach is illustrated using an example problem often quoted in the literature: the mine-pump system. The two mentioned phases are described in detail for this example. First, a program is obtained in a systematic way. Then, realizations of the program under various schemes for distribution and scheduling are considered and analyzed. A comparison with other approaches to real-time programming is given.     

A theoretical basis for stepwise refinement and the programming calculus

A uniform treatment of specifications, programs, and programming is presented. The treatment is based on adding a specification statement to a given procedural language and defining its semantics. The extended language is thus a specification language and programs are viewed as a subclass of specifications. A partial ordering on specifications/programs corresponding to ‘more defined’ is defined. In this partial ordering the program/specification hybrids that arise in the construction of a program by stepwise refinement form a monotonic sequence. We show how Dijkstra's calculus for the derivation of programs corresponds to constructing this monotonic sequence. Formalizing the calculus thus gives some insight into the intellectual activity it demands and allows us to hint at further developments.     

Functional Parallel Typified Language and Its Implementation on Clusters

In the paper, a functional parallel programming system implemented on clusters is discussed. It includes a language of compositional functional parallel programming, program development tools, and tools for controlling parallel code execution on the clusters.     

Measuring and analyzing real-time performance

To satisfy the deadline requirements of hard real-time systems, programmers must be able to determine the maximum execution time of any task. The use of Flex, an experimental real-time language being developed for the Concord project, is examined. The Flex system embodies an empirical approach that first measures the actual timing behavior and then uses the measurement results to determine the parameters of a programmer-supplied timing model. This timing model gives the system the programmer's understanding of the program's timing behavior in terms of its asymptotic time complexity. The measurement system determines the exact values of model parameters using sophisticated statistical methods to derive the program's timing characteristics precisely. Flex is better than performance analyzers that examine only code because it can cope with more kinds of program structures and its does not depend on an underlying hardware model. The integration of measurement and formal analysis is discussed     

An object-oriented real-time programming language

The real-time object model, an extended object-oriented model for describing real-time systems, is described. The design and implementation of RTC++, a programming language that extends C++ on the basis of the real-time object model, are discussed. The schedulability analysis and specification of rigid timing constraints in systems with active objects are reviewed