Operating Systems: Concurrency and

Deadlock Management
PART I: CONCURRENCY AND SYNCHRONIZATION
Chapter 1: Principles of Concurrency
Definition and Importance

Concurrency refers to the ability of multiple processes or threads to execute simultaneously

on a system. In modern multi-core processors and multi-threaded applications,
concurrency is fundamental to system performance and responsiveness. Multiple
processes compete for limited system resources, including CPU time, memory, I/O devices,
and data.
Key Concepts
Interleaving: On a single-core processor, the operating system rapidly switches between
processes, creating the illusion of simultaneous execution. Each process gets a time slice
(quantum) to execute.

Parallelism: On multi-core systems, multiple processes execute truly simultaneously on

different processors, enabling genuine parallel processing.
Concurrency Issues: When multiple processes access shared resources, race conditions can
occur. A race condition happens when the outcome of the program depends on the timing
of events. For example, if Process A and Process B both read and modify a shared variable
without synchronization, the final value may be unpredictable.
Race Conditions and Critical Sections

A critical section is a code segment where a process accesses shared resources. Only one
process should execute its critical section at any given time to maintain data consistency.
The problem is ensuring mutual exclusion—preventing simultaneous access to critical
sections.
Requirements for Synchronization
1. Mutual Exclusion: At most one process can execute in its critical section at any time
2. Progress: If no process is in its critical section and processes want to enter, one
should be allowed to proceed
3. Bounded Waiting: No process should wait indefinitely before entering its critical
section
4. No Assumptions: The solution should not assume anything about relative speeds of
processes
Chapter 2: Mutual Exclusion—Software Approaches
Introduction to Software Solutions
Software approaches to mutual exclusion were historically the first attempts to solve the
synchronization problem using only programming constructs, without hardware support.
Dekker's Algorithm

One of the earliest solutions for two-process mutual exclusion:

Process 0: Process 1:
flag[0] = true; flag[1] = true;
while (flag[1]); while (flag[0]);
// critical section // critical section
flag[0] = false; flag[1] = false;
How it works: Each process sets its flag before entering the critical section. Before entering,
it checks if the other process's flag is set. If both processes set their flags simultaneously, a
turn variable breaks the tie.

Limitations: While correct, Dekker's algorithm is complex and difficult to verify. It also
suffers from poor performance due to busy-waiting (continuous checking).
Peterson's Algorithm
A simpler and more elegant solution for two processes:

flag[i] = true;
turn = j; // give preference to the other process
while (flag[j] && turn == j);
// critical section
flag[i] = false;
Advantages: Easier to understand and verify than Dekker's algorithm. It satisfies all three
requirements: mutual exclusion, progress, and bounded waiting.
Disadvantages: Still uses busy-waiting, which wastes CPU cycles. Additionally, modern out-
of-order processors may reorder instructions, making such software solutions unreliable.

Limitations of Software Approaches

Busy-waiting consumes CPU resources unnecessarily
Complexity increases with more than two processes
Modern processors with instruction reordering break these algorithms
Difficult to verify correctness
Poor scalability for large systems
Chapter 3: Mutual Exclusion—Hardware Support
Test-and-Set (TAS) Instruction
Modern processors provide atomic hardware instructions to support mutual exclusion:
boolean TestAndSet(boolean *target) {
boolean rv = *target;
*target = true;
return rv;
}

This instruction atomically reads the current value and sets it to true. The atomicity
guarantee ensures no other process can interfere during execution.
Mutual Exclusion using TAS:
boolean lock = false;

While (TestAndSet(&lock)); // wait until we get the lock

// critical section
lock = false; // release the lock
Advantages: Simple to understand and implement. Works for any number of processes.
Disadvantages: Still uses busy-waiting, wasting CPU cycles.

Compare-and-Swap (CAS) Instruction

Another important atomic instruction:
int CompareAndSwap(int *word, int testval, int newval) {
int oldval = *word;
if (oldval == testval)
*word = newval;
return oldval;
}

CAS is more flexible than TAS and forms the basis of lock-free programming techniques.
Advantages of Hardware Support
Atomic operations guarantee no interference
Simple and efficient implementation
Forms the foundation for higher-level synchronization primitives
Enables lock-free algorithms

Disadvantages
Busy-waiting still wastes CPU resources
Doesn't prevent priority inversion or other advanced issues
Limited to simple mutual exclusion patterns
Chapter 4: Semaphores
Definition and Concept
A semaphore is an abstract data type that maintains an internal counter and provides two
atomic operations: wait() and signal(). Semaphores were introduced by Edsger Dijkstra and
provide a more elegant solution to synchronization problems than software or basic
hardware approaches.
Binary Semaphore

A binary semaphore has only two values: 0 (locked) and 1 (unlocked).

wait(S): signal(S):
while (S == 0); S++;
S--;
For Mutual Exclusion:
S = 1; // initially unlocked

Process i:
wait(S);
// critical section
signal(S);
Counting Semaphore
A counting semaphore can have any non-negative integer value. It's used to control access
to a pool of identical resources.

S = N; // N identical resources
wait(S):
while (S == 0);
S--;
signal(S):
S++;

Example: For N identical I/O buffers, initialize S=N. Each process that acquires a buffer calls
wait(S), and each process that releases a buffer calls signal(S).
Key Properties
Atomicity: Both wait() and signal() are atomic operations
No Busy-Waiting: Modern implementations use a queue of blocked processes,
avoiding CPU waste
Synchronization: Beyond mutual exclusion, semaphores can synchronize processes
to establish ordering

Important Implementation Detail

In actual operating systems, semaphores use a queue to store blocked processes:
struct Semaphore {
int value;
queue processes;
};
wait(S):
[Link]--;
if ([Link] < 0) {
add this process to [Link];
block();
}

signal(S):
[Link]++;
if ([Link] <= 0) {
remove a process from [Link];
wakeup(process);
}
This eliminates busy-waiting and is much more efficient.
Semaphore Problems

Incorrect usage can lead to deadlock or race conditions

Difficult to debug synchronization errors
No compile-time checking for correct usage
Requires programmer discipline

Chapter 5: Message Passing

Concept and Advantages

Message passing is an alternative to shared-memory synchronization. Instead of multiple

processes accessing shared variables, processes communicate by sending and receiving
messages. This approach is particularly useful for distributed systems and avoids many
issues of shared-memory programming.
Key Operations
send(destination, message): Sends a message to another process
receive(source, message): Receives a message from another process

Synchronous (Blocking) Message Passing

Send: The sending process blocks until the message is received
Receive: The receiving process blocks until a message arrives
Process A: Process B:
send(B, msg); receive(A, msg);
// blocked // processes message
// continues send(A, reply);
receive(B, reply); // resumes A

Advantages: Ensures message delivery and receipt. Natural synchronization point.

Disadvantages: Can lead to deadlock if processes are not carefully designed. Blocking can
reduce concurrency.
Asynchronous (Non-Blocking) Message Passing

Send: Returns immediately after sending

Receive: Returns with any available message or null
Requires buffering of messages. Can lead to buffer overflow if receiver is slow.
Advantages of Message Passing

Avoids shared-memory issues and race conditions

Natural fit for distributed systems
Decouples sender and receiver
Easier to reason about process interactions
No need for explicit locking mechanisms
Disadvantages
Higher overhead than shared-memory for local communication
Message copying and buffering costs
Potential deadlock if not carefully designed
More complex error handling

Implementation Considerations
Modern systems like RPC (Remote Procedure Call) and RMI (Remote Method Invocation)
build upon message passing concepts to provide higher-level abstractions.

Chapter 6: Signals
Definition and Purpose
A signal is a software notification mechanism used in operating systems to alert a process
that an event has occurred. Signals provide a way to handle asynchronous events like user
interrupts, timer expiration, or errors.
Common Signals

SIGINT: Interrupt signal (Ctrl+C)

SIGKILL: Kill signal (cannot be caught or ignored)
SIGTERM: Termination signal
SIGSTOP: Stop signal (cannot be caught)
SIGSEGV: Segmentation fault
SIGALRM: Alarm clock signal from timer
SIGPIPE: Broken pipe
Signal Handlers
A process can define a signal handler—a function that executes when a particular signal
arrives:
void handle_sigint(int sig) {
printf("Received SIGINT signal\n");
exit(0);
}
signal(SIGINT, handle_sigint);

Signal Delivery and Masking

Signal Mask: A process can block (mask) certain signals temporarily. Masked signals are
delivered after the mask is removed.
sigset_t set;
sigemptyset(&set);
sigaddset(&set, SIGINT);
sigprocmask(SIG_BLOCK, &set, NULL); // block SIGINT
// ... critical section ...
sigprocmask(SIG_UNBLOCK, &set, NULL); // unblock SIGINT

Synchronization Use
Signals can synchronize processes, but their use requires care:
volatile int flag = 0;

void handler(int sig) {

flag = 1;
}
signal(SIGUSR1, handler);
pause(); // wait for signal
if (flag) { /* signal received */ }
Limitations

Signals are not queued (multiple signals of the same type may be coalesced)
Cannot reliably pass data (except signal number)
Asynchronous nature makes reasoning difficult
Potential race conditions if not carefully designed

Chapter 7: Monitors
Definition and Motivation

A monitor is a high-level synchronization construct that combines mutual exclusion and

condition synchronization. It encapsulates shared data and the operations on that data,
ensuring that only one process can execute within the monitor at a time. Monitors are
easier to use correctly than semaphores and are now widely used in modern programming
languages.
Structure of a Monitor
A monitor consists of:
 1. Shared Data: Variables protected by the monitor
2. Methods/Procedures: Operations on shared data
3. Mutual Exclusion: Automatic—only one process executes monitor code at a time
4. Condition Variables: For synchronization beyond mutual exclusion
Monitor in Pseudocode

monitor MonitorName {
shared data declaration;

procedure procedure_1 (...) {

// body
}

procedure procedure_2 (...) {

// body
}

initialization code {
// performed once
}

Condition Variables
When a process needs to wait for a condition, it uses a condition variable:
condition cv;

// In a monitor method:
if (condition not satisfied)
wait(cv); // releases monitor lock and waits
// Another process:
signal(cv); // wakes one waiting process
Semantics of Signal

Signal-and-Continue: The signaling process continues, waiting process becomes ready.

Signal-and-Wait: The signaling process waits, signaled process resumes immediately.
Signal-and-Exit: Automatic transition at procedure exit.

Example: Monitor-Based Mutual Exclusion

monitor MutexExample {
int shared_var = 0;
 procedure increment() {
shared_var++;
}

procedure get_value(int &val) {

val = shared_var;
}

// Multiple processes call procedures safely

Comparison with Semaphores

Aspect Semaphore Monitor

Encapsulates shared
Encapsulation No data protection
data
Atomicity Manual Automatic
Condition Complex (multiple Built-in (condition
Synchronization semaphores) variables)
Yes (deadlock,
Error Prone More robust
starvation)
Overhead Low Slightly higher

Advantages

Easier to verify correctness

Automatic mutual exclusion reduces errors
Condition variables provide clean synchronization semantics
Encapsulation improves maintainability
Disadvantages
Not supported in all programming languages
Slightly higher overhead than semaphores
Less efficient for simple cases
Learning curve for proper use

Modern Implementations
Java's synchronized blocks and condition variables are monitor-like constructs:
synchronized(object) {
// mutual exclusion guaranteed
}
// Condition variables via [Link]() and notify()

Chapter 8: Classical Problems of Synchronization

Overview
Classical synchronization problems demonstrate common patterns and solutions for
concurrent programming. Understanding these helps developers recognize similar
patterns in real applications.

8.1: Readers-Writers Problem

Problem Statement

A shared resource (like a file or database) is accessed by two types of processes:

Readers: Only read the resource, don't modify it
Writers: Both read and write the resource
Requirements:

Multiple readers can read simultaneously

Writers must have exclusive access (no other readers or writers)
Readers should not wait for other readers
Writers should not be starved by continuous readers
First Solution: Reader Preference
int read_count = 0;
semaphore ws = 1; // writer semaphore
semaphore mutex = 1; // protects read_count

Reader:
wait(mutex);
read_count++;
if (read_count == 1)
wait(ws);
signal(mutex);
// perform read
wait(mutex);
read_count--;
if (read_count == 0)
signal(ws);
signal(mutex);

Writer:
wait(ws);
// perform write
signal(ws);
Issue: Writers can starve if readers keep arriving. The first reader arriving blocks writers,
and new readers don't check if writers are waiting.

Second Solution: Writer Preference

To prevent writer starvation:
int read_count = 0, write_count = 0;
semaphore ws = 1; // writer semaphore
semaphore rs = 1; // reader semaphore
semaphore mutex_read = 1; // protect read_count
semaphore mutex_write = 1; // protect write_count

Reader:
wait(rs);
wait(mutex_read);
read_count++;
if (read_count == 1)
wait(ws);
signal(mutex_read);
signal(rs);
// perform read
wait(mutex_read);
read_count--;
if (read_count == 0)
signal(ws);
signal(mutex_read);

Writer:
wait(mutex_write);
write_count++;
if (write_count == 1)
wait(rs);
signal(mutex_write);
wait(ws);
// perform write
signal(ws);
wait(mutex_write);
write_count--;
if (write_count == 0)
signal(rs);
signal(mutex_write);

Mechanism: Writers block the reader semaphore, preventing new readers from starting.
Existing readers finish, and the writer proceeds.
8.2: Producer-Consumer Problem (Bounded Buffer)
Problem Statement
Producers create items and place them in a bounded buffer. Consumers remove items from
the buffer. Synchronization must ensure:
Producer doesn't overflow the buffer
Consumer doesn't access empty buffer
Only one producer or consumer accesses buffer at a time

Solution using Semaphores

int buffer[N];
int in = 0, out = 0;
semaphore empty = N; // empty slots
semaphore full = 0; // filled slots
semaphore mutex = 1; // mutual exclusion
Producer:
produce();
wait(empty);
wait(mutex);
buffer[in] = item;
in = (in + 1) % N;
signal(mutex);
signal(full);

Consumer:
wait(full);
wait(mutex);
item = buffer[out];
out = (out + 1) % N;
signal(mutex);
signal(empty);
consume(item);
How It Works
empty: Tracks empty slots. Producer waits until buffer isn't full.
full: Tracks filled slots. Consumer waits until buffer isn't empty.
mutex: Ensures only one process modifies the buffer indices.

The order of wait() calls is crucial—calling wait(mutex) before wait(empty/full) can cause
deadlock.
Key Insight
The semaphore ordering prevents deadlock:

1. Producer checks resource availability (wait on empty)

2. Then acquires access right (wait on mutex)
3. Consumer does similarly with full
If reversed, two producers could acquire mutex, then both wait for empty—deadlock.

8.3: Dining Philosophers Problem

Problem Statement
Five philosophers sit at a circular table with one chopstick between each adjacent pair. Each
philosopher alternates between thinking and eating. To eat, a philosopher must acquire
both left and right chopsticks. After eating, chopsticks are returned.

Challenge: Design a protocol so no philosopher starves and deadlock is avoided.

Naive Solution (Leads to Deadlock)
Philosopher i:
think();
take_left_chopstick(i);
take_right_chopstick((i+1) % 5);
eat();
put_left_chopstick(i);
put_right_chopstick((i+1) % 5);

Problem: If all philosophers simultaneously take their left chopstick, none can acquire their
right chopstick—circular wait causes deadlock.
Solution 1: Asymmetric Approach
Make philosopher 0 left-handed (take right first):

Philosopher 0:
think();
take_right_chopstick(4);
take_left_chopstick(0);
eat();
put_left_chopstick(0);
put_right_chopstick(4);
Philosophers 1-4:
think();
take_left_chopstick(i);
take_right_chopstick((i+1) % 5);
eat();
put_left_chopstick(i);
put_right_chopstick((i+1) % 5);
Result: Prevents circular wait. At least one philosopher can always acquire both chopsticks.

Solution 2: Monitor-Based Solution

monitor DiningPhilosophers {
enum state { THINKING, HUNGRY, EATING } state[5];
condition self[5];
int i;
 procedure pickup(int i) {
state[i] = HUNGRY;
test(i);
if (state[i] != EATING)
wait(self[i]);
}

procedure putdown(int i) {
state[i] = THINKING;
test((i+4) % 5); // left neighbor
test((i+1) % 5); // right neighbor
}

procedure test(int i) {
if (state[i] == HUNGRY &&
state[(i+4) % 5] != EATING &&
state[(i+1) % 5] != EATING) {
state[i] = EATING;
signal(self[i]);
}
}

Advantages: Clearer code, automatic mutual exclusion, easier to verify.

Solution 3: Limiting Concurrent Diners
Allow at most 4 philosophers to sit (instead of all 5):

semaphore room = 4;
Philosopher i:
think();
wait(room);
acquire_both_chopsticks();
eat();
release_both_chopsticks();
signal(room);
Result: At least one philosopher can always get both chopsticks. Simple and elegant.

Key Lessons
 Resource ordering can prevent deadlock
Breaking symmetry helps in circular resource problems
Monitors provide cleaner solutions than semaphores
Limiting concurrent access can be simpler than complex protocols

PART II: DEADLOCK

Chapter 9: Principles of Deadlock
Definition
A deadlock occurs when a set of processes are blocked forever because each process is
waiting for a resource held by another process in the set. None of the processes can
proceed, and the system makes no progress.
System Model

Resources are classified as:

Reusable Resources: Can be used by one process at a time. Examples: CPUs, I/O
devices, memory, files.
Consumable Resources: Created (produced) and destroyed (consumed). Examples:
messages, signals, interrupts.
Necessary Conditions for Deadlock

All four conditions must hold simultaneously for deadlock:

1. Mutual Exclusion: A resource can be held by at most one process at a time. Shared
resources don't cause deadlock.
2. Hold and Wait: A process holding at least one resource waits for another resource
held by another process.
3. No Preemption: Resources cannot be forcibly taken away; only the holding process
can release them.
4. Circular Wait: A circular chain of processes exists where each process waits for a
resource held by the next process in the chain.
Resource Allocation Graph

A directed graph represents the resource allocation state:

Vertices: Represent processes or resources
Edges:
Request edge (P→R): Process P requests resource R
Allocation edge (R→P): Resource R is allocated to process P
Deadlock Detection: A cycle in the graph indicates potential deadlock.

Example
Process P1 holds resource R1
Process P1 requests resource R2
Process P2 holds resource R2
Process P2 requests resource R1
Graph:
P1 → R1 → P2 → R2 → P1 (cycle!)

All four conditions present → Deadlock occurs.

Deadlock vs. Starvation
Starvation: A process waits indefinitely but might eventually proceed if conditions change
(e.g., another process finishes).

Deadlock: Processes will never proceed; the situation is permanently stuck.

Impact of Deadlock
System halts without explicit intervention
Resources are wasted
User processes hang indefinitely
System reliability compromised
Difficult to detect in complex systems

Chapter 10: Deadlock Prevention

Overview
Deadlock prevention makes one of the four necessary conditions impossible, ensuring
deadlock cannot occur. It's the most restrictive approach but guarantees safety.

10.1: Preventing Mutual Exclusion

Approach: Make resources sharable.

Limitations:
Many resources are inherently non-sharable (printer, database record)
Not always practical or desirable
Limited applicability
Example:
Some systems use spooling for non-sharable resources. Instead of direct access, processes
write to spooled files, and a spooler daemon manages actual resource access sequentially.

10.2: Preventing Hold and Wait

Approach 1: Require All Resources Upfront

A process must request all resources needed before beginning execution:

Process:
request_all_resources();
perform_work();
release_all_resources();
Advantages: Simple to implement and understand.
Disadvantages:

Processes often don't know resource needs in advance

Resources held unnecessarily for long periods
Reduces concurrency significantly
Resource utilization is poor
Approach 2: No Holding While Requesting
If a process needs additional resources, it must release all currently held resources first:

while (not all resources acquired) {

release_all_held_resources();
request_needed_resources();
}
Advantages: Better resource utilization than Approach 1.
Disadvantages:

Context switches and potential livelock

Overhead of repeated acquisition
Processes may never acquire all needed resources (indefinite waiting)
Complex to implement correctly

10.3: Preventing No Preemption

Approach: Allow preemption of resources.
Preemption Protocol:
If a process holding resources requests another resource that's unavailable, all
currently held resources are preempted (taken away)
The process is restarted after obtaining the desired resource

Applicability:
Works well for CPUs and memory (can be swapped to disk)
Difficult for non-preemptible resources (printer, database locks)
Example: CPU scheduling preempts the CPU from one process to give to another.

Disadvantages:
Increased context switch overhead
Not applicable to all resource types
Potential loss of work
10.4: Preventing Circular Wait
Approach 1: Resource Ordering
Total ordering of resources is defined. Each process requests resources in strictly increasing
order:
Order: R1 < R2 < R3

Process:
request R1 then R2; // ✓ Valid (increasing order)
request R2 then R3; // ✓ Valid (increasing order)
request R3 then R1; // ✗ Invalid (decreasing order)
Mechanism: A process holding resource Ri cannot request resource Rj if Rj < Ri. This
prevents circular wait.
Proof: Suppose a cycle exists: P1→R1→P2→R2→...→Pn→Rn→P1

Since resources are ordered and a process holds Ri before requesting Ri+1:
R1 < R2 < ... < Rn
But P1 requests R1 after obtaining Rn:

Rn > Rn-1 > ... > R1

Contradiction! No cycle possible.
Advantages:

Simple to implement
No resource waste
Minimal overhead
Disadvantages:
Requires knowing all resources in advance
May enforce inefficient request ordering
Difficult to apply in dynamic systems
Not applicable when process resource needs unknown

Approach 2: Banker's Algorithm (Actually deadlock avoidance—see next section)

Summary: Prevention Comparison
 Condition Prevention Method Practical Impact
Mutual Limited; most resources
Make resources sharable
Exclusion non-sharable
Hold and Request all upfront or
Poor resource utilization
Wait release and re-request
No
Works for CPU/memory;
Preemptio Allow preemption
not for most devices
n
Circular Most practical; requires
Resource ordering
Wait static planning

Chapter 11: Deadlock Avoidance

Overview

Deadlock avoidance allows three necessary conditions but prevents circular wait
dynamically. Instead of making a resource unavailable, the system analyzes each resource
allocation request and grants it only if the system remains in a safe state.
Safe and Unsafe States
Safe State: A sequence of processes exists such that each process can acquire all needed
resources and complete. The system is not necessarily deadlocked but could become so.

Unsafe State: No safe sequence exists. The system may or may not deadlock, but the risk
exists.
Strategy: The system maintains safe states and rejects allocations that would lead to
unsafe states.
Banker's Algorithm (Dijkstra)

The most well-known deadlock avoidance algorithm. Named after a banker managing
loans to customers with limited capital.
Data Structures
Available[m]: Number of available instances of each resource type
Maximum[n][m]: Maximum resources each process could need
Allocated[n][m]: Resources currently allocated to each process
Need[n][m]: Remaining resources needed by each process
Need[i][j] = Maximum[i][j] - Allocated[i][j]

Safety Algorithm
Checks if a state is safe:
Work = Available; // Available resource instances
Finish = [false] * n; // Track completed processes
while (exists process i with Finish[i] == false) {
if (Need[i] <= Work) {
// Process i can complete
Work += Allocated[i]; // Process releases resources
Finish[i] = true;
}
}

if (all Finish[i] == true)

state is SAFE;
else
state is UNSAFE;
Resource Request Algorithm
When process Pi requests resources Request[i]:

1. If Request[i] <= Need[i], continue; else error (exceeds max)

2. If Request[i] <= Available, continue; else wait
3. Simulate allocation:
Available -= Request[i];
Allocated[i] += Request[i];
Need[i] -= Request[i];
4. Run safety algorithm
5. If safe state: confirm allocation
If unsafe state: restore original state and make process wait
Example
3 processes, 12 instances of one resource type

Process Maximum Allocated Need

P0 10 5 5
P1 4 2 2
P2 7 2 5

Available: 3
P1 requests 2: Available (3) >= Request (2) → Check if safe
After allocation: Available = 1, Allocated[1] = 4, Need[1] = 0
Sequence: P1 completes → Available = 5
P0 completes → Available = 15
P2 completes → Available = 22
SAFE → Grant request
P0 requests 1: After allocation: Available = 2
Sequence: Check if any process can complete...
No process can complete with Available = 2
UNSAFE → Deny request
Advantages

Guarantees no deadlock (more permissive than prevention)

Better resource utilization than prevention
Processes don't suffer indefinite starvation
Disadvantages
Requires knowing maximum resource needs in advance (often impractical)
Computation overhead for safety checking
Inherent assumption: processes request resources in certain patterns
Processes declared Maximum may be overestimated, causing unnecessary wait
Only for reusable resources

Limitations in Practice
Many systems can't predict resource needs upfront
Process resource needs vary dynamically
Not applicable for consumable resources
Overkill for systems with simple resource patterns

Chapter 12: Deadlock Detection

Overview
Instead of prevention or avoidance, deadlock detection allows deadlock to occur and then
detects it. Upon detection, the system takes recovery measures. This approach is optimistic
and more practical for general systems.
Detection for Single Resource Type

When each resource type has only one instance:

Algorithm: Build a wait-for graph where vertices represent processes and edges represent
wait relationships. A cycle indicates deadlock.
if Process Pi holds Rj and Pj requests Rj:
Draw edge Pi → Pj

Deadlock ⟺ Cycle exists in wait-for graph

Complexity: O(n²) for n processes.
Detection for Multiple Resource Types

Uses resource allocation graph analysis:

Available[m]: Available instances of each resource
Allocated[n][m]: Resources allocated to each process
Request[n][m]: Resources requested by each process (not yet allocated)
Finish = [false] * n;
Work = Available;
while (exists process i with Finish[i] == false) {
if (Request[i] <= Work) {
// Process i can complete
Work += Allocated[i];
Finish[i] = true;
} else {
// Process i cannot complete; possibly in deadlock
}
}

if (any Finish[i] == false)

Deadlock exists among these processes;
else
No deadlock
Key Difference from Safety Algorithm
Safety (Avoidance): Considers Need (future requests)
Detection: Considers Request (current blocked requests)

Detection Frequency
How often should the system check for deadlock?
Option 1: Check Every Resource Request

Advantage: Detects deadlock immediately

Disadvantage: High computational overhead
Option 2: Check Periodically
Advantage: Reduced overhead
Disadvantage: Deadlock not immediately detected; multiple processes affected

Option 3: Check When CPU Utilization is Low

Advantage: Uses idle CPU time
Disadvantage: Delayed detection; implementation complexity
Detection Complexity

For n processes and m resource types: O(n²m) or O(n+m) depending on implementation.

Recovery from Deadlock
Once deadlock is detected, recovery is necessary:
Recovery Method 1: Process Termination
Option A: Terminate All Deadlocked Processes
Simple and guaranteed to break deadlock
Loss of all work by these processes
Expensive restart
Option B: Terminate Processes One by One Until Deadlock Resolved

Less work loss than terminating all

Overhead: Re-run detection after each termination
Better resource utilization
Selection Criteria for Termination:
1. Process priority
2. Execution time (kill young processes)
3. Resources consumed
4. Resources still needed
5. Number of processes to terminate

Recovery Method 2: Resource Preemption

Select a victim process and take away its resources, assigning them to waiting processes.

Challenges:
1. Selecting victim: Which process to preempt? Criteria: minimize cost
2. Rollback: Return process to safe state. Often need to restart from beginning or use
checkpoints
3. Starvation: Same victim chosen repeatedly → need selection criteria to prevent
Starvation Prevention:

Track number of rollbacks per process

Increase cost if process rolled back multiple times
Eventually choose a different victim
Implementation Complexity:
Need to save/restore process state
Applicable mainly to computation-heavy processes
Difficult for I/O-bound processes (can't roll back I/O)

Chapter 13: Comparison of Deadlock Handling Strategies

Summary Table
 Strate Guarante Resource Computation
Practicality
gy es Utilization al Overhead
Poor
Preve No
(resource Minimal Limited
ntion deadlock
waste)
Limited
Avoid No High (safety
Good (need max
ance deadlock checks)
info)
Detect Deadlock Low (periodic
Excellent High
ion may occur check)
Used in
Ignor No
Excellent Minimal many
ance guarantee
systems

Prevention
Best for: Systems where resources are easily made sharable or orderable
Worst for: Complex systems with unknown resource requirements

Avoidance
Best for: Batch systems where process requirements known in advance
Worst for: Interactive and distributed systems
Detection

Best for: Systems where deadlock is rare or recovery is simple

Worst for: Systems where deadlock is frequent
Ignorance
Best for: Most practical systems (UNIX, Windows, Linux)
Reason: Deadlock is rare in well-designed applications. Manual intervention (restart)
when deadlock occurs is acceptable.
Assumption: Programmer responsibility to avoid deadlock through careful design

Modern System Approaches

Most modern operating systems use a combination:
1. Resource ordering for critical resources (partial prevention)
2. Timeouts (simple detection) - if process waits too long, assume deadlock
3. User intervention to restart deadlocked processes
4. Application-level handling (transactions with rollback)
Conclusion
Concurrency and deadlock management are fundamental to operating system design.
Understanding these principles enables building robust, efficient systems. Key takeaways:
Concurrency enables better resource utilization but introduces synchronization
challenges
Mutual exclusion mechanisms (semaphores, monitors) prevent race conditions
Synchronization problems demonstrate common patterns requiring careful
solutions
Deadlock can be prevented, avoided, or detected based on system requirements
No perfect solution exists; system designers balance correctness, performance, and
practicality

Modern systems typically employ hybrid strategies, combining prevention for critical
resources with detection and recovery for complex scenarios, acknowledging that some
deadlock situations are better managed through manual intervention than eliminated
entirely.