Chapter 8: Deadlocks | Operating Systems | FAST-NUCES

Chapter 8: Deadlocks
Easy Study Notes • OS Chapter 8

Topics Covered
System Model • Deadlock Characterization • Resource Allocation Graph • Methods for Handling •
Deadlock Prevention • Safe State • Deadlock Avoidance • Banker's Algorithm • Safety Algorithm

1. System Model

• System resources: Resource types R1, R2 ... Rm (CPU, memory, I/O devices)
• Each resource Ri has Wi instances
• Every process uses a resource in 3 steps:
◦ REQUEST — ask for the resource
◦ USE — work with the resource
◦ RELEASE — give back the resource

💡 Memory trick: Request → Use → Release (RUR)

2. What is a Deadlock?

A deadlock occurs when EVERY process in a set is waiting for an event that can ONLY be
caused by another process in the SAME set — they wait forever.

Deadlock Example — Two Processes

Pi requests Resource Rb held by Pj
Pi waits for Pj to release Rb
Meanwhile Pj requests Resource Ra held by Pi
Pj waits for Pi to release Ra
Result Neither can proceed — DEADLOCK!

Real World Examples

• Disk drives: P1 and P2 each hold one disk drive and need the other's — neither can proceed
• Database records: Process A locks R1, Process B locks R2; each tries to lock the other's record

3. Four Necessary Conditions for Deadlock

💡 ALL FOUR must hold simultaneously for a deadlock to occur. Remove even ONE → no
deadlock.

Page 1
Chapter 8: Deadlocks | Operating Systems | FAST-NUCES

Mutual Exclusion
Only ONE process can use a resource at a time. Non-sharable mode. Requesting process
1 must wait until the resource is released.
Example: Dining Philosophers — only one philosopher can hold a chopstick.

Hold and Wait

A process holding at least one resource is WAITING to acquire more resources held by other
2 processes.
Example: Process A holds tape+disk and waits for printer held by Process B.

No Preemption
Resources CANNOT be forcibly taken from a process. They can only be released voluntarily
3 by the holding process.
Example: OS cannot grab a printer away from a running process mid-job.

Circular Wait
4 A circle of processes: P0 waits for P1, P1 waits for P2, ..., Pn waits for P0.
Example: Like a ring of people, each waiting for the person in front of them.

4. Resource Allocation Graph (RAG)

• RAG is a directed graph showing who holds/needs what at a given moment

• V (vertices): All Processes (circles) + All Resource Types (rectangles with dots)
• E (edges): Directed arrows showing requests and allocations

Two Types of Edges

Edge Type Direction Meaning
Request Edge Pi → Rj Process Pi is WAITING for resource Rj
Assignment Edge Rj → Pi Resource Rj is ALLOCATED to process Pi
Claim Edge Pi - - → Rj Process Pi MAY request Rj in the future (dashed
line)

Cycles and Deadlock — Key Rules

Situation Conclusion
No cycle in graph NO deadlock (safe)
Cycle + 1 instance per resource DEADLOCK (certain)
Cycle + multiple instances per resource POSSIBLE deadlock (not certain)

Page 2
Chapter 8: Deadlocks | Operating Systems | FAST-NUCES

💡 Cycle is NECESSARY for deadlock but not always SUFFICIENT when multiple instances exist.

5. Methods for Handling Deadlocks

Three Approaches
# Method How it works
1 Prevention / Avoidance Design the system so deadlock can NEVER occur — eliminate
one of the 4 conditions
2 Detection + Recovery Allow deadlock to occur; detect it then recover (rollback or kill
process)
3 Ignore it (Ostrich) Pretend deadlocks never happen — used in most OS like
Unix/Windows (rare events)

6. Deadlock Prevention

💡 Prevent deadlock by making at least ONE of the four conditions IMPOSSIBLE.

▸ 1. Eliminate Mutual Exclusion

• Make resources sharable (e.g. read-only files)
• Sharable resources NEVER cause deadlock
• Problem: Some resources (e.g. mutex locks) are inherently non-sharable — can't always do this

▸ 2. Eliminate Hold and Wait

• Protocol 1: Process must request ALL resources before execution starts
◦ Problem: Holds printer entire execution even if only needed at the end (waste)
• Protocol 2: Process can request resources only when it holds NONE
◦ Must release all current resources before requesting new ones
• Both problems: Low resource utilization + starvation possible

▸ 3. Eliminate No Preemption
• If a process holding resources cannot get more: PREEMPT all its current resources
• Preempted resources are given to other waiting processes
• Process restarts only when it can get ALL old + new resources together

▸ 4. Eliminate Circular Wait

• Assign a unique number to each resource type
• Rule: Process can only request resources in INCREASING numeric order
• Example ordering:
◦ Tape drive = 1

Page 3
Chapter 8: Deadlocks | Operating Systems | FAST-NUCES

◦ Disk drive = 4
◦ Printer = 6
• You can only request resource N+1 after getting resource N

💡 Increasing order breaks the circle — you can't loop back to request a lower-numbered resource.

7. Deadlock Avoidance & Safe State

Avoidance: OS knows in advance the maximum resources each process will ever need. It only
grants requests that keep the system in a SAFE STATE.

Safe State
• A state is SAFE if there exists a sequence <P1, P2, ..., Pn> that satisfies all processes
• For each Pi: its remaining needs can be satisfied by: current available + resources held by all earlier Pj's
• Safe state = no deadlock possible
• Unsafe state = deadlock may occur (not guaranteed)

💡 Safe → no deadlock | Unsafe → possible deadlock (NOT certain deadlock)

Safe State Example (24 tape drives, 3 processes)

Process Max Need Allocated Still Needs
P0 20 10 10
P1 8 5 3
P2 18 4 14

• Available = 24 − (10+5+4) = 5
• P1 needs 3 → gets 3, finishes, returns 8 → Available = 10
• P0 needs 10 → gets 10, finishes, returns 20 → Available = 20
• P2 needs 14 → gets 14 from 20 available
• Safe sequence: <P1, P0, P2> ✓

Two Avoidance Algorithms

Single Instance Multiple Instances
Resource Allocation Graph (claim edges + cycle Banker's Algorithm
check)

8. Banker's Algorithm

Page 4
Chapter 8: Deadlocks | Operating Systems | FAST-NUCES

Think of it like a bank: only loan money if you know you can get it all back eventually. Only
grant requests that keep the system safe.

Data Structures
Available[j] k instances of Rj available right now
Max[i][j] Maximum instances of Rj that process Pi will ever need
Allocation[i][j] Instances of Rj currently allocated to Pi
Need[i][j] How many more Pi needs: Need = Max − Allocation

Safety Algorithm — Step by Step

• Step 1: Set Work = Available; set Finish[i] = false for all i
• Step 2: Find process i where Finish[i]=false AND Need[i] ≤ Work
• Step 3: Work = Work + Allocation[i]; Finish[i] = true; go to Step 2
• Step 4: If Finish[i]=true for ALL i → SAFE STATE. Otherwise → UNSAFE

💡 Pretend each process Pi runs to completion — return its resources, then find who can run next.

Resource Request Algorithm — Step by Step

• Step 1: If Request[i] > Need[i] → ERROR (exceeded max claim)
• Step 2: If Request[i] > Available → WAIT (resources not available)
• Step 3: Tentatively allocate: Available -= Request; Allocation[i] += Request; Need[i] -= Request
• Step 4: Run Safety Algorithm on new state
◦ If SAFE → grant the request
◦ If UNSAFE → rollback and make Pi wait

Banker's Algorithm — Full Worked Example

• 5 processes P0–P4; 3 resource types: A(10), B(5), C(7)
• Available = [3, 3, 2]

Process Max A Max B Max C Alloc A Alloc B Alloc C Need A Need B Need C
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
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1

▸ Safety Algorithm Walkthrough

• Work = [3,3,2]

Page 5
Chapter 8: Deadlocks | Operating Systems | FAST-NUCES

• P0 needs [7,4,3] > Work=[3,3,2]? YES — Skip

• P1 needs [1,2,2] ≤ Work=[3,3,2]? YES — Run P1. Work = [3,3,2]+[2,0,0] = [5,3,2]
• P3 needs [0,1,1] ≤ Work=[5,3,2]? YES — Run P3. Work = [5,3,2]+[2,1,1] = [7,4,3]
• P4 needs [4,3,1] ≤ Work=[7,4,3]? YES — Run P4. Work = [7,4,3]+[0,0,2] = [7,4,5]
• P0 needs [7,4,3] ≤ Work=[7,4,5]? YES — Run P0. Work = [7,4,5]+[0,1,0] = [7,5,5]
• P2 needs [6,0,0] ≤ Work=[7,5,5]? YES — Run P2.
• Safe Sequence: <P1, P3, P4, P0, P2> ✓

▸ Request Example — P1 requests (1,0,2)

• Check 1: (1,0,2) ≤ Need1=[1,2,2]? YES
• Check 2: (1,0,2) ≤ Available=[3,3,2]? YES
• Tentatively allocate:
◦ Available = [3,3,2]−[1,0,2] = [2,3,0]
◦ Allocation1 = [2,0,0]+[1,0,2] = [3,0,2]
◦ Need1 = [1,2,2]−[1,0,2] = [0,2,0]
• Run Safety → Safe Sequence <P1,P3,P4,P0,P2> still valid
• Decision: GRANT the request to P1 ✓

9. Quick Revision Cheat Sheet

Term In One Line

Deadlock Every process waits for a resource held by another in the same set —
forever
Mutual Exclusion Only 1 process can use a resource at a time
Hold and Wait Holding resource while waiting for more held by others
No Preemption Resources can't be forcibly taken away
Circular Wait P0→P1→P2→...→Pn→P0 chain of waiting
RAG Directed graph showing allocations & requests
Request Edge Pi → Rj means Pi is waiting for Rj
Assignment Edge Rj → Pi means Rj is given to Pi
Safe State A sequence exists that can satisfy all processes without deadlock
Unsafe State No safe sequence — deadlock may occur
Prevention Remove one of 4 conditions permanently
Avoidance Grant requests only if safe state maintained (Banker's)
Banker's Algorithm Check if granting a request keeps system safe (multi-instance)
Safety Algorithm Simulate process completion to verify safe state
Need[i][j] Max[i][j] − Allocation[i][j]
Ostrich Method Ignore deadlocks entirely (used in most real OS)

Page 6