Proving Deadlock Freedom with Four Identical Resources and Three Processes

Consider a system with:

• Four identical resource instances: $R = 4$
• Three processes: $P_1, P_2, P_3$
• Each process requires at most two resource instances to complete: $K = 2$

Assume resources are allocated one at a time, a process keeps any resources already allocated to it, and it releases all resources after completing. A deadlock requires processes to remain permanently unable to obtain the resources they need. Classical deadlock analysis identifies mutual exclusion, hold-and-wait, no preemption, and circular wait as necessary conditions.

The goal is to show that no possible allocation state can produce deadlock.

Footnotes

1. Operating Systems: Deadlocks - Defines the four necessary conditions for deadlock and explains resource-allocation concepts. ↩

1. The Key Counting Argument

A deadlock could occur only if every process were waiting for one additional resource while already holding one. Since each process needs at most two resources, the most dangerous configuration is:

The three processes collectively hold only three resources. Because the system contains four resources,

$$4 - 3 = 1$$

resource remains available.

Thus, at least one process can receive its remaining resource. It then holds two resources, reaches its maximum requirement, completes, and releases both resources. The released resources allow the remaining processes to complete in turn.

A safe state is therefore guaranteed.

2. Visualizing the Worst Case

The apparent worst case is that all three processes hold one resource and wait for one more. However, that state consumes only three of the four resources. The fourth resource breaks the potential waiting cycle.

A resource instance is interchangeable with every other instance, so no process needs a particular physical resource.

3. Why the Contradiction Works

The contradiction depends on the maximum requirement of two resources.

If all three processes are waiting, each must already hold one resource. That uses:

$$3 \times (2 - 1) = 3$$

resources: one less than the maximum requirement of each process.

The system has one additional resource:

$$4 - 3 = 1$$

That extra resource is enough to satisfy one process's remaining need. Once that process completes, it returns two resources, making completion of the others even easier.

The general sufficient condition for $n$ processes, each requiring at most $k$ identical resources, is:

$$R \geq n(k-1)+1$$

where:

• $R$ is the number of resource instances,
• $n$ is the number of processes,
• $k$ is the maximum number of resources needed by any process.

For this problem:

$$R \geq 3(2-1)+1$$ $$R \geq 4$$

The system has exactly four resources, so it satisfies the condition.

Footnotes

1. Lec27 Deadlock | GATE Question Previous Year - Presents the identical-resource deadlock-free condition in the form $R \geq \sum_i (A_i-1)+1$. ↩

4. The General Theorem

Theorem

If a system has $n$ processes, each requiring at most $k$ instances of one identical resource type, then the system is deadlock-free whenever:

$$R \geq n(k-1)+1$$

Proof

Assume the system has fewer than $n(k-1)+1$ resources. In the worst case, every process holds $k-1$ resources and waits for one more. The total number of resources held is:

$$n(k-1)$$

If only $n(k-1)$ resources are available, every resource may be allocated while every process still needs one additional resource. No process can complete, so deadlock is possible.

Now suppose instead that:

$$R \geq n(k-1)+1$$

Even if every process holds $k-1$ resources, at most $n(k-1)$ resources are occupied. Therefore, at least one resource remains free:

$$R-n(k-1)\geq 1$$

That resource completes the remaining requirement of one process. The process finishes and releases all its resources. The argument can then be repeated for every remaining process. Hence, deadlock cannot occur.

Footnotes

1. Deadlock Avoidance in OS - Illustrates the resource-counting argument and the boundary between deadlock-free and potentially deadlocked allocations. ↩

5. Banker-Style Safety Interpretation

The same result can be expressed using the idea of a safe sequence.

Suppose the current allocation is the worst possible deadlock candidate:

The available vector contains one unit because:

$$\text{Available}=4-(1+1+1)=1$$

Since each process has remaining need $1$, any process can finish first. Choose $P_1$:

1. Allocate the available resource to $P_1$.
2. $P_1$ now holds two resources and completes.
3. $P_1$ releases two resources.
4. Available resources become:

$$1-1+2=2$$

Now either $P_2$ or $P_3$ can finish. For example:

$$\langle P_1,P_2,P_3\rangle$$

is a safe sequence. The existence of such a sequence proves that the state is safe.

Footnotes

1. Chapter 7: Deadlocks - Describes safe states, remaining need, and the existence of a safe completion sequence in Banker-style reasoning. ↩

6. Why Three Resources Would Not Be Enough

The result is tight. If the system had only three resources, the following allocation would be possible:

Every process holds one resource and waits for a second. No resource is available, so no process can reach its maximum requirement or release its held resource.

Thus, with three resources, deadlock is possible. The fourth resource is not merely convenient; it is exactly the additional resource required by the theorem:

$$n(k-1)+1=3(2-1)+1=4$$

7. Final Conclusion

The system is deadlock-free because:

1. A deadlocked process must hold at least one resource.
2. Since each process needs at most two resources, a process that is still waiting can hold at most one resource.
3. Three processes can therefore hold at most three resources while all remain incomplete.
4. The fourth resource is necessarily available.
5. That resource lets one process obtain its second resource and complete.
6. The completed process releases two resources.
7. The same reasoning applies repeatedly to the remaining processes.

Therefore:

$$\boxed{\text{Four identical resources and three processes with maximum demand two are deadlock-free.}}$$