I was reading deadlock topic from Operating Systems book by Stallings. It states four pre requisites for deadlock:

  1. Mutual exclusion
  2. No preemption
  3. Hold and wait
  4. Circular wait

It then have following sentences scattered in the topic at difference places:

  1. the four conditions, taken together, constitute necessary and sufficient conditions for deadlock
  2. first three are necessary conditions for deadlock
  3. all four conditions listed above are sufficient for deadlock

Then I came across following question:

Which of the following are sufficient conditions for deadlock?
I. Mutual exclusion
II. Hold and wait
III. No preemption IV. Circular Wait
A. I and II
B. I and III
C. IV only
D. I, II and III

I got confused whats the correct answer. I feel all are necessary, but fourth one is the only sufficient one, or I should say fourth one is self sufficient. None of first three can be considered as sufficient. So I felt option C is correct.

But I still felt fuzzy. So I googled about "necessity vs sufficiency" and I found below:

  1. From here:

    A necessary condition must be there, but it alone does not provide sufficient cause for the occurrence of the event. Only the sufficient grounds can do this. In other words, all of the necessary elements must be there.

    (a) Does this suggest that all conditions together will be called as "sufficient", not just circular wait?
    (b) Does this mean that, alaways: $$\text{set of necessary items} \subseteq \text{set of sufficient items}$$

  2. But then wikipedia says:

    • A condition can be either necessary or sufficient without being the other.
    • A condition can be both necessary and sufficient.

    If these points are true then 1(b) above is false.

Can someone please clarify relation between necessity and sufficiency? Also can anybody tell what is/are sufficient condition(s) for deadlock?


Wikipedia also says, if $S \rightarrow N$, then $S$ is sufficient and $N$ is necessary. (Source: https://en.wikipedia.org/wiki/Necessity_and_sufficiency) Here, we have,

$CW \rightarrow HW, MX, NP$

$CW$: circular wait,
$HW$: hold and wait,
$MX$: mutual exclusion,
$NP$: no preemption

So, I believe $CW$ is sufficient and $\{HW, MX, NP\}$ are necessary.

  • $\begingroup$ A is necessary for B if when B happens, also A happens. C is sufficient for D if when C happens, also D happens. $\endgroup$ – Yuval Filmus Jul 24 '19 at 16:46
  • $\begingroup$ Yes I read that. I have added an update to the bottom of question based on this understanding. Is that right? $\endgroup$ – anir Jul 24 '19 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.