Deadlock detection and recovery in Operating Systems - Step-by-Step Execution

Concept Flow - Deadlock detection and recovery

System runs processes

↓

Resources requested

↓

Check for deadlock?

No→Continue normal execution

Yes↓

Detect deadlock using algorithm

↓

Deadlock found?

No→Continue normal execution

Yes↓

Recover from deadlock

↓

Release resources or terminate process

↓

System resumes normal operation

The system runs processes that request resources. It checks if a deadlock exists using detection algorithms. If found, it recovers by releasing resources or terminating processes, then resumes normal operation.

Execution Sample

Operating Systems

1. Processes request resources
2. System checks resource allocation graph
3. Detect cycles indicating deadlock
4. Select process to terminate or resources to preempt
5. Release resources and continue

This sequence shows how the system detects deadlock by finding cycles and recovers by freeing resources.

Analysis Table

Step	Action	Resource Allocation Graph State	Deadlock Detected?	Recovery Action
1	Processes request resources	Graph updated with new edges	No	None
2	Check for cycles in graph	Graph with edges: P1->R1, P2->R2, R1->P2, R2->P1	Yes	Deadlock detected between P1 and P2
3	Select process to terminate	Same graph	Yes	Choose P2 to terminate
4	Terminate P2 and release resources	Edges related to P2 removed	No	Resources freed
5	Resume normal execution	Graph updated, no cycles	No	Continue running processes

💡 Deadlock resolved after terminating P2 and releasing its resources

State Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
Resource Allocation Graph	Empty	Edges added for requests	Cycle detected	No change	Edges for P2 removed	No cycles
Deadlock Detected	False	False	True	True	False	False
Processes	P1, P2	P1, P2	P1, P2	P1, P2	P1	P1

Key Insights - 3 Insights

Why does the system check for cycles in the resource allocation graph?

Because a cycle in the graph means processes are waiting on each other in a loop, which is the definition of deadlock (see execution_table step 2).

Why terminate a process to recover from deadlock?

Terminating a process frees its resources, breaking the cycle and allowing other processes to continue (see execution_table step 4).

Can deadlock detection happen without recovery?

Yes, detection only finds deadlocks; recovery is a separate step to fix the problem (see execution_table steps 2 and 3).

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what indicates a deadlock?

A A cycle in the resource allocation graph

B No edges in the graph

C All processes are running freely

D Resources are all free

💡 Hint

Refer to the 'Resource Allocation Graph State' and 'Deadlock Detected?' columns at step 2

At which step does the system stop detecting deadlock?

A Step 1

B Step 3

C Step 4

D Step 5

💡 Hint

Check the 'Deadlock Detected?' column to see when it changes to false after recovery

If the system chose to terminate P1 instead of P2, how would the 'Processes' variable change after step 4?

A Processes would remain P1 and P2

B Processes would be P2 only

C Processes would be P1 only

D Processes would be empty

💡 Hint

Look at the 'Processes' row in variable_tracker after step 4

Concept Snapshot

Deadlock detection finds cycles in resource allocation graphs.
If a cycle exists, deadlock is present.
Recovery involves terminating processes or preempting resources.
After recovery, system resumes normal operation.
Detection and recovery are separate but linked steps.

Full Transcript

Deadlock detection and recovery involve the system monitoring resource requests by processes. When processes request resources, the system updates a resource allocation graph. It then checks this graph for cycles, which indicate deadlock. If a deadlock is detected, the system selects a process to terminate or resources to preempt to break the cycle. After releasing resources, the system resumes normal operation. This process ensures that the system does not get stuck waiting forever for resources.

Practice

1. What is the main purpose of deadlock detection in operating systems?

easy

A. To find when programs are stuck waiting forever

B. To speed up program execution

C. To allocate more memory to programs

D. To prevent viruses from entering the system

Solution

1. Step 1: Understand deadlock concept

   Deadlock happens when programs wait forever for resources held by each other.

2. Step 2: Identify deadlock detection role

   Deadlock detection finds these stuck programs so the system can fix the problem.

3. Final Answer:

   To find when programs are stuck waiting forever -> Option A

4. Quick Check:

   Deadlock detection = find stuck programs [OK]

Hint: Deadlock detection means finding stuck programs [OK]

Common Mistakes:

• Confusing detection with prevention
• Thinking it speeds up programs
• Mixing with security tasks

2. Which of the following is a correct method used in deadlock recovery?

easy

A. Terminating one or more processes

B. Encrypting data

C. Adding more RAM

D. Increasing CPU speed

Solution

1. Step 1: Review deadlock recovery methods

   Recovery fixes deadlocks by freeing resources or stopping processes causing the deadlock.

2. Step 2: Match options to recovery methods

   Terminating processes is a common way to break deadlocks by releasing resources.

3. Final Answer:

   Terminating one or more processes -> Option A

4. Quick Check:

   Recovery = stop processes to free resources [OK]

Hint: Recovery often stops processes to free resources [OK]

Common Mistakes:

• Thinking hardware upgrades fix deadlocks
• Confusing recovery with detection
• Believing encryption helps deadlocks

3. Consider a system with three processes P1, P2, P3 and resources R1, R2. If P1 holds R1 and waits for R2, P2 holds R2 and waits for R1, and P3 is idle, what does deadlock detection report?

medium

A. No deadlock detected

B. Deadlock involving P2 and P3

C. Deadlock involving P1 and P2

D. Deadlock involving all three processes

Solution

1. Step 1: Analyze resource holding and waiting

   P1 holds R1 and waits for R2; P2 holds R2 and waits for R1; P3 is idle (not waiting).

2. Step 2: Identify circular wait

   P1 and P2 are waiting on each other's resources, forming a cycle causing deadlock; P3 is not involved.

3. Final Answer:

   Deadlock involving P1 and P2 -> Option C

4. Quick Check:

   Circular wait between P1 and P2 = deadlock [OK]

Hint: Look for circular waiting processes [OK]

Common Mistakes:

• Including idle processes in deadlock
• Ignoring circular wait condition
• Assuming no deadlock if one process is idle

4. A system uses a deadlock detection algorithm but never recovers from deadlocks. What is the main problem with this approach?

medium

A. Deadlocks will be prevented automatically

B. Deadlocks will never be found

C. System will run faster

D. System will detect deadlocks but remain stuck

Solution

1. Step 1: Understand detection without recovery

   Detection finds deadlocks but does not fix them if recovery is missing.

2. Step 2: Identify system behavior

   The system will know deadlocks exist but processes remain stuck, causing hang or freeze.

3. Final Answer:

   System will detect deadlocks but remain stuck -> Option D

4. Quick Check:

   Detection alone = find deadlock, no fix [OK]

Hint: Detection finds; recovery fixes deadlocks [OK]

Common Mistakes:

• Thinking detection prevents deadlocks
• Assuming system runs faster without recovery
• Believing deadlocks won't be found

5. In a system with multiple processes and resources, which strategy best combines deadlock detection and recovery to maintain system fairness and efficiency?

hard

A. Prevent deadlocks by denying all resource requests

B. Detect deadlocks periodically and terminate the process holding the most resources

C. Ignore deadlocks and restart the system when it freezes

D. Allow deadlocks and manually fix them later

Solution

1. Step 1: Understand combined detection and recovery

   Detecting deadlocks periodically helps find problems early; recovering by terminating processes frees resources.

2. Step 2: Evaluate options for fairness and efficiency

   Terminating the process holding most resources frees maximum resources, improving system efficiency and fairness.

3. Final Answer:

   Detect deadlocks periodically and terminate the process holding the most resources -> Option B

4. Quick Check:

   Periodic detection + smart recovery = fairness and efficiency [OK]

Hint: Detect often; recover by freeing max resources [OK]

Common Mistakes:

• Preventing all requests reduces efficiency
• Ignoring deadlocks causes system freeze
• Manual fixes delay problem resolution