OS: Deadlock Detection

# 1. Mutual Exclusion
✓ Resource ek time pe sirf ek process use kar sakte hain
✓ Printers, locks � exclusive hote hain

# 2. Hold and Wait
✓ Process ne resource hold kiya hai aur doosra resource wait kar rahi hai
? "Mere paas printer hai, mujhe scanner chahiye"

# 3. No Preemption
✓ Resource forcibly nahi le sakte � process khud chhodegi
✓ OS resource nahi cheen sakta

# 4. Circular Wait
✓ P1 ✓ P2 ✓ P3 ✓ P1 (circular chain)
✓ Sab ek doosre ka resource wait kar rahe hain

# DEADLOCK = All 4 conditions simultaneously true
✓ Agar ek bhi condition tod do ✓ deadlock nahi hoga!

# Prevention: Koi ek condition tod do permanently

# 1. Mutual Exclusion todna
✓ Resources ko sharable banao
✓ Problem: Sab resources sharable nahi ho sakte
✓ Example: Printer � exclusive hona zaroori hai

# 2. Hold and Wait todna
✓ Process shuru mein saare resources ek saath le
✓ Ya resource chahiye toh pehle chhodo doosra
✓ Problem: Resource utilization kam hota hai

# 3. No Preemption todna
✓ Agar process naya resource na le sake toh pehle chhodo
✓ OS forcefully resource le sakta hai
✓ Problem: State save karna padta hai (complex)

# 4. Circular Wait todna
✓ Resources ko numerical order mein number karo
✓ Process sirf higher number le sake
✓ No circular chain possible
✓ BEST PRACTICE!

# Avoidance: Runtime pe safe state ensure karo

# Banker's Algorithm (Dijkstra):
✓ OS bank jaise kaam karta hai
✓ Har process maximum needs bataata hai
✓ OS allocate tab karta hai jab safe state ho

# Safe State: Ek sequence hai jisme sab processes complete ho jaayein

# Example:
4 processes: P0, P1, P2, P3
3 resources: A(10), B(5), C(7)

Allocation: Max: Available:
P0: 0 1 0 7 5 3 3 3 2
P1: 2 0 0 3 2 2
P2: 3 0 2 9 0 2
P3: 2 1 1 2 2 2

Need = Max - Allocation:
P0: 7 4 3
P1: 1 2 2
P2: 6 0 1
P3: 0 1 1

Safe Sequence: P1 ✓ P3 ✓ P2 ✓ P0 ?

# If safe sequence exists ✓ State is safe ✓ Allocate
# If no safe sequence ✓ State is unsafe ✓ Don't allocate

# Detection: Deadlock ho chuka hai ya nahi � find karo

# Wait-for Graph:
✓ Edge: Pi ✓ Pj means Pi is waiting for Pj
✓ CYCLE in graph = DEADLOCK!

# Detection Algorithm:
✓ Periodically run karo detection algorithm
✓ Resources allocated, requested check karo
✓ Cycle detect karo

# Recovery Options:
1. Process Termination
 ✓ Sabse kam priority wala process terminate karo
 ✓ Ya sab processes terminate karo ( drastic)

2. Resource Preemption
 ✓ Kisi process se resource cheeno
 ✓ Rollback karo previous safe state pe

# Trade-off:
✓ Detection overhead vs Deadlock impact
✓ High stakes systems (banking) mein regularly run karo
✓ Low stakes systems mein recovery strategy rakho