1
$\begingroup$

During the process of deadlock detection, the wait-for graph can be obtained from the resource-allocation graph. To detect whether there is a deadlock using the wait-for graph, can topological sort be used?

By making a slight modification, i.e., instead of removing the source as done in usual topological sort, we can remove the node (here, node represents a process) which does not point to another node first and proceed in this manner. As soon as the algorithm detects that it cannot proceed further and there are still nodes existing in the wait-for graph, it can be concluded as deadlock.

Other tags are topological-sort and deadlock-detection.

$\endgroup$
0
$\begingroup$

Hint: There is deadlock in the wait-for graph if the graph has directed cycles (why?). Perhaps topological sort is useful for detecting these.

$\endgroup$
-1
$\begingroup$

IN single stance WFG the presence of cycle indicate that their is deadlock it is sufficient condition but in multi-instance WFG if the cycle is presence then we cant right away declare that their is deadlock it is just necessary condition not sufficient condition their might chance to presence. if the topological sorting is used then I think it always come up with the result that there is no deadlock just because topological order is acyclic graph and we know that deadlock to be present there should be presence of cycle .

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.