0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

I don’t see your problem with the other cases: if one thread deadlocks itself, you have a deadlock, no matter how many other threads and locks you have.

$\endgroup$
5
  • $\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 May 7 '20 at 12:33
  • $\begingroup$ can you please solve my above query?? @gnasher729 $\endgroup$ – mb14 May 9 '20 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 May 9 '20 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 May 11 '20 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 May 11 '20 at 6:20

Your Answer

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

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