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

If we see definition of reentrant Lock :

In computer science, the reentrant mutex (recursive mutex, recursive lock) is particular type of mutual exclusion (mutex) device that may be locked multiple times by the same process/thread, without causing a deadlock.   https://en.wikipedia.org/wiki/Reentrant_mutex

A Re-entrantLock is owned by the thread last successfully locking, but not yet unlocking it. A thread invoking lock will return, successfully acquiring the lock, when the lock is not owned by another thread. The method will return immediately if the current thread already owns the lock https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/locks/ReentrantLock.html

Reentrant property is provided, so that a process who owns a lock, can acquire same lock multiple times. Here it is non-reentrant as given, process cant own same lock multiple times. So if a thread tries to acquire already owned lock, will get blocked, and this is a deadlock.

Here, the answer is (D).

Comments

Thank you sir, got it

---

isn't it necessary for a thread to unlock all the locks it acquired when coming out of critical section to make it a correct implementation of critical section problem?

or by mentioning non reentrant lock are they trying to tell there will be deadlock is a programmer tries to do 2 or more P operations on a binary semaphore without reentrant property?

Here in the question its mentioned that the locks are for shared memory locations and there is no point in having a recursive function calls which will result in acquiring a lock for multiple times. So basically a thread will lock it when its accessing memory location and release the lock when its critical section is done. Can someone explain why the thread is trying to acquire the lock again before finishing its critical section?

---

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 sir?

Answer 2

Here is my thought
 Consider two conditions ,

First one for option C) if there are 2 threads and 2 locks available then one by one each thread acquire a lock , ensure Mutual Exclusion and enter into it's shared memory location  then release it .. and again get another lock in the same manner  , hence deadlock is Not satisfied due to Non-reentrant property !! because it said " if a thread holds a lock , then it cannot re-acquire lock  without  releasing it " .

Now consider again ,

For option D ) if there are only 1 thread and 1 lock is available then a thread after acquire a lock enter into it's critical section then come out of it again looking for another lock but due to a single lock acquire that same lock and get blocked so the possibility of Deadlock is there ..

as in question it is asked for  minimum value .. minimum is X =1 and Y = 1

In Tanenbaum book it is said " Notice that it is possible for a single process to become deadlocked if it is waiting for an event that only it can cause. "...          

    Here X threads waiting for Y locks to ensure mutual exclusion are in deadlock when X =1 and Y = 1 .

Hence Option D is correct.

Comments

if it was a simple kind of lock then the answer would have have 2,2 , right?

---

@Bikram @Arjun The question says:

If a thread is unable to acquire a lock, it blocks until the lock becomes available.

This means even if the single thread tries to re-acquire the lock, it will get blocked, this means no waiting, so how deadlock can even happen as the base of deadlock happening is waiting for a certain thing to happen?

---

@ayush_27 the question has mentioned about non re-entrant lock. Here the thread which has acquired the lock tries to acquire the same lock and since its not possible to acquire the same lock, it goes into a state of deadlock i.e., indefinite waiting

Answer 3

This is my view on the question  -

According to one of the definition in Operating Systems by Galvin

A set of processes is deadlocked when every process in the set is waiting for a resource that is currently allocated to another process in the set ( and which can only be released when that other waiting process makes progress. )

Reference - https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/7_Deadlocks.html

When one thread tries to re-acuquire the same lock which it is currently helding could be best termed as a BUG and not deadlock. The question is ambiguous as it involves the term "dead-lock".  The question was made tricky due to the presence of non-renentrant lock, however the official key did not taken into consideration the definition and appropriate terminology of deadllock. More emphsasis was given on the non-renentrant lock rather than deadlock terminology. I feel answer should be option C)

Comments

the answer is perfect but yes it appeared to be ambiguous and tricky when it was seen in the question paper for the first tym.

---

In Tanenbaum book it is said " Notice that it is possible for a single process to become deadlocked if it is waiting for an event that only it can cause. "...    

@ bikram sir please tell me the page no. I am not able to find this reference in tanenbaum

---

 @sushmita  see this http://hamilton.nuigalway.ie/teaching/AOS/FIVE/deadlock.html

Answer 4

First, you have to know multithreading, mutual exclusion and reentrant mutex. The reentrant mutex (recursive mutex, recursive lock) is a particular type of mutual exclusion (mutex) device that may be locked multiple times by the same process/thread, without causing a deadlock.
Here non-re-entrant process can’t own the same lock multiple times, so if the process tries to acquire the already owned lock, will get blocked, and deadlock will happen.
From the above option, x=1 (a single thread) and y=1 (a single lock) deadlock are possible when we consider given situations in question.

so ans is option d...

Comments

Please don't repeat the answers. If you want to add something (more information), you can comment below the selected answer.

---

@tusharp is it repeated??
i think this is a completely different approach from other and if i comment on the selected answer then it will create conflict bro