GATE CSE 2017 Set 1 | Question: 27

Question

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$

Comments

A REENTRANT LOCK IS ONE WHERE A PROCESS CAN CLAIM THE LOCK MULTIPLE TIMES WITHOUT BLOCKING ON ITSELF. IT'S USEFUL IN SITUATIONS WHERE IT'S NOT EASY TO KEEP TRACK OF WHETHER YOU'VE ALREADY GRABBED A LOCK. IF A LOCK IS NON RE-ENTRANT YOU COULD GRAB THE LOCK, THEN BLOCK WHEN YOU GO TO GRAB IT AGAIN, EFFECTIVELY DEADLOCKING YOUR OWN PROCESS.

 

 

explains clearly

---

A very ambiguous question. Thank you @Bikram Sir for the detailed explaination :)

---

so As per my level of understanding in this
as option A ,single process can go to CS atmost 2 times,
as opt B both process can go to CS one time, one after other.
as opt C, both process can go to CS 2 times, simultaneously also possible by taking different locks
as opt D, 1 process can go to CS only for 1 time

Am I right @Deepak Poonia @Sachin Mittal 1 @Arjun sir?

Answer 1

suppose

I. p(y)

II. p(y)

cs

III. v(y)

IV. v(y)

in this case if we execute step number I then only after executing V(y) we can perform step II, else this will lead to dead lock.

Answer 2

I guess than by the same logic all binary semaphores are non-reentrant by default. so a system with single process that requires only one binary semaphore can be deadlocked. Is my interpretation right ? please  comment. thanks.

Answer 3

Answer is option C. How can a single thread cause a deadlock? It just violate the necessary conditions for a deadlock.

For reference check Q47 of the link below:

http://gfweb.s3.amazonaws.com/gatepapers/GATE2017/CS-GATE%272017-Paper-01-key-solution.pdf