Lecture Notes: Deadlock in Operating

Systems
Introduction
Deadlock is a critical issue in operating systems where a set of processes or threads become
unable to proceed because each is waiting for a resource held by another, creating a standstill.
Deadlocks can severely impact system performance and reliability, particularly in concurrent
environments. This lecture note covers three key aspects of deadlock: Conditions for
Deadlock, Deadlock Detection and Recovery, and the Banker's Algorithm. These
concepts are essential for understanding, preventing, and resolving deadlocks in resource-
sharing systems.

1. Conditions for Deadlock

Deadlock occurs when a set of processes form a circular wait for resources, and specific
conditions hold simultaneously. These conditions, known as the Coffman conditions, are
necessary for a deadlock to arise.

1.1 The Four Conditions

1. Mutual Exclusion:
o At least one resource involved must be held in a non-shareable mode, meaning
only one process can use it at a time.
o Example: A printer can only be used by one process at a time.
2. Hold and Wait:
o A process holding at least one resource is waiting to acquire additional
resources that are currently held by other processes.
o Example: A process holding a file lock waits for a database lock held by
another process.
3. No Preemption:
o Resources cannot be forcibly taken from a process; the process must release
them voluntarily.
o Example: A process cannot be forced to release a locked file until it completes
its operation.
4. Circular Wait:
o A set of processes form a circular chain, where each process is waiting for a
resource held by the next process in the chain.
o Example: Process A waits for Resource X held by Process B, which waits for
Resource Y held by Process A.

1.2 Implications
  All four conditions must be present for a deadlock to occur. Breaking any one
condition prevents deadlock.
 Deadlocks are common in systems with limited resources (e.g., memory, I/O devices,
locks) and concurrent processes.

1.3 Use Cases

 Database systems where transactions lock tables and wait for others to release locks.
 Operating systems managing shared resources like semaphores or file handles.
 Multithreaded applications where threads compete for mutexes.

2. Deadlock Detection and Recovery

When deadlocks cannot be prevented or avoided, the operating system can detect their
occurrence and take corrective actions to recover the system.

2.1 Deadlock Detection

Deadlock detection involves analyzing the system’s resource allocation state to identify
whether a deadlock exists.

 Resource Allocation Graph:

o A directed graph where:
 Nodes represent processes and resources.
 Edges indicate resource allocation (resource to process) and requests
(process to resource).
o A cycle in the graph indicates a potential deadlock (in systems with single-
instance resources).
o For multiple-instance resources, additional checks are needed.
 Wait-For Graph:
o A simplified graph showing only processes and their resource dependencies.
o A cycle in the wait-for graph confirms a deadlock.
 Algorithm:
o Periodically check the resource allocation state for cycles.
o For multiple-instance resources, use a matrix-based approach (e.g., tracking
allocated and requested resources).
 Challenges:
o Frequent checks can introduce significant overhead.
o False positives may occur in complex systems with transient cycles.

2.2 Deadlock Recovery

Once a deadlock is detected, the system must resolve it to restore normal operation. Common
recovery strategies include:

 Process Termination:
 o Abort All Deadlocked Processes: Terminate all processes involved in the
deadlock.
 Advantages: Simple and guarantees deadlock resolution.
 Disadvantages: Loss of all process progress, potentially costly.
o Abort One Process at a Time: Terminate processes incrementally until the
deadlock is broken.
 Advantages: Minimizes disruption.
 Disadvantages: Requires repeated detection and may be slow.
o Selection Criteria: Choose processes based on priority, resource usage, or
completion time to minimize impact.
 Resource Preemption:
o Forcibly take resources from one or more processes and allocate them to
others to break the deadlock.
o Steps:

Select a victim process to release its resources.

1.
Roll back the victim to a safe state (e.g., restart or undo operations).
2.
Allocate the released resources to waiting processes.
3.
o Advantages: Preserves more process progress than termination.
o Disadvantages: Complex to implement, especially for non-reversible
resources (e.g., printed output).
 Challenges:
o Recovery may cause data loss or require expensive rollback mechanisms.
o Choosing the optimal recovery strategy depends on system constraints and
application requirements.

2.3 Use Cases

 Operating systems detecting deadlocks in process resource allocation (e.g., Linux

kernel with lockdep).
 Database management systems resolving transaction deadlocks by aborting one
transaction.
 Real-time systems preempting resources to ensure timely task completion.

3. Banker's Algorithm
The Banker’s Algorithm is a deadlock avoidance strategy that ensures the system remains in
a safe state by carefully allocating resources. It is used in systems where resource needs are
known in advance.

3.1 Concept

 The algorithm simulates resource allocation to ensure that granting a request does not
lead to a deadlock. It mimics a banker who cautiously lends money to clients,
ensuring they can always repay.
 Safe State: A state where there exists at least one sequence of process executions that
allows all processes to complete without deadlocking.
  Unsafe State: A state where no such sequence exists, potentially leading to deadlock.

3.2 Data Structures

For a system with n processes and m resource types:

 Available: A vector of length m indicating the number of available instances of each

resource.
 Max: An n x m matrix where Max[i,j] is the maximum number of resource j that
process i will need.
 Allocation: An n x m matrix where Allocation[i,j] is the number of resource j
currently allocated to process i.
 Need: An n x m matrix where Need[i,j] = Max[i,j] - Allocation[i,j],
representing the additional resources process i needs.

3.3 Algorithm Steps

1. Initialization:
o Compute the Need matrix based on Max and Allocation.
o Track available resources in the Available vector.
2. Request Handling:
o When process Pi requests resources (e.g., a vector Request), check:
 If Request <= Need[i], proceed; otherwise, reject (invalid request).
 If Request <= Available, proceed; otherwise, wait (insufficient
resources).
o Simulate allocation:
 Subtract Request from Available.
 Add Request to Allocation[i].
 Subtract Request from Need[i].
3. Safety Check:
o Initialize a Work vector (copy of Available) and a Finish array (all false
for n processes).
o Find a process Pi where Finish[i] = false and Need[i] <= Work.
o If found:
 Add Allocation[i] to Work (simulating resource release after
completion).
 Set Finish[i] = true.
 Repeat until all processes are marked Finish = true (safe state) or no
such process exists (unsafe state).
o If the state is safe, grant the request; otherwise, deny and revert the simulated
allocation.

3.4 Advantages

 Prevents deadlocks by ensuring only safe resource allocations.

 Suitable for systems with predictable resource demands (e.g., batch processing).

3.5 Disadvantages
  Requires prior knowledge of maximum resource needs, which may not be feasible in
dynamic systems.
 Computationally expensive for large numbers of processes and resources.
 May lead to resource underutilization, as it conservatively denies requests.

3.6 Use Cases

 Resource management in operating systems with fixed resource pools (e.g., memory
or I/O devices).
 Real-time systems where predictable behavior is critical.
 Simulation environments testing resource allocation strategies.

Conclusion
Deadlock is a significant challenge in operating systems, arising when the four conditions of
mutual exclusion, hold and wait, no preemption, and circular wait are met. Deadlock
Detection and Recovery strategies, such as resource allocation graphs and process
termination, allow systems to identify and resolve deadlocks after they occur. The Banker’s
Algorithm provides a proactive approach to deadlock avoidance by ensuring safe resource
allocation. Understanding these concepts is crucial for designing robust, efficient, and
deadlock-free systems, particularly in concurrent and resource-constrained environments.
Future topics may include advanced deadlock prevention techniques, livelock resolution, and
concurrency optimization.