CSP-i: An implementation of communicating sequential processes

Hoare's proposal for a notation for communicating sequential processes has led to the development of a number of concurrent languages based on the concept of message passing. CSP-i is a new language which reflects the design objectives of the original CSP notation more faithfully than most of these other languages. This paper describes the development of the language, as well as an implementation for a single processor, with simulated time-slicing providing pseudo-concurrency.     

The use of Hoare's method of program verfification for the quicksort algorithm

Using the Quicksort Algortihm, given by van Emden, an analysis is made how Hoare's method of program verification can be applied to already existing programs. Changes to these programs become necessary to adopt them to the proving method and to the existing axioms. The interdependencies between these changes and the verification method are discussed and conclusions are draw about the applicability of Hoare's Methods for proving already existing programs.     

Denotational semantics of communicating sequential programs

A denotational semantics of Hoare's Communicating Sequential Programs is given based on a mathematical model of communicating processes as functions mapping for every initial state a stream of offers onto a set of streams of reactions plus a final state, which is defined only if the program terminates properly. The main purpose of this definition is found in serving as a reference for specification and verification methods.     

Resource monitors: A design methodology for operating systems

Resource manager objects are the operating system entities that manage computer system resources. In this paper we extend Hoare's and Brinch Hansen's monitor concept, and introduce a resource monitor language construct that represents a resource manager object. Resource monitors provide requesting processes with implicit synchronization, and do not require separate processes to perform the resource access operations. The resource monitor construct is compared to current language constructs used to structure operating system software. For this purpose we use an evaluation methodology that combines software complexity measurements with program performance measurements. The evaluation itself is carried out in a Concurrent Pascal-like programming environment. The current language constructs have a software complexity that is larger by 37 to 219 per cent over the resource monitor's complexity. The run-time synchronization overhead of programs that use current language constructs is 1.43 to 2.75 times higher than the overhead of programs that use a resource monitor.     

Using Ada for discrete event simulation

The process interaction approach is proposed for developing a discrete simulation environment in Ada. The introduction of simulation facilities in Ada not only concerns the classical aspect of model building, but allows a new class of problems to be tackled, that is the testing of correctness of programs intended for real-time applications. In this paper attention is focused on the presentation of the process scheduling in the simulation context and on the definition of standard forms of interactions among processes. Simulation facilities are organized by making use of Ada's structuring concepts.     

Remote rendezvous

BNR Pascal is a systems programming language intended for the implementation of the systems software of distributed computing systems. It supports the Ada Rendezvous model of tasking and communication, uniformly extended to support communications between tasks distributed over the computing nodes of a system. BNR Pascal was designed and implemented in 1980, and has since been used to implement the operating systems and real-time applications software for Northern Telecom's Meridian family of products. In total, more than 2 million lines of BNR Pascal exist. This paper describes the BNR Pascal remote rendezvous: the extension of rendezvous to interprocessor communication. It discusses the implementation of remote rendezvous, describing the advantages and disadvantages of several options. Finally, it details BNR's experience in using remote rendezvous in building substantial, practical distributed systems used in products.     

The cyclic executive model and Ada

Periodic processes are major parts of many real-time embedded computer applications. The programming language Ada permits programming simple periodic processes, but it has some serious limitations; producing Ada programs with real-time performance comparable to those produced to date using traditional cyclic executives requires resorting to techniques that are specific to one machine or compiler. We present and evaluate the cyclic executive model for controlling periodic processes. The features and limitations of Ada for programming cyclic executive software are discussed and demonstrated, and some practical techniques for circumventing Ada limitations are described.     

Input/output in high level programming languages

A system's input/output is its communication with the other systems in its environment. By viewing the relationship as communication between partners, we identify the fundamental requirements in input/output programming, and discuss the responses of various programming languages to these requirements. Traditional programming languages provide either nothing or an expensive incomplete solution. The new languages Modula and Ada now offer major improvements in this area. We describe the style of their solutions, and give corresponding guidance for low-level input/output programming.     

On the Implementation and Use of Ada on Fault-Tolerant Distributed Systems

In this paper, we discuss the use of Ada® on distributed systems in which failure of processors has to be tolerated. We assume that tasks are the primary object of distribution, and that communication between tasks on separate processors will take place using the facilities of the Ada language. It would be possible to build a separate set of facilities for communication between processors, and to treat the software on each machine as a separate program. This is unnecessary and undesirable. In addition, the Ada language Reference Manual states specifically that a system consisting of communicating processors with private memories is suitable for executing an Ada program.     

A proof outline logic for object-oriented programming

This paper describes a proof outline logic that covers most typical object-oriented language constructs in the presence of inheritance and subtyping. The logic is based on a weakest precondition calculus for assignments and object allocation which takes field shadowing into account. Dynamically bound method calls are tackled with a variant of Hoare's rule of adaptation that deals with the dynamic allocation of objects in object-oriented programs. The logic is based on an assertion language that is closely tailored to the abstraction level of the programming language.     

Proof rules for fault tolerant distributed programs

Proving the properties of a program which must execute on a distributed system whose nodes may fail is a complex task. Such proofs must take into account the effects of hardware failures at all possible points in the execution of individual processes. The difficulty in accomplishing this is compounded by the need to cater also for the simultaneous failure of two or more processing nodes. In this paper, we consider programs written in a version of Hoare's CSP and define a set of axioms and inference rules by which proofs can be constructed in three steps: proving the properties of each process when its communicants are prone to failure, establishing the effects of failure of each process, and combining these two steps to determing the fault tolerant properties of the whole program. The proof system is thus compositional, in the sense that proofs can be constructed in a modular way.     

Processes, Tasks, and Monitors: A Comparative Study of Concurrent Programming Primitives

Three notations for concurrent programming are compared, namely CSP, Ada, and monitors. CSP is an experimental language for exploring structuring concepts in concurrent programming. Ada is a general-purpose language with concurrent programming facilities. Monitors are a construct for managing access by concurrent processes to shared resources. We start by comparing "lower-level" communication, synchronization, and nondeterminism in CSP and Ada and then examine "higher-level" module interface properties of Ada tasks and monitors.     

分布式Ada语言系统的实现

基于Ada 95参考手册附录E“分布式系统”中的思想,提出了实现分布式Ada语言系统的一些概念和设计思想,并给出了实现分区通信子系统的具体方案.在此基础上,通过一些前置处理,并利用已实现的分区通信子系统的接口,实现了分布式Ada语言系统.最后通过一个实例,具体介绍了分布式Ada语言系统的程序设计方法.     

Real-time interrupt handling in Ada

The Ada? programming language defines the semantics of interrupt handling as part of the tasking mechanism, making it possible to construct implementation-independent interrupt handlers. However, for the Ada mechanism to be effective, an implementation must provide support not specified by the Ada standard, such as for initializing hardware interrupting devices, handling unexpected interrupts and optimizing for real-time performance constraints. This paper analyses some of the constraints that efficient interrupt support places on an implementation. It develops a model for the interaction between interrupt hardware and Ada tasks and describes optimizations for Ada interrupt handlers. Implementation issues, including task priorities and task termination for interrupt handlers, are discussed in detail.     

Performance of multi-tasking and synchronization mechanisms in the programming language SR

High-level language primitives for concurrent programming exist in languages such as Ada and Modula-2. However, each of these languages provides only a single means for specifying multitasking and synchronization, essential in the implementation of concurrent systems. The SR language provides several mechanisms for specifying multi-tasking and synchronization, so it can be used to explore the performance of various communication techniques. This paper presents performance results for SR's multi-tasking and synchronization mechanisms and discusses the effects of the generated code, the run-time support and the hardware on these results. These results are compared with those for similar mechanisms in other languages, leading to some general conclusions about the performance of process communication primitives. These performance results can be used by programmers to make design choices that allow systems programs written in high-level languages to meet real-time performance specifications.     

Introspective Sorting and Selection Algorithms

Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Θ(N log N), and it is in fact faster than most other sorting algorithms on most inputs. Its drawback is that its worst-case time bound is Θ(N²). Previous attempts to protect against the worst case by improving the way quicksort chooses pivot elements for partitioning have increased the average computing time too much – one might as well use heapsort, which has a Θ(N log N) worst-case time bound, but is on the average 2–5 times slower than quicksort. A similar dilemma exists with selection algorithms (for finding the i-th largest element) based on partitioning. This paper describes a simple solution to this dilemma: limit the depth of partitioning, and for subproblems that exceed the limit switch to another algorithm with a better worst-case bound. Using heapsort as the ‘stopper’ yields a sorting algorithm that is just as fast as quicksort in the average case, but also has an Θ(N log N) worst case time bound. For selection, a hybrid of Hoare's FIND algorithm, which is linear on average but quadratic in the worst case, and the Blum–Floyd–Pratt–Rivest–Tarjan algorithm is as fast as Hoare's algorithm in practice, yet has a linear worst-case time bound. Also discussed are issues of implementing the new algorithms as generic algorithms, and accurately measuring their performance in the framework of the C+:+ Standard Template Library. ©1997 by John Wiley & Sons, Ltd.     

Emerald: A general-purpose programming language

Emerald is a general-purpose language with aspects of traditional object-oriented languages, such as Smalltalk, and abstract data type languages, such as Modula-2 and Ada. It is strongly typed with a non-traditional object model and type system that emphasize abstract types, allow separation of typing and implementation, and provide the flexibility of polymorphism and subtyping with compile-time checking. This paper describes the Emerald language and its programming methodology. We give examples that demonstrate Emerald's features, and compare and contrast the Emerald approach to programming with the approaches used in other similar languages.     

分布式环境中Ada并行任务的识别和调度

给出了 Ａｄａ并行任务模块的识别算法和Ａｄａ并行任务通信开销矩阵的计算方法,在此基础上,提出了分布式环境中Ａｄａ并行任务的调度算法。     

Distributing concurrent Ada programs by source translation

This paper tackles the practical aspects of obtaining a distributed version of an Ada program. It proposes the use of an adapter, which can be a methodology or an automatic translator. The adapter accepts source of a concurrent Ada program, adds communication and control tasks, and produces source for a single distributed Ada program, which can then be compiled and run on a multi-processor computer. The original program can consist of packages and tasks, and both of these can be classed as virtual nodes. The process of adaption does not alter the contents of any package in the original program, so that the method is directly applicable to systems that make use of library and generic packages. The communication between virtual nodes, which would normally reside as one per processor, is via messages on a ring, but the protocols are kept as simple as possible, and the messages are fully checked Ada types, rather than byte strings. The method has been applied to programs of the client-server model, and could be adapted for other rendezvous-based languages such as occam.