Skip to content

🧩 Topic: Deadlock – Characterization

🧠 What is a Deadlock?

  • A deadlock is a situation where a group of two or more processes are blocked forever, waiting for each other to release resources.
  • It leads to permanent blocking and the system becomes unresponsive for those processes.

⚠️ Real-Life Analogy

Two people are holding one chopstick each and waiting for the other chopstick to eat. Neither can eat, and neither releases their chopstick. This is a deadlock.

🧩 Deadlock Conditions (Coffman’s Conditions)

Deadlock occurs only if all four of the following conditions hold simultaneously:

Condition Description
1. Mutual Exclusion At least one resource is non-shareable (only one process can use it at a time)
2. Hold and Wait A process holding a resource is waiting for more resources held by others
3. No Preemption Resources cannot be forcibly taken away; they must be released voluntarily
4. Circular Wait A set of processes are waiting for each other in a circular chain

🔁 Example

Consider three processes: P1, P2, P3 And three resources: R1, R2, R3

P1 → holding R1, waiting for R2  
P2 → holding R2, waiting for R3  
P3 → holding R3, waiting for R1

🔁 A circular wait occurs: P1 → P2 → P3 → P1 ✅ All four conditions are satisfied ⇒ Deadlock

🔄 Resource Allocation Graph (RAG)

  • A graphical method to visualize resource allocation and process waiting.

Components:

  • Process: Represented by a circle (e.g., P1, P2)
  • Resource: Represented by a square (e.g., R1, R2)
  • Request edge (→): From process to resource
  • Assignment edge (←): From resource to process

Deadlock Detection:

  • Cycle in RAG:

  • If only one instance per resource → cycle = deadlock

  • If multiple instances → cycle may or may not = deadlock

🧠 Key Points to Remember

Term Meaning
Deadlock A condition where no process can proceed because each is waiting for others
Coffman Conditions 4 conditions that must be present for deadlock to occur
Circular Wait The hallmark of deadlock; visualized using RAG

✅ Summary

  • A deadlock happens when processes are stuck waiting for resources held by each other.
  • Four conditions must hold together: Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait.
  • Resource Allocation Graph (RAG) helps detect potential deadlocks.

🧩 Topic: Deadlock Prevention

🧠 What is Deadlock Prevention?

  • Deadlock prevention is a strategy to design the system in such a way that at least one of the four necessary conditions for deadlock never holds.
  • The goal is to break at least one of the Coffman conditions.

🔁 Recall the 4 Coffman Conditions:

  1. Mutual Exclusion
  2. Hold and Wait
  3. No Preemption
  4. Circular Wait

Deadlock prevention means breaking any one or more of the above.

🧩 How to Prevent Deadlock

🔹 1. Mutual Exclusion

  • Explanation: Some resources (like printers) are not shareable.
  • Prevention: This condition cannot be eliminated for non-shareable resources.
  • ✅ Applicable only to resources that can be safely shared (like read-only files).

🔹 2. Hold and Wait

  • Explanation: A process holding a resource is waiting for another.

  • Prevention:

  • Require processes to request all resources at once before execution begins.

  • Or, allow a process to hold no resources while waiting for new ones.

✅ Eliminates hold and wait ❌ Causes low resource utilization and possible starvation

🔹 3. No Preemption

  • Explanation: Processes don’t give up resources voluntarily.

  • Prevention:

  • If a process requests a resource and it's not available, preempt all currently held resources, and restart the process later with all resources.

✅ Ensures resources can be forcibly taken ❌ Complex to implement ❌ May lead to data inconsistency or overhead

🔹 4. Circular Wait

  • Explanation: A circular chain of waiting processes exists.

  • Prevention:

  • Impose a strict global ordering of resource types (e.g., R1 < R2 < R3)

  • A process can only request resources in increasing order of enumeration.

✅ Simple and effective ❌ May require redesign of resource request logic

📌 Summary Table: Deadlock Prevention Methods

Coffman Condition How to Prevent It Issues
Mutual Exclusion Use sharable resources if possible Not always possible
Hold and Wait Request all resources at once Low resource utilization
No Preemption Forcefully take resources back Complex and risky
Circular Wait Impose resource ordering Rigid resource allocation

✅ Key Points

  • Deadlock prevention is proactive – avoids deadlock before it happens.
  • Requires system-level design changes to eliminate one of the four conditions.
  • Not always efficient – can lead to starvation, low CPU and resource usage.

🧩 Topic: Deadlock Avoidance

🧠 What is Deadlock Avoidance?

  • Deadlock avoidance means the operating system takes decisions dynamically to ensure the system never enters an unsafe state.

  • It requires prior knowledge of:

  • Maximum number of resources a process may need.

  • Number of available resources at any time.

⚖️ Safe vs Unsafe State

State Meaning
Safe State A sequence exists in which all processes can complete without deadlock
Unsafe State No such sequence is guaranteed ⇒ may lead to deadlock

✅ Avoidance ensures the system always stays in a safe state.

🔐 Banker's Algorithm – Most Common Deadlock Avoidance Technique

🧾 Assumptions:

  • System knows in advance:

  • Maximum demand of each process

  • Currently allocated resources
  • Available resources

🧮 Data Structures:

Let:

  • n = number of processes
  • m = number of resource types
Matrix/Vector Description
Available[m] Number of available instances of each resource
Max[n][m] Maximum demand of each process
Allocation[n][m] Currently allocated resources to each process
Need[n][m] Remaining need = Max – Allocation

✅ Banker’s Algorithm Steps

  1. Check if request ≤ need of that process

  2. Check if request ≤ available

  3. If not, process must wait

  4. Pretend to allocate resources:

  5. Update Available, Allocation, Need

  6. Check if system is in a safe state:

  7. Try to find a sequence where all processes can complete

✔️ If safe, grant the request ❌ If unsafe, deny request

🔁 Example

Let:

  • Available = [3, 3, 2]
  • Max Matrix:
   A B C  
P0 7 5 3  
P1 3 2 2  
P2 9 0 2  
P3 2 2 2  
P4 4 3 3
  • Allocation Matrix:
   A B C  
P0 0 1 0  
P1 2 0 0  
P2 3 0 2  
P3 2 1 1  
P4 0 0 2

💡 Use Need = Max – Allocation Run Banker's Algorithm to find if the system is in a safe state.

⚠️ Limitations of Deadlock Avoidance

Drawback Description
Advance Knowledge Needed OS must know the maximum resource needs
Complexity Frequent safety checks can be slow
Low Resource Utilization May deny requests that wouldn’t cause deadlock
Not Scalable Not suitable for systems with many processes

✅ Summary

  • Deadlock avoidance works by checking the system state before allocating resources.
  • Uses Banker’s Algorithm to ensure system stays in a safe state.
  • Safer than prevention, but needs advance information and more computation.

🧩 Topic: Deadlock Detection

🧠 What is Deadlock Detection?

  • Deadlock Detection is the technique used when the system does not prevent or avoid deadlocks, but instead checks periodically whether a deadlock has occurred.
  • If detected, some recovery mechanism is used to break the deadlock.

📌 When is Deadlock Detection Used?

  • In systems where:

  • Resources are requested dynamically

  • Performance is more important than prevention
  • Deadlocks are rare and temporary

🧩 Conditions for Detection

Deadlock can occur if all 4 Coffman Conditions are allowed:

  1. Mutual Exclusion
  2. Hold and Wait
  3. No Preemption
  4. Circular Wait

So, deadlock detection algorithms assume all conditions may hold and check the current state for circular wait.

📊 Detection Algorithm (Single Instance per Resource Type)

  • Uses a Resource Allocation Graph (RAG).
  • If there is a cycle in the graph, deadlock exists.

🟢 Works well when only one instance of each resource exists.

🔁 Detection Algorithm (Multiple Instances per Resource Type)

Similar to Banker’s Algorithm, but instead of checking for a safe state before allocation, it checks if current state is already deadlocked.

🧮 Data Structures Used

Name Meaning
Available[m] Available instances of each resource type
Allocation[n][m] Allocated resources for each process
Request[n][m] Currently requested resources
Finish[n] Boolean array to track process completion

✅ Detection Algorithm Steps

  1. Initialize:

  2. Finish[i] = false for all i where Allocation[i] ≠ 0

  3. Work = Available

  4. Find a process i such that:

  5. Finish[i] == false

  6. Request[i] ≤ Work

  7. If found:

  8. Work = Work + Allocation[i]

  9. Finish[i] = true

  10. Repeat Step 2

  11. If no such process is found:

  12. All processes where Finish[i] == false are deadlocked

💡 Example

Let:

  • Available = [3, 3, 2]
  • Allocation, Request matrices given for 5 processes.

Apply the steps above to determine which processes are deadlocked.

⚠️ Complexity

  • Time complexity: O(n² × m) (n = number of processes, m = resource types)

🧯 What to Do After Detection? (Recovery Options)

  1. Abort one or more processes

  2. Simple but may cause loss of work

  3. Resource Preemption

  4. Take resources away from some processes and restart them

  5. Risk of starvation

📌 Comparison: Prevention vs Avoidance vs Detection

Strategy Deadlock Happens? Advance Knowledge Suitable For
Prevention ❌ No ❌ Not needed Critical systems
Avoidance ❌ No ✅ Yes Predictable systems
Detection ✅ Yes ❌ No Flexible, but needs recovery

✅ Summary

  • Deadlock Detection checks for cycles or blocked processes in the system.
  • Uses Resource Allocation Graph (RAG) or Banker-like detection algorithm.
  • Detection must be followed by recovery (abort or preempt).
  • Best for systems where deadlocks are rare but possible.