Consider a deadlock detection scheme for a single server. Describe precisely when edges are added to and removed from the wait-for-graph.

Illustrate your answer with respect to the following transactions T, U and V at the server.



When U releases its write lock on ai, both T and V are waiting to obtain write locks on it. Does your scheme work correctly if T (first come) is granted the lock before V? If your answer is ‘No’, then modify your description.

Scheme:
When transaction T blocks on waiting for transaction U, add edge T U

When transaction T releases a lock, remove all edges leading to T. Illustration: U has write lock on ai.
T requests write ai. Add T U
V requests write ai. Add V U
U releases ai. Delete both of above edges.
No it does not work correctly! When T proceeds, the graph is wrong because V is waiting for T and it should indicate V T.

Modification: we could make the algorithm unfair by always releasing the last transaction in the queue.

To make it fair: store both direct and indirect edges when conflicts arise. In our example, when transaction T
blocks on waiting for transaction U add edge T U then, when V starts waiting add V U and V T