Introduction to Deadlock
A deadlock is a situation in an
operating system where a set of processes
are permanently blocked because:
·
Each process is holding at least one resource
·
Each process is waiting for another resource held by some other process
As a result, none of the processes can continue execution, and the system becomes stuck.
Real-Life Example: Two Cars on a Narrow Road
Imagine two
cars coming from opposite directions on a narrow one-lane road where only one car can pass at a
time. They meet in the middle.
Now:
·
Car A cannot move forward unless Car B moves
back.
·
Car B cannot move forward unless Car A moves
back.
·
Neither car is willing or able to move backward.
So:
·
Both cars hold their current position.
·
Both are waiting for the other to move.
·
No progress is possible.
This situation is called deadlock.
Relation to Operating System
In an operating system:
·
Cars → Processes
·
Road → Resources
·
Cars holding road → Processes holding resources
Just like the cars, processes wait forever, and the system gets stuck (रोकिन्छ).
Necessary Conditions for Deadlock
A deadlock can occur only if all the following four conditions hold simultaneously.
1. Mutual Exclusion
Some resources cannot be shared.
Only one process can use a
resource at a time.
Example:
·
Process P1 is using a printer
·
Process P2 is using a scanner
·
Printer and scanner are non-shareable
·
No other process can use these resources until
they are released
Because the resource is exclusive, other processes must wait.
2. No Preemption
Once a resource is allocated to a process, it cannot be taken away forcibly.
The process must release the resource voluntarily after finishing its
task.
Example:
·
Process A is using a file
·
Process B also needs the same file
·
OS cannot
take the file from Process A
· Process B must wait until Process A releases it
3. Hold and Wait
A process holds one or more resources
and at the same time waits for additional
resources held by other processes.
Example:
·
Process P1 holds Resource R1 and requests
Resource R2
·
Process P2 holds Resource R2 and requests
Resource R1
Both processes are holding and waiting.
4. Circular Wait
A set of processes are waiting for each other in a circular chain.
Example:
·
P1 waits for P2
·
P2 waits for P3
·
P3 waits for P1
This creates a cycle, and none can proceed.
Important Note:
Deadlock occurs only if all four
conditions occur together.
If any one condition is broken,
deadlock can be prevented.
Methods of Deadlock Handling
There are four main ways to handle deadlock in an operating system:
1. Deadlock Prevention
2. Deadlock Avoidance
3. Deadlock Detection and Recovery
4. Deadlock Ignorance (Ostrich Method)
1. Deadlock Prevention
Deadlock prevention aims to stop deadlock before it happens.
The system checks every resource request and does not allow execution if there is even a small possibility of deadlock.
Basic Idea:
Since deadlock occurs only when all four conditions hold, prevention works by violating at least one condition.
Timestamp-Based Prevention Schemes
These schemes use timestamps (time of process creation) to decide:
· Which process should wait
· Which process should be terminated
Older process → smaller timestamp
Younger process → larger timestamp
a) Wait–Die Scheme
·
If an older process requests a
resource held by a younger process →
Older process waits
·
If a younger process requests a
resource held by an older process →
Younger process dies (terminated) and restarts later
Prevents circular wait.
b) Wound–Wait Scheme
·
If an older process requests a
resource held by a younger process →
Younger process is killed
(wounded) and restarted later
·
If a younger process requests a
resource held by an older process →
Younger process waits
Older processes get priority.
2. Deadlock Avoidance
Deadlock avoidance ensures that the system never enters an unsafe state.
Before granting a resource request, the system checks:
“Will this allocation keep the system in a safe state?”
Banker’s Algorithm
· Most popular deadlock avoidance algorithm
· Used when resource information is known in advance
· Works like a bank giving loans only if it can satisfy all customers safely
Features:
· Checks system safety before allocating resources
· Ensures that all processes can complete execution
· Avoids deadlock completely
Disadvantages:
· Complex to implement
· High overhead due to frequent safety checks
· Not suitable for large or dynamic systems
3. Deadlock Detection and Recovery
Deadlock Detection:
The OS periodically checks whether deadlock has occurred by:
· Tracking allocated resources
· Tracking resource requests
Recovery Methods:
a) Terminate Processes
· Kill all deadlocked processes
· Simple but wastes all progress
b) Resource Preemption
· Take resources from some processes
· Give them to others until deadlock is resolved
4. Deadlock Ignorance (Ostrich
Method)
The system ignores the possibility of deadlock completely.
Why?
· Deadlock occurs rarely
· Detection and prevention are costly
If deadlock occurs:
· System may freeze
· Processes may be restarted manually or automatically
Used in systems like UNIX and Windows.
Recovery from Deadlock
Deadlock recovery is performed after deadlock is detected.
When deadlock occurs:
· System stops normal execution
· Recovery methods are applied
· System resumes operation after recovery
Techniques of Deadlock Recovery
1. Recovery Through Preemption
· OS forcibly takes resources from one or more processes
· Resources are reassigned to other processes
· Care must be taken to avoid starvation
2. Recovery Through Rollback
· Process is rolled back to a previous safe state (checkpoint)
· Resources are released
· Process is restarted later
3. Recovery Through Killing Processes
· OS terminates one or more deadlocked processes
· Deadlock cycle is broken
· Remaining processes continue execution
Comments
Post a Comment