The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
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
  2. Deadlock
  3. Starvation, but not deadlock
  4. None of the above
asked in Operating System by Veteran (68.8k points)
edited by | 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.

6 Answers

+36 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.
answered by Loyal (3.7k points)
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 ...
+25 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.
answered by Veteran (99k points)

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

answered by Loyal (3.9k points)
yes, it can be related this way too.
+6 votes
This is clearly the condition for circular wait so deadlock ,B.
answered by Loyal (3.2k points)
mod 4 indicates max no of chopstick are 4. so no of chopstick is less than no of philosopher so deadlock
+4 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.
answered by Junior (701 points)
describe in details
–7 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.
answered by (139 points)

@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.
Answer:

Related questions



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

32,330 questions
39,146 answers
108,245 comments
36,501 users