Deadlock in Operating Systems: Examples and Solutions

What is Deadlock?

A deadlock is a situation in which two or more processes are unable to continue because each is waiting for resources that are held by the others. This results in a cycle of dependencies, where none of the processes can proceed, causing them to be stuck indefinitely.

System Model

System consists of resources.
In a system with multiple resource types R1,R2,…,Rm (like CPU cycles, memory space, and I/O devices).
Each process utilizes resources in three steps:
- Request: The process asks for a resource. If it's free, the process gets it; if not, it waits.
- Use: The process does its work using the resource.
- Release: When finished, the process gives back the resource so others can use it.

Deadlock Characterization

Deadlock can occur if the following four conditions hold simultaneously:

Mutual Exclusion: Only one process can use a resource at a time.
Hold and Wait: : A process that is using one resource is also waiting for other resources that are being used by other processes.
No Preemption: A resource can only be released by the process holding it, once it has finished its task.
Circular Wait: There's a circular chain of processes where each process is waiting for a resource held by the next one in the chain. For example, there exists a set {P0, p1...,Pn}. Here p0 is waiting for P1, P1 is waiting for P2, P2 waiting for Pn and Pn waiting for P0.

Example 1: Deadlock Diagram

In the diagram, resources R1, R2, and R3 are held by one process each.

P1 holds R1 and waits for R2.
P2 holds R2 and waits for R3.
P3 holds R3 and waits for R1.

Resources can only be released by the process holding them; they can't be taken away by force.

There is a circular chain: P1 → P2 → P3 → P1.

Since all four conditions (Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait) are present, the graph indicates a deadlock.

Example 2: Non-Deadlock Diagram

In the diagram, resources R1 and R2 are each held by one process, satisfying the mutual exclusion condition.

P1 holds R1 and waits for R2.
P2 and P3 are only connected to R1.
P4 is only connected to R2.

The hold and wait condition isn't fully met, as P2 and P4 aren't waiting for other resources.

The no preemption condition is satisfied because resources can only be released by the process holding them and cannot be forcibly taken.

Only P1 and P3 form a circular wait, while P2 and P4 do not, so a full circular condition isn’t maintained.

Since not all deadlock conditions are met, this is not a deadlock graph.

Deadlock Solutions

THere's a simplified explanation of the three deadlock solutions:

Deadlock Prevention: : If a deadlock has already occurred, this method aims to prevent it from continuing or happening again.
Deadlock Avoidance: Before entering a potential deadlock situation, this method avoids it by ensuring that the system doesn't enter a deadlock-prone state.
Deadlock Ignoring: : If a deadlock occurs, the system simply ignores it and lets it resolve on its own.

Deadlock prevention and deadlock avoidance are both very costly methods. They are used in specific operating systems like Mac OS and Solaris.