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

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

一种基于等待图的死锁解除策略

在数据库的并发控制中，由于加锁引起的死锁问题通常是由等待图来检测。当检测到多个事务之间出现死锁现象时．通过回退其中的一个事务来打破等待图中的循环，从而消除死锁。随便回退其中的一个事务往往不能使得多个事务的总体收益最大．本文通过分析多个事务加锁情况及事务之间的联系，为每一个事务分配一个权值，并依据该权值决定回退哪一个事务从而使得多个事务的总体收益最大化。     

移动Agent系统的一种分布式死锁检测方案

传统的分布式死锁解决方案不适合于实体在网络中自由移动的MAS系统.本文描述了一种移动Agent系统的分布式死锁算法,使用专职Agent从事死锁检测和解决.该方案的特点是地点参考、拓扑独立、容错、异步操作.文中建立了StochasticPetri Net模型,并使用仿真试验给出它和Diffusion Computation算法的性能比较.     

Web服务环境中的死锁检测算法分析与比较

在Web服务环境中,多个事务并发执行时,会出现与传统的事务环境相同的死锁问题,而处理死锁最主要的手段为死锁检测。本文对传统的分布式死锁检测算法在Web服务集成中的应用进行了总结和比较。     

MDBS中一种改进的并发事务调度算法

MDBS中并发事务的调度策略必须满足可串行化准则,论文主要分析以事务提交图为中心的调度算法TM2,虽然保证了全局事务提交顺序的可串行化,但在提交时才进行冲突检测方式存在缺点,提出改进后的事务调度算法TM3不仅保证了全局事务的可串行化和防止了全局死锁的发生,还提高了全局事务执行的并发度。最后通过实验在数据库加速引擎中进行模拟,对比了两种调度算法的性能。     

一种基于移动Agent技术的分布式死锁检测算法

死锁的处理长期以来一直是分布式系统的研究重点,已有许多成熟算法.随着网络技术的发展,越来越多的客户和资源可在网络中自由移动,这种可移动性使得传统算法面临了新的挑战.在这种新的应用背景下,本文结合移动Agent技术,提出了一种分布式系统死锁检测和解除算法：Agent Guard.该算法使用一个移动Agent,使其遵循一定的路线算法在各个站点间移动来收集资源请求和分配信息并进行分析,从而发现并解除死锁.模拟实验证明,A-gent Guard算法能取得较短的死锁持续时间,较小的伪死锁率,且网络的通信复杂度也有降低.     

基于Petri网的分布式系统并发进程的死锁检测

分布式系统中的并发进程具有明显的并发、异步及分布性,而Petri网是模拟与分析并发、异步、分布式系统的有效工具.为此通过引入Petri网,给出了分布式系统局部并发进程等待的Petri网模型及死锁检测方法,提出了全链路合成的概念,利用全链路合成技术组装了全局并发进程等待的Petri网模型,给出了判断整个系统是否出现死锁的充分必要条件.     

基于两层模式的Web服务工作流失效恢复算法

现有的Web事务工作流恢复算法通常未考虑用户的个性需求,也没有考虑恢复时的连锁恢复情况.为此,定义全局事务工作流模式和执行事务模式2种失效恢复粒度,并提出基于这2种粒度的失效恢复算法.通过细粒度的执行事务模式进行事务实例级的层次式递归恢复,采用粗粒度的全局事务工作流模式进行模型级的恢复,并用来满足客户的个性需求.该算法...     

基于发布订阅模型的代理间信任机制研究

发布／订阅范型具有异步、松散耦合和多对多通信的特点,在大规模分布式计算环境中有着广阔的应用前景。针对发布／订阅系统网络代理之间存在可信任问题与发布者、订阅者的访问权限问题,提出了一种分布式网络层次模型,并提出了基于RSA加密的代理身份认证算法解决代理之间信任问题,并保证代理之间路由消息的安全性,该算法在发生事故时能区分事故责任。并改进Kerberos认证算法解决发布者、订阅者的访问权限。并对该模型与算法进行了分析。     

基于异步奖励深度确定性策略梯度的边缘计算多任务资源联合优化

移动边缘计算（MEC）系统中,因本地计算能力和电池能量不足,终端设备可以决定是否将延迟敏感性任务卸载到边缘节点中执行。针对卸载过程中用户任务随机产生且系统资源动态变化问题,提出了一种基于异步奖励的深度确定性策略梯度（asynchronous reward deep deterministic policy gradient,ARDDPG）算法。不同于传统独立任务资源分配采用顺序等待执行的策略,该算法在任务产生的时隙即可执行资源分配,不必等待上一个任务执行完毕,以异步模式获取任务计算奖励。ARDDPG算法在时延约束下联合优化了任务卸载决策、动态带宽分配和计算资源分配,并通过深度确定性策略梯度训练神经网络来探索最佳优化性能。仿真结果表明,与随机策略、基线策略和DQN算法相比,ARDDPG算法在不同时延约束和任务生成率下有效降低了任务丢弃率和系统的时延和能耗。     

容错的分布式系统通用死锁模型检测解除算法

分布式系统技术为采用低成本购建高性能系统提供了有效的途径,但是由于资源的分配与需求可能产生冲突,造成系统中发生死锁,导致系统运行陷入停滞.在不可靠的分布式系统中,故障会干扰正常的死锁检测,但现有的死锁检测算法不具有容错功能.对失效形式进行了归类,提出一个容错的死锁检测解除算法.算法建立在通用的AND-OR模型基础上,采用扩散计算和集中规约方式,不仅能够检测到死锁,而且能给出死锁环的全部成员.若死锁拓扑处于静态且为环状,算法的消息复杂度的上限为e n-1,时间复杂度为d,其中e为死锁等待图中边的个数,n和d为构成死锁环的节点的个数,分析表明算法性能等于或优于同类算法.     

Cooperative Distributed Algorithms for Dynamic Cycle Prevention

Parallel distributed algorithms are presented for adding and deleting edges in a directed graph without creating a cycle. Such algorithms are useful for a variety of problems in distributed systems such as preventing deadlock or ordering priorities. The algorithms operate in a realistic asynchronous computer network environment in which there are numerous possible interactions among overlapping instances of the algorithms.     

Deadlock detection in distributed database systems: a new algorithm and a comparative performance analysis

This paper attempts a comprehensive study of deadlock detection in distributed database systems. First, the two predominant deadlock models in these systems and the four different distributed deadlock detection approaches are discussed. Afterwards, a new deadlock detection algorithm is presented. The algorithm is based on dynamically creating deadlock detection agents (DDAs), each being responsible for detecting deadlocks in one connected component of the global wait-for-graph (WFG). The DDA scheme is a “self-tuning” system: after an initial warm-up phase, dedicated DDAs will be formed for “centers of locality”, i.e., parts of the system where many conflicts occur. A dynamic shift in locality of the distributed system will be responded to by automatically creating new DDAs while the obsolete ones terminate. In this paper, we also compare the most competitive representative of each class of algorithms suitable for distributed database systems based on a simulation model, and point out their relative strengths and weaknesses. The extensive experiments we carried out indicate that our newly proposed deadlock detection algorithm outperforms the other algorithms in the vast majority of configurations and workloads and, in contrast to all other algorithms, is very robust with respect to differing load and access profiles. Received December 4, 1997 / Accepted February 2, 1999     

Detecting and resolving deadlocks in mobile agent systems

Mobile agents environment is a new application paradigm with unique features such as mobility and autonomy. Traditional deadlock detection algorithms in distributed computing systems do not work well in mobile agent systems due to the unique feature property of the mobile agent. Existing deadlock detection and resolution algorithms in mobile agent systems have limitations such as performance inefficiency and duplicate detection/resolution when multiple mobile agents simultaneously detect/resolve the same deadlock. To address these problems, we propose an improved deadlock detection and resolution algorithm that adopts priority-based technique and lazy reaction strategy. The priority-based technique aims to ensure that there is only one instance of deadlock detection and resolution, and it also helps reduce mobile agent movement and data traffic together with the lazy reaction strategy. The liveness and safety properties of the proposed algorithm are proved in this paper. Theoretical analysis and experimental results show that the proposed algorithm provides better performance in terms of agent movement, data traffic, and execution time.     

并发操作系统中基于有色Petri网的死锁检测与避免

1.引言系统的并发性与资源的共享性是并发操作系统的主要特征,其目的是最大限度地提高计算机资源的利用率。死锁是并发操作系统必须解决的一个重要问题。人们试图用不同的方法来解决死锁问题。如Dijkstra提出的有名的死锁避免的“银行家算法”,Coffman等人给出的死锁检测算法。 Petri网模型作为模拟与分析并发、异步、分布式系统的一种有效工具,已被用于解决操作系统中的许多问题。如进程通讯中的生产者/消费者问题、哲学家用餐问题,资源竞     

Performance analysis of distributed deadlock detection algorithms

The paper presents a probabilistic performance analysis of a deadlock detection algorithm in distributed systems. Although there has been extensive study on deadlock detection algorithms in distributed systems, little attention has been paid to the study of the performance of these algorithms. Most work on performance study has been achieved through simulation but not through an analytic model. Min (1990), to the best of our knowledge, made the sole attempt to evaluate the performance of distributed deadlock detection algorithms analytically. Being different from Min's, our analytic approach takes the time-dependent behavior of each process into consideration rather than simply taking the mean-value estimation. Furthermore, the relation among the times when deadlocked processes become blocked is studied, which enhances the accuracy of the analysis. We measure performance metrics such as duration of deadlock, the number of algorithm invocations, and the mean waiting time of a blocked process. It is shown that the analytic estimates are nearly consistent with simulation results     

分布式计算中稳定性质的等价类划分

分布式计算中的稳定性质是那些在计算中一旦成立将保持成立的性质，如分布式死锁、分布式终止和分布式废码等，稳定性质检测是分布式计算中计算中的重要问题，常通过构造一致全局系统状态来检测稳定性质。