Operating System ByteXL

Introduction

In multiprogramming systems, multiple processes compete for limited resources like CPU time, memory,
and devices. Normally, the operating system manages this efficiently, but sometimes processes hold
resources while waiting for others—creating a circular dependency where none can proceed. This
permanent state of waiting is called deadlock, which can freeze affected processes or even the entire
system.

To understand and prevent deadlock, we must identify the specific conditions that cause it. In this section,
we’ll define deadlock, look at real-world examples, and explore the four conditions that must exist for it to
occur—forming the basis of all deadlock management strategies.

What is Deadlock?

Deadlock is a situation where a set of processes are blocked because each process is holding a resource and
waiting to acquire a resource held by another process in the set. No process in the set can proceed, and
without external intervention, they will wait indefinitely.

Key characteristics:

• Involves multiple processes (at least two)

• Each process holds at least one resource

• Each process waits for a resource held by another process in the deadlocked set

• Circular waiting dependency exists

• Permanent state—processes never resolve deadlock on their own

Real-World Analogy: Traffic Deadlock

Imagine a four-way intersection where four cars arrive simultaneously, one from each direction. Each car
proceeds partway into the intersection but cannot complete the turn because another car blocks its path.
Each car occupies space (holds a resource) and waits for space occupied by another car (waits for a
resource). No car can move forward, backward, or turn. Without external intervention (a traffic officer
directing cars), the deadlock persists indefinitely.

North Car

West Car → X ← East Car

South Car
Operating System ByteXL

Each car blocks the path of the next car clockwise.

Circular wait: North → East → South → West → North

Simple Example: Two Processes, Two Resources

Scenario: Process P1 and Process P2 need both Resource A and Resource B to complete their tasks.

Execution:

Time Process P1 Process P2 Resource A Resource B

1 Request A P1 Free

2 Acquire A P1 Free

3 Request B P1 P2

4 Acquire B P1 P2

5 Request B (blocked) P1 P2

6 Request A (blocked) P1 P2

7 Waiting for B... Waiting for A... P1 P2

Result: Deadlock. P1 holds A and waits for B. P2 holds B and waits for A. Neither can proceed.

System Example: Database Transactions

Scenario: Two database transactions need to update two records (Record X and Record Y).

Transaction T1:

1. Lock Record X

2. Update Record X

3. Lock Record Y

4. Update Record Y

5. Unlock X and Y

Transaction T2:
Operating System ByteXL

1. Lock Record Y

2. Update Record Y

3. Lock Record X

4. Update Record X

5. Unlock X and Y

Deadlock execution:

Time 1: T1 locks X

Time 2: T2 locks Y

Time 3: T1 tries to lock Y (blocked—T2 holds it)

Time 4: T2 tries to lock X (blocked—T1 holds it)

Result: Deadlock. T1 holds X, waits for Y. T2 holds Y, waits for X.

Resource Allocation Graph

A visual tool for understanding deadlock is the Resource Allocation Graph (RAG), which shows processes,
resources, and their relationships.

Components:

• Process (Circle): Represents a process (P1, P2, P3, ...)

• Resource (Rectangle): Represents a resource type (R1, R2, R3, ...)

• Dots inside rectangle: Represent instances of that resource type

• Request Edge (P → R): Process P requests resource R (arrow from process to resource)

• Assignment Edge (R → P): Resource R is allocated to process P (arrow from resource to process)

Example 1: Deadlock Graph

P1 → R1 → P2 → R2 → P1

P1 holds R1, requests R2

P2 holds R2, requests R1

Cycle detected: P1 → R2 → P2 → R1 → P1

Conclusion: Deadlock exists (assuming single instance per resource).

Example 2: No Deadlock

P1 → R1

P2 → R2

P3 → R1 (waiting)

P1 holds R1

P2 holds R2

P3 requests R1 (blocked, waiting for P1 to release)

No cycle: P3 will eventually get R1 when P1 releases it.

Conclusion: No deadlock—just temporary waiting.

Necessary and Sufficient Conditions for Deadlock

Deadlock occurs if and only if all four of the following conditions hold simultaneously. These are known as
the Coffman conditions (named after Edward G. Coffman Jr.).

Condition 1: Mutual Exclusion

At least one resource must be held in a non-shareable mode. Only one process can use the resource at a
time. If another process requests the resource, it must wait until the resource is released.

Why it's necessary: If resources can be shared freely, multiple processes can use them simultaneously
without blocking. Deadlock requires exclusive access where processes block each other.

Example:

• Printer: Only one process can print at a time (mutual exclusion)

• Read-only file: Multiple processes can read simultaneously (no mutual exclusion, no deadlock from
reading)

Real scenario:

Resource: Printer
Operating System ByteXL

Process P1: Acquires printer, prints document

Process P2: Requests printer, must wait (mutual exclusion)

If printers could be shared (impossible in practice), P2 wouldn't wait, and this condition wouldn't hold.

Condition 2: Hold and Wait

A process holding at least one resource is waiting to acquire additional resources currently held by other
processes.

Why it's necessary: Deadlock requires processes to simultaneously hold resources and wait for others. If
processes request all resources at once (before holding any), or release all resources before requesting new
ones, hold-and-wait doesn't occur.

Example:

Process P1:

1. Acquire Resource A (now holding A)

2. Request Resource B (waiting while holding A)

If P1 released A before requesting B, hold-and-wait wouldn't occur.

If P1 requested both A and B together, it would get both or neither—no partial hold.
Operating System ByteXL

Real scenario:

Process editing a file:

1. Locks file for editing (holds file lock)

2. Requests printer to print draft (waits while holding file lock)

Hold-and-wait: Holds file, waits for printer.

Condition 3: No Preemption

Resources cannot be forcibly taken away from a process holding them. A resource can only be released
voluntarily by the process holding it, after that process has completed its task.

Why it's necessary: If the OS could forcibly take resources from processes, it could break deadlock by
preempting resources from one process and giving them to another. Non-preemptive resources make
deadlock possible.

Example:

Process P1 holds Resource A

Process P2 needs Resource A

Non-preemptive: OS cannot take A from P1. P2 must wait until P1 releases A.

Preemptive: OS could take A from P1 and give it to P2 (breaks deadlock).

Real scenario:

Mutex lock held by Process P1:

→ Cannot be forcibly removed by OS

→ P1 must explicitly unlock it

→ Non-preemptive resource

CPU time (in many systems):

→ OS can preempt CPU from process (timer interrupt)

→ Preemptive resource (doesn't contribute to deadlock)

Condition 4: Circular Wait

A circular chain of processes exists where each process holds at least one resource needed by the next
process in the chain.

Why it's necessary: Without a cycle, waiting is linear—eventually, the first process in the chain gets its
resource, completes, releases resources, and the chain unblocks. A cycle means every process in the chain
waits for another, creating an unbreakable loop.

Example:

P1 holds R1, waits for R2

P2 holds R2, waits for R3

P3 holds R3, waits for R1

Circular chain: P1 → P2 → P3 → P1

Each process waits for the next, forming a cycle. No process can proceed.

Real scenario:

Process A: Holds database connection 1, requests database connection 2

Process B: Holds database connection 2, requests database connection 3

Process C: Holds database connection 3, requests database connection 1

Circular wait: A → B → C → A
Operating System ByteXL

All Four Conditions Must Hold

Deadlock occurs if and only if all four conditions are present simultaneously. If even one condition is
absent, deadlock cannot occur.

Example: Breaking Condition 1 (Mutual Exclusion)

Resource: Read-only file

Process P1: Reads file (shared access)

Process P2: Reads file (shared access)

No mutual exclusion → No deadlock (both can access simultaneously)

Example: Breaking Condition 2 (Hold and Wait)

Process P1:

1. Request both A and B together

2. If both available, acquire both

3. If not, release any acquired resource and retry

No hold-and-wait → No deadlock (never holds one while waiting for another)

Example: Breaking Condition 3 (No Preemption)

Process P1 holds Resource A

Process P2 needs Resource A

OS forcibly takes A from P1 and gives it to P2.

Preemption allowed → No deadlock (OS can break cycles)

Example: Breaking Condition 4 (Circular Wait)

All processes must request resources in order: R1 before R2 before R3

Process P1: Requests R1, then R2

Process P2: Requests R1, then R3

No circular dependency can form → No deadlock

(P2 cannot request R1 after R3 because R1 comes before R3 in the ordering)

What's Next

We've defined deadlock and identified the four necessary conditions: mutual exclusion, hold and wait, no
preemption, and circular wait. Deadlock occurs only when all four hold simultaneously. This understanding
reveals two management strategies: prevention (ensuring at least one condition never holds) and
avoidance (allowing conditions but carefully allocating resources to avoid deadlock). In the next section,
we'll explore prevention strategies that break specific conditions and Banker's algorithm for safe resource
allocation.
Operating System ByteXL
Operating System ByteXL