A deadlock in DBMS and OS is a condition wherein two or more processes or transactions are waiting for each other in order to be finished but none of the processes or transactions are willing to give up the resources that the other processes need. In this situation, no processes ever get finished and are in the waiting state forever.
Table of Contents
Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously.
Mutual exclusion:
Only one process at a time can use a resource
Hold and wait:
A process holding at least one resource is waiting to acquire additional resources held by other processes
No preemption:
A resource can be released only voluntarily by the process holding it after that process has completed its task
Circular wait:
there exists a set {P0, P1, …, Pn} of waiting for processes such that P0 is waiting for a resource that is held by P1, P1 is waiting for a resource that is held by P2, …, Pn–1 is waiting for a resource that is held by Pn, and Pn is waiting for a resource that is held by P0.
Deadlock Prevention
Mutual Exclusion – not required for sharable resources (e.g., read-only files); must hold for non-sharable resources
Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources.
- Require process to request and be allocated all its resources before it begins execution, or allow the process to request resources only when the process has none allocated to it.
- Low resource utilization; starvation possible
No Preemption – If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released.
Preempted resources are added to the list of resources for which the process is waiting.
Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting.
Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in increasing order of enumeration.
