Chapter 23, Problem 8PE

Explanation of Solution

Deadlock-detection algorithm:

Consider the given deadlock-detection algorithm:

• Let a cycle, T_i -> T_j -> T_m -> T_i exists in the graph, which is built by the controller.
• The edges in the graph will be local edges either from (T_k, T_l) or a distributed edge of the form (T_k, T_l, n).
• Every local edge (T_k, T_l) certainly means T_k 's waiting for T_l.
• Since a distributed edge (T_k, T_l, n) is only inserted into the graph if T_k's request reaches T_l and T_l is unable to release the lock instantly, T_l is going to have to wait for T_l to free up the resources.
• Every edge of the cycle therefore truly represents a transaction waiting for yet another.

Proving the converse implication:

• As soon as it is found out that T_k is waiting for T_l:
  • If both T_k and T_l are located at same site, that is either S₁ S₃, a local edge between T_k and T_l is inserted...