System resources (e.g. CPU time, Memory space, I/O devices such as printers etc.) are finite, and many processes will be competing for these resources.  If the requested resource is not readily available, the processes will have to wait. If each process holds a resource and wait for another resource, which is held by another waiting process, and if it finally forms a circular wait sequence, where everyone will be waiting indefinitely without getting the resource, it will result in a deadlock.

Necessary Conditions for Deadlock

There are four necessary conditions for a deadlock to occur: Mutual exclusion, hold and wait, no preemption and circular wait. 

Mutual Exclusion – There should be at least one non-shareable resource.

Hold and Wait – A deadlock will occur if a process can hold a resource and then wait for another. If only every resource can wait for a resource (without holding), there won’t be any deadlock as no one is holding on to any resource.

No preemption – If resources allocated to a process cannot be preempted there is a high change of deadlocks. But if resources allocated to a process can be preempted, meaning taken out and given to one waiting, deadlocks won’t happen.

Circular Wait – If each process holds a resource and wait for another resource, which is held by another waiting process, and if it finally forms a circular wait sequence, a deadlock will occur. For instance P1 (hold R1) waits for R2 (hold by P2), P2 (hold R2) wait for R3 (hold by P3), P3 (hold R3) wait for R1 (hold by P1). Everybody will keep on holding and waiting in a loop. There are many diagrams that will help you figure out if there is a circular wait sequence.

Introduction to important terms

There are some important operating system terms that are commonly used in the context of deadlocks.

Preemptive and Non-preemptive resources – A preemptive resource can be taken away from the process that is holding it whereas a non-preemptive resource cannot be taken away from the process that is holding it. As you may guess, non-preemptive property is a required condition for deadlock.

Reusable and Consumable resources – A resource is reusable if it can be used again by another process, like CPU, memory, printers etc.; and consumable if they can be used only once, like a message which is consumed by any one of the listeners. When deadlocks are discussed, we usually discuss about reusable resources.

Shareable and Non-shareable resources – Non-shareable resources need to be taken care while discussing about deadlocks, as they cannot be shared simultaneously by processes, and processes will have to wait for their turn to use them. Shareable resources cannot cause a deadlock, as they can be used by processes simultaneously without any waiting. However, we cannot make all resources non-shareable to avoid deadlock, as certain resources are cannot be shared safely.

Starvation

Starvation means that a process is denied necessary resources, without which the program can never finish its task. Starvation is often caused by errors in a scheduling algorithm, but can also be caused by resource leaks, and can be intentionally caused via a denial-of-service attack such as a fork bomb. Refer to the wiki page on resource starvation to read more: http://en.wikipedia.org/wiki/Resource_starvation.

Safe state

A system can be considered to be in safe state if it is not in a state of deadlock and can allocate resources upto the maximum available. A safe sequence of processes and allocation of resources ensures a safe state. If a system is already in a safe state, we can try to stay away from an unsafe state and avoid deadlock. Deadlocks cannot be avoided in an unsafe state.

Next we will see the necessary conditions for deadlocks, deadlock prevention, deadlock avoidance and deadlock detection.