Question

A multithreaded program P executes with x number of threads used y number of locks for ensuring mutual exclusion while operating on shared memory locations. All locks in the program are non-re-entrant. 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 k = 1
3. x = 2, y = 2
4. x = 1, y = 1

Answer 1

Correct Answer - Option 4 : x = 1, y = 1

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 don’t allow a thread to re-acquire the lock. 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:

1) It is asking about minimum value of x and y

2) Locks are non-re-entrant (recursive)

3) Programs gets block if another lock is unavailable

Now, question is asking about the minimum value of x and y for which execution of p can result in a deadlock. So, 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 are more than one lock available in the system, then process/thread can acquire the lock to do the further execution.