edited by
32,869 views
122 votes
122 votes

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$
edited by

7 Answers

Best answer
78 votes
78 votes

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

edited by
32 votes
32 votes

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.

1 votes
1 votes

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)

edited by
0 votes
0 votes
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...
Answer:

Related questions

24 votes
24 votes
3 answers
2
48 votes
48 votes
7 answers
3
Arjun asked Feb 14, 2017
16,774 views
Threads of a process shareglobal variables but not heapheap but not global variablesneither global variables nor heapboth heap and global variables