Guaranteed Deadlock Recovery: Deadlock Resolution with Rollback Propagation
Y. Wang, M. Marritt, Alexander B. Romanovsky · 1998
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 systems 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 guarantee deadlock recovery. 1 Introduction Checkpointing and rollback recovery is a technique that periodically saves the volatile state of a process onto stable storage so that the state can be restored when the process need...