UNIT – 6: DEADLOCK AND PROTECTION
INTRODUCTION TO DEADLOCK
In a computer system, multiple processes run simultaneously and need resources
like CPU time, memory, files, and I/O devices to execute. Resources are usually
allocated to processes in a sequence:
1. The process requests a resource.
2. If available, the OS allocates it; otherwise, the process waits.
3. After usage, the process releases the resource.
Deadlock is a condition where multiple processes are waiting for resources held by
each other, and none of them can proceed.
Example:
- P1 holds R1 and requests R2 (held by P2)
- P2 holds R2 and requests R3 (held by P3)
- P3 holds R3 and requests R1 (held by P1)
→ Cycle forms → Deadlock occurs.
DIFFERENCE BETWEEN DEADLOCK AND STARVATION
Deadlock:
- All processes involved are blocked.
- Infinite waiting time.
- Caused due to circular dependency.
- All deadlocks cause starvation.
Starvation:
- Only low-priority process is blocked.
- Long waiting, not infinite.
- Caused due to priority-based resource allocation.
- Not all starvation is deadlock.
NECESSARY CONDITIONS FOR DEADLOCK
1. Mutual Exclusion – Only one process can use a resource at a time.
2. Hold and Wait – A process holds one resource and waits for another.
3. No Preemption – Resource cannot be forcibly taken back.
4. Circular Wait – A chain of processes exists where each waits for a resource held
by another process in the chain.
STRATEGIES FOR HANDLING DEADLOCK
1. Deadlock Ignorance – Assume deadlocks are rare and ignore them (used in
Windows/Linux).
2. Deadlock Prevention – Break one of the four conditions.
3. Deadlock Avoidance – Allocate only if system stays in a safe state.
4. Deadlock Detection and Recovery – Let it happen, then detect and recover.
DEADLOCK PREVENTION
To prevent deadlock, we break one of the four conditions:
1. Mutual Exclusion – Not practical to break. Spooling used for printers.
2. Hold and Wait – Request all resources at once. Not practical.
3. No Preemption – Force process to release resource. May lose progress.
4. Circular Wait – Order resources by number. Request in order to avoid cycles.
DEADLOCK AVOIDANCE
OS checks if new request keeps system in safe state.
Safe State: All processes can complete in some order.
Unsafe State: Risk of deadlock.
Processes must declare max resource need. Banker's Algorithm is often used.
RESOURCE ALLOCATION GRAPH (RAG)
Circle → Process (P1, P2, etc.)
Rectangle → Resource (R1, R2, etc.)
Arrow from process to resource → Request
Arrow from resource to process → Allocation
Cycle in RAG with single instance = Deadlock
Cycle with multiple instances ≠ always deadlock
ALLOCATION AND REQUEST MATRICES
1. Allocation Matrix – Shows resources held by each process.
2. Request Matrix – Shows needed resources.
3. Available Vector – Resources currently available.
If requests can't be fulfilled → Deadlock.
DEADLOCK DETECTION AND RECOVERY
Detection:
- Use RAG or matrices. Detect cycles or use Banker's Algorithm.
Recovery:
For Resources:
- Preempt Resource – Take and reassign it.
- Rollback – Return to safe state.
For Processes:
- Kill a Process – Choose the one with least progress.
- Kill All – Last resort, causes inefficiency.
