Reproducible execution of SR programs

Reproducing the execution of a concurrent program is important in debugging and testing. It requires that, regardless of the actual order in which processes may execute, the reproduced execution is identical, with respect to the order in which certain activities occur, to a previously recorded execution. This paper presents a solution to the reproducibility problem for programs written in the SR concurrent programming language. Our solution transforms an arbitrary SR program into one for recording an event sequence and one for replaying from an event sequence. SR provides a rich collection of synchronization mechanisms, including rendezvous, asynchronous message passing, remote procedure call, and dynamic process creation. SR language features allow: flexible invocation servicing (e.g. use of invocation parameters in selecting an invocation to service in message passing or rendezvous); dynamically created processes and resource (module) instances; dynamic communication paths between processes; and dynamic distribution of programs across multiple machines. Because of these features, adaptations of previous solutions to the reproducibility problem for other languages and notations do not work for SR. Our solution handles all the above features. It results in a naturally distributed control algorithm for programs that are distributed. This paper also describes the implementations of our transformation tools. Copyright © 1999 John Wiley & Sons, Ltd.     

An SR approach to multiway rendezvous

This paper presents a new approach to programming multiway rendezvous problems in the SR language. The approach uses SR's concurrent invocation statement and rendezvous mechanism to coordinate the interacting processes. This approach is compared with one that suggested an extension to SR's rendezvous mechanism. The two approaches result in differing program structure. The new approach is shown to lead to simpler and cleaner interfaces between the main process and the worker processes, and uses only existing language mechanisms. The results are of importance to both programmers and designers of concurrent program languages.     

RJ: a Java package providing JR‐like concurrent programming

The JR concurrent programming language extends Java with a richer concurrency model, by adding several new types and statements. JR provides dynamic remote virtual machine creation, dynamic remote object creation, remote method invocation, dynamic process creation, rendezvous, asynchronous message passing, semaphores, concurrent invocation, and shared variables. This paper presents RJ, a package for Java that provides JR‐like features. The paper gives an overview of RJ and its key features; describes the implications of RJ's design, including how RJ provides additional, useful flexibility; discusses the implementation of RJ; and gives qualitative and quantitative evaluations of our work with respect to feasibility and usability, experimentation, migration, and performance. RJ has been successful in meeting these goals and in providing insight into the trade‐offs between using a concurrent programming language versus using the equivalent concurrent package. Our work has yielded a few surprises in dealing with some concurrent programming language features, in understanding the run‐time performances of JR versus RJ programs, and in obtaining some additional, useful flexibility for concurrent programming applications. Copyright © 2015 John Wiley & Sons, Ltd.     

New mechanisms for invocation handling in concurrent programming languages

Invocation handling mechanism in many concurrent languages have significant limitations that make it difficult or costly to solve common programming situations encountered in program visualization, debugging, and scheduling scenarios. This paper discusses these limitations, introduces new language mechanisms aimed at remedying these limitations, and presents an implementation of the new mechanisms. The examples are given in SR; the new mechanisms and implementation are an extension of SR and its implementation. However, these new mechanisms are applicable to other concurrent languages. They can augment or replace current invocation handling mechanisms.     

User accessible reply capabilities in invoking and servicing operations

Many message passing languages and packages include some form of synchronous invocation. In a synchronous invocation, the invoker waits for the invocation's servicer to pass back results. A synchronous invocation can be viewed as a pair of asynchronous invocations: one—initiating the computation—with parameter values from the invoker to the servicer and the other—once the requested computation has completed—with the ‘go‐ahead’ and return value from the servicer to the invoker. The target of the latter invocation is known as the reply operation, and a reference to it is known as a reply capability. This paper addresses the issues of making such reply capabilities directly accessible to user code. It presents the design and prototype implementation of a new version of the JR concurrent programming language, called xJR, in which the reply capability can be explicit. This paper gives xJR examples, including realistic ones, to highlight the additional flexibility the new features offer (such as a non‐lexical reply). These additional features do not impact the run‐time performance of existing JR features and can even lead to more efficient code in some programming scenarios. Our experience with the prototype implementation indicates that an actual implementation would be fruitful and would preserve the prototype's performance advantages. Copyright © 2015 John Wiley & Sons, Ltd.     

Kernel-Kernel communication in a shared-memory multiprocessor

In the standard kernel organization on a bus-based multiprocessor, all processors share the code and data of the operating system; explicit synchronization is used to control access to kernel data structures. Distributed-memory multicomputers use an alternative approach, in which each instance of the kernel performs local operations directly and uses remote invocation to perform remote operations. Either approach to interkernel communication can be used in a large-scale shared-memory multiprocessor. In the paper we discuss the issues and architectural features that must be considered when choosing between remote memory access and remote invocation. We focus in particular on experience with the Psyche multiprocessor operating system on the BBN Butterfly Plus. We find that the Butterfly architecture is biased towards the use of remote invocation for kernel operations that perform a significant number of memory references, and that current architectural trends are likely to increase this bias in future machines. This conclusion suggests that straightforward parallelization of existing kernels (e.g. by using semaphores to protect shared data) is unlikely in the future to yield acceptable performance. We note, however, that remote memory access is useful for small, frequently-executed operations, and is likely to remain so.     

A timed semantics of Orc

Orc is a kernel language for structured concurrent programming. Orc provides three powerful combinators that define the structure of a concurrent computation. These combinators support sequential and concurrent execution, and concurrent execution with blocking and termination.Orc is particularly well-suited for task orchestration, a form of concurrent programming with applications in workflow, business process management, and web service orchestration. Orc provides constructs to orchestrate the concurrent invocation of services while managing time-outs, priorities, and failures of services or communication.Our previous work on the semantics of Orc focused on its asynchronous behavior. The inclusion of time or the effect of delay on a computation had not been modeled. In this paper, we define an operational semantics of Orc that allows reasoning about delays, which are introduced explicitly by time-based constructs or implicitly by network delays. We develop a number of identities among Orc expressions and define an equality relation that is a congruence. We also present a denotational semantics in which the meaning of an Orc program is a set of traces, and show that the two semantics are equivalent.     

Pattern matching and pattern-directed invocation in systems programming languages

Pattern recognition systems in the artificial intelligence field have been based on the assumption that components of the system should be invoked not by directly calling them, but by running data across their sensors and having the invocation take place when a defined pattern is found. Most systems programming, however, has taken a completely different route; the emphasis there is on structures of execution and data types. A new approach to systems programming languages where a bridge is made between structure and pattern-directed invocation is described. The syntax of pattern-directed invocation, along with the semantics of a support structure for message receiving and sending necessary for pattern-directed invocation of routines is presented. Finally, some conclusions are made about pattern-directed invocation, and further areas of work are stated.     

Object Clustering for High Performance Parallel Computing

In this article we present a new parallel programming environment, called distributed object-oriented virtual computing environment (DOVE), for clustered computers based on distributed object model. In DOVE, a parallel program is built as a collection of concurrent objects each of which has its own computing power and which interacts with one another by remote method invocation. The parallelism is encapsulated within distributed objects, which can be handled the same way as local objects. The main goal of DOVE is to provide users with an easy-to-use transparent parallel programming environment while supporting efficient parallelism encapsulated and distributed among objects. For the experiment and evaluation of DOVE, two parallel application programs have been developed both on DOVE and PVM.     

Computation Orchestration

The widespread deployment of networked applications and adoption of the internet has fostered an environment in which many distributed services are available. There is great demand to automate business processes and workflows among organizations and individuals. Solutions to such problems require orchestration of concurrent and distributed services in the face of arbitrary delays and failures of components and communication. We propose a novel approach, called Orc for orchestration, that supports a structured model of concurrent and distributed programming. This model assumes that basic services, like sequential computation and data manipulation, are implemented by primitive sites. Orc provides constructs to orchestrate the concurrent invocation of sites to achieve a goal – while managing time-outs, priorities, and failure of sites or communication.     

Safety,liveness and fairness in temporal logic

In this paper we present syntactic characterization of temporal formulas that express various properties of interest in the verification of concurrent programs. Such a characterization helps us in choosing the right techniques for proving correctness with respect to these properties. The properties that we consider include safety properties, liveness properties and fairness properties. We also present algorithms for checking if a given temporal formula expresses any of these properties.This work is partly supported by NSF grant CCR-9212183. A preliminary version of this paper appeared in the Fourth ACM Symposium on Principles of Distributed Computing.     

并发Java程序动态分析及重演技术研究

Java语言在并发程序方面的广泛应用对软件测试提出了新的挑战。众所周知,由于并发程序的不确定性,使得并发程序的设计、开发、调试和测试都非常困难。文章介绍了Safepro／Java中的多线程测试技术,通过对Java源程序进行适当的修改并且保持语义不变,跟踪并发Java程序的运行过程,收集有关数据并对数据进行分析,最终控制并发Java程序的重演。     

Design of an empirical study for comparing the usability of concurrent programming languages

Context: Developing concurrent software has long been recognized as a difficult and error-prone task. To support developers, a multitude of language proposals exist that promise to make concurrent programming easier. Empirical studies are needed to support the claim that a language is more usable than another.Objective: This paper presents the design of a study to compare concurrent programming languages with respect to comprehending and debugging existing programs and writing correct new programs. The design is applied to a comparison of two object-oriented languages for concurrency, multithreaded Java and SCOOP.Method: A critical challenge for such a study is avoiding the bias that might be introduced during the training phase and when interpreting participants’ solutions. We address these issues by the use of self-study material and an evaluation scheme that exposes any subjective decisions of the corrector, or eliminates them altogether.Results: The study template consisting of the experimental design and the structure of the self-study and evaluation material is demonstrated to work successfully in an academic setting. The concrete instantiation of the study template shows results in favor of SCOOP even though the study participants had previous training in writing multithreaded Java programs.Conclusion: It is concluded that the proposed template of a small but therefore easy-to-implement empirical study with a focus on core language constructs is helpful in characterizing the usability of concurrent programming paradigms. Applying the template to further languages could shed light on which approaches are promising and hence drive language research into the right direction.     

Modules,objects and distributed programming: Issues in RPC and remote object invocation

Distributed programming can be greatly simplified by language support for distributed communication, such as that provided by remote procedure call (RPC) or remote object invocation. This paper examines design and implementation issues in these systems, and focuses on the influence of the communication system on a distributed program. To make the discussion concrete, we introduce a single application as implemented in two environments: Modula-2+, an extension of Modula-2 with RPC, and Emerald, an object-based language that supports remote object invocation. We show that small differences in the implementation of the communication system can have a significant impact on how distributed applications are structured.     

An implementation of the object-oriented concurrent programming language SINA

SINA is an object-oriented language for distributed and concurrent programming. The primary focus of this paper is on the object-oriented concurrent programming mechanisms of SINA and their implementation. This paper presents the SINA constructs for concurrent programming and inter-object communication, some illustrative examples and a message-based implementation model for SINA that we have used in our current implementation.     

Concurrent programming in VISO

Concurrent programming is more difficult to use and understand than sequential programming. In order to simplify this type of programming a number of approaches have been developed such as visual programming. Visual Occam (VISO) is a visual programming language for concurrent programming. It has a graphical syntax based on the language Occam and its semantics is represented both in petri net and process calculus. This paper presents a modular visual approach to write concurrent programs using the VISO language. Concurrent programs in VISO are specified graphically at different levels of abstraction. This paper describes this modular visual approach by constructing two examples in VISO. The first example is a simple concurrent program and it is mainly used to show the details of constructing a concurrent program in VISO. The second example is a larger concurrent program with more levels of abstraction. Copyright © 2000 John Wiley & Sons, Ltd.     

基于消息的离散事件仿真方法

本文提出了一种基于沙息的离散事件仿真方法,它将面向对象的程序设计方法,分布式仿真和并行算法的概念结合在一起,与传统的离散事件仿真方法相比,是一种更加灵活而直观的模型仿真方法。     

A Fully Abstract Semantics for Concurrent Constraint Programming

A compositional and fully abstract semantics for concurrent constraint programming is developed. It is the first fully abstract semantics which takes into account both non-determinism, infinite computations, and fairness. We present a simple concurrent constraint programming language, whose semantics is given by a set of reduction rules augmented with fairness requirements. In the fully abstract semantics we consider two aspects of a trace, viz. the function computed by the trace (the functionality) and the set of input and output data (the limit of the trace). We then derive the fully abstract semantics from the set of traces using a closure operation. We give two proofs of full abstraction; the first relies on the use of a syntactically infinite context. The second proof requires only a finite context, but assumes as input a representation of the function to be computed by the context. Finally, we examine the algebraic properties of the programming language with respect to the fully abstract semantics. It turns out that the non-deterministic selection operation can be defined using operations derived from parallel composition and the usual set-theoretic operations on sets of traces.     

一种利用适合性测试支持方法重定向的演算

一些面向上下文的编程语言使用结构化的块结构(block-structured construct)将方法调用重定向到层中方法.但该结构无法支持层的动态添加与激活,这增加了程序可执行文件的大小.为了解决该问题,提出一种新方法:使用适合性测试支持方法的重定向,并定义一个运行时的适合性测试演算(runtime fitness testing calculus on top offeatherweight Java calculus)形式化描述该方法.该演算以FJ 演算(featherweight Java calculus)为核心,通过融入新的语言结构——层,基于上下文的方法查找与对象转化描述基于适合性测试的方法重定向,分析它对程序类型安全的影响,制定相应约束,并证明在满足该约束的条件下能够保持程序的类型安全,从而证明所提方法的有效性.以该演算为指导,描述如何通过扩展Java 的编译器与虚拟机,实现将层、基于上下文的方法查找与对象转化融入到Java 语言,并通过实验测试实现,证明所提方法的可行性.该演算及其实现可用于指导如何扩展类似Java(Java-like)的语言以支持程序基于上下文动态调整其行为,并同时保证程序的类型安全.