Operating System - Deadlock Avoidance

What is Deadlock Avoidance?

Deadlock avoidance is a strategy where the system dynamically examines every resource request and decides whether it is safe to grant it, avoiding unsafe states that could lead to deadlock.

 Key Concept: Safe and Unsafe States

  • Safe State: There is at least one sequence of process execution where each process can finish, even if all request their maximum resources.

  • Unsafe State: No such sequence exists. It doesn’t mean deadlock has occurred yet, but it could happen.

 Banker’s Algorithm (Safe State Algorithm)

Named because it's like a banker who only loans money if they’re sure they can fulfill all future demands of their clients without going bankrupt.

For n processes and m resource types, we use:

  1. Available[]: How many instances of each resource are currently available.

  2. Max[][]: Maximum resources each process may need.

  3. Allocation[][]: Resources currently allocated to each process.

  4. Need[][]: What each process still needs (Need = Max - Allocation).

 Safe State Check Algorithm

  1. Initialize:

    • Work = Available (copy of available resources).

    • Finish[i] = false for all processes.

  2. Find a process i such that:

    • Finish[i] == false

    • Need[i] <= Work (i.e., all needed resources can be satisfied now).

  3. If found:

    • Pretend to allocate resources: Work = Work + Allocation[i].

    • Set Finish[i] = true.

    • Go back to step 2.

  4. If no such process is found, and some Finish[i] == false, the system is not in a safe state.

  5. If all Finish[i] == true, the system is in a safe state.

Example: 3 Processes, 3 Resources

Available = [3, 3, 2]

Process Max Allocation Need (Max - Allocation)
P0 [7,5,3] [0,1,0] [7,4,3]
P1 [3,2,2] [2,0,0] [1,2,2]
P2 [9,0,2] [3,0,2] [6,0,0]

 Step-by-Step Safe Sequence Check:

Start with Work = [3,3,2]

  • Check P1: Need = [1,2,2] <= Work = [3,3,2] → ✅
    → Allocate and release: Work = Work + Allocation[1] = [5,3,2], Finish[1]=true

  • Check P0: Need = [7,4,3] > Work = [5,3,2] → ❌

  • Check P2: Need = [6,0,0] <= Work = [5,3,2] → ❌

Only P1 could complete so far.

Next:

  • Still can't do P0 or P2 → No other process can proceed → Not a safe state ❌

So this is not a safe state.