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

Answer is (D).
If initial value is $1$//execute $P_1$ or $P_{10}$ first 
If initial value is $0$, $P_{10}$ can execute and make the value $1$.
Since the both code (i.e. $P_1$ to $P_9$ and $P_{10})$ can be executed any number of times and code for $P_{10}$ is 

repeat
{
    V(mutex)
    C.S.
    V(mutex)
}
forever 

Now, let me say $P_1$ is in Critical Section (CS)
then $P_{10}$ comes executes the $CS$ (up on mutex)
now $P_2$ comes (down on mutex)
now $P_{10}$ moves out of CS (again binary semaphore will be 1 )
now $P_3$ comes (down on mutex)
now $P_{10}$ come (up on mutex)
now $P_4$ comes (down on mutex) 
So, if we take $P_{10}$ out of $CS$ recursively all $10$ process can be in $CS$ at same time using Binary semaphore only.

Comments

Q1:@kalpish Isn't this the case with mutex that the only process can give signal to mutex which has applied wait on the mutex ?

I have understood your explanation. But I have read this concept from different sources.Like  https://www.tutorialspoint.com/mutex-vs-semaphore

Q2:Here are we using mutex or binary semaphore?

Q3: If we are using mutex then what is the difference between mutex and binary semaphores?

@arjun sir

@abhishekmehta4u

---

@Akash Kumar Roy Exactly! thats what i was also thinking that why everyone is treating Mutex as Binary semaphores, they're completly different things.

https://stackoverflow.com/questions/62814/difference-between-binary-semaphore-and-mutex

---

A Mutex is different than a semaphore as it is a locking mechanism while a semaphore is a signalling mechanism. A binary semaphore can be used as a Mutex but a Mutex can never be used as a semaphore.

Answer 2

10 i.e.  ans D)

Comments

but option D is none which means none of the process can enter it .Here it is none not the None of the the above.please Clarfy

---

Well I agree with you.its just like misguiding students

Answer 3

option d) none

all 10 processes can enter the critical section

Comments

how 10 is possible

---

see it is given "The code for P10 is identical except it uses V(mutex) instead of P(mutex)"
it means for P10 code is
V(mutex)

{critical section}

V(mutex)
so everytime p10 is entering any process can enter, also p10 repeats forever.

---

The question only tells about replacing P(mutex) with V(mutex) so P10 only has V(mutex) in both places

Answer 4

consider code for i=1 to 9
initially mutex value set to be 1
so it can allow only 1 processor at a time
now p1 enter into critical section.
by this time remaining all are in block state
i.e blocked processes=2,3,4,5,6,7,8,9
but consider code for 10th process it tells that unblock any process because it contain operation. Because of this it can unblock the processor and send it to the critical section
by doing this process all processes can enter into critical section
so finally there are 10 processes at maximum can enter into critical section
answer is option d none.