Subscribe by Email


Saturday, May 11, 2013

What is meant by Deadlock? List the necessary conditions for arising deadlocks?


Consider two competing processes or actions in a situation where both of them wait for each other to be done and so neither of them ever finish. Such a situation is called a deadlock. 
- When the number of competing processes is exactly two, then it is said to be a ‘deadly embrace’. 
- The two involved competing actions tend to move towards some sort of tragedy which might be mutual extinction or mutual death. 

"In operating systems a situation occurs where two threads or processes enter the waiting state at the same time because of the resource that they both want is being used by some other process that also in waiting state for some resource being held by another process in waiting state and so on". 

- It so happens that the process is then unable to change its state since the resources it requires are being used by the other processes which is then keeping the process in waiting state indefinitely. 
- The system is now in a deadlock. 
- Systems such as the distributed systems, parallel computing systems, multi-processing systems face the problem of being in a deadlock quite often. 
- This is so because here the hardware and software locks are purposed for handling the resources that are shared and implementing the process synchronization. 
- Deadlocks may also occur in telecommunication systems because of the corrupt signals and their loss rather than resource contention. 
- A deadlock situation can be compared to problems such as that of the catch-22 or chicken or egg problem. 
- A deadlock can also occur in a circular chain pattern. 
For example, consider a computer having 3 processes and corresponding 3 CD drives i.e., one held by each process. 
- Now all the three processes would be in a deadlock if they all request another drive.

Conditions for a Deadlock to arise

There are certain conditions that should be there for a deadlock to arise:
  1. Mutual exclusion: There has to be at least one resource that cannot be shared. So that only one process would use at any given time.
  2. Resource holding (or hold and wait): There should be at least one resource held by a process that in turn should be request more resources that are being held by other processes.
  3. No preemption: Once the resources have been allocated, they should not de-allocated by the operating system. The condition is that the process holding the resource must release it voluntarily.
  4. Circular wait: A circular chain of processes must be formed as explained in the earlier example.
"These 4 conditions for deadlock are collectively called the ‘Coffman conditions’. If any of these conditions is not met, a deadlock can’t occur".

- Handling a deadlock is an important capability of the operating systems. 
However, there are many modern operating systems that still cannot avoid deadlocks. 
- On occurrence of a deadlock many non-standard approaches are followed by different operating systems for handling it. 
- Many of these approaches try to avoid at least one of the Coffman conditions (generally the 4th one). 
- Below we discuss some of the approaches:
  1. Ignoring deadlock
  2. Detection
  3. Prevention
  4. Avoidance
- There is a second kind of deadlocks called the ‘distributed deadlock’ and it is common where concurrency control is used or we can say in the distributed systems. 


No comments:

Facebook activity