Deadlock detection

Deadlock detection

If the system does not employ either a deadlock prevention or avoidance algorithm deadlock, the deadlock situation may occur. In this environment, the system must provide:

* An algorithm that examines the state of the system to determine whether there has been a deadlock. 
* An algorithm to recover from deadlock.

If all resources have only one event, then we can define a deadlock detection algorithm which uses a variant of the resource allocation graph, called wait-for graph.

As before, there is a deadlock in the system if and only if the wait-for graph contains a cycle. To detect deadlocks, the system needs to keep the wait-for graph and periodically call the algorithm that finds cycles in the graph. Algorithm to detect cycles in the graph are used to sequence operations n1, where n is the number of vertices in the graph

Read More

Deadlock avoidance

 
The caches guarantee that all incoming replies (REPLYs and COHE_REPLYs) are accepted even if they require further messages to be sent out. If a REPLY leads to a retry (either because of an RAR or a NackUpgradeConflictReply), the MSHR originally allocated by the REQUEST will be used as a resource from which to send the message to the cache ports. If a REPLY leads to a writeback or replacement message, its write-back buffer entry or MSHR can be used as a resource from which to send the message. In all cases, the resources needed to send any possible messages on REPLY are reserved at the time of the REQUEST.
Additionally, the tag arrays of the caches have a special port reserved for COHE messages to insure that these messages do not interact with REQUESTs or REPLYs to cause a deadlock. Such a port would likely be considered excessive in a real system; an alternative is to have the caches break deadlocks caused by COHEs by sending these messages back to the directory marked with s.reply fields set to RAR (request a retry).

Read More