OS handout

Question

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

P(i)

{

     while(1)

     {

         P(m[i]);

         P(m[(i+1)%4];

         <CS>

         V(m[i]);

         V(m[(i+1)%4];

      }

}

What is the maximum no. Of processes that can be in<CS> .......

Comments

I think max 2 processes can be in critical section .

---

Yes answer will be $2$ according to me.

$P[0]$ starts executing $wait(mutex[0])$ and $wait(mutex[1])$ is executed and values of $mutex[0]$ and $mutex[1]$ is changed to $0$. $P[0]$ now enters critical section.

$P[0]$ is preempted by $P[1]$ , but it gets stuck in busy waiting because $mutex[1]$ is already $0$. So it won’t enter it’s critical section.

Instead of $P[1]$ if  $P[2]$ preempts $P[0]$ then it will be able to enter it’s Critical Section and it will turn $mutex[2]$ and $mutex[3]$ to $0$.

Till now we have 2 processes in their Critical Section. $P[1]$ and $P[0]$.

Now if we preempt $P[2]$ while it is executing it’s critical section with $P[3]$ then again it will be stuck in busy waiting because $mutex[3]$ is $0$.

Instead of $P[3]$ if we preempt $P[2]$ with $P[4]$ then again it won’t be able to enter it’s critical section because.it requires both  $mutex[4]$ and  $mutex[0]$ and  $mutex[0]$ is already occupied but $P[0]$.

Therefore at max only $2$ processes can enter in it’s critical section.

---

Yes the answer will be 2.
Initially, only P0 and P2 are satisfied.

Answer 1

All 5

If they execute p(m[i]) and gets preempted.