Correct compilation of specifications to deterministic asynchronous circuits

Powerful methods have been developed by A. martin and others wherby asynchronous circuits may be automatically constructed by starting from high-level specifications and incrementally transforming them into asynchronous circuits. In this paper we make the informal arguments for the correctness of this compilatin process mathematically rigorous. With rigorsouly justified transformations, specifications may be translated into circuits that provably meet their specification. A full proof of the correctness of the circuit compiler is given. Other results of independent interest include: the process model takes fairness of gates into account, hazard-freeness is formally defined, and all hazard-free circuits constructed solely of and, or, not gates and C elements are proven to behave deterministically to any outside observer. A novel notion of equivalence is used to justify the correctness of the compiler.     

A specification-based approach to concurrency analysis

The behavior of a concurrent program often depends on the arbitrary interleaving of computations performed by asynchronous processes. The resulting non-determinism can lead to such phenomena as deadlock and starvation, making program development extremely difficult, and consequently making the development of tools for formal analysis highly desirable.A specification-based approach to concurrency analysis is a particularly promising way of addressing some of the difficulties inherent in concurrent program development. According to this approach, a programmer first writes a specification describing the interprocess communication behavior of a concurrent program. A set of formal analysis techniques are then applied in an effort to determine whether the specification can be fully satisfied. If the analysis is successful, target code is generated automatically that conforms to the specification.This approach has a variety of benefits. While such properties as safety and liveness are rather difficult to discern in actual code, they are actually easy to include as part of a specification. Moreover, state spaces induced by specifications tend to be smaller and more manageable than state spaces of actual code, and this leads to more effective analysis techniques. Finally, the generation of interprocess communication code from formal specifications is accomplished in a relatively straightforward manner.Research partially supported by NSF grant CCR-9109231.     

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

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

OCCAM-an overview

The language OCCAM has been developed on the basis of communication and concurrency. OCCAM describes the structure of a system of connected microcomputers. It can also be used to program the individual computers. In addition, OCCAM is a design formalism. Its formal semantics allows a program to be read either as a set of commands or as a predicate in an extension of the predicate calculus. The semantics provides a set of rules for transforming programs.The initial implementation of OCCAM is described. Examples are given of its use in a concurrent system and for program transformation.     

CIM环境下分布数据一致性的研究与实现

提出了基于信号量的并发控制机制和两个并发控制算法，以解决异构分布的环境下，分布关系间和分布子关系间分布数据的一致性问题，提出在ＣＩＭ条件下，分布数据一致性问题的方法。     

Scheduling transactions in mobile distributed real-time database systems

A DMVOCC-MVDA （distributed multiversion optimistic concurrency control with multiversion dynamic adjustment） protocol was presented to process mobile distributed real-time transaction in mobile broadcast environments. At the mobile hosts, all transactions perform local pre-validation. The local pre-validation process is carried out against the committed transactions at the server in the last broadcast cycle. Transactions that survive in local pre-validation must be submitted to the server for local final validation. The new protocol eliminates conflicts between mobile read-only and mobile update transactions, and resolves data conflicts flexibly by using multiversion dynamic adjustment of serialization order to avoid unnecessary restarts of transactions. Mobile read-only transactions can be committed with no-blocking, and respond time of mobile read-only transactions is greatly shortened. The tolerance of mobile transactions of disconnections from the broadcast channel is increased. In global validation mobile distributed transactions have to do check to ensure distributed serializability in all participants. The simulation results show that the new concurrency control protocol proposed offers better performance than other protocols in terms of miss rate, restart rate, commit rate. Under high work load （think time is ls） the miss rate of DMVOCC-MVDA is only 14.6%, is significantly lower than that of other protocols. The restart rate of DMVOCC-MVDA is only 32.3%, showing that DMVOCC-MVDA can effectively reduce the restart rate of mobile transactions. And the commit rate of DMVOCC-MVDA is up to 61.2%, which is obviously higher than that of other protocols.     

基于Petri网模型的异步并发性

通过分析Petri网的网状结构特性,研究其描述异步并发的能力和特点．然后以Petri网的角度重新定义异步并发的概念,并结合实际异步并发应用中的特性,完成建模过程分析．最后,以教务系统中排课系统Ajax的异步传输机制为例建立模型,指导和检验系统的运行情况．     

一种网络服务器的研究与实现

在计算机网络中,应用服务器的响应速度直接影响着整个系统的性能.本文分析了网络服务器的工作模式,探讨了网络服务器的几种实现技术,并比较了这些技术的优缺点和适用范围.最后,给出了一个具体的网络服务器的实现技术和部分代码.     

Confusion diagnosis and avoidance of discrete event systems using supervisory control

Nondeterministic firing of concurrent transitions in Petri nets (PNs) may lead to the disappearance of conflicts. The disappearance implies that the partial conflicting transitions in a conflict become disabled before the resolution of the conflict. The phenomenon is called confusions that are caused by the interlacement of conflicting and concurrent transitions in PNs, which generates incomplete and faulty system conflicting behavior such that conflicts cannot be correctly resolved. In this paper, conflict‐increasing confusions (CICs) and conflict‐decreasing confusions (CDCs) in a PN are investigated. The relation graph of conflicts and confusions (RGC²) in a PN is proposed to detect the structure of confusions. To avoid the occurrence of confusions in a PN, an algorithm based on generalized mutual exclusion constraints (GMECs) is proposed, which can generate confusion‐avoidance supervisors such that the occurrence of conflicts can be ensured in a PN. Finally, an example of confusion detection and avoidance in a flexible assembly system is presented. © 2015 Institute of Electrical Engineers of Japan. Published by John Wiley & Sons, Inc.     

盘阵中基于平衡超图划分的自适应请求并发与负载平衡策略

作为一种并行系统,盘阵性能极大地依赖于设备间负载平衡;为了减少执行时间,单个I/O请求需要通过多个设备并发完成,负载平衡并不意味着请求并发,而请求并发也不能保证盘阵负载平衡.因此,必须将二者结合起来,才能使盘阵性能得到更好的优化.为此本文提出基于平衡超图划分的自适应数据分布策略,并提出了两个目标函数同时进行请求并发与负载平衡的控制,根据I/O访问模式优化盘阵性能.根据两种I/O benchmark合成负载进行模拟试验表明,该策略比传统的单方面自适应负载平衡策略或基于超图的请求并发策略效果都有一定优化.