25,339 views

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:

1. $x = 1, y = 2$
2. $x = 2, y = 1$
3. $x = 2, y = 2$
4. $x = 1, y = 1$

@prateekbeh We are assuming that if thread "tries" to acquire the same lock again already owned by it, due to non-reentrant lock,it will get Blocked leading to Deadlock.

....
Wait(S)
// Some code
Wait(S)       ---- Thread will get blocked here forever.
//Some code
......

Signal(S)

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
edited
A very ambiguous question. Thank you @Bikram Sir for the detailed explaination :)

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.

Thank you sir, got it
edited
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?

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.

by

Consider two conditions , ......

Gate Fever, flash12

Yes, for a single process ( X=1 ) Circular wait condition is not hold so deadlock can not occur. But , this question have other conditions , like : These are three key conditions : Minimum number of thread and lock All locks in the program are Non-reentrant . ( key Point ) " If a thread is unable to acquire a lock, it blocks until the lock becomes available."

Means thread gets block if another lock is unavailable . Re entrant means it can again acquire a lock but question says about Non re entrant , non re-entrant process cant own same lock multiple times, so if process tries to acquire already owned lock, will get blocked , and deadlock will happen.

Also, Question asked for minimum value of X and Y require, so if a single thread with a single lock can not acquire any other locks other than the lock which it already acquire , this situation leads to deadlock ( as in the question it says If a thread is unable to acquire a lock, it blocks until the lock becomes available. )

so for X=1 ( a single thread ) and Y=1 ( a single lock ) deadlock is possible when we consider given situations in question.

The main point is : With 1 thread and 1 lock , a thread after acquire a lock enter into it's critical section then come out of CS, again looking for another lock but due to a single lock available, that thread acquire that same lock again and again and get blocked .

Hope you get it now !!
if it was a simple kind of lock then the answer would have have 2,2 , right?

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. )

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)

by

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
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...

edited by

@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