  ### OS : Semaphore

Questions : 10

QID : 54GATE-2018, 2M

Consider the following solution to the producer-consumer synchronization problem. The shared buffer size is N. Three semaphores empty, full and mutex are defined with respective initial values of 0, N and 1. Semaphore empty denotes the number of available slots in the buffer, for the consumer to read from. Semaphore full denotes the number of available slots in the buffer, for the producer to write to. The placeholder variables, denoted by P, Q, R, and S, in the code below can be assigned either empty or full. The valid semaphore operations are: wait() and signal().

Which one of the following assignments to P, Q, R and S will yield the correct solution? Options:
A) P: full, Q: full, R: empty, S: empty
B) P: empty, Q: empty, R: full, S: full
C) P: full, Q: empty, R: empty, S: full
D) P: empty, Q: full, R: full, S: empty
Ans : Option C
Solution :
Scenario 1:
If consumer starts first, it should wait since no item is produced yet. So to make wait(R) unsuccessful, we have to put R:empty which is initialized to ZERO.

Scenario 2:
If producer starts first, it should not be blocked. It should be allowed to produce 100 items. To allow it for 100 times, wait(P) should be successful. So we have to put P:full, which is initialized to 100.

When consumer consumes item, it should increment full by1, so signal(full) at S.

When producer produces item, it should increment empty by1, so signal(empty) at Q

A counting semaphore S is initialized to 12 and following operations are performed by different processes.
10P, 2V, 14P, 3V, 8P, 2V, 6P, 4V

What will be resulting value of S and size of queue ?

Options:
A) 15 and 15
B) -15 and 0
C) -15 and 15
D) 0 and 15
Ans : Option C
Solution :
after 10P, S will be 2 and size of queue=0 because all operations will be successful.

after 2V, S will be 4 and size of queue=0,
after 14P, S will be -10 and size of queue=10,
after 3V, S will be -7 and size of queue=7,
after 8P, S will be -15 and size of queue=15,
after 2V, S will be -13 and size of queue=13,
after 6P, S will be -19 and size of queue=19,
after 4V, S will be -15 and size of queue=15
...and so on.

A binary semaphore S is initialized to 1 and following operations are performed by different processes.
10P, 4V, 8P, 2V, 6P, 1V, 8P, 4V

What will be resulting value of S and size of queue ?

Options:
A) 1 and 21
B) 0 and 21
C) 1 and 20
D) 0 and 20
Ans : Option D
Solution :
after 10P, S will be 0 and size of queue=9 because 1st operations will be successful and 9 will be unsuccessful.

after 4V, S will be 0 and size of queue=5,
after 8P, S will be 0 and size of queue=13,
after 2V, S will be 0 and size of queue=11,
after 6P, S will be 0 and size of queue=17,
after 1V, S will be 0 and size of queue=16,
after 8P, S will be 0 and size of queue=24,
after 4V, S will be 0 and size of queue=20
QID : 63GATE-2013, 1M

Three concurrent processes X, Y, and Z execute three different code segments that access and update certain shared variables. Process X executes the P operation (i.e., wait) on semaphores a, b and c; process Y executes the P operation on semaphores b, c and d; process Z executes the P operation on semaphores c, d, and a before entering the respective code segments. After completing the execution of its code segment, each process invokes the V operation (i.e., signal) on its three semaphores. All semaphores are binary semaphores initialized to one. Which one of the following represents a deadlock-free order of invoking the P operations by the processes?

Options:
A) X:P(a) P(b) P(c)
Y:P(b) P(c) P(d)
Z:P(c) P(d) P(a)

B) X:P(b) P(a) P(c)
Y:P(b) P(c) P(d)
Z:P(a) P(c) P(d)

C) X:P(b) P(a) P(c)
Y:P(c) P(b) P(d)
Z:P(a) P(c) P(d)

D) X:P(a) P(b) P(c)
Y:P(c) P(b) P(d)
Z:P(c) P(d) P(a)

Ans : Option B
Solution : QID : 64GATE-1998, 1M

A Counting semaphore was initialized to 10. Then 6P (wait) operations and 4V (Signal) operations were completed on this semaphore. The resulting value of the semaphore is

Options:
A) 0
B) 8
C) 10
D) 12
Ans : Option B
Solution :
QID : 67GATE-1997, 2M

Each process Pi, i=1....9 is coded as follows:

REPEAT
P(mutex)
{
critical section
}
V(mutex)
FOREVER

The code for P10 is identical except that it uses V(mutex) in place of P(mutex). What is the largest number of process that can be inside critical section at any moment.

Options:
A) 1
B) 2
C) 3
D) None of the above
Ans : Option D
Solution :
Lets assume P1 starts then P2 starts and so on upto P9.
In such cases assume mutex is 1 initially.
P1 will enter CS making mutex 1 to 0.
P2 to P9 will blocked by P(mutex) and they will sit in queue.

Then P10 starts and executes V(mutex) continuously since its Repeat-forever,
Each time it performs V(mutex), it will dequeue one process from queue and allow it to enter in CS.
So all P2 to P9 will eventually enter in CS.
P10 can enter in CS anytime.

So, all 10 processes can canter in CS simultaneously.
QID : 94GATE-2016, 2M

Consider a non-negative counting semaphore S. The operation P(S) decrements S, and V(S) increments S. During an execution, 20 P(S) operations and 12 V(S) operations are issued in some order. The largest initial value of S for which at least one P(S) operation will remain blocked is _____ .

Ans : 7
Solution :
If we set S=20, then all P will be successful.

If we set S=10, then 10P will be successful and 10P will be blocked.
But 12V operations will unblock all these blocked.

We want to make sure that 13P operations will be blocked so that even after 12V operations, 1P operation will still remain blocked.
For that we have to set S=7 initially.
_____________________________

Other Way of solving is:
These operations can be performed in any order.
If we perform all V operations initially, the value of semaphore should not exceed 19, then only out of 20P, one operation will be blocked.
For this initial value must be 7 initially.
(Initially 7 and then 12V operations will make it 19)
QID : 259GATE-2010, 2M

The following program consists of 3 concurrent processes and 3 binary semaphores. The semaphores are initialized as S0=1, S1=0, S2=0.

How many times will process P0 print '0' ? Options:
A) At least twice
B) Exactly twice
C) Exactly thrice
D) Exactly once
Ans : Option A
Solution : QID : 269GATE-2008, 2M

The P and V operations on counting semaphores, where s is a counting semaphore, are defined as follows:

P(s) : s =  s - 1;
if (s  < 0) then wait;

V(s) : s = s + 1;
if (s <= 0) then wakeup a process waiting on s;

Assume that Pb and Vb the wait and signal operations on binary semaphores are provided. Two binary semaphores Xb and Yb are used to implement the semaphore operations P(s) and V(s) as follows:

P(s) : Pb(Xb);
s = s - 1;
if (s < 0) {
Vb(Xb) ;
Pb(Yb) ;
}
else Vb(Xb);

V(s) : Pb(Xb) ;
s = s + 1;
if (s <= 0) Vb(Yb) ;
Vb(Xb) ;

The initial values of Xb and Yb are respectively:

Options:
A) 0 and 0
B) 0 and 1
C) 1 and 0
D) 1 and 1
Ans : Option C
Solution :
QID : 288GATE-2006, 2M

The atomic fetch-and-set x,y instruction unconditionally sets the memory location x to 1 and fetches the old value of x in y without allowing any intervening access to the memory location x. Consider the following implementation of P and V functions on a binary semaphore S.

void P (binary_semaphore *s) {
unsigned y;
unsigned *x = &(s->value);
do {
fetch-and-set x, y;
} while (y);
}

void V (binary_semaphore *s) {
S->value = 0;
}

Which one of the following is true?

Options:
A) The implementation may not work if context switching is disabled in P
B) Instead of using fetch-and-set, a pair of normal load/store can be used
C) The implementation of V is wrong
D) The code does not implement a binary semaphore
Ans : Option A
Solution :

Submit Here

#### Previous GATE Papers

Year Key Organized by