The resources of a system are limited and therefore when the two processes compete for them, a deadlock is likely to occur. Now, since the processes have the right to access the resource and even hold it, the other processes are prevented from utilizing these resources and thus they are put in to a waiting state. In this case, the process using the resource is said to have obtained a lock on it.
There are two common places where the deadlocks are most likely to occur:
- Processes in the operating system whether centralized or distributed.
- Transactions in a database
There are certain locking protocols such as that of the two – phase locking that may give rise to a deadlock. This happens as follows:
– A data item X is locked by a process A and another data item Y is locked on by the process B.
– Process A attempts to also lock the item Y.
– Since the item Y is already locked, this process is put in to a blocked state.
– Similarly process B tries to obtain a lock on item X and is blocked in the same way.
– Thus, both the processes are blocked and none of them will release their locks as per the rules of the two – phase locking protocol.
– A deadlock occurs in a similar way: Process A is in waiting state waiting for a resource to be released by process B and this process B is in turn waiting for the process A to release some resource.
– These two processes won’t progress until and unless there is some intervention from outside.
– Not only two, but more processes can be involved in a deadlock when they are involved in a cycle of waiting processes.
– For example, process 1 waiting for process two which is waiting for process 3 which is in turn waiting for process 1.
What is Deadlock Detection?
– Deadlock detection is all about finding and resolving the deadlocks that would actually occur.
– The strategies used for detecting the deadlocks are based on the WFG or the wait-for-graph.
– This comes explicitly built – in with some schemes and is used for analyzation of the cycles.
– In WFG, the processes are represented by the nodes and the dependencies or the blockages are represented by the edges.
– If process A is waiting for B to release some resource, this is represented by an edge in the wait-for-graph from node A (representing process A) to node B (representing process B).
– Here, a knot declares a deadlock.
– A knot is formed when from one node all the others can be reached.
– It is fairly easy to construct a wait-for-graph for the centralized systems.
– Periodic checks can be carried out for checking the cycles whenever a process is blocked thus causing an edge addition to the graph.
– If a cycle is known to exist, the victim process is aborted.
Models used for Deadlock Detection
– There is a model used for the detection of the deadlocks called the AND model.
– It is also known as the resource model.
– A deadlock is indicated by a cycle in the graph.
– There is another model called the OR model where a cycle does not necessarily means a deadlock since here the process might be unlocked by any of the requested resources.
– The deadlock problem might be made more complex because of the additional complexities of the structure of the operating system.
– The single resource model which is the simplest one requires that any process has only one request that has not been granted.
– This implies that the blocked process waits only for one other process and is thus involved in only one deadlock cycle.
– In the AND model, a process might make a number of resource requests and is kept in blocked state until all are granted.
– Therefore, here one process can be involved in multiple deadlock cycles.