in Operating System edited by
40 votes

Let $m[0]\ldots m[4]$ be mutexes (binary semaphores) and $P[0]\ldots P[4]$ be processes. 
Suppose each process $P[i]$ executes the following:

     wait (m[i]); wait (m(i+1) mod 4]);
     release (m[i]); release (m(i+1) mod 4]);

This could cause

  1. Thrashing
  2. Deadlock
  3. Starvation, but not deadlock
  4. None of the above
in Operating System edited by


Deadlock is happening, correct. Can starvation also happen? I think the answer is yes because there is nothing stopping a process from restarting an unbounded number of times. Please suggest.
Do not care about Brackets. That may be typo.

Subscribe to GO Classes for GATE CSE 2022

7 Answers

67 votes
Best answer

$P0:m[0]; m[1]$

$P1:m[1] ;m[2]$

$P2:m[2] ;m[3]$

$P3:m[3] ;m[0]$

$P4:m[4] ;m[1]$
$po$ holding $mo$ waiting for $m1$
$p1$ holding $m1$ waiting for $m2$
$p2$ holding $m2$ waiting for $m3$
$p3$ holding $m3$ waiting for $m0$
$p4$ holding $m4$ waiting for $m1$
So its circular wait and no process can go into critical section even thought its free  hence
Answer: (B) Deadlock.

edited by


Given ans r right...

But can we say like that...

5 processes r there and each one need two mutex resources... Means to be deadlock free we need at least 6 mutex resources...even though they r accessed some order...

i think it should be P3:m[3] m[0] (bcoz of mod 4)...correct me if i am wrong

since m[i] or m[i+1] are mutexes they can only hold values of either 0 or 1... 0 mod 4 = 0 and 1 mod 4 = 1 .. so we can straightaway remove mod first and then solve the problem ...
How can the deadlock be prevented in this? I think till P3 this is dinning philosopher's problem so deadlock can be prevented if just one process reverses its order. Correct me if i am wrong..

yes if we remove p4 then it's a solid dining philosopher problem.

here there is no starvation .right?
Starvation is there
As process P0 and P2 can enter Critical Section at the same time, therefore there is no mutual exclusion. And no mutual exclusion means no deadlock. What am I missing here??

In all of the solutions, we are preempting the processes in halfway between their wait operation. But as per Galvin wait() & signal() are both atomic operations.

//This entire outer wait() is an atomic operation , right ??
wait(m[i]; wait(m(i+1) mod 4])

So is it correct to preempt the processes in-between wait()?

No, this is a typo mistake. These are two different wait calls.
60 votes
Let p[0] , p[1] , p[2] , p[3] and p[4] be the processes.Let p[0] execute the first wait() statement on variable m[0] and preempt then p[1] execute the first wait() statement on m[1] and so on till p[4].

Now lets come back to p[0] and execute the second statement wait(m[(0+1)mod4] ) =  wait(m[1]) but wait(m[1]) is already done earlier so it will be unsuccessful wait() operation.So we go to p[1] now.It performs m[(1+1)mod4] = m[2].But it is also done earlier so unsuccesful wait() operation.This we continue to do till p[4] so m[(4+1)mod4] = m[1] which is again an unsuccessful wait() operation since it is done earlier..

In short , no process can go into critical section now.Hence the processes are deadlocked.

We should note that preemption of a process can be taken at any point of time i.e. at any line.If by taking a preemption before critical section such that it is leading to deadlock , then we can conclude that the code suffers from deadlock.If we do not find any such instances of preemption , then we can conclude that the code is deadlock free.

Similarly we can check for mutual exclusion also.

Hence , B) option is correct.


you r getting deadlock 2 times,

1)choosing right fork

2) next turn

but I think choosing right fork() is not a cause a deadlock here.



here too we are choosing right fork and here no deadlock. Similar there too.

Here deadlock is causing due to mod4 operation,I guess.

@Habib clarify it.

@Kapilp I have a doubt in that selected question too.

Is explaination is correct there?

Because mod4 operation is causing circular wait, which never mentioned there.

Here no mention of fork () is done at all.

Plz see the working of wait () operation
Sorry @habib

fork here means (left fork and right fork) that philosopher using for their eating purpose. Ok now?

So, why here is a deadlock?

Here 5 Processes using 4 forks.

P0 picking fork m[1] first

P1  "         "     m[2]  "

P2  "         "     m[3] "

P3  "         "     m[0]  "

P4  "         "     m[1]  "

So, here process P0 and P4 picking same fork, at the same time. That is why there is a deadlock here, right?
No see actually p[0] picking m[0] first , then P[1] picking m[1] first and so on till P[4]. This is the instant till which each of the processes have executed one statement each.

Now we come back to P[0].It will try to hold m[(0+1)mod4] = m[1]. But m[1] is held by P[1]. Similarly we try to perform for P[1].but m[2] is also held by P[2]. So it is also not granted. In this way we try for all processes to acquire m[(i+1)mod4] . but already Held by other process in their execution of their respective code which is given in the question.

So no process can enter into critical section although it is empty. Hence deadlock occurs.
what is the difference if we write mod 5 in place of mod 4?
Then also in the execution of first wait() i.e. wait(m[i]) will take place i.e. P[0] will execute wait(m[0]) ,then P[0] will preempt and P[1] will execute wait(m[1]) ,......,finally P[4] will execute wait(m[4]) after P[3] preempts.

Now P[4] preempts and we come back to P[0] and try to execute m[(0+1)mod5] = m[1] . But m[1] is already locked by P[1],Hence we proceed to P[1] if it is able to be executed.But for P[1] , it tries to execute m[(1+1)mod5] = m[2] which is locked by P[2].So we check like this till P[4] , P[4] tries to execute m[(4+1)mod5] = m[0] which is already locked by P[0] .

So no process is able to go into critical section by taking preemption like this.As we know preemption of a process can be taken anywhere if it is a concurrent process.

Hence the above solution suffers from deadlock as well.
But it is a dining phyloshopher problem ,rt?

And dining phyloshopher problem not cause any starvation or deadlock situation.

So, why here it is causing deadlock?

I mean is it different from dining phyloshopher problem?
@Srestha this is the intentional purpose of just using the name 'Dining Philosopher's Problem' .Plz do not go by the name , go with what is the code given in the question actually.So we have to examine the code whether it is free from deadlock or not by taking preemption at appropriate step and if no process is allowed to go into critical section , as I have explained to you which preemption I took , then the code suffers from deadlock.

Similarly we can also check for mutual exlusion etc.

@Habib ok u mean until and unless it is mentioned dining phyloshopher problem , we have to check the code line by line.It is fine.

but see again

According to mod 4

P[0] getting m[0] and preempt

P[1] getting m[1]   "

P[2] getting m[2]  "

P[3] getting m[3]   "

P[4] getting m[4]   "

Now, when it comes back again

P[0] getting m[(0+1)%4]=m[1]

P[1] getting m[(1+1)%4]=m[2]

P[2] getting m[(2+1)%4]=m[3]

P[3] getting m[(3+1)%4]=m[0]

P[4] getting m[(4+1)%4]=m[1]

So, see here m[4] is not waiting for any one else. So, it is free to execute.


And as m[4] is executing ,

Here circular wait is for m[0],m[1],m[2],m[3]

and not for m[4]


@Habib clarify here
But here when P[0] tries to lock m[1] in second statement it is unsuccessful since m[1] is already Held by P[1] so the second statement of P[0] is not going to be executed. Similar is the case for other processes.

N you are saying m[4] is executing second wait () operation . Had this been successful it would have entered critical section successfully and hence deadlock had been avoided.

But this is not the case here.please check that the second wait for p4 would be on m[(4+1)mod 4] which is m[1] and hence which is already Held by P[1] . Hence it also fails to execute second wait () statement and hence no process is able to go into critical section. Hence deadlock occurs.

In the question they have mentioned "could cause"

So In this type of question can we assume that initial value of all mutex is 0,instead of 1.

Bcoz we have to check every possibility?

srestha ma'am can we say here that we have 5 process and 5 resources and every one need 2 resources so to be deadlock free it needs 6. but we don't have, that's why it is in deadlock

13 votes

As correctly mentioned by Jarvis.

It is a form of Dining Philospher Problem - 

Let all the 5 philosphers (processes)  sit on a round table with the rice bowl in the centre and  5 chop sticks (mutex), each in between two philosophers.Each philospher needs two chop sticks to eat the rice bowl. If all the philosophers are hungry at the same time , each will pick a chop stick closest to them . Hence, each will be stuck with one chop stick and waiting for another chop stick. Thus a Deadlock.

1 comment

yes, it can be related this way too.
8 votes
This is clearly the condition for circular wait so deadlock ,B.

1 comment

mod 4 indicates max no of chopstick are 4. so no of chopstick is less than no of philosopher so deadlock
5 votes
B) Deadlock

in case if every process execute their first instruction and pre-empt then every process will be waiting for every other process, hence cycle.

1 comment

describe in details
3 votes

( Above code is converted into simple 

'wait()' and 'signal()' operations)
$Deadlock$   is the correct choice.

1 comment

Please elaborate @Headshot
–6 votes
I think there will be no deadlock as there is no circular wait.

For P[3] it will be m[3] and m[0] and for p[4] it will be m[4] and m[1]. There is no circular wait.

But there might be starvation because of higher priority processes.

So, answer is C.

Anyone correct me if I am wrong.


@stuts there is circular wait. Read the best answer above.

yes circular will be there
But it will be cycle of length 4, instead of cycle of length 5.

Related questions