CS330 - Operating Systems
System Deadlocks, Prevention, Avoidance, Detection & Recovery
A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource acquired by some other process.
Process P1 holds Resource R1 and waits for Resource R2
Process P2 holds Resource R2 and waits for Resource R1
Result: Both processes wait forever!
Deadlock can arise if ALL FOUR conditions hold simultaneously:
At least one resource must be held in a non-sharable mode. Only one process at a time can use the resource.
A process must be holding at least one resource and waiting to acquire additional resources held by other processes.
Resources cannot be preempted; a resource can be released only voluntarily by the process holding it.
A set {P0, P1, ..., Pn} of waiting processes must exist such that P0 waits for P1, P1 waits for P2, ..., and Pn waits for P0.
All four conditions must be present for a deadlock to occur. If we can prevent ANY ONE of these conditions, we can prevent deadlock!
A directed graph used to describe deadlocks
[Insert RAG diagrams showing deadlock and no-deadlock scenarios]
Ensure that at least one of the four necessary conditions cannot hold.
Requires advance knowledge of resource needs. System decides if request should wait.
Allow deadlocks to occur, then detect and recover.
Ostrich Algorithm - pretend deadlocks never occur.
Restrain the ways resource requests can be made to ensure at least one condition cannot occur:
Prevention: Not practical for most resources. Some resources are inherently non-sharable (e.g., printer).
Solution: Use spooling for some resources (printer queues).
Prevention: Guarantee that when a process requests a resource, it doesn't hold any other resources.
Solutions:
Prevention: If a process holding resources requests another that cannot be immediately allocated, all currently held resources are released.
Limitation: Applied only to resources whose state can be saved (CPU, memory).
Prevention: Impose a total ordering of all resource types.
Solution: Require processes to request resources in increasing order of enumeration.
A state is safe if the system can allocate resources to each process in some order and still avoid deadlock.
A system is in a safe state if there exists a safe sequence of all processes.
No Deadlock Possible
May Lead to Deadlock
System Stuck
For single instance of each resource type:
Named after banking system that ensures bank never allocates all cash.
Available resources
Maximum demand
Currently allocated
Need = Max - Allocation
System is in safe state with this execution order
Allow system to enter deadlock state, then detect and recover.
| Factor | Consideration |
|---|---|
| Priority | Lower priority process selected first |
| Time | How long process has computed and remaining time |
| Resources | Resources used and resources needed to complete |
| Rollback Cost | Number of processes that need termination |
| Interactive/Batch | Interactive processes may have higher priority |
Given: 5 processes (P0-P4), 3 resource types (A=10, B=5, C=7)
| Process | Allocation (A B C) |
Max (A B C) |
Need (A B C) |
|---|---|---|---|
| P0 | 0 1 0 | 7 5 3 | 7 4 3 |
| P1 | 2 0 0 | 3 2 2 | 1 2 2 |
| P2 | 3 0 2 | 9 0 2 | 6 0 0 |
| P3 | 2 1 1 | 2 2 2 | 0 1 1 |
| P4 | 0 0 2 | 4 3 3 | 4 3 1 |
Available: A=3, B=3, C=2
Safe Sequence: <P1, P3, P4, P2, P0>
System State: SAFE ✓
If P1 requests (1,0,2):
Q1. Which of the following is NOT a necessary condition for deadlock?
Q2. In Resource Allocation Graph, a cycle indicates:
Q3. Banker's algorithm is used for:
Q4. A safe state means:
Q5. Which method prevents circular wait?
Q6. Explain the difference between deadlock prevention and deadlock avoidance.
Prevention: Structurally makes deadlock impossible by ensuring at least one necessary condition cannot occur.
Avoidance: Dynamically examines resource allocation state to ensure system never enters unsafe state.
Q7. Given 3 processes with following needs. Is the system in safe state?
| Process | Allocated | Max |
|---|---|---|
| P0 | 1 | 4 |
| P1 | 2 | 3 |
| P2 | 2 | 9 |
Available = 2
Need: P0=3, P1=1, P2=7
Can satisfy P1 (Need=1 ≤ Available=2)
After P1: Available = 2 + 2 = 4
Can satisfy P0 (Need=3 ≤ Available=4)
After P0: Available = 4 + 1 = 5
Cannot satisfy P2 (Need=7 > Available=5)
System is NOT in safe state
| Term | Definition |
|---|---|
| Deadlock | Processes blocked forever waiting for each other |
| Livelock | Processes continuously change state but make no progress |
| Starvation | Process waits indefinitely while others proceed |
| Safe State | System can allocate resources without entering deadlock |
| Unsafe State | May lead to deadlock (not necessarily deadlocked) |
| RAG | Resource Allocation Graph for visualizing resource allocation |
| Banker's Algorithm | Deadlock avoidance algorithm for multiple resource instances |
| Wait-for Graph | Variant of RAG for deadlock detection |
| Circular Wait | Cyclic chain of processes waiting for resources |
| Resource Ordering | Prevention technique assigning order to resources |
| Rollback | Return process to previous safe state |
| Victim Selection | Choosing process to terminate or preempt |
[Insert RAG diagram with processes and resources]
[Insert comparison of RAGs with and without cycles]
[Insert state transition diagram]
[Insert step-by-step Banker's algorithm execution]
Note: Please provide the actual diagrams from your course materials to replace these placeholders.