基于交互式定理证明的并发程序验证工作综述

并发程序与并发系统可以拥有非常高的执行效率和相对串行系统较快的响应速度,在现实中有着非常广泛的应用。但是并发程序与并发系统往往难以保证其实现的正确性,实际应用程序运行中的错误会带来严重的后果。同时,并发程序执行时的不确定性会给其正确性验证带来巨大的困难。在形式化验证方法中,人们可以通过交互式定理证明器严格地对并发程序进行验证。本文对在交互式定理证明中可用于描述并发程序正确性的验证目标进行总结,它们包括霍尔三元组、可线性化、上下文精化和逻辑原子性。交互式定理证明方法中常用程序逻辑对程序进行验证,本文分析了基于并发分离逻辑、依赖保证逻辑、关系霍尔逻辑等理论研究的系列成果与相应形式化方案,并对使用了这些方法的程序验证工具和程序验证成果进行了总结。     

Transformations for early reply and forward message passing mechanisms

Message passing notations (language, package, etc.) typically include some form of asynchronous or synchronous invocation. In a synchronous invocation, the invoker waits for the invocation's servicer to pass back results. Some message passing notations also include early reply or deferred reply (including forwarding), which alters how and when the servicer passes back its results; this additional flexibility is useful in realistic applications. It is well known how to transform a synchronous invocation into only asynchronous invocations. This paper extends such transformations to early reply and forward. This paper also describes the use of these transformations within the implementations of programming notations. Using the transformation simplifies the implementation without significantly affecting run‐time costs. Copyright © 2015 John Wiley & Sons, Ltd.     

基于Soot的Java程序竞争静态检测工具设计

设计了基于Soot字节码分析框架并实现了软件原型,利用Soot提供的Spark指向分析框架对整个程序做出指向分析,在此基础上拓展了Soot分析框架,对每个可能竞争对进行线程局部对象分析、可能并行分析、别名锁分析,数据竞争结果逐步精确.     

一种基于Hadoop的动态树增量更新方法

为适应真实环境中数据量大、流程复杂、计算密集的数据挖掘需求,提高传统树增量更新挖掘效率,改变已有算法的串行执行方式,提出一种基于Hadoop的动态树增量更新方法。介绍云计算、模型与执行流程等基本概念,针对现有Hadoop平台中任务调度的随机分配策略,设计一种动态云平台中的资源调度与分配算法,以期达到成本消耗的最小化,给出树增量更新挖掘算法以及2个并行算法（DeleteFreqTree和FindNewTree）,完成树数据的增量挖掘工作。实验结果表明,该并行算法有效可行,具有高效性与良好的扩展率,能够对海量树数据进行更新挖掘。     

面向对象应用软件中对象与关系型数据库之间运行机制相关联的软件设计模式

在面向对象的应用软件中,广泛存在着对象中的数据和方法与关系型数据库之间相关联的问题。目前使用的主流数据库多是关系型的,并且使用SQL作为查询和报表生成语言。对于面向对象的应用软件来说,需要归纳出一种有效并读写一致的摄取和更新关系型数据库中数据的机制。本文对对象与关系型数据库之间相关联的软件设计模式进行了研究,使用统一建模语言UML完成比软件设计模式更为具体的软件构造实现,并且使用该方法对一假设的网上银行系统进行建模研究。     

复制式协同特征造型中并发控制的研究*

一个好的并发控制方法应在操作不发生冲突的同时具有最大限度的并发度。针对复制式协同设计提出了一种基于特征依赖关系的自适应粒度的并发控制方法,极大地提高了协同设计的并发度,最后采用C++编程语言结合WinSocket技术建立一个实现该并发控制方法的协同特征造型系统。     

支持多线程的空间数据GSQL解析器设计与实现*

为了使基于ingres扩展的空间数据库支持多线程空间数据上传和下载,设计实现了一个支持多线程的GSQL解析器。在分析PostGIS解析器的基础上,通过全局变量封装,实现解析器对多线程的支持。为了提高GSQL解析器的效率,提出并实现了可变长内存池管理机制。通过验证,GSQL解析器在多线程上传和下载空间数据时性能优良,而且使用可变长的内存池管理机制大幅度提高了GSQL解析器的时空效率。     

Event fairness and non-interleaving concurrency

Event fairness suitable for non-interleaving concurrency is proposed. Fairness is viewed with respect to concurrency, rather than non-determinism, in the sense that no concurrent component of the system should be delayed indefinitely. Shields' asynchronous transition systems and Mazurkiewicz's traces have been used; the model gives rise to a partial order. A class of generalised notions of (weak, strong and unconditional) event fairness relative to progress requirements is derived. The weakest fairness notion in this class is shown to coincide with maximality with respect to the partial order over traces.     

解决分布式数据库2PL执行-提交冲突的一种改进的乐观方法

分布式数据库系统通常采用2PL(两阶段锁定协议)来维护其一致性.本文运用Shadow-Opt方法,通过区分写操作将新旧算法结合从而保证一致性并提高性能.     

An optimal distributed solution to the dining philosophers problem

An optimal distributed solution to the dining philosophers problem is presented. The solution is optimal in the sense that it incurs the least communication and computational overhead, and allows the maximum achievable concurrency. The worst case upper bound for concurrency is shown to ben div 3,n being the number of philosophers. There is no previous algorithm known to achieve this bound.