一种Java并发程序死锁动态检测的新方法

死锁是并发程序中最为常见的一类错误,直到现在并没有得到很好地解决.本文以Java并发程序为例,重点研究针对资源死锁较为有效的动态检测算法:根据并发程序的动态执行追踪信息,分析出加锁控制依赖关系,再根据死锁所应满足的条件在该依赖关系集上作适量演算便得到潜在死锁关系对.进一步地,结合线程间控制流图所反映的部分静态依赖关系,剔除假性死锁关系对,提高了计算结果的精度.该算法显著的特点是简单易于实现,且无需构造锁树或锁图等图形表示.     

星形图上最小无死锁受限条件及无死锁路径算法

针对是形图中台能产生死锁的问题,对星形图上无无线锁的路径算法进行了研究,得到了星形图上的两类最小无死锁受限条件,并给出了一个满足该两类最小无死锁受限条件的无死锁路径算法。同时还证明了文献中提出的两个死锁受限条件分别只是该文所提出的两类最小无死锁受限条件的一个特例。     

基于任务-资源图的AGVS循环死锁搜索算法的改进研究

针对AGVS中循环死锁搜索算法研究中存在的不能搜索全部的循环死锁的问题,利用任务-资源图提出一个改进算法.改进算法如下:首先,根据AGV的相对位置关系和执行任务的情况,利用任务-资源图(Task-Resource graph,T-R图)对AGVS进行建模,然后根据循环死锁的T-R图特征,在每一个状态时刻下的T-R图使用图的强连通分支理论搜索循环死锁.当访问完所有状态时刻下的T-R图,也就找到了AGVS中的所有循环死锁.算例验证与理论分析均说明改进算法可以搜索到全部类型的循环死锁,解决了原算法存在的不足.根据改进算法开发的控制规则,可以有效避免新循环死锁的产生.同时指出,对改进算法稍加修改,可以找到AGVS中所有的循环死锁和非循环死锁.     

基于Petri网的并发系统活性分析

本文从数据库系统在时刻t的状态N出发，构造出相应的Petri网模型，进而构造出其可达标识图．通过分析可达标识图，可判断系统是否为死锁状态．若不是死锁状态，系统是否可能出现死锁，什么情况下系统肯定不会出现死锁．最后，给出了数据库系统中事务并发操作的死锁检测方法与避免措施．     

基于Elastos线程同步机制的死锁检测技术研究

Elastos是基于构件的操作系统,构件对象的行为模式决定了内核底层机制的实现.在Elastos中,进程对象、线程对象以及线程的同步对象等都是构件对象.介绍了Elastos的CAR构件技术及与之相应的线程同步机制,在此基础上分析了一类资源死锁产生的可能原因;结合Elastos本身的相关特点,讨论了实现死锁检测技术的各个环节,综合考虑了可靠性、正确性及效率方面的要求,给出了一个可行的死锁检测算法.通过实际验证,此算法可以得到正确的结果.     

Nucleus PLUS自旋锁测试方法研究

Nucleus PLUS是新一代的嵌入式实时多任务操作系统内核。在多核操作系统环境下,同一时刻多任务同时访问内核,自旋锁可以很好地处理不同处理器之间存在的同步与互斥问题,但自旋锁如果使用不当,极易产生死锁,造成应用层功能无法实现,所以很有必要对自旋锁展开重点测试。通过对自旋锁机制的研究,提供了一种针对自旋锁的测试方法,避免自旋锁在使用中产生死锁。     

星形图上无死锁的路径算法

星形图具有许多良好的拓扑性质，是一种有可能替代传统的超立方体的并行计算互联网络的模型。在本文中，作者针对在星形图这样一种高度规则的网络中，可能产生死锁的问题，对星形图上无死锁的路径算法进行了研究。首先利用星形图中匹配基的性质，给出了从Ｓｎ（Ｂ）到Ｓｋ的正规映射的定义，然后提出了星形图上的两个无死锁受限条件，最后证明了一个满足无死锁受限条件的路径算法。作者还提出了星形图上路径算法的最小无死锁受限条件     

基于Petri网的数据库系统并发控制活性分析

从数据库系统在时刻t的状态N出发,构造出相应的Petri网模型,进而构造出其可达标识图。通过分析可达标识图,可判断系统是否为死锁状态。若不是死锁状态,系统是否可能出现死锁,什么情况下系统肯定不会出现死锁。最后,给出了数据库系统中事务并发操作的死锁检测方法与避免措施。     

Java死锁的产生及解决机制

本文从线程和角度深入分析了Java中死锁产生的原因，并提出了Java死锁解决的可行性方案。     

一种基于依赖分析的并发程序潜在死锁检测算法

死锁是并发程序特有的一种运行时错误,由于并发程序在执行时的不确定性,死锁的检测和定位是非常困难的.本文提出了一种基于依赖分析的并发程序潜在死锁检测算法,该算法是一种静态分析算法,能检测并发程序中是否存在潜在死锁,并能定位死锁发生时各线程可能被挂起的语句节点.本文给出了算法的形式化定义和时间复杂度分析,实验测试结果表明算法是正确且有效的.     

基于元路径的图Transformer神经网络

图神经网络作为一种新的深度学习模型,被广泛运用在图数据中,并极大地推动了推荐系统、社交网络、知识图谱等应用的发展.现有的异构图神经网络通常事先定义了多条元路径来学习异构图中的复合关系.然而,这些模型通常在特征聚合步骤中只考虑单条元路径,导致模型只关注了元路径的局部结构,忽略了元路径之间的全局相关性;还有一些模型则是忽略掉了元路径的中间节点和边信息,导致模型无法学习到元路径内部的语义信息.针对以上问题,本文提出一种基于元路径的图Transformer神经网络(MaGTNN).该模型首先将异构图采样为基于元路径的多关系子图,利用提出的位置编码和边编码的方法来获取元路径中的语义信息.随后使用改进的图Transformer层计算出目标节点与其元邻居的相似度,并利用该相似度来聚合其所有的元邻居信息.在3个公开数据集的节点分类和节点聚类任务中, MaGTNN均高于最新的基准模型.     

A graph-based algorithm for consistency maintenance in incremental and interactive integration tools

Development processes in engineering disciplines are inherently complex. Throughout the development process, the system to be built is modeled from different perspectives, on different levels of abstraction, and with different intents. Since state-of-the-art development processes are highly incremental and iterative, models of the system are not constructed in one shot; rather, they are extended and improved repeatedly. Furthermore, models are related by manifold dependencies and need to be maintained mutually consistent with respect to these dependencies. Thus, tools are urgently needed which assist developers in maintaining consistency between inter-dependent and evolving models. These tools have to operate incrementally, i.e., they have to propagate changes performed on one model into related models which are affected by these changes. In addition, they need to support user interactions in settings where the effects of changes cannot be determined automatically and deterministically. We present an algorithm for incremental and interactive consistency maintenance which meets these requirements. The algorithm is based on graphs, which are used as the data model for representing the models to be integrated, and graph transformation rules, which describe the modifications of the graphs to be performed on a high level of abstraction. This paper is an extended version of [6].     

图依赖研究与应用综述

图依赖是用于解决图数据的数据一致性问题的数据质量规则。基于图依赖提升数据一致性的过程通常分为图依赖定义与形式化、图依赖自动挖掘、基于图依赖的数据一致性提升三步。介绍了针对数据一致性的图依赖理论,并根据拓展类型将图依赖分为基于结构约束拓展、基于语义约束拓展和基于外部约束拓展的图依赖;综述并对比了从图数据中自动挖掘图依赖及其拓展的算法;分析了应用图依赖提高数据一致性的研究现状;总结了当前研究中仍存在的问题,并依据问题展望了图依赖在数据质量领域的应用前景。     

On Deadlock Detection in Distributed Systems

A hierarchically organized and a distributed protocol for deadlock detection in distributed databases are presented in [1]. In this paper we show that the distributed protocol is incorrect, and present possible remedies. However, the distributed protocol remains impractical because "condensations" of "transaction-wait-for" graphs make graph updates difficult to perform. Delayed graph updates cause the occurrence of false deadlocks in this as well as in some other deadlock detection protocols for distributed systems. The performance degradation that results from false deadlocks depends on the characteristics of each protocol.     

改进的图谱理论阈值分割方法

针对现有的基于归一化的图谱理论阈值分割算法的权值计算公式没有充分考虑像素点的关联,在图像含有弱边界时很难得到真实解,导致图像细节分割不理想的问题,本算法首先使用高斯混合模型构造新的约束条件引入到权值计算中,使得权值计算充分地考虑像素点之间的关联。在计算图谱划分测度前,本算法通过高斯混合模型的均值参数自适应确定门限值的分布区间,较大地提高了图谱划分测度计算的效率。实验结果表明,相对于现有的基于归一化的图谱理论的阈值分割方法,本文算法具有较好的分割效果,可以保留图像更多细节。     

基于概率分布的图卷积文本分类模型

近年来,图神经网络模型因其对非欧氏数据的建模和对全局依赖关系的捕获能力而广泛应用于文本分类任务。现有的基于图卷积网络的分类模型中的构图方法存在消耗内存过大、难以适应新文本等问题。此外,现有研究中用于描述图节点间的全局依赖关系的方法并不完全适用于分类任务。为解决上述问题,该文设计并提出了基于概率分布的文本分类网络模型,以语料库中的词和标签为节点构建标签-词异构关系图,利用词语在各标签上的概率分布描述节点间的全局依赖关系,并通过图卷积操作进行文本表示学习。在5个公开的文本分类数据集上的实验表明,该文提出的模型在有效缩减图尺寸的同时,相比于其他文本分类网络模型取得了较为先进的结果。     

MPI-RCDD: A Framework for MPI Runtime Communication Deadlock Detection

The message passing interface (MPI) has become a de facto standard for programming models of highperformance computing, but its rich and flexible interface semantics makes the program easy to generate communication deadlock, which seriously affects the usability of the system. However, the existing detection tools for MPI communication deadlock are not scalable enough to adapt to the continuous expansion of system scale. In this context, we propose a framework for MPI runtime communication deadlock detection, namely MPI-RCDD, which contains three kinds of main mechanisms. Firstly, MPI-RCDD has a message logging protocol that is associated with deadlock detection to ensure that the communication messages required for deadlock analysis are not lost. Secondly, it uses the asynchronous processing thread provided by the MPI to implement the transfer of dependencies between processes, so that multiple processes can participate in deadlock detection simultaneously, thus alleviating the performance bottleneck problem of centralized analysis. In addition, it uses an AND⊕OR model based algorithm named AODA to perform deadlock analysis work. The AODA algorithm combines the advantages of both timeout-based and dependency-based deadlock analysis approaches, and allows the processes in the timeout state to search for a deadlock circle or knot in the process of dependency transfer. Further, the AODA algorithm cannot lead to false positives and can represent the source of the deadlock accurately. The experimental results on typical MPI communication deadlock benchmarks such as Umpire Test Suit demonstrate the capability of MPIRCDD. Additionally, the experiments on the NPB benchmarks obtain the satisfying performance cost, which show that the MPI-RCDD has strong scalability.     

基于资源等待图的死锁检测算法

死锁是操作系统、数据库系统以及通信网络中经常出现的现象.分析了使用资源分配图和进程等待图完成死锁检测的不足,提出了资源等待图的概念,并给出了基于资源等待图进行死锁检测的方法,该算法能够完成当资源类含有多个实例时的死锁检测.