OPERATING SYSTEM deadlock prevention techniques

Operating System Deadlock Prevention: A Comprehensive Guide
Introduction
Operating systems (OS) are complex software systems responsible for managing hardware resources and providing an environment for application execution. One of the fundamental challenges in operating systems is ensuring efficient and safe resource management, especially in multitasking and multi-user environments. Among the issues that arise, deadlock is one of the most critical problems. A deadlock is a situation where a set of processes are blocked because each process is holding a resource and waiting for another resource held by another process.

Deadlocks are particularly problematic in systems that require high availability and consistency. Their prevention is therefore an essential part of OS design and process management. In this document, we explore deadlock prevention in detail — including definitions, conditions, methods, algorithms, and real-world applications.

Understanding Deadlocks
What is a Deadlock?
A deadlock is a condition that occurs when four necessary conditions (known as Coffman conditions) are met simultaneously:

Mutual Exclusion – At least one resource must be held in a non-shareable mode.

Hold and Wait – A process is holding at least one resource and is waiting to acquire additional resources held by other processes.

No Preemption – Resources cannot be forcibly removed from processes holding them.

Circular Wait – A closed chain of processes exists such that each process holds at least one resource needed by the next process in the chain.

When all these conditions are true simultaneously, a deadlock occurs.

Implications of Deadlock
Deadlocks lead to significant problems:

System throughput decreases.

CPU cycles are wasted.

Users experience freezing or crashing applications.

Critical processes may halt permanently, leading to system instability.

Deadlock Handling Strategies
There are three primary strategies for handling deadlocks in operating systems:

Deadlock Prevention – Proactively prevent one or more of the Coffman conditions.

Deadlock Avoidance – Dynamically examine resource allocation to avoid unsafe states.

Deadlock Detection and Recovery – Allow deadlocks to occur and then detect and recover.

This guide focuses entirely on Deadlock Prevention.

Deadlock Prevention
Deadlock prevention involves designing the system in such a way that at least one of the necessary conditions for deadlock cannot hold. If we break any of the Coffman conditions, we prevent the occurrence of deadlock.

Let’s examine how each condition can be violated to prevent deadlock.

1. Preventing Mutual Exclusion
Mutual exclusion implies that resources cannot be shared. For some resources like printers or tape drives, mutual exclusion is necessary. However, for others like read-only files, mutual exclusion can be avoided.

Approach:
Design the system to make as many resources as possible sharable.

Avoid assigning resources that do not need mutual exclusion.

1. DEADLOCK
PREVENTION
OPERATING
SYSTEM
53-Akshay Vennikkal
54-Harsh Vishwakarma
55-Yash Vishwakarma
56-Anusha Yadav
#-Gracy Verma

2. 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.
Consider an example when two trains are coming
toward each other on the same track and there is only
one track, none of the trains can move once they are in
front of each other. A similar situation occurs in
operating systems when there are two or more
processes that hold some resources and wait for
resources held by other(s). For example, in the below
diagram, Process 1 is holding Resource 1 and waiting
for resource 2 which is acquired by process 2, and
process 2 is waiting for resource 1.
WHAT IS DEADLOCK?

3. HOLD AND
WAIT
MUTUAL
EXCLUSION
CIRCULAR
WAIT
NO
PREEMPTION
A process is holding at least
one resource and waiting for
resources.
Two or more resources are non-
shareable (Only one process
can use at a time)
A set of processes are waiting
for each other in circular form.
A resource cannot be taken
from a process unless the
process releases the resource.
DIFFERENT
CONDITIONS
WHEN
DEADLOCK
OCCUR

4. MUTUAL EXCLUSION
Mutual exclusion is a property of process
synchronization which states that “no
two processes can exist in the critical
section at any given point of time”. The
term was first coined by Dijkstra. Any
process synchronization technique being
used must satisfy the property of mutual
exclusion, without which it would not be
possible to get rid of a race condition.

5. If boy enters the room
then it will show occupied
and the girl won't be able
to enter that room.
After the boy is done he
will come out of that
room and the room will
again indicate vacant and
then the girl could use
the room.

6. To prevent this condition processes must be prevented from holding one or more resources while
simultaneously waiting for one or more others. There are several possibilities for this:
Require that all processes request all resources at one time. This can be wasteful of system resources
if a process needs one resource early in its execution and doesn't need some other resource until
much later.
Require that processes holding resources must release them before requesting new resources, and
then re-acquire the released resources along with the new ones in a single new request. This can be
a problem if a process has partially completed an operation using a resource and then fails to get it
re-allocated after releasing it.
Either of the methods described above can lead to starvation if a process requires one or more
popular resources.
HOLD AND WAIT

7. No Preemption means that a resource can only be free when the process holding it finishes
execution. If a process requests a resource that is already allocated to another process, the OS
frees all resources.
The preempted resources need the list of waiting resources for a process and the process
restarts only when it regains the old resource or the one that it is requesting. If the requested
resource is available, then it is immediately allocated to the process. If not available then the OS
releases the requesting resource from its current process and gives it to the requesting
process.
NO PREEMPTION

8. CIRCULAR WAIT
When a process waits for a resource held by
another process, which is also waiting for a
resource held by a third process, and so on, a
circular chain is created. This ordeal is known
as circular wait. It forms a circular loop where
it is necessary that every process requests
resources in increasing order of enumeration.
For example, Process A has Resource B but it
needs Resource A and requests it. Similarly,
another process, Process B has Resource A
but it is requesting Resource B. This situation
creates a circular wait loop.

9. METHODS OF HANDLING DEADLOCK
Deadlock prevention or
avoidance
Deadlock detection and
recovery
Ignore the problem
altogether
The idea is to not let the system
into a deadlock state.
One can zoom into each
category individually, Prevention
is done by negating one of
above mentioned necessary
conditions for deadlock
Let deadlock occur,
then do preemption
to handle it once
occurred.
If deadlock is very rare,
then let it happen and
reboot the system. This is
the approach that both
Windows and UNIX take.

10. The kernel does not avoid deadlocks of user-space locks (because often it
doesn't even know about them).
Deadlocks of kernel locks are avoided by writing code that is correct. This is
greatly helped by lockdep, which can prove the correctness of locking
operations.
(The lockdep code has been ported to user space, but it helps only for programs
that bother to use it.)
When the UI thread of an Android app is blocked for too long, an "Application
Not Responding" (ANR) error is triggered. If the app is in the foreground, the
system displays a dialog to the user, as shown in figure 1. The ANR dialog gives
the user the opportunity to force quit the app
ANR:
How does the linux kernel avoids deadlocks in user processes?

11. Advantageous to the processes that
perform a single burst of activity.
No preemption is required.
Convenient to apply to resources that
can save and restore their states
easily.
Compile-time checks help apply it
feasibly
The system design solves problems so
no run-time computation is required.
Advantages of Deadlock Disadvantages of Deadlock
Delay in process initiation.
Knowledge of future resources is
necessary.
Frequent preemptions.
Doesn’t allow incremental
resource requests.
There are inherent preemption
losses.