对象库的并发控制

本文提出了适于工程设计环境的并发控制技术－－动态确认并发控制模式。与传统商业应用相比,该环境中的事务持续时间一般很长,因此它需要新的并发控制技术。动态确认是乐观的并发控制模式,避免了对数据长时间的上锁。它产生的操作是“关于数据库可串行化的”,即认为只要产生相同结果,则该调度就和从同一初始数据库状态开始执行的事务串行操作等价。显然,这个串行化标准是弱于通用串行化标准的。     

并发对象中双层结构的同步控制模型

随着Internet网迅速普及,特别是对NOW研究的不断深入,以及并行计算机的推广应用,人们对并发程序的开发需求不断增加,而传统的功能分解方法给并发程序的复用带来了困难,因此有必要将面向对象方法融入并发程序设计以增强程序的易复用性和易扩充性。     

并发对象的一种描述机制

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

多库中并发控制的研究和实现

多库是一组分布在多个结点上自制的数据库系统的集合,每个局部数据库系统可能使用不同的并发控制协议。自制和异构为保证多库系统的全局可串性带来了困难。本文首先描述了多库中全局可串性问题,然后介绍了并发控制服务CCS系统的特点及系统的逻辑流程,最后讨论了系统中各个接口对象的设计及实现。     

TSO内存模型下限界可线性化的可判定性研究

TSO-to-TSO可线性化、TSO-to-SC可线性化和TSO可线性化是Total Store Order（简称TSO）内存模型下可线性化的三个变种。在本文中我们提出了?-限界TSO-to-TSO可线性化和?-限界TSO可线性化,考察了?-限界TSO-to-TSO可线性化、?-限界TSO-to-SC可线性化和?-限界TSO可线性化的验证问题。它们分别是这三种可线性化的限界版本,都使用?-扩展历史,这样的扩展历史对应的执行有着限界数目（不超过?个）的函数调用、函数返回、调用刷出和返回刷出动作。?-扩展历史对应执行中的写动作数目是不限界的,进而执行中使用的存储缓冲区的大小也是不限界的,对应的操作语义是无穷状态迁移系统,所以三个限界版本可线性化的验证问题是不平凡的。 我们将定义在并发数据结构与顺序规约之间的?-限界TSO-to-TSO可线性化、?-限界TSO-to-SC可线性化和?-限界TSO可线性化的验证问题归约到?-扩展历史集合之间的TSO-to-TSO可线性化问题,从而以统一的方式验证了TSO内存模型下可线性化的三个限界版本。验证方法的关键步骤是判定一个并发数据结构是否有一个特定的?-扩展历史。我们证明了这个问题是可判定的,证明方法是将这一问题归约为已知可判定的易失通道机器的控制状态可达问题。本质上,这一归约将每一个函数调用或函数返回动作转化为写、刷出或cas（compare-and-swap）动作。在TSO-to-TSO可线性化的定义中,一个函数调用或函数返回动作会同时影响存储缓冲区和控制状态。为了模拟函数调用或函数返回动作对存储缓冲区的影响,我们在每个函数调用或函数返回动作之后立刻执行一个特定的写动作。这个写动作及其对应的刷出动作模拟了函数调用或函数返回动作对存储缓冲区的影响。我们引入观察者进程,为每个函数调用或函数返回动作“绑定”一个观察者进程的cas动作,以这种方式模拟了函数调用或函数返回动作对控制状态的影响。因此,我们证明了TSO内存模型下可线性化的这三个限界版本都是可判定的。我们进而证明了在TSO内存模型下判定可线性化的这三个限界版本的复杂度都在递归函数的Fast-Growing层级中。我们通过证明已知对应复杂度的单通道简单通道机器的可达问题和TSO内存模型下可线性化的三个限界版本可以互相归约得到这个结论。     

一种对象粒度的Java程序并发错误检测框架

由于多线程程序执行的复杂性和不确定性,Java程序中的并发错误难以被检测和修复.不变式检测方法作为目前最为有效的检测手段,采用提取正确程序行为的方式,能自动识别程序并发错误.但是,传统的不变式检测方法基于单个字段分析程序行为,不考虑程序中的关联变量间的依赖关系,所以无法检测多个关联变量引发的并发错误.针对这一问题,本文实现了一个对象粒度的不变式检测框架OBJ-D,基于对象操作分析程序行为.OBJ-D通过记录对象的读写依赖,能反映同一对象中多个变量间的依赖关系,为检测多变量并发错误创造了条件.测试表明,在不影响训练敏感度和性能开销的前提下,OBJ-D能同时有效检测单变量和多变量引发的并发错误,并只引入很少的假阳性.     

集中式CSCW环境中对实时共享对象的并发控制算法

在实时CSCW环境中，必然存在多个用户都需要同时访问的共享对象，系统必须对用户访问对象的操作做出实时的响应，以使对象的变化与用户的期望相一致，本文提出了一种解决并发控制的方法，目标是在并发和实时的情况下实现多客户感知的对象一致性，算法基于变换和用户期望，利用前向变换来构建对象的历史记录。     

自动验证并发实时系统的线性时段性质

介绍了一个就线性时段性验证实时系统正确性的工具的设计思想以及相关算法,使用时间自动机作为产时系统的描述模型,同时,为了便珩描述并发实时系统,使用带共享变量和通道的时间自动机网作为模型描述并发实时系统,在检验时间自动机网时,用户可以使用工具提供的合成程序将其合并为一个时间自动机然后进行检验,由于时间自动机的状态空间是无究的,通过引入整数状态和状态等价关系的概念,将整个状态0空间划分为有限的状态等价类空间,模型检验过程只需要通过对等价类空间的搜索就可以完成,但往往等价类空间的规模很大,超出了现在计算机的处理能力,原始搜索算法仅仅在理论上是可知地的,为了增工具的使用性,工具中使用的算法运用了一些优化技术来避免对等价类空间的穷尽搜索,使得工具在使用时具有比较好的时间和空间效率。     

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

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

并发系统的模型和自动验证

时序逻辑可以很好地应用于描述和验证并发系统的动态特性。AMC(Model Checker for Asynchronous concurrent systems)代替传统的从公理出发的形式推导,将并发系统描述转换为系统状态模型,然后应用模型实现对系统时序特性的自动验证。AMC能处理一般形式的合理性问题,并能对大的并发系统进行层次结构模型验证。     

程序切片技术在并发程序模型检查中的应用

模型检查技术在硬件和协议设计方面已经取得很大成功,但在软件验证方面仍存在很多困难。其主要问题是如何从源代码中自动抽取验证所要模型并精简其状态空间。文中通过对程序切片技术的研究,来解决并发程序验证的建模问题,包括把验证公式映射到切片准则．并把得到的程序切片转化为验证所需的模型。经程序切片处理后,软件模型检查效率得到提高。     

并发非阻塞自组织链表算法

利用自组织链表处理局部性较强的请求可提高性能,而非阻塞算法则能保证健壮性和可靠性。基于此,提出一种并发非阻塞自组织链表算法。使用MTF并发规则进行自组织操作,采用同步原语CAS实现并发程序,以保证查找、插入和删除操作的可线性化。实验结果表明,与Heller、Harris算法相比,随着读操作比例增大、链表变长,该算法的性能得到迅速改善。当读操作比例为90%、键值范围为4096时,其消耗时间最少。     

基于并行对象的可视化模型

提出了一种基于并行对象的可视化模型,该模型中吸取了数据流图、Petri-net和UML技术中的基本思想,通过使用数据流图来确定数据加工状态,从而初步得到并行对象的雏形,然后使用Petri-net来描述并行对象的动态特征,最后使用UML对并行对象的静态信息进行描述。通过静态描述和动态描述自动为用户生成并行程序的代码框架。     

具有并发类库的C++

本文探讨如何通过类库将并发性引入顺序面向对象语言.以C++为例,在并发类库中提供并发类及相应工具,使之支持分布并行的面向对象程序设计.本文介绍并发类库及语言底层支撑系统的设计与实现,最后给出初步测试结果.     

一种大规模并行程序模型的检测方法

JPF是NASA开发的Java程序模型检测工具。该文通过改写JPF内核中生成状态空间的模块,使待检测程序在受监控状态下模拟执行。用Data-Race算法收集警告信息,引导程序模型检测工具只对死锁相关线程进行模型检测,避免了状态空间爆炸,实现了对大规模并行程序部分线程死锁问题的模型检测。利用启发式搜索算法,在不同的搜索深度赋给待执行线程不同的权值,进一步优化了模拟执行 结果。     

论交叠式并发控制系统

建立了交叠式并发控制系统的理论基础,把整个控制系统建立在交叠式并发(存储对象控制)的计算机体系结构之上,整个控制系统需要这种计算机的硬件、操作系统和编译系统的支持。首先,用对象作为主线索贯穿交叠式并发控制系统的组成方式、运行过程和开发过程。一个交叠式并发控制系统由一些对象组合而成;另外,外部环境中任何一个控制单元及其所附带的(异常)消息可以随时启动相应的某个对象的方法执行,这样就可能出现几个对象的方法交叠地并发执行;最后,它的设计过程是先进行总体设计,按功能和接口分解出一个个对象,然后利用编译系统随时往计算机中添加(生成)任意一个对象。     

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.     

面向图形对象的协同编辑系统的并发操作冲突检测

协同者的并发操作的冲突是引发不一致的主要原因，因而并发操作的冲突判别则是系统开发的一个重要的方面．本文分析了基于图形对象的协同编辑系统的并发操作冲突的机理，给出了操作命令的一般表示方法，提出一个通用的基于该描述的冲突判别推理方法，并基于不同领域知识将该方法用于二维绘图系统和三维产品特征建模系统中的并发操作冲突的分析，实验结果表明该方法是可以适合不同协同系统的通用方法．     

基于约束依赖图的并发程序模型检测工具

模型检测是一种基于状态空间搜索的自动化验证方法,可以有效地提升程序的质量.然而,由于并发程序中线程调度的不确定性以及数据同步的复杂性,对该类程序验证时存在更为严重的状态空间爆炸问题.目前,大多采用基于独立性分析的偏序约简技术缩小并发程序探索空间.针对粗糙的独立性分析会显著增加需探索的等价类路径问题,开发了一款可细化线程迁移依赖性分析的并发程序模型检测工具CDG4CPV.首先,构造了待验证可达性性质对应的规约自动机;随后,根据线程迁移边的类型和共享变量访问信息构建约束依赖图;最后,利用约束依赖图剪裁控制流图在展开过程中的独立可执行分支.在SV-COMP 2022竞赛的并发程序数据集上进行了对比实验,并对工具的效率进行比较分析.实验结果表明,该工具可以有效地提升并发程序模型检测的效率.特别是,与基于BDD的程序分析算法相比,该工具可使探索状态数目平均减少91.38%,使时间和空间开销分别平均降低86.25%和69.80%.