GATE CSE 2017 Set 1 | Question: 27 with modification

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 lGATE2017-1-27 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

If non- re entrant was not part of question then it would be OPTION - C?

Comments

I dont think the re entrant condition is going to play any role here.
Answer should be C.
Lets say the thread 1 acquires lock on L1.
Thread 2 acquires a lock on L2.
Now let say thread1 wants a lock on L2 and thread2 wants a lock on L1.
Both of the threads will be blocked and wont be able to proceed.
Hence a deadlock.

Answer 1

For the non re-entrant condition mentioned, the answer should be option C.

If the thread has to acquire the lock → work on critical section → release lock, then a single thread cannot create deadlock, so x should be 2.

coming to y, if y is 1, then the circular dependency is not happening i.e say the threads are T1 and T2

and the lock be l1.

Say T1 acquires l1 i.e T1 → l1. But T1 would enter critical section and thus one of T1 and T2 is not locked thus deadlock is not happening.

Taking y to be 2

Say T1 → l1 and T2 → l2. Now both T1 and T2 are in a deadlock trying to acquire l2 and l1 respectively.

 

Now for the interesting case of re-entrant code i.e where the thread can leave critical section without releasing the lock and try to aquire again, then both x and y can be 1, since T1 would try to aquire l1 two times, with the first time being a success the second time would definitely be a failure as the lock has not been released.