A multithreaded program P executes with x number of threads and uses y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-reentrant, i.e., if a thread holds a lock l, then it cannot re-acquire lock l without releasing it. If a thread is unable to acquire a lock, it blocks until the lock becomes available. The minimum value of x and the minimum value of y together for which execution of P can result in a deadlock are:

  • A. x=1,y=2
  • B. x=2,y=1
  • C: x=2,y=2
  • D: x=1,y=1

Though, answer is option D but is there any possibility to have deadlock in other 3 options. If yes, then what it is because not able to visualize other options. Kindly explain.


1 Answer 1


A single thread can get itself deadlocked by locking the same lock twice without an unlock in between. Which is obviously a stupid thing to do.

Why A-C are not solutions: Read the question carefully. It asks for the MINIMUM value of x and y. Since x=1, y=1 can lead to deadlock, the others are not MINIMUM values. Of course you can have a deadlock in every case, but x, y are not minimum values.

  • $\begingroup$ Can option c will lead to deadlock?? Like if P1 holds lock1, then it enter Critical section, then came out and again tried to acquire lock1 but it can't due to non-reentrant lock. So it acquire lock2 and enter the critical section. Again it came out of it and tried to acquire the locks but got blocked due to non-reentrantcy of locks. So, now P2 tried to enter critical section by acquiring lock but it also got blocked because locks were yet not released by P1. Hence these two threads got deadlocked. $\endgroup$
    – mb14
    Commented May 7, 2020 at 12:33
  • $\begingroup$ can you please solve my above query?? @gnasher729 $\endgroup$
    – mb14
    Commented May 9, 2020 at 11:27
  • $\begingroup$ Mb14: Hint: This Problem is very, very, very simple. When you try to acquire a lock, your thread stops if the thread can’t get the lock. No chance to get a second lock, the thread just stopped running. $\endgroup$
    – gnasher729
    Commented May 9, 2020 at 20:58
  • $\begingroup$ Thanks for your help. But can you tell that how Option c won't lead to deadlock. I mean how processes will work according to option C without any deadlock. And what is wrong in my approach about option c mentioned above. Due to minimum condition answer is option D but I want to know about option C also. @gnasher729 $\endgroup$
    – mb14
    Commented May 11, 2020 at 6:03
  • $\begingroup$ As you have mentioned in your answer that "if one thread deadlock itself you have a deadlock no matter how many other threads you have". But in deadlock every thread in the system should get block not only one thread. If one thread gets block and others are working then system will not be in deadlock. $\endgroup$
    – mb14
    Commented May 11, 2020 at 6:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.