How a deadlock is detected from wait for graph?


There are multiple copies of resources are available in a system. A process can request for more than one copy of a resource. Suppose a process will be blocked till at least one copy of resource is granted, what is the sufficient condition to detect a deadlock from wait for graph of the system?

a) A cycle is present in WFG.

b) A knot is present in WFG.

c) Both a and b can be the conditions and equally powerful.

d) Both a and b can be failed in given conditions in problem


It’s very simple…suppose one task is given to you and me… And task is to write something on paper…now suppose you have a paper and i have a pen and you are waiting for me give a pen and i m waiting for you to give me a paper… So if we draw this situation using wait for graph then …there are four nodes… You(a process) , me(a process) , pen(a resource) , paper(a resource) … now you have a paper so draw a line and connect nodes you and paper… Similarly connect me and pen node… Now you are waiting for pen so draw line and connect you and pen node… and i m waiting for paper so draw and connect me and paper node… And then apply any one algorithm to detect a cycle in graph… Same thing is in wait for graph… But simple… Only two nodes of processes you and me… And connect both because we are waiting for each other… and then apply any cycle detection algorithm


If there is a cycle present in the wait for graph, one is sure to get into deadlock.
It happens as follows:-
If process A seeks resources R1, R2
Process B is using R2 and seeks R3
Process C using R4 and wants R3
This creates a cycle and all three process enters into deadlock