Four Coffman Conditions & Resource Allocation Graphs (RAG)

Explanation

Coffman conditions form the theoretical basis of all deadlock prevention strategies. Total ordering of resources prevents Circular Wait.

Key points

• Breaking any single condition mathematically guarantees deadlock cannot occur
• Resource Allocation Graph (RAG): P -> R is Request edge, R -> P is Assignment edge
• Single instance with cycle = Deadlock; Multi-instance with cycle = Deadlock is possible but not guaranteed

Example

Code examples

// Detection of Circular Wait in Single-Instance Resource Allocation (Cycle Finding)
bool hasDeadlockCycle(int u, vector<bool>& visited, vector<bool>& recStack, const vector<vector<int>>& adj) {
    visited[u] = true;
    recStack[u] = true;
    for (int v : adj[u]) {
        if (!visited[v] && hasDeadlockCycle(v, visited, recStack, adj)) return true;
        else if (recStack[v]) return true; // Cycle detected = Deadlock
    }
    recStack[u] = false;
    return false;
}

Exam questions

• State and explain the four Coffman conditions necessary for deadlock to occur.
• Draw a Resource Allocation Graph showing a deadlock condition and prove how breaking circular wait prevents it.