Self Doubt

Question

Q : Each process P_i , i = 1 to 9 executes the following code :

 while (TRUE)

 {

        P(mutex);

       Critical section ;

        V(mutex);

}

The process P₁₀ executes the following code :

while(TRUE)

{

        V(mutex);

        critical section ;

        P(mutex);

}

Initial value of binary semaphore "mutex"  =  1.Then what is the maximum number of processes that may be present in the critical section at any instant of time?

a)      2

b)      3

c)      9

d)     10

e)      1

Plz explain in details which one is true out of these options.

Comments

I think ans should be 3

P1 enter cs making mutex 0

p10 enter cs making mutex 1again

p2 eneter cs making mutex 0

now  p10 cannot come out if it does it will be blocked so no other way to make mutex 1 again and if p1 come out mutex will be 1 now only 1 one process can enter making count to 3 process in cs

what is tha ans????

---

This is a question asked in GATE 1997.

Answer 1

Initially Binary semaphore $\color{green}{mutex = 1}$, and we know that a binary semaphore can have only two states $0$ (or) $1$. So, even if we perform an UP on semaphore $s = 1$, no advantage here. So, best way here would be proceeding with an alternating sequence of $0$ and $1$.

 // Code for process 0-9            //Code for process 10
 while (TRUE) {                     while(TRUE) {
    P(mutex);                          V(mutex);
    <Critical section>                 <Critical section>
    V(mutex);                          P(mutex);
}                                   }

Suppose We start with process $P_{1}$, means $P_{1}$ enters Critical section by performing a DOWN on semaphore mutex. At this point $ \color{green}{ mutex = 0}$, Now $P_{10}$ executes and performs an UP on mutex and enters Critical section. At this point $ \color{green}{ mutex = 1}$, Now, Any one process out of $P_{2} \dots P_{9}$ enters critical section by performing a DOWN on binary semaphore mutex.Finally, $ \color{green}{ mutex = 0}$ and there is no way we could perform an UP on binary semaphore without allowing any process to leave Critical Section.

So, Maximum number of processes which are allowed to enter critical section $\color{red}{= 3}$ (two out of $P_{1} \dots P_{9}$ and $P_{10}$)

Comments

can pi=1 to 9 can't do the same (down and up the mutex value) repeatedly??

---

But u cannot increase the number of processes in the critical section by doing so.U have P and V of one process so semaphore value again becomes 1 .But having done the V(mutex) operation , the process which was in the critical section just before is out now.So u will not get maximum no of process possible which is 3 in this case.

---

so after p1 execute (comes out of the cs) p10 will execute ,then again p2 execute ,and suppose there is another process p11 along with the same code ,then we can say that max 4 process will be in cs ?

Answer 2

p1 to p9 requires mutex value to be=1 to enter into CS, right? But, p10 does UP() to enter CS,Observe the below sequence:
suppose initial value of mutex=1
p1: P(mutex), p1 is in CS, and mutex=0
now, p2 to p9 all 8 processes come to enter into CS, But as mutex=0 they can't and get blocked and enqueued in the list.
Then, p10 comes to enter CS, but according to UP function, if there are waiting processes in the list, so p10 wakes up one by one all processes and thus p2,p3,..,p9 all enter into CS.
Atlast, p10:V(mutex), p10 is in CS and now mutex=1
So, all 10 processes can enter into CS at the same time.