Deadlock

Deadlock

Basic Concepts

Definition of Deadlock

Deadlock: a situation in which several processes wait for one another because they compete for resources; without outside intervention, none of them can make progress.

Characteristics of deadlock:

1. Mutual exclusion: a resource cannot be used by several processes at the same time
2. Hold and wait: a process does not release the resources it holds while waiting for other resources
3. No preemption: a resource cannot be forcibly taken away
4. Circular wait: a chain of waiting processes forms a cycle

A Deadlock Example

A classic deadlock scenario:

Process A holds resource R1 and requests resource R2
Process B holds resource R2 and requests resource R1

Resource allocation graph:

    R1 -----> P1
    |         |
    |         v
    |         P2
    |         |
    R2 <------|

Deadlock Prevention

Breaking Mutual Exclusion

Strategy: use shareable resources so that mutual exclusion is never needed.

Methods:

• Use read-only resources
• Use virtualization
• Use resource pools

Example:

// Use shared memory instead of a mutex
shared_memory *data = get_shared_memory();
// Several processes can read at the same time
read_data(data);

Breaking Hold and Wait

Strategy: a process must request all the resources it needs at once.

Methods:

1. Resource pre-allocation: the process requests all resources before it starts running
2. Resource release: the process releases every resource it holds before requesting a new one

Example:

// Request all resources at once
void process() {
    acquire_all_resources();
    // do the work
    release_all_resources();
}

Breaking No Preemption

Strategy: allow resources to be forcibly taken away.

Methods:

• Assign priorities to resources
• Implement a resource preemption mechanism
• Use timeouts

Example:

// Resource preemption
void resource_preemption() {
    if (high_priority_process_needs_resource()) {
        preempt_resource_from_low_priority_process();
        allocate_resource_to_high_priority_process();
    }
}

Breaking Circular Wait

Strategy: number the resources and require processes to request them in increasing order.

Methods:

• Ordered resource allocation
• A resource numbering scheme
• A hierarchical structure of resources

Example:

// Resource numbering: R1=1, R2=2, R3=3
void ordered_resource_allocation() {
    // resources can only be requested in number order
    acquire_resource(1);  // R1
    acquire_resource(2);  // R2
    acquire_resource(3);  // R3
    // R3 can never be requested before R1
}

Deadlock Avoidance

The Banker’s Algorithm

Principle: before allocating resources, check whether the allocation would lead to an unsafe state; allocate only in a safe state.

Data structures:

int available[RESOURCES];     // available resources
int maximum[PROCESSES][RESOURCES];    // maximum demand
int allocation[PROCESSES][RESOURCES]; // already allocated
int need[PROCESSES][RESOURCES];       // still needed

Safety check:

bool is_safe_state() {
    int work[RESOURCES];
    bool finish[PROCESSES];

    // initialization
    for (int i = 0; i < RESOURCES; i++)
        work[i] = available[i];
    for (int i = 0; i < PROCESSES; i++)
        finish[i] = false;

    // look for a process that can finish
    for (int count = 0; count < PROCESSES; count++) {
        bool found = false;
        for (int i = 0; i < PROCESSES; i++) {
            if (!finish[i] && can_allocate(i, work)) {
                // allocate resources to process i
                for (int j = 0; j < RESOURCES; j++)
                    work[j] += allocation[i][j];
                finish[i] = true;
                found = true;
            }
        }
        if (!found) return false; // unsafe state
    }
    return true; // safe state
}

Resource allocation algorithm:

bool request_resources(int process_id, int request[]) {
    // check that the request does not exceed the need
    for (int i = 0; i < RESOURCES; i++) {
        if (request[i] > need[process_id][i])
            return false;
    }

    // check that enough resources are available
    for (int i = 0; i < RESOURCES; i++) {
        if (request[i] > available[i])
            return false;
    }

    // try to allocate the resources
    for (int i = 0; i < RESOURCES; i++) {
        available[i] -= request[i];
        allocation[process_id][i] += request[i];
        need[process_id][i] -= request[i];
    }

    // check whether the state is still safe
    if (is_safe_state()) {
        return true; // allocation succeeded
    } else {
        // restore the previous state
        for (int i = 0; i < RESOURCES; i++) {
            available[i] += request[i];
            allocation[process_id][i] -= request[i];
            need[process_id][i] += request[i];
        }
        return false; // allocation failed
    }
}

The Resource Allocation Graph Algorithm

Principle: use a directed graph to describe how resources are allocated, and detect whether it contains a cycle.

How the graph is built:

• Nodes: processes and resources
• Edges: allocation and request relationships

Detection algorithm:

bool detect_deadlock() {
    // simplify the resource allocation graph
    while (a_simplifiable_node_exists()) {
        // find a process node that can be simplified
        for (each process node P) {
            if (all_requests_of(P_can_be_satisfied)) {
                // remove all edges of P
                remove_all_edges_from(P);
                // mark P as simplified
                mark_as_simplified(P);
            }
        }
    }

    // check whether any edges remain
    if (graph_has_remaining_edges())
        return true; // a deadlock exists
    else
        return false; // no deadlock exists
}

Deadlock Detection

The Resource Allocation Graph

How the graph is represented:

• Circular nodes: processes
• Square nodes: resources
• Solid arrows: allocation (resource → process)
• Dashed arrows: request (process → resource)

Example:

The Detection Algorithm

Simplification algorithm:

1. Find a process node that has no outgoing request edge
2. Remove all of that node’s allocation edges
3. Repeat steps 1-2 until nothing more can be simplified
4. If edges remain in the graph, a deadlock exists

Implementation:

bool detect_deadlock_using_graph() {
    // build the resource allocation graph
    build_resource_allocation_graph();

    // simplify the graph
    while (true) {
        bool simplified = false;

        // look for a process that can be simplified
        for (each process P) {
            if (P_has_no_request_edge) {
                // remove all allocation edges of P
                remove_allocation_edges(P);
                simplified = true;
            }
        }

        if (!simplified) break;
    }

    // check whether any edges remain
    return has_remaining_edges();
}

When Detection Runs

Detection policies:

1. Periodic detection: check once every so often
2. On-demand detection: check whenever a process requests a resource
3. Exhaustion detection: check when a resource type is used up

Cost of detection:

• Time complexity: O(n²), where n is the number of processes
• Space complexity: O(n×m), where m is the number of resource types

Deadlock Recovery

Process Termination

Strategy: terminate some or all of the deadlocked processes.

Methods:

1. Terminate all deadlocked processes: simple but costly
2. Terminate deadlocked processes one at a time: kill the process with the smallest cost

Selection criteria:

• Process priority
• How long the process has already run
• How much time the process still needs
• How many resources the process uses

Example:

void terminate_deadlocked_processes() {
    // compute the termination cost of every process
    for (each deadlocked process P) {
        cost[P] = calculate_termination_cost(P);
    }

    // terminate the cheapest process each time
    while (a_deadlock_exists()) {
        process = find_minimum_cost_process();
        terminate_process(process);
        release_resources(process);
    }
}

Resource Preemption

Strategy: preempt resources from some processes and give them to others.

Methods:

1. Choose a victim process: pick the process with the smallest cost
2. Roll back to a safe state: roll the process back to a checkpoint
3. Reallocate the resources: give the preempted resources to other processes

Rollback mechanism:

void resource_preemption() {
    // choose a victim process
    victim = select_victim_process();

    // roll back to the checkpoint
    rollback_to_checkpoint(victim);

    // release the resources
    release_resources(victim);

    // redistribute the resources
    redistribute_resources();
}

Checkpointing

Principle: save the state of processes periodically, so that a deadlocked process can be rolled back.

Implementation:

// Save a checkpoint
void save_checkpoint(int process_id) {
    checkpoint[process_id] = {
        .registers = get_process_registers(process_id),
        .memory = get_process_memory(process_id),
        .resources = get_process_resources(process_id)
    };
}

// Roll back to a checkpoint
void rollback_to_checkpoint(int process_id) {
    restore_process_state(process_id, checkpoint[process_id]);
}

Comparing Deadlock Handling Strategies

Choosing a Strategy

Real-World Use

Choices made by operating systems:

• Windows: relies mainly on deadlock detection and recovery
• Linux: relies mainly on deadlock prevention and avoidance
• Real-time systems: rely mainly on deadlock prevention

Factors to consider:

1. Type of system: real-time, time-sharing, or batch
2. Nature of the resources: how many there are, what types, and how they are allocated
3. Performance requirements: response time, throughput, resource utilization
4. Reliability requirements: stability of the system and its ability to recover from failures

Deadlock Case Studies

Case 1: The Dining Philosophers Problem

Problem:

• 5 philosophers sit around a round table
• Each philosopher needs two chopsticks to eat
• The chopsticks lie between the philosophers

How the deadlock happens:

All philosophers pick up their left chopstick at the same time
Then they wait for the right chopstick
A circular wait forms

Solution:

// Use ordered resource allocation
void philosopher(int i) {
    int left = i;
    int right = (i + 1) % 5;

    // always request the lower-numbered chopstick first
    if (left < right) {
        acquire_chopstick(left);
        acquire_chopstick(right);
    } else {
        acquire_chopstick(right);
        acquire_chopstick(left);
    }

    eat();

    release_chopstick(left);
    release_chopstick(right);
}

Case 2: Database Deadlock

Problem:

• Transaction A holds lock L1 and requests lock L2
• Transaction B holds lock L2 and requests lock L1

Solution:

-- Use a timeout mechanism
SET LOCK_TIMEOUT 5000; -- 5 second timeout

-- Use deadlock detection
SET DEADLOCK_PRIORITY LOW; -- set the deadlock priority

-- Use ordered resource allocation
-- Always request locks in a fixed order
BEGIN TRANSACTION;
    UPDATE table1 SET column1 = value1 WHERE id = 1;
    UPDATE table2 SET column2 = value2 WHERE id = 1;
COMMIT;

---

Glossary