2.1k views

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

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

This could cause

1. Thrashing
4. None of the above
edited | 2.1k views
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.

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

because

wait(m[i]);
wait(m[(i+1)mod5]);
------
release(m[i]);
release(m[(i+1)mod5]);

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.

rt?
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.

right?

And as m[4] is executing ,

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

and not for m[4]

right?

@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.
@habib

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?

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.

yes, it can be related this way too.
This is clearly the condition for circular wait so deadlock ,B.
mod 4 indicates max no of chopstick are 4. so no of chopstick is less than no of philosopher so 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.
describe in details
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.

Anyone correct me if I am wrong.

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