An axiomatic semantics for the synchronous language Gentzen

We propose an axiomatic semantics for the synchronous language Gentzen, which is an instantiation of the paradigm Timed Concurrent Constraint Programming proposed by Saraswat, Jagadeesan and Gupta. We view Gentzen as a prototype of the class of state-oriented synchronous languages, since it offers the basic constructs that are shared by the languages in the class. Since synchronous concurrency cannot be simulated by arbitrary interleaving, we cannot exploit “head normal forms”, on which axiomatic theories for asynchronous process calculi are based. We suggest how axiomatic semantics for other state-oriented synchronous languages can be obtained by expressing constructs of such languages in terms of Gentzen constructs.     

Memory management of safety-critical hard real-time systems designed in SystemJ

SystemJ is a programming language based on the Globally Asynchronous Locally Synchronous (GALS) Model of Computation (MoC) used to design safety critical hard real-time systems. SystemJ uses the Java programming language as the “host” language, for carrying out data computations, because Java provides clearly defined operational semantics, type and memory safety in the form of the Garbage Collector(GC), which help with formal functional verification. The same GC, which helps in functional verification, makes Worst Case Reaction Time (WCRT)¹ analysis challenging. Any WCRT analysis framework for GALS programs needs to consider the operations performed by the host language. It has been shown that the worst case time estimates for garbage collection cycles are in seconds, whereas the program’s WCRT itself is in micro-seconds. These pessimistic estimates render the WCRT analysis framework ineffective. In order to overcome this problem, we develop a compiler assisted memory management technique for applications written in SystemJ. The SystemJ MoC plays the central role in the proposed technique. The SystemJ MoC allows clearly demarcating the state boundaries of the program, which in turn allows us to partition the heap, at compile time, into two distinct areas: (1) the memory area called the permanent heap, which holds objects that are alive throughout the life time of the application, and (2) the memory area used to hold all other objects, called the transient heap. The size of these memory areas are bounded statically. Furthermore, the memory allocation and reclaim procedures are simple load and pointer reset operations, respectively, which are guaranteed to complete within a bounded number of clock-cycles, thereby alleviating the need for large pessimistic WCRT bounds obtained due to the GC. Experimental results also show that the proposed approach is approximately three times faster, in terms of memory allocation times as compared to standard real-time GC approaches.     

Formal modelling and verification of GALS systems using GRL and CADP

A GALS (Globally Asynchronous, Locally Synchronous) system consists of several synchronous components that evolve concurrently and interact with each other asynchronously. The design of GALS systems is tedious and error-prone due to the high degree of synchronous and asynchronous concurrency present in complex architectures. In this paper, we present GRL (GALS Representation Language), a formal language designed to model GALS systems, for the purpose of formal verification of the asynchronous aspects. GRL combines the synchronous reactive model underlying dataflow languages and the asynchronous concurrent model underlying process algebras. We propose a translation from GRL to LNT, a value-passing concurrent language with classical process algebra flavour. This makes possible the analysis of GRL specifications using all the state-of-the-art simulation and verification functionalities provided by the CADP toolbox.     

As-if-serial exception handling semantics for Java futures

Exception handling enables programmers to specify the behavior of a program when an exceptional event occurs at runtime. Exception handling, thus, facilitates software fault tolerance and the production of reliable and robust software systems. With the recent emergence of multi-processor systems and parallel programming constructs, techniques are needed that provide exception handling support in these environments that are intuitive and easy to use. Unfortunately, extant semantics of exception handling for concurrent settings is significantly more complex to reason about than their serial counterparts.In this paper, we investigate a similarly intuitive semantics for exception handling for the future parallel programming construct in Java. Futures are used by programmers to identify potentially asynchronous computations and to introduce parallelism into sequential programs. The intent of futures is to provide some performance benefits through the use of method-level concurrency while maintaining as-if-serial semantics that novice programmers can easily understand — the semantics of a program with futures is the same as that for an equivalent serial version of the program. We extend this model to provide as-if-serial exception handling semantics. Using this model our runtime delivers exceptions to the same point it would deliver them if the program was executed sequentially. We present the design and implementation of our approach and evaluate its efficiency using an open source Java virtual machine.     

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.     

A process oriented semantics of the PRAM-language FORK

The parallel language FORK [1], based on a scalable shared memory model, is a PASCAL-like language with some additional parallel constructs. A PRAM (Parallel Random Access Machine) algorithm can be expressed on a high level of abstraction as a FORK program which is translated into efficient PRAM code guaranteeing theoretically predicted runtimes.

In this paper, we concentrate on those features of the language FORK related to parallelism, such as the group concept, a shared memory access and synchronous or asynchronous execution. We present a trace-based denotational interleaving semantics where processes describe synchronous computations. Processes are created or deleted dynamically and run asynchronously. Interleaving rules reflect the underlying CRCW (concurrent-read-concurrent-write) PRAM model.     

Tile Formats for Located and Mobile Systems

Standard SOS formats are limited in their ability to define the operational semantics of process calculi with concurrency, causality, and mobility, and with bound names and name generation mechanisms. In this paper we describe a general approach, based on the tile model, to the definition of the operational semantics of process calculi. By providing tile systems for located CCS and asynchronous π-calculus we demonstrate that the proposed approach is more suited than SOS to provide a uniform treatment of concurrency and mobility within a compositional framework.     

Automated transformations from UML behavior models to contracts

In model driven architecture （MDA）, system requirements are first captured by UML （unified mod- eling language） use cases with sequence diagrams to describe their intended use and implemented by classes of objected-oriented languages in the subsequent design stages. It is important that the dynamic behavior specified by the sequence diagrams is in full compliance with the implementation classes. This paper proposes an auto- matic approach and tool support for generating class contracts, which define a precondition and a postcondition for each operation of the class. The former serves as a guard to ensure invocations of the operations respect the semantics introduced by the sequence diagrams, and the latter places the system in a legal state to facilitate the succeeding operation calls. The contracts can be easily mapped to code of an object-oriented language such as Java. Thus, the approach helps to bridge the gap between the requirements and design stages of system development process. We use our model transformation tool to first generate a UML protocol state machine from the sequence diagrams, and then derive the contracts for a controller class. The transformations take into account the concurrency and critical constructs of the respective UML diagrams.     

A continuation‐based task programming model for C++: design of the Causeway library

There is a big class of problems that requires writing programs in an asynchronous manner. Cloud computing, service‐oriented architectures, multi‐core and heterogeneous systems all require programs to be written with asynchronous components. The necessity of concurrency and asynchronous execution brings in the added complexity of the inversion of control into the system, either through message passing or through event processing. In this paper, we introduce explicit programming language support for asynchronous programming that completely hides inversion of control. The presented programming model defines a common abstraction of the different types of tasks, both synchronous and asynchronous. It defines common imperative control constructs equivalent to those of the host programming language, along with a few more advanced ones for transactional and parallel execution that can universally work for any task type. It allows the programmer to implement the logic of an asynchronous system in a natural way by writing simple, seemingly, synchronous imperative code. We will show that the programs written using this approach are easier to understand by programmers. They are also easier to design automated tests for, and for performing computer‐based static analysis of the program logic. The principles behind this approach were tested in a couple of real‐world systems with worldwide user base. Our experience shows that it makes the complex code with a lot of interdependencies between asynchronously executed tasks easy to write and reason about. Copyright © 2016 John Wiley & Sons, Ltd.     

LET模型的时间语义编程语言

嵌入式实时系统的正确性不仅取决于计算结果的正确性,更取决于产生结果时间的正确性.然而软件不确定的并发执行带来系统时间行为不可预测问题,使得验证复杂度升高,成本增加,为此实时系统领域提出了许多实时编程语言来提高系统的时间可预测性.LET(logical execution time)模型结合了同步模型ZET(zero e...     

一个基于SQL的并发控制机制

传统的读写事务模型（由ｒｅａｄ（ｘ）和ｗｒｉｔｅ（ｘ）序列组成）不能使调度机制充分利用应用程序的语义信息对事务进行灵活调度，从而不能有效提高系统的并发度．本文根据ＳＱＬ语言的操作语义，给出了基于ＳＱＬ的事务模型．利用这种事务模型并结合２ＰＬ方法，设计了并发控制机制：Ｃｏｎｄｉｔｉｏｎ—ｌｏｃｋｉｎｇ．这个机制可以：（１）避免数据库中的幽灵（ｐｈａｎｔｏｍ）问题，（２）利用应用程序的语义信息和完整性约束提高系统的并发度，（３）减少发生死锁的机会．因此，这是一个实用的并发控制机制．     

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.     

Scala and Lift Functional Recipes for the Web

Today, there's significant interest in functional languages and frameworks that fit the Web better than imperative languages. We explore Scala, an OO-functional language on the Java virtual machine, and Lift, a framework implemented on Scala's functional features. The Scala language offers functional programming features and asynchronous message-passing concurrency alongside a statically typed model. Lift exploits this model to offer secure, higher-level abstractions to Web developers.     

Translating Java for Multiple Model Checkers: The Bandera Back-End

One approach to model checking program source code is to view a model checker as a target machine. In this setting, program source code is translated to a model checker’s input language using a process that shares much in common with program compilation. For example, well-defined intermediate program representations are used to stage the translation through a series of analyses and optimizing transformations and target-specific details are isolated in code generation modules.In this paper, we present the Bandera Intermediate Representation (BIR)—a guarded-assignment transformation system language that has been designed to support the translation of Java programs to a variety of model checkers. BIR includes constructs, such as inheritance, dynamic creation of data, and locking primitives, that are designed to model the semantics of Java primitives. BIR also includes several non-deterministic choice constructs that support abstraction in modeling and specification of properties of dynamic heap structures.We have developed a BIR-based tool infrastructure that has been applied to develop customized analysis frameworks for several different input languages using different model checking tools. We present BIR’s type system and operational semantics in sufficient detail to support similar applications by other researchers. This semantics details several state space reductions and state space search variations. We describe the translation of Java to BIR and how BIR is translated to the input languages of several model checkers.     

Goto and Concurrency Introducing Safe Jumps in Esterel

Esterel is a design language for the specification of real time embedded systems. Based on the synchronous concurrency paradigm, its semantics describes execution as a succession of instants of computation. In this work, we consider the introduction of a new gotopause instruction in the language, which acts as a non-instantaneous jump instruction compatible with concurrency. It allows the programmer to activate state control points anywhere in the program, from where the execution is resumed in the next instant. In order to provide the formal semantics of the extended language, we first define a state semantics of Esterel, which we prove observationally equivalent to the original logical behavioral semantics. Including gotopause in the state semantics is then straightforward. We sketch two key applications of our new primitive: a direct encoding of automata and a quasi-linear rewriting of programs eliminating schizophrenic behaviors.     

基于Java的RMI技术的研究与应用

Java语言因其突出的简单性、可移植性、安全性和支持并发机制的程序设计等优良特性,使它成为基于Internet网络应用开发的首选语言。其价值主要体现在强大的开发分布式网络应用的能力上,而RMI则是开发纯Java的网络分布式应用系统的核心解决方案。通过对Java RMI分布式应用程序实例的分析,给出了Java RMI分布式应用程序的实现和运行方法,为Java语言应用开发人员提供参考。     

Using atomic await commands to develop concurrent programs in Java

Systematic techniques for dealing with concurrency can be very helpful in concurrent programming. In his concurrent programming text, Andrews [2] describes a technique for developing concurrent programs based on first developing solutions using course-grained atomic commands and atomic await primitives (which are usually not available in real programming environments), then systematically transforming the solution to an implementation that uses available synchronization primitives. Transformations are known for semaphores, conditional critical regions, and monitors. In this paper, transformations are given for the synchronization constructs provided by the Java programming language [1]. Familiarity with the basic facilities to support concurrency provided by Java is assumed.