GATE IT 2006 | Question: 57

Question

The wait and signal operations of a monitor are implemented using semaphores as follows. In the following,

• $x$ is a condition variable,
• mutex is a semaphore initialized to $1$,
• $x$_sem is a semaphore initialized to $0$,
• $x$_count is the number of processes waiting on semaphore $x$_sem, initially $0$,
• next is a semaphore initialized to $0$,
• next_count is the number of processes waiting on semaphore next, initially $0$.

The body of each procedure that is visible outside the monitor is replaced with the following:
                            

P(mutex);
...
body of procedure
...
if (next_count > 0)
    V(next);
else
    V(mutex);

Each occurrence of $x$.wait is replaced with the following:
                        

x_count = x_count + 1;
if (next_count > 0)
    V(next);
else
    V(mutex);
------------------------------------------------------------ E1;
x_count = x_count - 1;

Each occurrence of $x$.signal is replaced with the following:
                            

if (x_count > 0)
{
    next_count = next_count + 1;
    ------------------- E2;
    P(next);
    next_count = next_count - 1;
}

For correct implementation of the monitor, statements $E1$ and $E2$ are, respectively,

• A. $P(x\_sem), V(next)$
• B. $V(next), P(x\_sem)$
• C. $P(next), V(x\_sem)$
• D. $P(x\_sem), V(x\_sem)$

Comments

@Habibkhan

sir,not able to understand this one..

---

@ Arjun sir, @ Sachin mittal sir , @ Ayush upadhyay sir , @ bikram sir and @ Ankitgupta1729 sir

Please help me to understand that what is next semaphore and next_count doing logically? I am not able to understand its meaning?

Answer 1

• x_count is the number of processes waiting on semaphore x_sem, initially 0,

x_count is incremented and decremented in x.wait, which shows that in between them wait(x_sem) must happen which is P(x_sem). Correspondingly V(x_sem) must happen in x.signal. So, D choice.

---

What is a monitor?

Comments

If I say in simple way that monitor mean synchronisation or other words follow mutual exclusion.

But I am not understand how

wait (x_sem) is relate to P(x_sem)

And

Signal (x_sem) to V(x_sem)

In this question

Plz explain???

---

P(S) is another name for wait(S) and V(S) is another name for signal(S).

see this

---

@Arjun sir, how the code will work if the 1st process enters the function P(), executes the code and then executes P(x_sem), as the semaphore is initialised to 0??

Answer 2

We need value for x.wait and x.signal

We are working on 3 semaphores, mutex,  x_sem, next .

Now, check the first code

x_count = x_count + 1;

So, x_count becomes 1

but next_count still 0

So, unable to enter in the first block x.wait

if (next_count > 0)

and E1 will not execute first

So, going to execute x.signal

here x.count >0 satisfying the condition

if block permit increment next_count to be 1

 next_count = next_count + 1;

Now we want to execute x(ultimate we want to execute x)

So, V(x_sem) will be executed here

Wait(next) or P(next) will stop to execute code

Now , go to first part of code

if (next_count > 0)
    V(next);
else
    V(mutex);
------------------------------------------------------------ E1;
x_count = x_count - 1;

Now, next_count>0 is true.

So, code gets executed. V(next) and V(mutex)  gets executed here. And also x_sem already executed. So, now,P(x_sem) will be executed for Mutual Exclusion.

Comments

In you answer:-

So, x_count becomes 1

but next_count still 0

But what is next_count doing logically?I am not able to understand its meaning?