BDL: a specialized language for per-object reactive control

The problem of describing the concurrent behavior of objects in object oriented languages is addressed. The approach taken is to let methods be the behavior units whose synchronization is controlled separate from their specification. Our proposal is a domain-specific language called BDL for expressing constraints on this control and actually implementing its enforcement. We propose a model where each object includes a so-called “execution controller”, programmed in BDL. This separates cleanly the concepts of what the methods do, the object processes, from the circumstances in which they are allowed to do it, the control. The object controller ensures that scheduling constraints between the object's methods are met. Aggregate objects can be controlled in terms of their components. This language has a convenient formal base. Thus, using BDL expressions, behavioral properties of objects or groups of interesting objects can be verified. Our approach allows, for example, deadlock detection or verification of safety properties, while maintaining a reasonable code size for the running controller. A compiler from BDL has been implemented, automatically generating controller code in an Esterel program, i.e., in a reactive programming language. From this code, the Esterel compiler, in turn, generates an automaton on which verifications are done. Then this automaton is translated into a C code to be executed. This multistage process typifies the method for successful use of a domain-specific language. This also allows high level concurrent programming     

The concurrency models of Ada and occam—a practical comparison

A comparison of the concurrency models of Ada and occam is presented. This comparison is performed in terms of an Ada-to-occam compiler. A subset of the Ada programming language may be compiled allowing a study of how programs and algorithms expressed using the Ada concurrency model can be mapped to the occam concurrency model. The resultant occam code may then be executed on a transputer. This paper describes the Ada and occam concurrency models, highlights the major differences between them, discusses the problems encountered in trying to map concurrent Ada programs to equivalent occam programs as a result of these differences and explains how these problems were overcome in the present compiler.     

Source Transformation for Concurrency Analysis

Concurrent programming poses a unique set of problems for quality assurance. These difficulties include the complexities of deadlock, livelock and divergence, which can be extremely difficult to detect and debug. A variety of tools have been developed to assist designers and developers of concurrent applications. Some of these tools, such as VeriSoft, are specific to particular implementation languages, such as C++.The Java Remote Method Invocation (Java RMI) package facilitates the implementation of concurrent applications, including those where processes reside on different hosts and communicate over networks. Unfortunately, it does not relieve the developer from the potential pitfalls of controlling concurrent access to remote objects, and may, in fact, make concurrency problems even more difficult to find.This paper presents an approach that allows the VeriSoft state exploration system to be used to analyze Java RMI programs for deadlock, livelock, divergence, and assertion violations. The system works by transforming Java RMI programs into C++ programs where Java syntax, structure, concurrency and memory management are replaced by C++ equivalents and Java RMI communication has been transformed to VeriSoft C++ inter-process communication. We present the details of this transformation and discuss preliminary results for a number of small examples.     

DFL: A Data Flow Language

Many novel computer architectures like array and multiprocessors which achieve high performance through the use of concurrency exploit variations of the von Neumann model of computation. The effective utilization of the machines makes special demands on programmers and their programming languages, such as the structuring of data into vectors or the partitioning of programs into concurrent processes. In comparison, the data flow model of computation demands only that the principle of structured programming be followed. A data flow program, often represented as a data flow graph, is a program that expresses a computation by indicating the data dependencies among operators. A data flow computer is a machine designed to take advantage of concurrency in data flow graphs by executing data independent operations in parallel. In this paper, we discuss the design of a high level language (DFL: Data Flow Language) suitable for data flow computers. Some sample procedures in DFL are presented. The implementation aspects have not been discussed in detail since there are no new problems encountered. The language DFL embodies the concepts of functional programming, but in appearance closely resembles Pascal. The language is a better vehicle than the data flow graph for expressing a parallel algorithm. The compiler has been implemented on a DEC 1090 system in Pascal.     

ConC++:C++的一种并发扩充语言

提出一种对Ｃ＋＋进行并发扩充的语言ＣｏｎＣ＋＋．ＣｏｎＣ＋＋是一个并发面向对象语言,它采用并发类和保护类的机制支持并发,并发类有一个主动函数,一旦对象被创建,这个主动函数就开始执行;保护类封装了一组数据和对数据的操作,它没有自己的线程,而且是用来实现对并发类对象的同步、互斥和通信,这种集中控制对象的并发的方法体现了对象的自治性特点,减少了上下切换和死锁发生的可能,从而提高了程序的性能。     

Observable Behavior of Dynamic Systems: Component Reasoning for Concurrent Objects

Current object-oriented approaches to distributed programs may be criticized in several respects. First, method calls are generally synchronous, which leads to much waiting in distributed and unstable networks. Second, the common model of thread concurrency makes reasoning about program behavior very challenging. Models based on concurrent objects communicating by asynchronous method calls, have been proposed to combine object orientation and distribution in a more satisfactory way. In this paper, a high-level language and proof system are developed for such a model, emphasizing simplicity and modularity. In particular, the proof system is used to derive external specifications of observable behavior for objects, encapsulating their state. A simple and compositional proof system is paramount to allow verification of real programs. The proposed proof rules are derived from the Hoare rules of a standard sequential language by a semantic encoding preserving soundness and relative completeness. Thus, the paper demonstrates that these models not only address the first criticism above, but also the second.     

The implementation of concurrency for a PL/I-like language

The formulation of concurrency and synchronization has been recognized as a matter of growing importance in system programming languages in order to achieve well-structured, reliable and easy to understand system software such as operating systems. Unfortunately, only experimental languages, such as Concurrent Pascal or MODULA, contain adequate linguistic constructs for support of such concepts as processes and monitors. The compilers for those languages are available only on a few machines and are devoted primarily to education. In this paper a simple method of extending a PL/I-like programming language by concurrency features is described which is based on the usage of an existing compiler. The method has proven to be a cost effective way of adopting recent research results in existing software engineering tools, thus avoiding the need of switching over to a completely new programming environment.     

并发对象的一种描述机制

面向对象模型潜在的并发计算能力为并发程序设计提供了更高层次的解决方案。为了充分利用这种潜在的并发招行能力,必须在对象模型中显式地给出并发控制。本文给出了一种描述并发对象的机制,即：把对象的并发控制作为对象的单独属性进行描述,在定义子类时,把对象的并发描述与对象的方法分开进行继承。我们的目标是使得引进的并发机制尽量少地与对象模型的各个重要特性相冲突,减轻继承异常。另外,我们提出的并发模型允许对象内部的并发。     

A formal semantics for debugging synchronous message passing-based concurrent programs

In this paper, we propose a semantic framework to debug synchronous message passing-based con- current programs, which are increasingly useful as parallel computing and distributed systems become more and more pervasive. We first design a concurrent programming language model to uniformly represent exist- ing concurrent programming languages. Compared to sequential programming languages, this model contains communication statements, i.e., sending and receiving statements, and a concurrent structure to represent com- munication and concurrency. We then propose a debugging process consisting of a tracing and a locating procedure. The tracing procedure re-executes a program with a failed test case and uses specially designed data structures to collect useful execution information for locating bugs. We provide for the tracing procedure a struc- tural operational semantics to represent synchronous communication and concurrency. The locating procedure backward locates the ill-designed statement by using information obtained in the tracing procedure, generates a fix equation, and tries to fix the bug by solving the fix equation. We also propose a structural operational semantics for the locating procedure. We supply two examples to test our proposed operational semantics.     

Observable behavior of distributed systems: Component reasoning for concurrent objects

Distributed and concurrent object-oriented systems are difficult to analyze due to the complexity of their concurrency, communication, and synchronization mechanisms. Rather than performing analysis at the level of code in, e.g., Java or C++, we consider the analysis of such systems at the level of an abstract, executable modeling language. This language, based on concurrent objects communicating by asynchronous method calls, avoids some difficulties of mainstream object-oriented programming languages related to compositionality and aliasing. To facilitate system analysis, compositional verification systems are needed, which allow components to be analyzed independently of their environment. In this paper, a proof system for partial correctness reasoning is established based on communication histories and class invariants. A particular feature of our approach is that the alphabets of different objects are completely disjoint. Compared to related work, this allows the formulation of a much simpler Hoare-style proof system and reduces reasoning complexity by significantly simplifying formulas in terms of the number of needed quantifiers. The soundness and relative completeness of this proof system are shown using a transformational approach from a sequential language with a non-deterministic assignment operator.     

主动规则的并发控制与死锁处理

在基于规则的主动数据库系统中 ,被触发规则通常以事务模式运行 ,这些并行事务由规则耦合方式确定其开始处理时刻和可串行化提交次序 .本文根据并行事务对于共享数据对象的锁继承和锁剥夺关系 ,提出了一个并发控制算法 ,并基于事务树 (森林 )给出一个有效的死锁检测算法和具有最小代价的死锁恢复算法 .     

Concurrent modeling language (CML) for discrete process modeling,simulation and control

Modern manufacturing systems can be viewed as distributed concurrent discrete processes, using extensive communication internally and with the environment. The concurrency and reactive nature of the system make it difficult to model and analyze correctly. This paper presents a genuine high level and concurrent modeling language, CML, that can be used for modeling and control of manufacturing processes. In addition, it can be used for simulation and analysis of the system's operation. The CML language is based on flat concurrent prolog which is a declarative concurrent logic programming language, therefore, highly expressive, and theoretically sound.     

Relating state-based and process-based concurrency through linear logic (full-version)

This paper has the purpose of reviewing some of the established relationships between logic and concurrency, and of exploring new ones.Concurrent and distributed systems are notoriously hard to get right. Therefore, following an approach that has proved highly beneficial for sequential programs, much effort has been invested in tracing the foundations of concurrency in logic. The starting points of such investigations have been various idealized languages of concurrent and distributed programming, in particular the well established state-transformation model inspired by Petri nets and multiset rewriting, and the prolific process-based models such as the π-calculus and other process algebras. In nearly all cases, the target of these investigations has been linear logic, a formal language that supports a view of formulas as consumable resources. In the first part of this paper, we review some of these interpretations of concurrent languages into linear logic and observe that, possibly modulo duality, they invariably target a small semantic fragment of linear logic that we call LV^obs.In the second part of the paper, we propose a new approach to understanding concurrent and distributed programming as a manifestation of logic, which yields a language that merges those two main paradigms of concurrency. Specifically, we present a new semantics for multiset rewriting founded on an alternative view of linear logic and specifically LV^obs. The resulting interpretation is extended with a majority of linear connectives into the language of ω-multisets. This interpretation drops the distinction between multiset elements and rewrite rules, and considerably enriches the expressive power of standard multiset rewriting with embedded rules, choice, replication, and more. Derivations are now primarily viewed as open objects, and are closed only to examine intermediate rewriting states. The resulting language can also be interpreted as a process algebra. For example, a simple translation maps process constructors of the asynchronous π-calculus to rewrite operators. The language of ω-multisets forms the basis for the security protocol specification language MSR 3. With relations to both multiset rewriting and process algebra, it supports specifications that are process-based, state-based, or of a mixed nature, with the potential of combining verification techniques from both worlds. Additionally, its logical underpinning makes it an ideal common ground for systematically comparing protocol specification languages.     

Temporal Semantics for Concurrent M M

Concurrent is a programming language based on the notion of concurrent, communicating objects, where each object directly executes a specification given in temporal logic, and communicates with other objects using asynchronous broadcast message-passing. Thus, Concurrent represents a combination of the direct execution of temporal specifications, together with a novel model of concurrent computation. In contrast to the notions of predicates as processes and stream parallelism seen in concurrent logic languages, Concurrent represents a more coarse-grained approach, where an object consists of a set of logical rules and communication is achieved by the evaluation of certain types of predicate. Representing concurrent systems as groups of such objects provides a powerful tool for modelling complex reactive systems. In order to reason about the behaviour of Concurrent systems, we requir a suitable semantics. Being based upon executable temporal logic, objects in isolation have an intuitive semantics. However, the addition of both operational constraints upon the object's execution and global constraints provided by the asynchronous model of concurrency and communication, complicates the overall semantics of networks of objects. It is this, more complex, semantics that we address here, where temporal semantics for varieties of Concurrent are provided.     

Preserving abstraction in concurrent programming

Recent programming languages have attempted to provide support for concurrency and for modular programming based on abstract interfaces. Building on experience of adding monitors to CLU, a language oriented towards data abstraction, it is explained how these two goals conflict. In particular, the clash between conventional views on interface abstraction and the programming style required for avoiding monitor deadlock is discussed. It is argued that the best compromise between these goals is a combination of a fine-grain locking mechanism together with a method for explicitly defining concurrency properties for selected interfaces     

A temporal programming model with atomic blocks based on projection temporal logic

Atomic blocks, a high-level language construct that allows programmers to explicitly specify the atomicity of operations without worrying about the implementations, are a promising approach that simplifies concurrent programming. On the other hand, temporal logic is a successful model in logic programming and concurrency verification, but none of existing temporal programming models supports concurrent programming with atomic blocks yet. In this paper, we propose a temporal programming model (αPTL) which extends the projection temporal logic (PTL) to support concurrent programming with atomic blocks. The novel construct that formulates atomic execution of code blocks, which we call atomic interval formulas, is always interpreted over two consecutive states, with the internal states of the block being abstracted away. We show that the framing mechanism in projection temporal logic also works in the new model, which consequently supports our development of an executive language. The language supports concurrency by introducing a loose interleaving semantics which tracks only the mutual exclusion between atomic blocks. We demonstrate the usage of αPTL by modeling and verifying both the fine-grained and coarse-grained concurrency.     

Compiler to interpreter: experiences with a distributed programming language

One interpretive approach for handling concurrency is to provide an interpreter instance for each executing language‐level process. Such an approach has mainly been applied to concurrent implementations of logic and functional languages. This paper describes the use of this approach in constructing an interpreter for an imperative, distributed programming language from an existing compiler and run‐time support system (RTS). Primary design goals were to exploit the existing compiler to the extent possible as well as to have minimal impact on the RTS used to support concurrency. We have been successful in meeting these goals. Additionally, performance results show our interpreter's execution times compare favorably to the times required for compilation, linkage, and execution of small programs or programs with a significant number of calls to the RTS; on such programs, our interpreter's performance also compares favorably to that of the standard Java implementation. However, for larger programs and programs with fewer calls to the underlying RTS, the conventional compiler‐based implementation outperforms the interpreter implementation. For many distributed programs in which network costs dominate, the performances of the two implementations differ little. Copyright © 2001 John Wiley & Sons, Ltd.     

The problem with threads

For concurrent programming to become mainstream, we must discard threads as a programming model. Nondeterminism should be judiciously and carefully introduced where needed, and it should be explicit in programs. In general-purpose software engineering practice, we have reached a point where one approach to concurrent programming dominates all others namely, threads, sequential processes that share memory. They represent a key concurrency model supported by modern computers, programming languages, and operating systems. In scientific computing, where performance requirements have long demanded concurrent programming, data-parallel language extensions and message-passing libraries such as PVM, MPI, and OpenMP dominate over threads for concurrent programming. Computer architectures intended for scientific computing often differ significantly from so-called general-purpose architectures.     

Continuation-Passing C, compiling threads to events through continuations

In this paper, we introduce Continuation Passing C (CPC), a programming language for concurrent systems in which native and cooperative threads are unified and presented to the programmer as a single abstraction. The CPC compiler uses a compilation technique, based on the CPS transform, that yields efficient code and an extremely lightweight representation for contexts. We provide a proof of the correctness of our compilation scheme. We show in particular that lambda-lifting, a common compilation technique for functional languages, is also correct in an imperative language like C, under some conditions enforced by the CPC compiler. The current CPC compiler is mature enough to write substantial programs such as Hekate, a highly concurrent BitTorrent seeder. Our benchmark results show that CPC is as efficient, while using significantly less space, as the most efficient thread libraries available.     

C++的一种并发扩充方案*

该文给出了一种对C++进行并发扩充的方案.它基于这样的并发面向对象模型：系统由一组自治的并发对象构成,对象可以有一个体,一旦对象被创建,对象体就开始执行；对象间采用同步消息传递,允许对象内部的并发；对象的并发控制分散在各方法的激励条件中.文章还给出了一种转换策略,把扩充的C++描述转换成C++描述,使之能被现有的C++编译器识别.转换中利用了某些多任务操作系统(如Windows 95)所提供的多线程和同步设施.