GATE - 2017 | OS | A multithreaded program P executes with x number of threads and used

GATE - 2017 [Operating System]

Question:

A multithreaded program P executes with x number of threads and used 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

     

Solution:

Correct Option is (D)

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 options, x=1 (a single thread) and y=1 (a single lock) deadlock are possible when we consider given situations in question.

------------------------------------------

Concept:

Re-entrant locks: It allows a thread to reacquire the lock multiple times without blocking on itself. It prevents the thread from the situation of deadlock.

Non- re-entrant locks: It doesn’t allow a thread to re-acquire the lock. The same process cannot acquire the lock multiple times without releasing it. So, here situation of deadlock occurs.

Explanation:

Three key points to be considered for this:

• It is asking about the minimum value of x and y
• Locks are non-re-entrant (recursive)
• Programs get blocked if another lock is unavailable

Now, the question is asking about the minimum value of x and y for which execution of p can result in a deadlock. So, the minimum value of x and y are 1 and 1. Only one thread and one lock can cause deadlock if the thread tries to reacquire the lock. If there is more than one lock available in the system, then the process/thread can acquire the lock to do further execution.

----------------------------------------------

 

Reentrant (Recursive) locks allow a thread to reacquire the lock. That means the same process can claim the lock multiple times without blocking on itself. This prevents the thread from deadlocking itself. This is the main advantage of reentrant locks over non-reentrant locks.

Non-reentrant (Non- recursive) locks do not allow a thread to reacquire the lock. That means the same process can not claim the lock multiple times without releasing it. So, if a thread/process is unable to acquire a lock, it blocks until the lock becomes available. This situation is deadlocked.

Therefore, only one thread and only one lock can cause deadlock, if the thread does try to reacquire the lock.

When we have more than one process or one lock, then process/thread can acquire another lock to proceed further, or another process/thread can acquire a lock to proceed further.

 

Thank You