Deadlock in Operating Systems: Four Conditions and Worked Resource-Allocation Graphs

A resource-allocation graph records which process holds each resource and which resource it requests. The decisive detail is the number of instances: a cycle proves deadlock for single-instance resource types, but may permit progress when a resource type has multiple instances. A three-process trace reaches permanent waiting; a multiple-instance trace finds a first finisher and completes. Deadlock in Operating Systems: Four Conditions, Banker's Algorithm, and Worked Examples connects Coffman conditions to prevention, avoidance, detection, recovery and Banker's algorithm; resource-allocation graph decisions instead turn on assignment edges, request edges, instance counts, and the first process able to finish.

Deadlock basics: processes, resources and permanent waiting

A deadlock is a state in which every process in a set waits for an event that only another process in that set can cause, usually the release of a held resource. Resources normally follow a request, use, release lifecycle. Here, no process can reach release.

A resource type is not the same as an instance. A printer may have one, while a connection pool has several.

Deadlock also differs from two similar ideas:

• In starvation, one process stays postponed while other processes continue completing.

• In livelock, processes keep changing state but make no useful progress.

In the running example, all three processes are blocked, so none can release what another needs. Assume R1, R2 and R3 are non-shareable single-instance resources, released only after completion, with no forced removal.

The four Coffman conditions and what each one says

All four Coffman conditions must hold simultaneously:

1. Mutual exclusion: at least one relevant resource cannot be used concurrently.

2. Hold and wait: a process holds at least one resource while waiting for another.

3. No preemption: the system cannot seize an allocated resource.

4. Circular wait: a closed chain exists in which each process waits for a resource held by the next process.

Attach them to one state. P1 holds R1 and requests R2. P2 holds R2 and requests R3. P3 holds R3 and requests R1. Therefore, Available = (R1=0, R2=0, R3=0).

Each type has one non-shareable instance, every process holds and waits, and allocated resources cannot be seized. The circular chain is P1 -> P2 -> P3 -> P1.

Three conditions do not establish deadlock. With one instance of every resource type, a cycle is sufficient. With multiple instances, a cycle is necessary but may not be sufficient.

Read a resource-allocation graph without reversing arrows

A process is drawn as a circle. A resource type is a square, and each dot inside that square represents one instance. Edge direction carries the meaning:

• Pi -> Rj is a request edge. Process Pi wants Rj.

• Rj -> Pi is an assignment edge. Process Pi holds an instance of Rj.

For the running state, the resource graph cycle is R1 -> P1 -> R2 -> P2 -> R3 -> P3 -> R1. Remove the single-instance resource nodes and it becomes the wait-for cycle P1 -> P2 -> P3 -> P1. Never use the shortcut that every graph cycle means deadlock.

Worked deadlock example: prove that no process can move

Write the state before concluding:

The total vector is (1,1,1), allocated is (1,1,1), and available is (0,0,0). Conservation checks out:

Total = Allocated + Available = (1,1,1) + (0,0,0) = (1,1,1).

Test for a first finisher. P1 cannot receive R2 because P2 holds it. P2 cannot receive R3 because P3 holds it. P3 cannot receive R1 because P1 holds it. Nobody can finish first or release anything. The state has all four conditions and is deadlocked.

For contrast, suppose P3 released R3 before requesting R1. Then P2 could acquire R3, finish and release R2; P1 could then finish. The original rules prohibit this early release, so they preserve the deadlock.

A cycle without deadlock: the multiple-instance counterexample

Change the inventory to Total = (A=2, B=1). Let P1 hold one A and request B. Let P2 hold B and request one A. Let P3 hold the other A, request nothing, and be ready to finish. Initially, Allocated = (2,1) and Available = (0,0). The graph contains the cycle P1 -> B -> P2 -> A -> P1.

The completion trace shows why that cycle is not proof:

1. P3 finishes and releases one A: (0,0) -> (1,0).

2. Give that A to P2: (1,0) -> (0,0). P2 finishes and releases one A plus one B: (0,0) -> (1,1).

3. Give B to P1: (1,1) -> (1,0). P1 finishes and releases one A plus one B: (1,0) -> (2,1).

The order is <P3, P2, P1>, so the state is not deadlocked. A runnable process outside the cycle holds a second A instance and can release it. This is a direct completion trace, not a Banker's-algorithm result.

Deadlock traps: conditions, cycles and terminology

Three wrong inferences cause mistakes:

• Reversed arrows: reading process -> resource as an allocation. Correct it to “wants”; resource -> process means “holds”.

• One blocked process means deadlock: another process may finish and release a useful instance. Search for a first finisher.

• Every cycle means deadlock: for multiple-instance resource types, perform a completion trace.

Mutual exclusion does not mean processes cannot run together. It concerns a non-shareable resource. No preemption concerns taking an allocated resource, not CPU scheduling preemption. Hold and wait means holding something while waiting, not merely having an outstanding request.

A self-contained single-instance cycle is sufficient even if unrelated processes elsewhere can run, because the processes on the cycle remain stuck. No cycle rules out deadlock, regardless of resource multiplicity.

How objective questions test deadlock reasoning

Common questions ask which condition a policy breaks, how graph edges work, whether a cycle proves deadlock, who can finish first, or how deadlock differs from starvation and livelock.

Use these quick checks:

1. The three-process state has all four conditions and is deadlocked.

2. Its wait-for cycle is P1 -> P2 -> P3 -> P1.

3. The two-resource state contains a cycle but completes as <P3, P2, P1>.

4. If P3 in the second state waits for B instead of being runnable, the old first finisher disappears. Analyse the changed state afresh.

Practise the same distinctions under time pressure with the GATE Test Series. The GATE CS Exam Preparation page is the broader catalogue route.

The short version and the next step

Reconstruct any deadlock problem in five moves:

1. Define the waiting set.

2. Write every hold and request.

3. Test all four necessary conditions.

4. Draw each arrow in the correct direction.

5. Apply the cycle rule for the actual number of resource instances.

Remember the anchors (1,1,1), Available=(0,0,0), P1 -> P2 -> P3 -> P1, and the contrasting successful order <P3, P2, P1>.

Now self-test by adding a second R2 instance to the first example and leaving it available. Total becomes (1,2,1) and available becomes (0,1,0). Grant R2 to P1, which finishes and releases R1 and R2, producing (1,1,0). Next, P3 acquires R1, finishes and releases R1 and R3, producing (1,1,1). Finally, P2 acquires R3, finishes and restores (1,2,1). The order <P1, P3, P2> proves that the old cycle is no longer sufficient.

Continue with Banker's Algorithm for GATE for safe-state calculations. If you prefer a structured route through Operating Systems and the wider curriculum, GATE Guidance by Sanchit Sir is an optional next step.