Operating System - Methods for Handling Deadlocks

<<Previous - Resource Allocation Graph

Next - Process Synchronization >>





There are 4 ways to handle the deadlock problems in Operating System:

Methods to handle Deadlocks - Overview

MethodApproach
Ignore
Deadlocks
Letting it happen and do the damage: Ignore the deadlock problem altogether. If it occurs, Restart
Deadlock Detection and Recovery Detecting while it is happening and Recovering from it: Detect the deadlock when it occurs and recover it.
Deadlock Prevention Preventing it from happening by removing one necessary condition: Use a Protocol to prevent deadlocks.
Deadlock Avoidance Avoiding a process from starting: When a process A needs a resource which is used by another process B, avoid providing CPU time to the new process

Note that the Deadlock Prevention and Avoidance approaches are often considered the same, even though the difference is in the implementation


Methods to handle Deadlocks - Details


Ignoring Deadlocks - Letting it happen and do the damage

Most popular among the desktop operating systems is ignoring the deadlock altogether and let it happen when it happens. Deadlocks occur very very rarely but the operation to either detect or prevent deadlocks for every process is costly. Trying to prevent or detecting will also impact speed/performance of all the processes which are most likely not going to be involved in a deadlock. Hence, Windows and Linux Operating Systems chose to ignore deadlocks in most scenarios.


Deadlock Detection and Recovery

Most popularly used in Android Operating System which detects deadlock. Deadlock occurs when multiple processes are locked with each process trying to access each other's resource and continuously waiting without a result. Deadlock is easily detected when a process is in a locked state. In such a case, OS closes the process and let it start again. Since deadlock is a very very rare scenario, deadlock does not occur again for the same process after it is started again.


Deadlock Avoidance - Avoiding Resource allocation

Deadlock avoidance is done by avoding a process from starting when the resources it needs is being accessed by processes already running. New process is not provided CPU time. User is also informed so that an alternate user action can be taken.


Deadlock Prevention - Providing resource allocation but preventing deadlock

Deadlock is prevented by removing one of the conditions required for a deadlock to occur. Deadlock usually occurs only when all the four conditions mentioned below are true. If we ensure that one of the conditions does not occur, deadlock doesnnot occur as well

  • Mutual exclusion - non-shareable resources can be accessed by only one process
  • Hold and Wait - process holds a resource and waits for another resources held by another process
  • No Preemption - only a process holding a resource can release it and no interrupt can release it
  • Circular wait - Process A waits for resource held by process B and process B in turn waits for process A. A similar situation with 3 or more processes can also occur

<<Previous - Resource Allocation Graph

Next - Process Synchronization >>









Operating System - Methods for Handling Deadlocks

<<Previous - Resource Allocation Graph

Next - Process Synchronization >>





There are 4 ways to handle the deadlock problems in Operating System:

Methods to handle Deadlocks - Overview

MethodApproach
Ignore
Deadlocks
Letting it happen and do the damage: Ignore the deadlock problem altogether. If it occurs, Restart
Deadlock Detection and Recovery Detecting while it is happening and Recovering from it: Detect the deadlock when it occurs and recover it.
Deadlock Prevention Preventing it from happening by removing one necessary condition: Use a Protocol to prevent deadlocks.
Deadlock Avoidance Avoiding a process from starting: When a process A needs a resource which is used by another process B, avoid providing CPU time to the new process

Note that the Deadlock Prevention and Avoidance approaches are often considered the same, even though the difference is in the implementation


Methods to handle Deadlocks - Details


Ignoring Deadlocks - Letting it happen and do the damage

Most popular among the desktop operating systems is ignoring the deadlock altogether and let it happen when it happens. Deadlocks occur very very rarely but the operation to either detect or prevent deadlocks for every process is costly. Trying to prevent or detecting will also impact speed/performance of all the processes which are most likely not going to be involved in a deadlock. Hence, Windows and Linux Operating Systems chose to ignore deadlocks in most scenarios.


Deadlock Detection and Recovery

Most popularly used in Android Operating System which detects deadlock. Deadlock occurs when multiple processes are locked with each process trying to access each other's resource and continuously waiting without a result. Deadlock is easily detected when a process is in a locked state. In such a case, OS closes the process and let it start again. Since deadlock is a very very rare scenario, deadlock does not occur again for the same process after it is started again.


Deadlock Avoidance - Avoiding Resource allocation

Deadlock avoidance is done by avoding a process from starting when the resources it needs is being accessed by processes already running. New process is not provided CPU time. User is also informed so that an alternate user action can be taken.


Deadlock Prevention - Providing resource allocation but preventing deadlock

Deadlock is prevented by removing one of the conditions required for a deadlock to occur. Deadlock usually occurs only when all the four conditions mentioned below are true. If we ensure that one of the conditions does not occur, deadlock doesnnot occur as well

  • Mutual exclusion - non-shareable resources can be accessed by only one process
  • Hold and Wait - process holds a resource and waits for another resources held by another process
  • No Preemption - only a process holding a resource can release it and no interrupt can release it
  • Circular wait - Process A waits for resource held by process B and process B in turn waits for process A. A similar situation with 3 or more processes can also occur

<<Previous - Resource Allocation Graph

Next - Process Synchronization >>















Learn about Stack Data Structure

Learn about Heap Data Structure

Learn about Operating System

Learn AVL Tree

Learn Djikstra's Algorithm