GATE CSE 1997 | Question: 6.8

Question

Each Process $P_i, i = 1\ldots 9$ is coded as follows

repeat 
    P(mutex)
    {Critical section}
    V(mutex)
forever

The code for $P_{10}$ is identical except it uses V(mutex) in place of P(mutex). What is the largest number of processes that can be inside the critical section at any moment?

• A. $1$
• B. $2$
• C. $3$
• D. None

Comments

The difference is in "vice versa".

In this question(Gate question), P10 is like V(mutext) CS V(mutex) but in your question it is V(mutex) CS P(mutex).

If you try to check now, be it any sequence, you cannot fit more than 3 process when mutex=1.

---

If nothing is given. We have to consider it's a binary semaphore? Am I right?

---

Even if it’s vice versa then also more than 3 processes can be in C.S. :

The code I’m using for mutex :

Struct BSemaphore
{
    enum value(0,1);
    Queue type L;
}
P(BSemaphore mutex)
{
  if(mutex.value == 1)
      mutex.value = 0;
  else
      put the process in mutex.L;
      sleep();
V(BSemaphore mutex)
{
  if(mutex.L is empty)
      mutex.value = 1;
  else
      Select a process from mutex.L;
      wakeup();
    }
}

---

Sequence :

mutex = 1;

p1 enters makes mutex = 0;

p10 enters makes mutex = 1;

p2 enters makes mutex = 0; // At this point there are 3 processes inside C.S.

p10 leaves , executes p(mutex) , but as it’s already zero goes to sleep and in queue.

p2 leaves executes v(mutex) , makes mutex = 1 and wakeup p10 . // At this point there is only 1 process inside C.S.

p3 enters makes mutex = 0;

p10 enters makes mutex = 1;

p4 enters makes mutex = 0 ; // At this point there are 4 processes inside C.S.

---

 

And also answer of this should be 1 , due to two reasons :

1: Mutexes are not binary semaphore , mutex is a locking mechanism and the thread which acquired the lock can only release it.

2: Option d) says None , instead of none of the above.

Answer 1

 maximum 10 processes can enter in the crictical section at a time.
hence option D should be the right choice.

           
  if the code for the process 10 would be like              

repeat 
    V(mutex)
    {Critical section}
    P(mutex)
forever

 then answer should be 3.

And if code would be like for Process 10
repeat 
    P(mutex)
    {Critical section}
    P(mutex)
forever

then answer should be 1.

Comments

Rajesh Panwar , Could you please explain how we would get 3 for the following case?

  if the code for the process 10 would be like              

repeat
    V(mutex)
    {Critical section}
    P(mutex)
forever

---

one process is executing critical section. all other are waiting. when P10 comes and increases semaphor value then the first process waiting in queue and P10 both comes into critical section. So there will be max 3 processes.

credits : @Laxmi

Answer 2

From p1….p9 only one process can run..therefore we will just have 1 in CS and when p10 tries and execute..then 2 process will be in CS and..If p10 again comes mutex will be 3 if he does it again4….he can execute as many times he want….then we would have mutex set to very high value..and at that time..if p1,2,3 pn all tries to execute they will simply do mutex— and enter in CS we would have all the processes in CS that ways….Is my reasoning correct?

Answer 3

p1(not finished)(preemption occur)  ->  p10(not finished)(preemption occur) -> p2(not finished)(preemption occur) -> (from the start)p10 i run p10 from the start OR (case2)i have to wait till the previous p10 process finish if case 2 is true then only 3 process in cs at maximum          if case 2 i s false i run p10 again then any other process ....so on so this ccase ans=10

Answer 4

Answer is (D)

Set Mutex = 1
V(mutex) -> increment value of mutex
P(mutex) -> decrement value of mutex

Process enters into CS only when mutex = 1
P10 enters
   mutex = 1    {P10}
P1 enters
   mutex = 0    {P10,P1}
P10 exits
   mutex = 1    {P1}
P10 enters
   mutex = 1   {P1,P10}

P2 enters
   mutex = 0    {P10,P1,P2}
P10 exits
   mutex = 1    {P1,P2}
P10 enters
   mutex = 1   {P1,P2,P10}

P3 enters
   mutex = 0    {P10,P1,P2,P3}
P10 exits
   mutex = 1    {P1,P2,P3}
P10 enters
   mutex = 1   {P1,P2,P3,P10}

....

P9 enters
   mutex = 0    { P10,P1,P2 ... P9 }
P10 exits
   mutex = 1    {P1 ... P9}
P10 enters
   mutex = 1   {P1,P2.... P9,P10}

So maximum 10 process in Critical section at a specific time period.
Options D