Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Deadlocks: conditions, prevention and avoidance

Deadlocks occur when processes wait forever for resources; engineers must detect, prevent, or avoid them to keep systems correct and available.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

Deadlocks stop progress: several processes each hold some resources and wait for others forever. An engineer uses deadlock theory when designing concurrent programs, OS resource managers, databases and embedded systems to ensure liveness (no infinite waits), safety (no corrupted resources) and predictable response.

Key ideas

Start from first principles and simple definitions.

  • Process: an executing program instance that can request and hold resources. (Used throughout.)
  • Resource: any entity (CPU, printer, file, lock, memory) that processes can request and hold.
  • Allocation: the action of giving a resource instance to a process.
  • Request: a process asking for a resource instance.
  • Deadlock: a situation where a set of two or more processes are each waiting for resources held by others, and none can proceed. Exact exam form: "A system is in deadlock if there exists a set of processes such that every process in the set is waiting for an event that can be caused only by another process in the set."

Coffman conditions (necessary for deadlock). State them exactly as a theorem-style list (these are necessary, not sufficient by themselves to guarantee deadlock):

  1. Mutual exclusion — at least one resource must be held in a non-shareable mode; only one process can use the resource at a time.
  2. Hold-and-wait — a process holds at least one resource and is waiting to acquire additional resources held by other processes.
  3. No preemption — resources cannot be forcibly taken from a process; they are released only voluntarily by the holding process.
  4. Circular wait — there exists a set {P0, P1, ..., Pn} of processes such that P0 is waiting for a resource held by P1, P1 waits for a resource held by P2, ..., Pn waits for a resource held by P0.

All four conditions are necessary for deadlock; their simultaneous presence makes deadlock possible but not inevitable. In exams, you may be asked to explain how breaking any one of these prevents deadlock.

Resource-allocation graph (RAG) — how to draw and use it:

  • Draw a directed bipartite graph with process nodes as circles labeled P0, P1, ... and resource nodes as squares labeled R0, R1, ...
  • For each request by process Pi for resource Rj draw an arrow Pi → Rj (request edge).
  • For each allocation of an instance of resource Rj to Pi draw an arrow Rj → Pi (assignment edge).
  • If resources are single-instance: A cycle in the RAG is necessary and sufficient for deadlock. Describe on the answer: draw a small example of two processes and two resources forming a cycle (P0 → R0 → P1 → R1 → P0) and label arrows as request/assignment.
  • If resources have multiple instances: a cycle is necessary but not sufficient. Explain by showing that with multiple instances a cycle may still be resolvable if there is an available free instance.

Deadlock prevention — break a Coffman condition. Give exact methods and assumptions:

  • Prevent mutual exclusion: make resource sharable when possible (not always possible: e.g., printers typically exclusive).
  • Prevent hold-and-wait: require processes to request all resources at once, or require them to release all held resources before requesting new ones. Assumption: processes can predict future needs (often unrealistic).
  • Prevent no preemption: allow the system to preempt resources — take resources away and give them to others, possibly rolling back processes. Assumption: resources can be safely preempted or state can be rolled back.
  • Prevent circular wait: impose a global ordering of resource types and require each process to request resources in increasing order. Diagram to draw: list resources R1 < R2 < R3; show two processes acquiring in order to illustrate circular wait impossible.

Deadlock avoidance — dynamic checks to ensure safe states.

  • Safe state: a state is safe if there exists a sequence of all processes P1..Pn such that for each Pi, the resources that Pi still needs can be satisfied by currently available resources plus resources held by all Pj with j < i (which can finish and release their resources). If system can find such sequence, no deadlock will occur if processes continue as specified.
  • Banker's algorithm (for single-unit or multiple-unit resources): treat each resource allocation as a loan; before granting a request, simulate granting it and check whether resulting state is safe. If safe, grant; otherwise deny (or block) the request. Resource-request algorithm (for a request vector Request[i] from process i):
    • If Request[i] ≤ Need[i] then continue; otherwise error (the process has exceeded its declared maximum).
    • If Request[i] ≤ Available then pretend to allocate: Available = Available − Request[i]; Allocation[i] = Allocation[i] + Request[i]; Need[i] = Need[i] − Request[i]; run the safety algorithm; if the state is safe, grant the request; otherwise roll back the pretend allocation and make i wait.
    • If Request[i] > Available then make i wait (do not allocate).
  • State the safety algorithm steps exactly (assumptions: finite resources, known maximum demands):
    1. Initialize: Work = Available (vector); for all processes i, set Finish[i] = false.
    2. Find an i such that Finish[i] == false and Need[i] ≤ Work (vector-wise). If none found, go to step 4.
    3. Work = Work + Allocation[i]; Finish[i] = true; go to step 2.
    4. If Finish[i] == true for all i then the state is safe; otherwise unsafe.

Assumptions behind Banker's: maximum resource needs of each process are declared in advance; resources are reusable; number of processes and resource instances finite.

When to use each approach: Prevention is static and conservative (may reduce concurrency), avoidance (like Banker) needs prior knowledge and runtime checks, detection with recovery accepts deadlock may happen and then recovers using process termination or preemption.

Formulas

Need[i, j] = Max[i, j] − Allocation[i, j] — Need of process i for resource type j (units: resource instances). Applies in Banker's algorithm. Work = Available — initialize work vector for safety check (units: resource instances). If Need[i] ≤ Work then Work = Work + Allocation[i] — safety step: all vectors compared component-wise; units: resource instances. Safe state ⇔ ∃ ordering Pk1, Pk2, ..., Pkn such that for each t, Need[k t] ≤ Available + Σ_{r < t} Allocation[k r] — formal condition (component-wise inequality).

Worked examples

  1. Banker's algorithm — safety check (numerical): Given resource types A(10), B(5), C(7) — total instances. Processes P0..P4 with matrices: Max: P0: (7,5,3) P1: (3,2,2) P2: (9,0,2) P3: (2,2,2) P4: (4,3,3) Allocation: P0: (0,1,0) P1: (2,0,0) P2: (3,0,2) P3: (2,1,1) P4: (0,0,2) Compute Available = Total − Σ Allocation.

Allocation sums: A: 0+2+3+2+0 = 7; B:1+0+0+1+0 = 2; C:0+0+2+1+2 =5. Available = (10,5,7) − (7,2,5) = (3,3,2). Need = Max − Allocation: P0: (7,5,3) − (0,1,0) = (7,4,3) P1: (3,2,2) − (2,0,0) = (1,2,2) P2: (9,0,2) − (3,0,2) = (6,0,0) P3: (2,2,2) − (2,1,1) = (0,1,1) P4: (4,3,3) − (0,0,2) = (4,3,1) Safety test steps: Work = (3,3,2). Find process with Need ≤ Work: P1 Need (1,2,2) ≤ (3,3,2) yes. Work = Work + Allocation[P1] = (3,3,2) + (2,0,0) = (5,3,2). Next find Need ≤ Work: P3 Need (0,1,1) ≤ (5,3,2) yes. Work = (5,3,2) + (2,1,1) = (7,4,3). Next P0 Need (7,4,3) ≤ (7,4,3) yes. Work = (7,4,3) + (0,1,0) = (7,5,3). Next P4 Need (4,3,1) ≤ (7,5,3) yes. Work = (7,5,3) + (0,0,2) = (7,5,5). Next P2 Need (6,0,0) ≤ (7,5,5) yes. All Finish true → state safe. Final answer: state is safe and one safe sequence is P1, P3, P0, P4, P2.

  1. Resource-allocation graph diagram answer (theory question): Model answer: Draw two process circles P0, P1 and two resource squares R0, R1. Show R0 → P0 (R0 allocated to P0), P0 → R1 (P0 requests R1), R1 → P1, P1 → R0. Label arrows as "assignment" (R → P) and "request" (P → R). Conclude: This RAG has a cycle so with single-instance resources a deadlock exists involving P0 and P1.

  2. Deadlock prevention by ordering (short model answer): Explain impose total order R1 < R2 < R3. Show a table of two processes acquiring R1 then R2; since all request in increasing order, a circular wait cannot form. Conclude prevention of circular wait.

Common mistakes

  • In Banker's algorithm forgetting to compare Need ≤ Work component-wise, or updating Work with Allocation only after selecting a safe process.
  • Using inconsistent totals or miscomputing Available (double-check sums).
  • Thinking prevention methods are always practical; e.g., requiring all resources at once hurts concurrency.

For your exam

Question types you will see: definitions (define deadlock, safe state), short notes (Coffman conditions, prevention methods), derivations (prove cycle ⇔ deadlock for single-instance RAG), numericals (Banker's algorithm safety check with matrices), diagram tasks (draw RAG and identify cycles), and compare-and-contrast (prevention vs avoidance vs detection and recovery). A full-marks answer includes: clear definitions with bold named terms, assumptions stated, step-by-step algorithms with variable names and vectors, and labelled diagrams when required. For numerical Banker's answers show matrices: Max, Allocation, Need, Available, Work steps and the safe sequence.

Quick check

  1. Name the four Coffman conditions.
  2. In a resource-allocation graph with single-instance resources, what does a cycle mean?
  3. In the Banker's algorithm, what vector is initialized to Available and then updated during the safety check? Answers: 1) Mutual exclusion, Hold-and-wait, No preemption, Circular wait. 2) A cycle is necessary and sufficient for deadlock (so deadlock exists). 3) The Work vector (Work = Available).

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?