Deadlocks, Starvation, and Livelocks

When multiple processes or threads compete for shared resources, three critical problems can arise: deadlocks, starvation, and livelocks. These issues can bring systems to a halt, cause performance degradation, or prevent processes from making progress.

What is a Deadlock?

Deadlock Definition

A deadlock is a situation where two or more processes are blocked indefinitely, each waiting for a resource held by another process in the set. None of the processes can proceed because they're all waiting for resources that will never become available.

Commonly, whenever a thread is able to enter a critical section, we say that it has acquired a lock. Whenever a thread is unable to enter a critical section, we say that it has been blocked. By the same token, whenever a thread is able to leave a critical section, we say that it has released a lock.

Classic Deadlock Example

Consider two processes, A and B, competing for two resources, R1 and R2:

Process A: Acquires R1, then requests R2
Process B: Acquires R2, then requests R1

Timeline:

1. Process A acquires resource R1
2. Process B acquires resource R2
3. Process A requests R2 (blocked - held by B)
4. Process B requests R1 (blocked - held by A)

Both processes are now deadlocked - neither can proceed because each holds a resource the other needs.

Deadlock Conditions

The Four Necessary Conditions

For a deadlock to occur, all four of these conditions must be present:

1. Mutual Exclusion

• Resources cannot be shared simultaneously
• Only one process can use a resource at a time
• Example: A printer can only print one document at a time

2. Hold and Wait

• Processes hold resources while waiting for others
• They don't release resources they already have
• Example: Process holds memory while waiting for disk access

3. No Preemption

Preemption is the ability to forcibly take away a resource from a process. An OS can preempt an unresponsive process by taking away a resource that it is holding. Sometimes you may want to preempt a process to ensure that a critical section is executed atomically.

• Resources cannot be forcibly taken away from processes
• Only the process holding a resource can release it
• Example: Cannot forcibly stop a process using a printer

4. Circular Wait

• There exists a circular chain of processes waiting for resources
• Each process waits for a resource held by the next process in the chain
• Example: A → B → C → A (circular dependency)

Resource Allocation Graph

A resource allocation graph is a visual tool for detecting deadlocks:

Processes: P1, P2, P3
Resources: R1, R2, R3

P1 → R1 (P1 holds R1)
P2 → R2 (P2 holds R2)  
P3 → R3 (P3 holds R3)
P1 → R2 (P1 waiting for R2)
P2 → R3 (P2 waiting for R3)
P3 → R1 (P3 waiting for R1)

Rules:

• Process nodes (circles): Represent processes
• Resource nodes (rectangles): Represent resources
• Assignment edges (solid arrows): Process holds resource
• Request edges (dashed arrows): Process waiting for resource

Deadlock Detection:

• If the graph contains a cycle, there is a deadlock
• The cycle indicates a circular wait condition

Deadlock Detection

Algorithm for Deadlock Detection

bool detectDeadlock() {
    // Initialize work vector with available resources
    vector<int> work = available;
    vector<bool> finish(processes.size(), false);

    // Find a process that can finish
    bool found;
    do {
        found = false;
        for (int i = 0; i < processes.size(); i++) {
            if (!finish[i] && canAllocate(i, work)) {
                // Process i can finish
                work = addResources(work, allocation[i]);
                finish[i] = true;
                found = true;
            }
        }
    } while (found);

    // Check if all processes can finish
    for (int i = 0; i < processes.size(); i++) {
        if (!finish[i]) {
            return true; // Deadlock detected
        }
    }
    return false; // No deadlock
}

Deadlock Prevention

Strategy 1: Eliminate Mutual Exclusion

Approach: Make resources shareable Example: Read-only files can be shared by multiple processes Limitation: Not always possible (printers, memory locations)

Strategy 2: Eliminate Hold and Wait

Approach: Require processes to request all resources at once Implementation: Resource reservation protocols Example: Process must declare all needed resources before starting

// Before: Hold and wait (can cause deadlock)
acquireResource(R1);
// ... some work ...
acquireResource(R2); // Might block here

// After: Request all at once (prevents deadlock)
acquireAllResources({R1, R2});
// ... work with both resources ...
releaseAllResources({R1, R2});

Strategy 3: Allow Preemption

Approach: Allow resources to be forcibly taken away Implementation: Resource preemption with rollback Example: Virtual memory can be swapped out

// Preempt resource from process
void preemptResource(int processId, int resourceId) {
    // Save process state
    saveProcessState(processId);

    // Take resource away
    releaseResource(processId, resourceId);

    // Restart process from saved state
    restartProcess(processId);
}

Strategy 4: Eliminate Circular Wait

Approach: Impose a total ordering on resources Implementation: Resource ordering protocols Example: Always request resources in ascending order

// Resource ordering: R1 < R2 < R3
void acquireResources(int r1, int r2) {
    if (r1 < r2) {
        acquireResource(r1);
        acquireResource(r2);
    } else {
        acquireResource(r2);
        acquireResource(r1);
    }
}

Deadlock Avoidance

Banker's Algorithm

The Banker's Algorithm is a deadlock avoidance algorithm that ensures the system never enters an unsafe state.

Key Concepts

Safe State: A state where there exists at least one sequence of resource allocations that allows all processes to complete. Unsafe State: A state where no such sequence exists - deadlock is possible.

Algorithm Steps

1. Check if request can be granted
2. Simulate the allocation
3. Check if resulting state is safe
4. Grant request only if safe

bool isSafeState() {
    vector<int> work = available;
    vector<bool> finish(processes.size(), false);

    // Find a process that can finish
    bool found;
    do {
        found = false;
        for (int i = 0; i < processes.size(); i++) {
            if (!finish[i] && canAllocate(i, work)) {
                work = addResources(work, allocation[i]);
                finish[i] = true;
                found = true;
            }
        }
    } while (found);

    // Check if all processes can finish
    for (int i = 0; i < processes.size(); i++) {
        if (!finish[i]) {
            return false; // Unsafe state
        }
    }
    return true; // Safe state
}

bool requestResource(int processId, vector<int> request) {
    // Check if request exceeds need
    if (request > need[processId]) {
        return false; // Invalid request
    }

    // Check if request exceeds available
    if (request > available) {
        return false; // Must wait
    }

    // Simulate allocation
    available = available - request;
    allocation[processId] = allocation[processId] + request;
    need[processId] = need[processId] - request;

    // Check if state is safe
    if (isSafeState()) {
        return true; // Grant request
    } else {
        // Restore state
        available = available + request;
        allocation[processId] = allocation[processId] - request;
        need[processId] = need[processId] + request;
        return false; // Deny request
    }
}

Deadlock Recovery

Process Termination

Approach: Terminate one or more processes to break deadlock Methods:

• Abort all deadlocked processes
• Abort one process at a time until deadlock is resolved
• Abort the process that can be terminated with minimum cost

Resource Preemption

Approach: Preempt resources from processes to break deadlock Considerations:

• Selection criteria: Which process to preempt from
• Rollback: How far to roll back the preempted process
• Starvation: Ensure the same process isn't always preempted

What is Starvation?

Starvation Definition

Starvation occurs when a process is permanently or indefinitely denied access to a resource because other processes are consistently given priority. The starving process may be ready to run but never gets the CPU, or may be waiting for a resource that is always allocated to higher-priority processes.

CPU Starvation

High-priority processes: P1, P2, P3 (always ready)
Low-priority process: P4 (never gets CPU time)

Timeline:
P1 runs → P2 runs → P3 runs → P1 runs → P2 runs...
P4 never gets a chance to run

Resource Starvation

Resource: Printer
Processes: P1 (high priority), P2 (low priority)

P1 always has print jobs, P2 never gets printer access

Starvation vs Deadlock

Aspect	Starvation	Deadlock
Process State	Ready to run	Blocked waiting
Resource State	Available but not allocated	Held by other processes
Duration	Indefinite	Permanent
Resolution	Can be resolved by priority changes	Requires process termination

Starvation Prevention

Aging

Approach: Gradually increase priority of waiting processes Implementation: Boost priority based on waiting time

void updatePriorities() {
    for (int i = 0; i < processes.size(); i++) {
        if (processes[i].waitingTime > threshold) {
            processes[i].priority += boost;
        }
    }
}

Fair Scheduling

Approach: Ensure all processes get fair access to resources Methods:

• Round-robin scheduling
• Fair queuing algorithms
• Resource reservation

Priority Inversion Prevention

Priority Inversion: High-priority process blocked by low-priority process Solutions:

• Priority inheritance: Low-priority process inherits high priority
• Priority ceiling: Resources have priority ceilings
• Immediate priority inheritance

What is Livelock?

Livelock Definition

A livelock is similar to a deadlock, but instead of being blocked, processes are actively changing state without making progress toward their goal. They're doing work, but it's futile work that doesn't advance their objectives.

Polite People Passing Through a Door

Person A: Moves right to let Person B pass
Person B: Moves right to let Person A pass
Person A: Moves left to let Person B pass
Person B: Moves left to let Person A pass
... (continues indefinitely)

Both people are actively moving but never actually pass through the door.

Computer Science Example

// Two processes trying to acquire two resources
Process A: Release R1, try to acquire R2
Process B: Release R2, try to acquire R1
Process A: Release R2, try to acquire R1
Process B: Release R1, try to acquire R2
// ... continues indefinitely

Livelock vs Deadlock

Aspect	Livelock	Deadlock
Process State	Active, changing state	Blocked, static
CPU Usage	High (busy doing futile work)	Low (blocked)
Detection	Harder to detect	Easier to detect
Resolution	Add randomness or timeouts	Process termination

Livelock Prevention

Randomization

Approach: Add randomness to break synchronized behavior Example: Random delays before retrying

void acquireResource(int resourceId) {
    while (!tryAcquire(resourceId)) {
        // Random delay to break livelock
        int delay = random(1, 100);
        sleep(delay);
    }
}

Timeouts

Approach: Give up after a certain time Example: Timeout-based resource acquisition

bool acquireResourceWithTimeout(int resourceId, int timeout) {
    int startTime = getCurrentTime();
    while (getCurrentTime() - startTime < timeout) {
        if (tryAcquire(resourceId)) {
            return true;
        }
        sleep(1);
    }
    return false; // Timeout
}

Exponential Backoff

Approach: Increase delay exponentially with each failure Example: Exponential backoff for retries

void acquireResourceWithBackoff(int resourceId) {
    int delay = 1;
    while (!tryAcquire(resourceId)) {
        sleep(delay);
        delay = min(delay * 2, maxDelay);
    }
}

Real-World Examples

Database Systems

Deadlock: Two transactions waiting for locks held by each other Solution: Deadlock detection with transaction rollback

Operating Systems

Starvation: Low-priority processes never getting CPU time Solution: Aging and fair scheduling algorithms

Network Protocols

Livelock: Network congestion causing packets to be dropped and retransmitted Solution: Exponential backoff and congestion control

High-Frequency Trading

Deadlock: Multiple trading algorithms competing for market data feeds Solution: Resource ordering and timeout mechanisms

Detection and Monitoring

System Monitoring

Tools:

• Process monitors: Track process states and resource usage
• Resource monitors: Monitor resource allocation patterns
• Performance counters: Track system performance metrics

Detection Algorithms

Deadlock Detection:

• Resource allocation graph analysis
• Cycle detection algorithms
• Periodic system state checks

Starvation Detection:

• Wait time monitoring
• Priority analysis
• Resource access patterns

Livelock Detection:

• State change monitoring
• Progress tracking
• CPU usage analysis

Best Practices

Design Principles

1. Resource Ordering: Always acquire resources in a consistent order
2. Timeout Mechanisms: Use timeouts to prevent indefinite waiting
3. Resource Limits: Set limits on resource usage
4. Monitoring: Implement comprehensive monitoring and alerting

Implementation Guidelines

1. Avoid Nested Locks: Minimize the number of locks held simultaneously
2. Use Lock Hierarchies: Establish clear lock ordering rules
3. Implement Timeouts: Always use timeouts for resource acquisition
4. Monitor and Log: Track resource usage and potential issues

Testing Strategies

1. Stress Testing: Test with high concurrency and resource contention
2. Deadlock Injection: Intentionally create deadlock scenarios
3. Recovery Testing: Test deadlock detection and recovery mechanisms
4. Performance Testing: Measure impact of prevention mechanisms

Questions

Q: What are the four necessary conditions for a deadlock to occur?

The four necessary conditions for deadlock are: 1) Mutual exclusion - resources cannot be shared, 2) Hold and wait - processes hold resources while waiting for others, 3) No preemption - resources cannot be forcibly taken away, 4) Circular wait - there exists a circular chain of processes waiting for resources held by other processes in the chain.

Q: What is the difference between deadlock and livelock?

In deadlock, processes are blocked waiting for resources and cannot make progress - they are in a static waiting state. In livelock, processes are actively changing state but not making progress toward their goal - they are in a dynamic but unproductive state. Both prevent progress, but livelock involves active but futile work.

Q: What is starvation in the context of resource allocation?

Starvation occurs when a process is permanently or indefinitely denied access to a resource because other processes are consistently given priority. The starving process may be ready to run but never gets the CPU, or may be waiting for a resource that is always allocated to higher-priority processes.

Q: Which deadlock prevention strategy eliminates the 'hold and wait' condition?

Resource reservation (also called resource allocation protocols) eliminates the 'hold and wait' condition by requiring processes to request all resources they need at once, before starting execution. This prevents processes from holding some resources while waiting for others, breaking the hold and wait condition.

Q: What is the Banker's Algorithm used for?

A: Detecting existing deadlocks in the system

The Banker's Algorithm is a deadlock avoidance algorithm that checks if granting a resource request would leave the system in a safe state. It simulates the allocation and checks if all processes can complete with the remaining resources. If the state would be unsafe, the request is denied.

Q: What is a safe state in deadlock avoidance?

A safe state is one where there exists at least one sequence of resource allocations that allows all processes to complete their execution. In a safe state, even if all processes request their maximum resources, there is a way to allocate resources so that all processes can finish without deadlock.

Q: What is the main disadvantage of deadlock detection and recovery?

The main disadvantage of deadlock detection and recovery is that it can cause data loss when processes are terminated to break deadlocks. When a process is killed to recover from deadlock, any uncommitted work or data in that process is lost, which may be unacceptable in many applications.

Q: What is priority inversion and how does it relate to starvation?

Priority inversion occurs when a high-priority process is blocked waiting for a resource held by a low-priority process, which in turn is blocked by a medium-priority process. This can cause the high-priority process to starve, as it cannot proceed even though it has higher priority than the blocking processes.

Q: What is the difference between deadlock prevention and deadlock avoidance?

Deadlock prevention eliminates one or more of the four necessary conditions for deadlock (mutual exclusion, hold and wait, no preemption, circular wait). Deadlock avoidance uses algorithms like the Banker's Algorithm to ensure the system never enters an unsafe state where deadlock could occur.

Q: What is a resource allocation graph and how is it used in deadlock detection?

A resource allocation graph is a directed graph where nodes represent processes and resources, and edges represent resource allocation (process holds resource) or resource requests (process waiting for resource). A cycle in this graph indicates a deadlock, as it shows a circular wait condition among processes.