Operating System (CS2701)

Deadlock Prevention, Avoidance & Recover

​

​

Dr. Rourab Paul

Computer Science Department, SNU University, Chennai

​

​

Operating System

Introduction

Operating System

2

A deadlock occurs when two or more processes are waiting indefinitely for resources held by each other.

​

Example:

​

Process P1 holds Resource R1, waits for R2

​

Process P2 holds Resource R2, waits for R1

​

→ Both are stuck forever!

Conditions for Deadlock

Operating System

3

Deadlock occurs only if all four hold simultaneously:

1. Mutual Exclusion – Resources are non-shareable�
2. Hold and Wait – Process holds one resource, requests another�
3. No Preemption – Resources cannot be forcibly taken back�
4. Circular Wait – A circular chain of waiting processes

​

We emphasize that all four conditions must hold for a deadlock to occur.

​

Deadlock Prevention

Operating System

4

Strategy: Deny one of the four necessary conditions.

The most realistic and widely used deadlock prevention method is breaking the Circular Wait condition — by imposing an ordering on resources and requiring threads to request resources in that fixed order

Example — Circular Wait Prevention

Operating System

5

We define a global order on resources:

F(first_mutex) = 1

F(second_mutex) = 5

​

Rule:� A thread can only lock resources in increasing order of F.

Allowed: first_mutex → second_mutex�Not Allowed: second_mutex → first_mutex

Prevents circular waiting, hence no deadlock.

​

Example — Circular Wait Prevention

Operating System

6

pthread_mutex_lock(&first_mutex);

pthread_mutex_lock(&second_mutex);

// critical section

pthread_mutex_unlock(&second_mutex);

pthread_mutex_unlock(&first_mutex);

​

All threads follow the same lock order → deadlock-free

Deadlock Avoidance

Operating System

7

Don’t prevent conditions — analyze requests dynamically to avoid unsafe states.

Concept:� Allow resource allocation only if it keeps the system in a safe state.

Uses Banker’s Algorithm (Dijkstra):

• Each process declares maximum resource need in advance.�
• System grants a request only if it results in a safe state.

​

Banker’s Algorithm for Deadlock Avoidance

Operating System

8

Proposed by Edsger Dijkstra.�

Used to avoid deadlock by ensuring the system never enters an unsafe state.�

Called “Banker” because it’s like a bank lending money:��� The bank only lends if it can satisfy all customers eventually, ensuring nobody is left waiting indefinitely.

​

Banker’s Algorithm for Deadlock Avoidance

Operating System

9

Safe State: A state is safe if the system can allocate resources to all processes in some order and every process can complete.

Unsafe State: A state is unsafe if there exists at least one sequence where some process may never finish.

Unsafe ≠ deadlock, but unsafe can lead to deadlock.

Process Resource Info:

Max Need: Maximum resources a process may request.

Allocation: Resources currently held by the process.

Need: Remaining resources needed = Max Need − Allocation

Available: Free resources in the system.

Banker’s Algorithm Steps

Operating System

10

1. Initialize Available, Allocation, and Need matrices.
2. Find a process P whose Need ≤ Available.
3. If found:�Pretend to allocate resources to P.�Add P’s allocated resources back to Available after it finishes.�Mark P as completed.
4. Repeat step 2 for all processes.
5. If all processes can finish → state is safe.
6. If no process can proceed → unsafe, so the request is denied.

​

Banker’s Algorithm Example

Operating System

11

System:

• Total resources: 10
• Processes: P0, P1, P2
• Max Needs:

Banker’s Algorithm Example Step 2

Operating System

12

System:

• Total resources: 10
• Processes: P0, P1, P2

Available = Total - sum(Allocation) = 10 - (0+1+2) = 7

​

Banker’s Algorithm Example Step 3.1

Operating System

13

• Available = 7
• Check each process:
• P0: Need = 7 → 7 ≤ 7 ✅ → can allocate
• P1: Need = 4 → 4 ≤ 7 ✅ → can allocate
• P2: Need = 1 → 1 ≤ 7 ✅ → can allocate
• We can choose any process whose Need ≤ Available.
• To illustrate, we pick P2 (smallest Need) first.

​

Banker’s Algorithm Example Step 3.2

Operating System

14

Allocate resources to P2 (Need = 1)

P2 completes its execution

Release resources held by P2: Allocation = 2

Update Available: Available = old Available + Allocation of P2 = 7 + 2 = 9

P2 is marked finished.�

​

Banker’s Algorithm Example Step 3.3

Operating System

15

Now, Available = 9

• Check next process:
• P1: Need = 4 → 4 ≤ 9 ✅ → allocate → finish → release 1 → Available = 9 + 1 = 10
• P0: Need = 7 → 7 ≤ 10 ✅ → allocate → finish → release 0 → Available = 10 + 0 = 10

Banker’s Algorithm Example Step 3.4

Operating System

16

• All processes can finish in some order without deadlock.
• Safe sequence found:
• P2 → P1 → P0
• Any order that satisfies Need ≤ Available works as a safe sequence. Another valid safe sequence could be P1 → P2 → P0, etc.
• If at any point no process can be satisfied, the system is in an unsafe state.
• Banker’s Algorithm denies requests that would leave the system in an unsafe state.

Prevention VS Avoidance

Operating System

17

Recover

Operating System

18

To eliminate deadlocks by aborting a process or thread, we use one of two methods. In both methods, the system reclaims all resources allocated to the terminated processes.

• Abort all deadlocked processes. This method clearly will break the deadlock cycle, but at great expense. The deadlocked processes may have computed for a long time, and the results of these partial computations must be discarded and probably will have to be recomputed later.
• Abort one process at a time until the deadlock cycle is eliminated. This method incurs considerable overhead, since after each process is aborted, a deadlock-detection algorithm must be invoked to determine whether any processes are still deadlocked

Thank You

Operating System

19