Guaranteed Deadlock Recovery: Deadlock Resolution with Rollback Propagation
Guaranteed Deadlock Recovery: Deadlock Resolution with Rollback Propagation
复制标题
DOI：
--
复制
发表时间：
1998-08
期刊：
影响因子：
--
通讯作者：
Yi-Min Wang;M. Marritt;A. Romanovsky
中科院分区：
文献类型：
--
作者：
Yi-Min Wang;M. Marritt;A. Romanovsky
传统上，通过简单地中止死锁循环中涉及的任何进程或最低优先级进程(称为牺牲品)来执行死锁解决。在消息传递应用中，由于消息依赖而可能进行回滚传播，受害者的回滚可能也需要其他进程回滚，重新启动的进程可能再次陷入相同的死锁。我们引入了保证死锁恢复的概念，它保证了在回滚后不会重新形成中断的死锁循环，并展示了如何通过根据运行时依赖信息仔细选择受害者来实现这一点。我们还展示了一种将动态优先级方案结合到分布式死锁检测算法中以执行有保证的死锁恢复的技术。
Traditionally, deadlock resolution is performed by simply aborting any process or the lowest-priority process (called the victim) involved in a deadlock cycle. In message-passing applications where rollback propagation due to message dependencies is possible, the rollback of the victim may require other processes to roll back as well, and the restarted processes may get into the same deadlock again. We introduce the concept of guaranteed deadlock recovery which guarantees that a broken deadlock cycle will not be re-formed after the rollback, and show how to achieve this by carefully selecting the victim based on run-time dependency information. We also demonstrate a technique to incorporate a dynamic priority scheme into a distributed deadlock detection algorithm to perform guaranteed deadlock recovery.