Why are the Coffman conditions necessary for a deadlock to occur?

Question

Quoting https://en.wikipedia.org/wiki/Deadlock#Necessary_conditions :

A deadlock situation can arise if all of the following conditions hold simultaneously in a system:

1. Mutual exclusion: at least one resource must be held in a non-shareable mode.Only one process can use the resource at any given instant of time.
2. Hold and wait or resource holding: a process is currently holding at least one resource and requesting additional resources which are being held by other processes.
3. No preemption: a resource can be released only voluntarily by the process holding it.
4. Circular wait: a process must be waiting for a resource which is being held by another process, which in turn is waiting for the first process to release the resource. In general, there is a set of waiting processes, P = {P1, P2, …, PN}, such that P1 is waiting for a resource held by P2, P2 is waiting for a resource held by P3 and so on until PN is waiting for a resource held by P1.

Wikipedia claims these conditions are necessary for a deadlock to occur. In addition, I’ve heard claims they are also sufficient (although I may’ve misinterpreted these claims).

The problem is that I have examples that seem to me to contradict both necessity or sufficiency of those conditions. And I can’t see my error.

Necessity first:
Let R1 and R2 be two resources shareable by two processes at most. Let P1, P2, P3, P4 be processes such as P1 and P2 hold one piece of R1 each and each wait for a piece of R2, and P3 and P4 hold one piece of R2 each and each wait for a piece of R1, as below:

Assume that #3 holds. #2 and #4 are obviously fulfilled, but #1 is not as both R1 and R2 can be shared. Yet a deadlock seems to occur.

Now sufficiency:
Let R1 and R2 be two resources, such as R1 is shareable by two processes at most and R2 is non-shareable. Let P1, P2 and P3 be processes such as P1 holds R2 and wants a piece of R1, R2 holds a piece of R1 and wants R2 and R3 holds a piece of R1 and wants nothing more, as below:

Again, assume #3 holds. Then #1 is fulfilled as R2 is non-shareable, P1 and P2 both fulfil #2 so this condition also holds, and #4 is fulfilled by the cycle formed by P1 and P2. Yet no deadlock occurs, since as soon as P3 finishes its piece of R1 can be granted to P1, whose requirements will be fulfilled by then; so, as soon as P1 releases R2, P2 will be able to proceed.

Where is my error? Where is my misunderstanding?

Answer 1

You've introduced a count restriction on sharing. While this is interesting, it is different from what is normally considered. A shareable resource ought to be shareable by anyone and everyone at the same time.

What #1 says is that one resource must be held in a non-sharable mode. In your example if R1 were truly sharable, there would be no reason that another process couldn't also acquire R1 in a shareable mode (and thus, no deadlock would occur).

What you're doing is introducing a "limited shareable" resource, which initially behaves as a shareable resource, though when the limit is reached then behaves as a non-shareable resource. So, you're playing with the rules (which is fine), but that changes things a bit. We must consider that R1 morphs into a non-shared resource whenever its sharing limit is reached.

---

Think of it this way: shareable mode buys us nothing except a list of current users of a resource. It does not restrict the program in any way.

Shareable use of resources alone is hardly worth considering in the context of deadlocks. What starts to make it interesting is the use of and need for non-shareable modes.

When you're updating a resource, that is best done in a non-shared mode, otherwise you can have race conditions. So, updates put you in a situation where you either have races or potential deadlocks. Races are avoided by non-sharable modes (there are other methods, though more limited). Deadlocks due to non-shared modes can be avoided by following a directed acyclic resource hierarchy, which eliminates the cycles necessary for deadlocks.

Answer 2

The quote you include is a little badly phrased, and this is misleading you. Specifically, paragraph 1 of the quote is a description not of a condition for deadlock occurring, but of an underlying assumption on the kind of system to which the remaining paragraphs apply. Therefore, what we can say is that if #1 is true, then #2, #3 and #4 form a necessary and sufficient set of conditions for deadlock occurring. In situations where #1 is not true (as in the scenarios you describe) different conditions may apply.