Register
Dark Mode

GATE CSE 2017 Set 1 | Question: 27

in Operating System edited by
33,248 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$
in Operating System edited by
by
33.2k views

4 Comments

Show 6 previous comments
by
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
1
1
by
edited by
A very ambiguous question. Thank you @Bikram Sir for the detailed explaination :)
2
2
by

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?

1
1

7 Answers

78 votes
78 votes
Best answer

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
by

69 Comments

by
re entrant propert y given for the lock..why we assume that threads may require same lock multiple times
1
1
by
they are asking for minimum nunber of process and lock . So we can assume that same process is tring to acquire already owned lock.
0
0
by

Suppose there are two threads and two locks available ata a time.
(We are assuming it as provided in the question paper).Now if suppose lock L1 is acquired on thread t1, same way Lock L2 is acuqired on T2 thread. Now the completion of T1 depends on T2 and T2 waits till T1 is Completed. That's nothing but Deadlock.

If we talk about T1 thread and Lock L1. Then in some instant of time will come when T1 will complete its execution. So T1 alone can't be the Reason For Deadlock.

So my opinion is Inclined towards answer C.

@Arjun Suresh Sir kindly verify and confirm.

0
0
by

Even in Grade Up also Correct Answer given is Option C.

0
0
by
How can a multi-thread program P, have X=1 thread running?????

If X=1,then P is not multi-thread program.

Pls reply
4
4
by
what a point bro,what a point
2
2
by
@arjun sir.....is this option d) absolutely correct?
0
0
by
yes multi threaded program!
0
0
by
@karthik are you saying MAX_NUM_THREADS=1 is not valid?
0
0
by
Max_num_thread=1 is valid, but for single threaded program. It should not be 1 for a multi-thread program P
0
0
by
Depends on your level of imagination - you can say it is "not multiple threads" in execution. But multi-threaded doeas not mean that. A multithreaded program means it is written so that multiple threads can be launched on it (thread safe). It is not a requirement that during execution we should have >1 threads.
18
18
by
I think multithreaded program can have one thread in excecution.

I think ,If process is multithreaded, it does not implily that it will never have single thread in execution.
4
4
by

Tanenbaum and Woodhull define deadlock as:

A set of processes is deadlocked if each process in the set is waiting for an event that only another process in the set can cause.

Notice that it is possible for a single process to become deadlocked if it is waiting for an event that only it can cause. However, it is usually the case that one process is waiting for a resource that is held by another process

 link is http://hamilton.nuigalway.ie/teaching/AOS/FIVE/deadlock.html

that means ans: (2, 2) could be correct?

0
0
by
Here it is mentioned if a process wants to reacquire the lock, it should release it. I don't understand why it will be a requirement for X=1 thread and Y=1 lock. There is only 1 thread, it can acquire the lock whenever it wants to and release it when it does not need anymore and reacquire it again!!
Not understanding how deadlock holds! There is no competition
3
3
by

what if it was a reentrant lock? then what would be the answer?

0
0
by
if it is Re-entrant then there is No Deadlock .
0
0
by
Sir

See, by looking at the question, we cannot say " if it is Re-entrant then there is No Deadlock . "

but we can say, a lock can hold multiple thread, then it is reentrant
0
0
by
in re-entrant locks, isn't deadlock possible if two threads wait for a resource the other one is holding just like in case of two processes??

@ Bikram sir??
0
0
by
I think if lock would be re-entrant then for causing deadlock  minimum 2 thread and one lock would be sufficient
4
4
by
@srestha  @kaluti and @sushmita

if they say the lock is Re-entrant and other conditions remain the same .... then

for a single thread and single lock , X=1 and Y=1 case

 process can own same lock multiple times, so if process tries to accuire already owned lock, will NOT get blocked , and deadlock will not happen.
8
8
by
@ritwik @srestha and @sushmita

as @kaluti mention above ,

 yes if they mention the lock property is re-entrant only with all other conditions same , then to become deadlock Minimum 2 threads and 1 lock is needed.

as for 2 threads one thread hold the lock again and again where another thread waiting to het the lock and get blocked ... hence deadlock is possible .
5
5
by
yes that is correct.

Actually it is a need-allocation-maximum need question(means how much maximum need, how much allocated), rt? where need is 1 and also allocation is 1.

reentrent and non reentrant is extra term used here.(to confuse)

But why in this question we are thinking lock is already acquired?

otherwise x=2,y=1 would be answer.rt?
0
0
by
@srestha

it says minimum

that's why we think x=1 and y =1 and in this case lock have to acquire over and over  ...

and reentrent and non reentrant is not any extra term used here to confuse , rather they are some conditions to be satisfied !!
0
0
by
yes, that is true.

but never it is mentioned, that a lock may be acquired.

So, an intution needed, to think a lock may also be acquired.

As, no direct formula will work here.
0
0
by

question says, " ensuring mutual exclusion " so to ensure that a lock have to be acquired.

this is not straight forward formula based and u have to think the scenario after reading the question .That it should satisfy those conditions or not !!

And yes , this is a very good tricky question .

2
2
by

@Bikram Sir

What ME says?

" A mutual exclusion (mutex) is a program object that prevents simultaneous access to a shared resource "

that doesnot mean lock already acquired.rt?

0
0
by
before going to critical section , if you do not lock the shared resources then how  Mutual Exclusion is possible ?
0
0
by

All locks in the program are non-reentrant, i.e., if a thread holds a lock ll, then it cannot re-acquire lock ll without releasing it

So, process can release a lock, each time, after completing Critical Section and acquire in the begining of entering CS. So in case of x=1,y=1 deadlock will not occur

1
1
by
reshown by
Why thread tries to acquire the lock which it already acquired
1
1
by

@student2018

This Question have three key points :

  1. Minimum 
  2. Non-reentrant 
  3. and 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. 


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 it already acquire !!! which lead to deadlock ( as in the question it says If a thread is unable to acquire a lock, it blocks until the lock becomes available. ) .

see below discussion to get things clear , if any .

7
7
by
if one thread acquires a lock already how can it acquire same lock as no of lock given here is 1.

there will be no lock to acquire again if x=1 and y=1.
0
0
by
This is how i thought on this question. Please verify

If we suppose the program P is like below

Where P() and V() are usual wait and signal semaphore operations respectively.

If Semaphore X is initially 1 and a thread of the process say A executed below code

P()

{

P(X); //acquired lock by making X=0;

P(X); // Process/Thread will be blocked here as locks are non-reentrant.

/*some code*/

V(X);

} //end of program P

A single thread of process A will get blocked.
And eventually all threads of this process will get blocked.

Suppose now another single threaded process B executes the above code

it will also get blocked because no thread of any process is available to provide signal operation.

This will cause deadlock.

So a single thread of execution and a single lock is sufficient to get deadlock.
4
4
by

@Bikram sir

How can deadlock occur for X=1 because for deadlock to occur we must have minimum two processes as follows from the definition of deadlock

Source- Tannenbaum

3
3
by
@Ayush you should never by-heart the statements for GATE. Doing so might make you a University topper but not GATE topper. A thread is a lightweight process and for the purpose of deadlock, it is no different from a process.
13
13
by

Dynamic thinking hmmmm. I got your point sir. Thank you sir, for I have still time to develop and make changes to my preparation accordingly.

So does that mean in question we are being asked for what minimum value of x and y can result in a situation where the process P can no longer proceed execution and also there is no definite period of time within which our process P can come out of such situation? Is that what meaning of word deadlock implied here?

2
2
by
edited by

@  Ayush Upadhyaya

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 :

  1. Minimum number of thread and lock
  2. All locks in the program are Non-reentrant  . ( key Point )
  3. " 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 .

So the possibility of Deadlock is there with single thread .

Hope you get it now !!

40
40
by
Thanks a ton bikram sir !! :)
0
0
by
Sir, the above explanation

for Two thread and 1 lock,

if one thread make continuous locks

then there will  be condition of starvation,

How deadock?

please guide
2
2
by

as for 2 threads one thread hold the lock again and again where another thread waiting to het the lock and get blocked ... hence deadlock is possible .

Bikram sir i have a doubt, is the above condition deadlock or starvation? Since one thread will eventually release the lock which can then be acquired by another thread in case of reentrant lock.?

1
1
by

@sushmita

here condition is " P can result in a deadlock  "

and they are not told there must be a deadlock.

So, we can say starvation may sometimes lead to a deadlock

0
0
by

Hi @srestha ji, 

Following statement is looking very loose. Could you please provide some example or reference to support your point ?

starvation may sometimes lead to a deadlock

0
0
by

Hi @sushmita ji,

as for 2 threads one thread hold the lock again and again where another thread waiting to het the lock and get blocked ... hence deadlock is possible .

I am also thinking how could if be possible ? If you have some answer please mention.

1
1
by
@sushmita That surely is starvation condition -- where is that given as deadlock?
3
3
by
Sir, why would a thread request for an already acquired lock? I dont understand.
8
8
by

 @srestha can we imagine this condition as recursive call to a function is made by the process. When it makes call for the first time, it acquires the lock. But when it tries to recursively call the function and as the lock is non -reenterant, process will be blocked and no other process can call that function as lock is already acquired.

Therefore x=1 and y =1 is sufficient.

Is this correct reasoning for this?

5
5
by
yes, I think it will be correct.because once lock is not released, we cannot reacquire lock
1
1
by

@ sir

If the locks are re-entrant the minimum number of minimum value of X = 2 and  Y = 2

T1 holding Lock1 and requesting Lock2

T2 holding Lock2 and requesting Lock1

X = 2 and Y = 1 will lead to starvation but not deadlock

T1 holding Lock1 and requesting Lock1 again and again and moreover granted as re-entrant

also T2 requesting Lock1 it will get block as T1 holding but at some point of time T1 release lock1 and T2 will get it

Hence this will lead to starvation but not deadlock

  Small doubt :

uses y number of locks for ensuring mutual exclusion while operating on shared memory location

can we think it as a 'y' binary semaphores 

3
3
by
I think the program would also result in deadlock if we have 2 threads and 1 lock. Because once a thread acquires a lock, it would wait for the same lock again due to reentrant property and hence result in deadlock.

 

But since there is no necessity of 2 threads for deadlock, 1 thread is sufficient.
0
0
by

@Arjun

as for 2 threads one thread hold the lock again and again where another thread waiting to het the lock and get blocked ... hence deadlock is possible .

by Bikram sir. is it true?

0
0
by
Because they asked min value of x and y

So 1 thread and 1 lock is sufficient for deadlock
0
0
by

If the locks are re-entrant and all other conditions are same then it would take minimum two threads and two processes for a possible deadlock.  

 

Am I correct on this? 

1
1
by
@toxicdesire

I am correct on this ...
0
0
by

@Bikram Sir,

You are saying only 2 threads and 1 re-entrant lock is sufficient for the possibility of deadlock.

But in this scenario, at least one process will always have acquired the lock right? So, only one process will be waiting for the lock. Now it may never get a chance to acquire a lock, but then it will be a case of starvation right? How is it a deadlock? Infinite starvation and deadlock are two different things right?

 

0
0
by
edited by
0
0
by

@Bikram sir, i have a doubt 

​​is binary semaphore a non reentrant lock??

 

1
1
by
1
1
by

I got the question but my real concern is:  

why would "a thread "  acquire a lock  if it already acquired it?

2
2
by
0
0
by
0
0
by

will you plese explain it in simple words @Bikram

0
0
by
0
0
by
0
0
by
why would the thread want to reacquire the lock when it has already acquired it and is inside the critical section?
1
1
by
According to me lock are mange by user and user can put a lock anytime he want so deadlock possible
0
0
by
How is a single process getting deadlocked ?, Does’t deadlock require atleast 2 processes?
0
0
by
Multiple threads suffice to create a deadlock.
2
2
by
Thank you sir, got it
0
0
by
edited by
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?
1
1
by

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?

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

by

4 Comments

Show 6 previous comments
by
if it was a simple kind of lock then the answer would have have 2,2 , right?
0
0
by

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

0
0
by

@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

0
0
1 vote
1 vote

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
by

4 Comments

Show 8 previous comments
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.
1
1
by
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
2
2
by
2
2
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...
by

2 Comments

by
edited by
Please don't repeat the answers. If you want to add something (more information), you can comment below the selected answer.
0
0
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 

2
2
Page:
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

Subscribe to GATE CSE 2024 Test Series

Subscribe to GO Classes for GATE CSE 2024

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

64.3k questions

77.9k answers

244k comments

80.0k users

Developed by Chun
Link Copied!