Understanding Deadlock in

Operating Systems
Welcome to our project-based learning module on understanding
deadlock in operating systems. Deadlock is a critical concept where
two or more processes become blocked indefinitely, each waiting for a
resource held by another. This presentation will explore the conditions
that lead to deadlock, common real-world examples, and various
strategies for prevention and avoidance.

By the end of this module, you will have a comprehensive

understanding of deadlock and be equipped with ideas for hands-on
projects to deepen your learning.

AC
by Ajay Chauhan
What is Deadlock?
Blocked Processes
A set of processes is unable to proceed, as each is waiting for a resource held by another process in the same set.

System Standstill
The system reaches a state of deadlock, meaning no process can execute or release resources, leading to a complete halt.

Traffic Analogy
Imagine two cars stuck in an intersection, each blocking the other's path. Neither car can move forward, creating a deadlock.

Deadlock in operating systems is a situation where processes become perpetually stuck. This often occurs in multi-tasking environments where multiple processes compete
for a finite number of resources. The analogy of cars in an intersection clearly illustrates this resource contention and the resulting inability to progress.
Necessary Conditions for Deadlock (Coffman
Conditions)
1 Mutual Exclusion 2 Hold and Wait
Only one process can use a resource at any given A process holds at least one resource while waiting
time. This condition is inherent to non-shareable to acquire additional resources held by other
resources, like a printer or a specific memory block. processes.

3 No Preemption 4 Circular Wait

Resources cannot be forcibly taken from a process A circular chain of processes exists, where each
once they have been allocated. A process must process in the chain is waiting for a resource held by
voluntarily release its resources. the next process in the chain.

For a deadlock to occur, all four of these conditions, known as the Coffman Conditions, must be present simultaneously.
Understanding these conditions is crucial for designing systems that can prevent or handle deadlocks effectively.
Real-World Example: Traffic Deadlock
The Scenario

Consider a typical urban intersection. Car A and Car B approach the

intersection at the same time. Car A intends to go straight, while Car B
intends to turn left across Car A's path.

The Deadlock

Both cars enter the intersection, assuming the other will yield. However,
their paths cross, and each car blocks the other. Neither can move forward
without the other moving first, leading to an indefinite standstill.

OS Analogy

This scenario directly parallels resource allocation in operating systems.

Cars represent processes, and the intersection lanes represent shared
resources. Just as the cars are stuck, processes can become blocked if
they simultaneously request and hold resources that others need.

This traffic deadlock vividly illustrates how the Coffman conditions manifest in a real-world setting, providing an accessible analogy for understanding
complex OS concepts.
Resource Allocation Graph
The Resource Allocation Graph is a powerful visual tool used to detect deadlocks in an operating system. By representing processes and
resources as nodes, and resource requests and assignments as directed edges, cycles in the graph directly indicate a deadlock.

Nodes
Processes are depicted as circles, and resources as rectangles. Each resource rectangle may have multiple instances
represented by dots inside.

Edges
Request edges (process to resource) show a process waiting for a resource instance. Assignment edges (resource
instance to process) show a resource instance allocated to a process.

Cycle Detection
If the graph contains a cycle, and each resource involved in the cycle only has one instance, then a deadlock exists. If
there are multiple instances, a cycle indicates a potential deadlock.
Deadlock Prevention Strategies

Break Mutual Exclusion Eliminate Hold and Wait

Attempt to make resources shareable. For example, spooling Require processes to request all necessary resources at the
allows multiple processes to "share" a printer by queuing print beginning of their execution. If all resources are not available, the
jobs. However, this is not always possible for all resource types. process waits without holding any. Alternatively, a process
releases all its current resources before requesting new ones.

Allow Preemption Break Circular Wait

If a process requests a resource that is currently held by another Impose a total ordering of all resource types. Processes must
process that is waiting, the operating system can preempt the request resources in increasing order of enumeration. This
resource. The preempted resources are then added to the list of ensures that a circular wait condition cannot be formed.
resources for which the waiting process is contending.

Each prevention strategy aims to negate one of the Coffman conditions, thereby ensuring that deadlock cannot occur. While effective, these
strategies can sometimes lead to reduced resource utilisation or process starvation.
Deadlock Avoidance: Banker's Algorithm
Deadlock avoidance is a less restrictive approach than prevention, allowing the system to dynamically decide if a resource request can be granted without
leading to an unsafe state. The Banker's Algorithm is a prominent example of this strategy.

Safe State
Safety Check
A state is considered safe if there exists a
When a process requests resources, the
sequence of processes that can all complete
algorithm simulates the allocation to see if the
their execution, even if their maximum
system would remain in a safe state.
resource needs are eventually met.

Dynamic Allocation Resource Max Needs

If granting the request leads to an unsafe The Banker's Algorithm requires prior
state, the request is denied, and the process knowledge of the maximum number of
waits. Otherwise, the resources are allocated. resources each process might need during its
execution.

While effective, the Banker's Algorithm demands that the system knows the maximum resource needs of all processes in advance, which is often difficult to
achieve in real-world scenarios. It is more suitable for systems with a fixed number of processes and resources.
Project Ideas: Exploring Deadlock
For your project-based learning, here are some stimulating ideas to delve deeper into the concept of deadlock and its management in operating systems:

Implement Detection & Recovery

Simulate Deadlock Scenarios
Extend your simulation to include a deadlock detection algorithm (e.g.,
Develop a simple program in a language like Python or Java that using a resource allocation graph) and a recovery mechanism (e.g.,
simulates multiple processes requesting and releasing resources, process termination or resource preemption).
demonstrating how a deadlock can occur under specific conditions.

Performance Analysis of Avoidance

Compare Prevention Techniques
Investigate the Banker's Algorithm. Implement it in your simulation and
Implement different deadlock prevention strategies within your evaluate its overhead in terms of computation and its efficiency in
simulation and analyse their effectiveness in preventing deadlocks and managing resource allocation.
their impact on resource utilisation.

These projects will provide hands-on experience and a practical understanding of how deadlocks are identified, prevented, and resolved in real-world
operating systems. Choose a project that aligns with your interests and available tools.