os – Shubham

📊 DEADLOCKS — MIND MAP

Deadlock → Circular wait where processes hold resources & wait for others

4 Conditions → Mutual Exclusion, Hold & Wait, No Preemption, Circular Wait

Prevention → Eliminate any one of the 4 conditions

Avoidance → Banker’s Algorithm, Resource Allocation Graph

Detection → Wait-for Graph, Detection Algorithm

Recovery → Process termination, Resource preemption

1.1 What is Deadlock?

📖 Definition: A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for a resource held by another process in the set. No process can proceed — they are all stuck forever.

💡 Real-life Example — Traffic Jam:

Imagine a 4-way intersection where:

Car A is blocking Car B’s path and waiting for Car C to move
Car B is blocking Car C’s path and waiting for Car D to move
Car C is blocking Car D’s path and waiting for Car A to move
Car D is blocking Car A’s path and waiting for Car B to move

Result → Nobody moves! This circular dependency = Deadlock

💡 OS Example:

Process P1 holds Resource R1 and needs R2.
Process P2 holds Resource R2 and needs R1.
→ Both are waiting for each other → Deadlock!

1.2 Conditions for Deadlock (Coffman Conditions)

⚠️ Key Point: ALL four conditions must hold simultaneously for deadlock to occur. Eliminating even ONE condition prevents deadlock.

1. Mutual Exclusion

At least one resource must be non-shareable — only one process can use it at a time.

Example: A printer can only be used by one process at a time.

2. Hold and Wait

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

Example: P1 holds Printer and is waiting for Scanner.

3. No Preemption

Resources cannot be forcibly taken away from a process. A resource can only be released voluntarily by the process holding it.

Example: OS cannot forcibly take the printer away from P1.

4. Circular Wait

A set of processes {P0, P1, …, Pn} exist such that P0 is waiting for a resource held by P1, P1 is waiting for P2, …, Pn is waiting for P0.

Example: P1→P2→P3→P1 (circular chain)

Circular Wait Diagram: P1 ──holds──► R1 ──needed by──► P2 ▲ │ │ │ needs holds │ │ R2 ◄──────────────────────────── R2 P1 waits for R2 (held by P2) P2 waits for R1 (held by P1) → DEADLOCK!

Fig 1.1 — Circular Wait causing Deadlock

1.3 Resource Allocation Graph (RAG)

📖 Definition: A Resource Allocation Graph is a directed graph used to describe deadlocks. It shows which process holds which resource and which resource is requested by which process.

RAG Components:

Process Node: Represented by a circle (○) → P1, P2, P3
Resource Node: Represented by a rectangle (□) → R1, R2, R3
Request Edge: Arrow from Process → Resource (Pi → Rj) means Pi is requesting Rj
Assignment Edge: Arrow from Resource → Process (Rj → Pi) means Rj is assigned to Pi

RAG WITHOUT Deadlock: RAG WITH Deadlock: (P1) ──request──► [R1] (P1) ──request──► [R1] │ │ assign assign │ │ ▼ ▼ (P2) (P2)──request──►[R2] │ assign │ ▼ (P1) ← Cycle! = Deadlock

Fig 1.2 — Resource Allocation Graph Examples

⚠️ RAG Rule:

If graph has NO cycle → No deadlock
If graph HAS a cycle → Deadlock MAY exist (definitely if single instance per resource)

1.4 Deadlock Prevention

📖 Definition: Deadlock prevention means designing the system so that at least one of the four necessary conditions for deadlock can never hold. We eliminate the possibility of deadlock occurring.

✅ Method 1 — Eliminate Mutual Exclusion:

Make resources shareable wherever possible.

Problem: Not all resources can be shared (printer, tape drive)

✅ Method 2 — Eliminate Hold & Wait:

Two approaches:

Approach 1: Process must request ALL resources before starting execution. If all available → proceed. Else → wait without holding anything.
Approach 2: Process can request resources only when it has NONE.

Problem: Low resource utilization, starvation possible

✅ Method 3 — Allow Preemption:

If a process holding resources requests a new resource that is not available:

All currently held resources are preempted (taken away)
Process added to waiting list
Process restarts only when it gets ALL needed resources

Problem: Only works for resources whose state can be saved (CPU registers, memory)

✅ Method 4 — Eliminate Circular Wait:

Impose a total ordering on all resource types. Process can only request resources in increasing order of enumeration.

Example: R1=1, R2=2, R3=3 → Process must request R1 before R2 before R3. No circular wait possible!

❌ Disadvantages of Prevention:

Low resource utilization
Reduced system throughput
Starvation may occur

1.5 Deadlock Avoidance & Safe State

📖 Definition: Deadlock avoidance requires that the OS have additional information about how resources will be requested. The system dynamically examines the resource allocation state to ensure circular wait never exists.

📖 Safe State: A state is safe if the system can allocate resources to each process in some order and still avoid deadlock. A safe sequence {P1, P2, …, Pn} exists such that for each Pi, the resources Pi can still request can be satisfied by currently available resources plus resources held by all Pj (j < i).

💡 Safe vs Unsafe State:

Safe State: System can guarantee completion of all processes → No deadlock
Unsafe State: No guarantee → Deadlock MAY occur (not necessarily)
Deadlock State: Processes are already stuck → Deadlock occurred

State Relationship: ┌─────────────────────────────┐ │ UNSAFE STATE │ │ ┌───────────────────────┐ │ │ │ SAFE STATE │ │ │ └───────────────────────┘ │ │ │ │ ┌──────────────┐ │ │ │ DEADLOCK │ │ │ └──────────────┘ │ └─────────────────────────────┘ Safe → Always OK Unsafe → Might be OK, might deadlock Deadlock → Already stuck

Fig 1.3 — Safe, Unsafe & Deadlock States

1.1 What is Deadlock?

1.2 Conditions for Deadlock (Coffman Conditions)

1.3 Resource Allocation Graph (RAG)

1.4 Deadlock Prevention

1.5 Deadlock Avoidance & Safe State

🏦 Banker’s Algorithm