edited by
21,762 views
48 votes
48 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
edited by

7 Answers

Best answer
76 votes
76 votes

$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
69 votes
69 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.
15 votes
15 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.

8 votes
8 votes
This is clearly the condition for circular wait so deadlock ,B.
Answer:

Related questions