Deadlock
A deadlock is a state in a
computer system where a set of processes is unable to proceed because each is
waiting for a resource that is held by another process in the set. Deadlock is
a situation of interprocess communication where progress is impossible.
Here's a common example: Consider
two processes, A and B, and two resources, 1 and 2. Process A has resource 1
and needs resource 2. At the same time, process B has resource 2 and needs
resource 1. Neither process can continue until the other process releases a
resource. They are in a deadlock.
There are four necessary conditions for a deadlock to occur, known as Coffman conditions:
- Mutual Exclusion: At least one resource must
be held in a non-sharable mode, meaning only one process can use the
resource at any given time.
- Hold and Wait: A process holding at least
one resource and waiting to acquire additional resources that are currently
held by other processes.
- No Preemption: Resources cannot be forcibly
taken from a process holding them; resources must be explicitly released
by the process holding them.
- Circular Wait: There exists a set of waiting
processes such that P1 is waiting for a resource held by P2, P2 is waiting
for a resource held by P3, and so on until Pn is waiting for a resource
held by P1. This forms a circular chain.
Deadlocks are a problem because
they halt the execution of processes, and resolving a deadlock often requires
intervention, which can be costly in terms of system performance or even lead
to system failure. Operating systems use various techniques to prevent, detect
and recover from deadlocks.
Deadlock System Models
A system model is necessary to
characterize and analyze deadlocks. Typically, a system is modeled in terms of
resources and processes.
Here's a simple model:
Resources: These are the
things that the processes in our system will be using and competing for.
Examples include printers, memory, CPU cycles, disk drives, databases, and so
on.
In the system model, resources are
characterized by two properties:
- Each resource type Rj has Nj instances. Each
instance is identical in terms of its functionality.
- Each resource instance can be either in the
available state or allocated to exactly one process.
Processes: These are the
activities in our system that use resources and compete with other processes
for resources.
In the system model, processes
follow this general sequence:
- Request: The process requests the resources it
needs. If the resources are not available at that time, the process must
wait until they are.
- Use: Once the process has all its resources, it can
perform its function.
- Release: When the process is finished with the
resources, it releases them.
It's important to note that not
all resources are immediately reusable; for instance, a printer cannot be
reallocated to another process until the current print job is finished.
This system model can help to
understand how resources are requested, used, and released, and it forms the
basis for the characterization and analysis of deadlock scenarios.
Necessary Conditions leading to
Deadlocks
For a deadlock to occur, four
necessary conditions must hold simultaneously in a system. These are known as
Coffman conditions after their authors, E. G. Coffman, Jr., M. J. Elphick, and
A. K. Shoshani:
- Mutual Exclusion: At least one resource must
be in a non-sharable mode, that is, only one process at a time can use the
resource. If another process requests that resource, the requesting
process must be delayed until the resource has been released.
- Hold and Wait (or Resource Holding): A
process is currently holding at least one resource and requesting
additional resources which are being held by other processes.
- No Preemption: Resources cannot be forcibly
removed from the processes holding them until the resources are used to
completion. In other words, a resource can only be released by the process
that is currently holding it.
- Circular Wait: There exists a set {P0, P1,
…, Pn} of waiting processes such that P0 is waiting for a resource held by
P1, P1 is waiting for a resource held by P2, and so on, Pn is waiting for
a resource held by P0.
All these four conditions must
hold for a deadlock to occur. If we can prevent at least one of the conditions
from holding, we can prevent deadlocks. The system can adopt a specific
strategy for ensuring that at least one of these conditions does not hold, thus
making deadlocks impossible.
Deadlock Handling - Preventions
and avoidance.
Handling deadlocks involves
employing a strategy that ensures at least one of the four necessary conditions
for deadlocks cannot occur. This can be done through three approaches: deadlock
prevention, deadlock avoidance, and deadlock detection.
- Deadlock Prevention: In this approach, the
system actively prevents the occurrence of one or more of the four
necessary conditions. This can be done in one of two ways:
- Negate Mutual Exclusion: Make resources
sharable where possible. For some resources, such as a printer or a CD
drive, this is not possible as they are intrinsically non-sharable.
- Negate Hold and Wait: Require processes to
request all the resources they will need upfront before execution begins.
This can be inefficient as a resource may be held idle for a long time.
Alternatively, allow a process to request resources only when it has
none; thus, it must release all its held resources before requesting
more.
- Negate No Preemption: If a process that is
holding some resources requests another resource that cannot be
immediately allocated, then all resources currently being held are
released. Preempted resources are added to the list of resources for
which the process is waiting. The process will be restarted only when it
can regain its old resources and obtain the new ones it is requesting.
- Negate Circular Wait: Impose a total
ordering of all resource types and require that each process requests
resources in an increasing order of enumeration.
- Deadlock Avoidance: The system requires
additional information in advance about which resources a process will
need during its lifetime. With this information, the system can decide for
each resource request whether the process should wait or can safely be
allocated the resource. The system can then make a safe decision that avoids
entering an unsafe (potentially deadlocked) state.
- The most famous deadlock avoidance algorithm is
the Banker's Algorithm, which is used when a process requests resources.
The algorithm checks if granting the request will mean that the system
remains in a safe state, then the request is granted, else the process
must wait.
- Deadlock Detection and Recovery: If
deadlocks cannot be prevented or avoided, they can be allowed to occur,
detected, and then recovered. A detection algorithm is used to determine
whether a deadlock has occurred. If a deadlock is detected, the system
must recover from the deadlock, typically by terminating some or all of
the processes in the deadlock or by preempting resources from some
processes.
Each of these strategies has its
own trade-offs in terms of resource utilization and system throughput. The
appropriate strategy will depend on the specific details of the system and its
workload.