Deadlock Avoidance Bankers Algorithm

Definition

Deadlock Avoidance means the system grants resources carefully to avoid entering unsafe states where deadlock might occur. Unlike prevention (eliminates conditions), avoidance allows all conditions but prevents deadlock through careful allocation decisions. Banker’s Algorithm is the most famous avoidance algorithm.

Safe vs Unsafe States

Safe State

A state where deadlock is impossible (or at least not guaranteed).

Definition: A sequence exists where processes can complete without deadlock.

Example - 3 Processes, Total 10 Units of Resource:

Allocation:  P1=4, P2=3, P3=2 (total=9 used)
Available: 1

Safe sequence: P3 (needs 2, has 2) → releases 2 → total available = 3
              P1 (needs 4 more, has 4) → releases 4 → total available = 7
              P2 (needs 3 more, has 3) → releases 3 → total available = 10

All complete! So state is SAFE.

Unsafe State

A state where deadlock might occur.

Allocation:  P1=5, P2=5, P3=5 (total=15)
Available: 0 (exactly allocated)

What if:
P1 needs 1 more unit → blocked (none available)
P2 needs 1 more unit → blocked (none available)
P3 needs 1 more unit → blocked (none available)

No process can finish! DEADLOCK possible (or starvation).
This is UNSAFE.

But if P1 could finish with 5 (no more needed):
P1 finishes → releases 5 → others proceed
Then SAFE.

Key: Unsafe means might deadlock depending on demands.

Banker’s Algorithm

Named after bank loan management analogy.

The Idea

Bank manager decides whether to grant loan request:

Bank has: $250,000 available
Customers:
- Customer 1: Max need $100,000, currently owes $50,000
- Customer 2: Max need $150,000, currently owes $100,000
- Customer 3: Max need $80,000, currently owes $50,000

Customer 1 requests $30,000 more.

Manager thinks:
"If I give this loan, will I be able to satisfy everyone?"
- Customer 1 owed $50+30=$80, needs $20 more max
- If 1 gets $20, returns $100, have $120
- Customer 2 needs $50 more max
- If 2 gets $50, returns $150, have $120
- Customer 3 needs $30 more max
- If 3 gets $30, returns $80, have $90

Everyone can complete! Safe to grant loan.

Algorithm Steps

Before granting resource request:

Tentatively grant the request
Compute new state (if request granted)
Check if state is safe (sequence exists to complete all)
If safe: Grant request
If unsafe: Deny request (process waits)

Data Structures

// For each process i and resource j:
MAX[i][j]       = Maximum needed by process i of resource j
ALLOCATED[i][j] = Currently allocated to process i
NEED[i][j]      = NEED = MAX - ALLOCATED (still needs)
AVAILABLE[j]    = Available units of resource j

Example System

Resources: Disk (D), Printer (P)
Total: 10 Disks, 5 Printers

         MAX     ALLOCATED    NEED      AVAILABLE
P1:  (7,3)    (5,1)        (2,2)      D: 1
P2:  (3,2)    (2,0)        (1,2)      P: 4
P3:  (9,0)    (2,0)        (7,0)

Safety Check Algorithm

function is_safe():
    // Find a safe sequence where all processes finish

    WORK = AVAILABLE  // Available to work with
    FINISH[i] = false for all i

    while (exists process i where FINISH[i] == false
           and NEED[i] <= WORK):
        // This process can finish!
        WORK += ALLOCATED[i]  // Process finishes, returns resources
        FINISH[i] = true

    if (all FINISH[i] == true):
        return SAFE
    else:
        return UNSAFE

Request Handling

Process i requests NEED[i]

if (NEED[i] > AVAILABLE):
    block process i
else:
    // Tentatively grant
    AVAILABLE -= NEED[i]
    ALLOCATED[i] += NEED[i]
    NEED[i] -= NEED[i]  // Zero out need

    if (is_safe()):
        // Grant confirmed (process continues)
    else:
        // Undo tentative allocation
        AVAILABLE += NEED[i]
        ALLOCATED[i] -= NEED[i]
        NEED[i] += NEED[i]  // Restore need

        block process i

Banker’s Algorithm Example

System State

Resources: 12 units

Process 1: MAX=(10), ALLOCATED=(5), NEED=(5), AVAILABLE=2
Process 2: MAX=(4), ALLOCATED=(2), NEED=(2)
Process 3: MAX=(7), ALLOCATED=(3), NEED=(4)

Total: 10 allocated, 2 available ✓

Process 1 Requests 2 Units

Check if safe:

If we grant 2 to Process 1:
  ALLOCATED[1] = 7, NEED[1] = 3
  AVAILABLE = 0

Can anyone finish?
- Process 1: needs 3, have 0 → NO
- Process 2: needs 2, have 0 → NO
- Process 3: needs 4, have 0 → NO

UNSAFE! → DENY request

Process 2 Requests 1 Unit

Check if safe:

If we grant 1 to Process 2:
  ALLOCATED[2] = 3, NEED[2] = 1
  AVAILABLE = 1

Process 2 needs 1 more:
  Process 2 gets 1, finishes, releases 4 → AVAILABLE = 5

Now with 5:
  Process 1 needs 5 → finishes, releases 10 → AVAILABLE = 15
  Process 3 needs 4 → finishes, releases 7 → AVAILABLE = 22

Safe sequence: 2 → 1 → 3

SAFE! → GRANT request

Advantages of Banker’s Algorithm

Guaranteed Safety: System never enters unsafe state
Deadlock Prevention: By maintaining safety
Maximum Concurrency: More than prevention strategies
Fair: Don’t unnecessarily deny requests

Disadvantages

High Overhead:
- Must check safety for every request
- Safety check is O(n² × m) where n=processes, m=resources
- On every allocation!

Must Know Maximum Need:

Process must declare max resource upfront
But dynamic programs don't know max in advance!
Example: User enters unknown number of queries

Processes Can’t Change:
- Can’t add new processes (might violate safety)
- Can’t change max needs
Resource Waste:
- Conservative (deny safe requests if they might be risky)
- May hold back on allocation even if process could use more

Practical Issues

Unknown Maximum Need

Process doesn't know max in advance:

while (true) {
    // Read unknown amount of data
    Process receives query

    Allocates 1KB for query result
    // At this point, max could be 1KB or 1MB or 1GB
    // What does process declare?
}

Solution: Declare conservatively high maximum (wastes safety)

Performance

For large systems with many resources:

Safety check expensive
Every allocation delayed
May not be worth it for rare deadlock

When to Use Banker’s Algorithm

Good For:

Small systems (few processes, few resource types)
Offline systems (know all needs upfront)
Critical systems (deadlock must be prevented)
Database transactions (knows queries upfront)

NOT Good For:

Large systems (performance overhead)
Dynamic systems (don’t know max needs)
Frequently allocating (high checking overhead)
Systems where deadlock unlikely (prevention simpler)

Real-World Usage

Where Used:

Some database systems (transaction management)
Specialized real-time systems
Academic research

Not Commonly Used:

Operating systems (overhead too high)
Web servers (dynamic allocation)
Modern systems (prefer detection-and-recovery)

Comparison with Prevention

Aspect	Prevention	Avoidance (Banker’s)
Guarantee	Deadlock impossible	Deadlock prevented
When decided	Design time	Runtime
Concurrency	Lower	Higher
Overhead	Low	High per allocation
Flexibility	Rigid	Flexible
Knowledge needed	Resource structure	Exact max needs
Practical use	Common	Rare

Summary

Banker’s Algorithm is powerful deadlock avoidance technique that maintains safety. For every resource request, it checks if granting keeps system in safe state. Provides better concurrency than prevention but has high computational overhead. Requires knowing maximum resource needs upfront. Rarely used in practice (overhead and knowledge requirement), but important for understanding deadlock avoidance concepts. Prevention (like resource ordering) and detection-and-recovery more practical for most systems.