公开(公告)号：US09104989B2

公开(公告)日：2015-08-11

申请号：US12272312

申请日：2008-11-17

Applicant: Yuxi Bai ,  Alexandre Olegovich Verbitski ,  Ming-Chuan Wu

Inventor： Yuxi Bai ,  Alexandre Olegovich Verbitski ,  Ming-Chuan Wu

IPC: G06Q10/06 ,  G06F9/52

CPC classification number: G06Q10/06 ,  G06F9/52 ,  G06Q10/063 ,  Y10S707/00

Abstract: Systems and methods that enable resolving deadlock cycles by victim selection based on cost and/or priority of strongly connected components in a static wait-for graph. As such, victims can be selected by iteratively estimating total deadlock resolution cost (based on cost of strongly connected components) for remaining deadlock participants, selecting the participant with the least estimated total cost as the next victim, and reducing the wait-for graph after removing the victim vertex. The victim selection algorithm can be a cost-based greedy algorithm, wherein during each victim selection iteration, a single optimal victim is selected based on estimated remaining cost.

Abstract translation: 基于静态等待图中强连接组件的成本和/或优先级，通过受害者选择来解决死锁周期的系统和方法。 因此，可以通过迭代地估计剩余死锁参与者的总死锁分辨率成本（基于强连接组件的成本）来选择受害者，选择具有最低估计总成本的参与者作为下一个受害者，并且减少等待图表 删除受害者顶点。 受害者选择算法可以是基于成本的贪心算法，其中在每个受害者选择迭代期间，基于估计的剩余成本选择单个最佳受害者。

公开(公告)号：US20100125480A1

公开(公告)日：2010-05-20

申请号：US12272312

申请日：2008-11-17

Applicant: Yuxi Bai ,  Alexandre Olegovich Verbitski ,  Ming-Chuan Wu

Inventor： Yuxi Bai ,  Alexandre Olegovich Verbitski ,  Ming-Chuan Wu

IPC: G06Q10/00

CPC classification number: G06Q10/06 ,  G06F9/52 ,  G06Q10/063 ,  Y10S707/00

Abstract: Systems and methods that enable resolving deadlock cycles by victim selection based on cost and/or priority of strongly connected components in a static wait-for graph. As such, victims can be selected by iteratively estimating total deadlock resolution cost (based on cost of strongly connected components) for remaining deadlock participants, selecting the participant with the least estimated total cost as the next victim, and reducing the wait-for graph after removing the victim vertex. The victim selection algorithm can be a cost-based greedy algorithm, wherein during each victim selection iteration, a single optimal victim is selected based on estimated remaining cost.

Abstract translation: 基于静态等待图中强连接组件的成本和/或优先级，通过受害者选择来解决死锁周期的系统和方法。 因此，可以通过迭代地估计剩余死锁参与者的总死锁分辨率成本（基于强连接组件的成本）来选择受害者，选择具有最低估计总成本的参与者作为下一个受害者，并且减少等待图表 删除受害者顶点。 受害者选择算法可以是基于成本的贪心算法，其中在每个受害者选择迭代期间，基于估计的剩余成本选择单个最佳受害者。

公开(公告)号：US20080282244A1

公开(公告)日：2008-11-13

申请号：US11800675

申请日：2007-05-07

Applicant: Ming-Chuan Wu ,  Yuxi Bai ,  Robert H. Gerber ,  Alexandre Verbitski

Inventor： Ming-Chuan Wu ,  Yuxi Bai ,  Robert H. Gerber ,  Alexandre Verbitski

IPC: G06F9/46

CPC classification number: G06F9/524

Abstract: Aspects of the subject matter described herein relate to deadlock detection in distributed environments. In aspects, nodes that are part of the environment each independently create a local wait-for graph. Each node transforms its local wait-for graph to remove non-global transactions that do not need resources from multiple nodes. Each node then sends its transformed local wait-for graph to a global deadlock monitor. The global deadlock monitor combines the local wait-for graphs into a global wait-for graph. Phantom deadlocks are detected and removed from the global wait-for graph. The global deadlock monitor may then detect and resolve deadlocks that involve global transactions.

Abstract translation: 本文所述主题的方面涉及分布式环境中的死锁检测。 在方面，作为环境一部分的节点各自独立地创建本地等待图。 每个节点转换其本地等待图，以去除不需要多个节点资源的非全局事务。 然后，每个节点将其转换的本地等待图发送到全局死锁监视器。 全局死锁监视器将本地等待图形合并到全局等待图中。 从全局等待图中检测并删除幻像死锁。 然后，全局死锁监视器可以检测并解决涉及全局事务的死锁。