Minimum number of processes for the deadlock?

Question

A system has 6 identical resources and $N$ processes competing for them. Each process can request at most two requests. Which one of the following values of $N$ could lead to a deadlock?

1. 1
2. 2
3. 3
4. 4

---

My attempt:

Deadlock free condition is:

$R \geq P(N-1)+1 ,$

Where R is total number of resources,

P is the number of processes, and

N is the max need of resources by each process.

$6 \geq P(2-1) + 1$

$6 \geq P + 1$

$5 \geq P$

So, the number of processes should be less than $5$ for the deadlock free condition.

Hence, all options can not be deadlocked.

---

In this exercise problem the answer given option (4).

Can you explain it in a formal way, please?

Answer 1

I agree that no deadlock is possible here. If there are three or fewer processes, there clearly cannot be a deadlock because there are enough resources for every process to just hold two resources the whole time.

So any deadlock must have at least four participating processes. To participate in a deadlock, a process must hold at least one resource. Further, a process cannot hold more than two resources so a process that currently has two resources can definitely run until it frees at least one of those resources. Therefore, if there is a deadlock, it must involve four processes, each holding exactly one resource. This means that there are two resources free so any process that requests a resource will be granted it and will then run until it releases one or both of the resources it holds. Out of our set of four supposedly deadlocked processes, at least one is always runnable, so there is no deadlock. (In fact, at least two are runnable at all times.)

Perhaps the question-setter had the following situation in mind. Suppose processes 1 and 2 are using two resources each and processes 3 and 4 are using one resource each. Now, if 3 and 4 each request one more resource, they will block. But this is not deadlock because the situation can be resolved by either one of the two runnable processes (1 and 2) giving up one of their resources. Deadlock is the situation where every one of a set of processes is blocked and the only way to resolve the situation is for one of those blocked processes to give up resources, which it can't do because it's blocked.

Answer 2

I would think that even with 5 processes, deadlock isn't possible. If 5 processes each need up to 2 of six identical resources, we could assume that each acquires one resources, and then we have 5 processes with a single resource left. Sure, four processes may have to wait when one process acquired the last resource, but eventually that process will free a resource, and things progress. No deadlock. (The OP's formula tells the exact same story, just for a more general case).