Consider the edge chasing algorithm (without priorities). Give examples to show that it could detect phantom deadlocks.

Question

What will be an ideal response?

Answer 1

Transaction U, V and W perform operations on a data item at each of the servers X, Y and Z in the following order:



U gets data item at Y



V gets data item at X and then blocks at Y.



W gets data item at Z U blocks at Y.

W blocks at X.



V aborts at Y



The table below shows three servers X, Y and Z, the transactions they coordinate, the holders and requesters of their data items and the corresponding wait-for relationships before V aborts:



Now consider the probes sent out by the three servers:

At server X: W V (which is blocked at Y); probe sent to Y; then

At Y: probe received; observes V U (blocked at Z), so adds to probe to get and sends it to Z.



When V aborts at Y; Y tells X - the coordinator of V, but V has not visited Z, so Z will not be told about the fact that V has aborted!



At Z: probe is received; Z observes U W and notes the cycle WþþVþU W and as a result detects pha