Introduction of Deadlock in Operating System

A deadlock is a situation in a computing environment where a set of processes gets permanently stuck because each process is waiting for a resource held by another process, and none of them can proceed.

How Does Deadlock Occur in OS?

A process in an operating system typically uses resources in the following sequence:

• Request a resource
• Use the resource
• Release the resource

Deadlock arises when processes hold some resources while waiting for others.

Example:

• Process P1 holds Resource R1 and requests R2.
• Process P2 holds Resource R2 and requests R1.
  Neither process can proceed causing a deadlock.

Examples of Deadlock

There are several examples of deadlock. Some of them are mentioned below.

1. The system has 2 tape drives. P0 and P1 each hold one tape drive and each needs another one.

2. Semaphores A and B, initialized to 1, P0, and P1 are in deadlock as follows:

• P0 executes wait(A) and preempts.
• P1 executes wait(B).
• Now P0 and P1 enter in deadlock.

3. Assume the space is available for allocation of 200K bytes, and the following sequence of events occurs.

Deadlock occurs if both processes progress to their second request.  

Necessary Conditions for Deadlock in OS

Deadlock can arise if the following four conditions hold simultaneously (Necessary Conditions) 

1. Mutual Exclusion: Only one process can use a resource at any given time i.e. the resources are non-sharable.
2. Hold and Wait: A process is holding at least one resource at a time and is waiting to acquire other resources held by some other process.
3. No Preemption: A resource cannot be taken from a process unless the process releases the resource. 
4. Circular Wait:  set of processes are waiting for each other in a circular fashion. For example, imagine four processes P1, P2, P3, and P4 and four resources R1, R2, R3, and R4.
   

   The above image demonstrates a circular wait deadlock, here's how:

• P1 is holding R1 and waiting for R2 (which is held by P2).
• P2 is holding R2 and waiting for R3 (which is held by P3).
• P3 is holding R3 and waiting for R4 (which is held by P4).
• P4 is holding R4 and waiting for R1 (which is held by P1).