retagged by
23,599 views
26 votes
26 votes

At a particular time of computation, the value of a counting semaphore is $7$. Then $20$ $P$ operations and $15$ $V$ operations were completed on this semaphore. The resulting value of the semaphore is :

  1. $42$
  2. $2$
  3. $7$
  4. $12$
retagged by

5 Answers

Best answer
37 votes
37 votes

The answer is option B.

Currently semaphore is $7$ so, after $20$ $P$(wait) operation it will come to $-13$ then for $15$ V(signal) operation the value comes to $2.$

edited by
15 votes
15 votes

Option B 

since P(S) decreases the counting semaphore value 

 The initial value of semaphore is 7 

After finishing 20 P operations S=-13 (i.e 7-20 =-13)

Now S=-13

V(S) increases the counting semaphore value

After finishing 15 V operations S=-13+15=2

Therefore Answer is 2 option B

8 votes
8 votes

Counting Semaphore is an integer variable whose value can range over an unrestricted domain, this implies it can take positive values(1, 200, 4004), zero value(0) and even negative values( -1, -67, -1337).

Now you must be wondering how can the value of a semaphore be negative, as Wait() operation must busy-wait as soon as the semaphore value = 0? 

This depends on the definition of Wait() or P() operation. As per Galvin, there are two definitions of P() operation. One with busy waiting and one with non-busy-waiting.

Non-busy-waiting mode: Once the process finds out, that the value of the semaphore is zero, it is added to the waiting queue of semaphore(process also change its state from running to wait/block). Note that, even in this scenario, wherein the semaphore value = 0, the wait operation still decrements the semaphore further making it negative.

Now we will see the meaning of each value of the counting semaphore

Semaphore value is positive, this indicates the number of resource instances available.

Semaphore value is 0, this indicates that all the resource instances are exhausted.

Semaphore value is negative, this indicates the number of processes that are currently in the waiting queue of the counting semaphore.

 

Busy-waiting mode(as per classic definition of P()): Once the process finds out, that the value of the semaphore is zero, the process continuously busy waits. The process is stuck in P() operation’s while loop, the process cannot complete this P() operation until and unless semaphore value is greater than zero. Also, in this scenario the value of semaphore(positively initialized) can never be negative even if it is a counting semaphore. 

 

Now to the question,

Initially counting semaphore = 7, this means 7 instances of a resource are still available.

It is given that, 20 P() operations are completed. Each P() operation will decrement the semaphore value by 1. Hence after the first 7 P() operations the value of semaphore = 0. Now before we proceed further, we need to decide which definition of P() we are gonna use( busy-wait or non-busy-wait ). Since it is explicitly given that 20 P() operations are completed, we are free to choose any definition and we will still end up with the same answer. 

Since most of the answers have implicitly considered the non-busy-wait mode. I’ll try to cover the busy-wait mode. So after first 7 P() operations the value of semaphore = 0. Now, if any process tries to perform P() on the semaphore, it will busy-wait, i.e 13 P() operations are continuously stuck at while loop and still not completed, the value of the semaphore is still = 0. Now we proceed to perform 15 V() or Signal() operations, each V() operation increments semaphore value by 1, which will make our semaphore value = 15. This gives chance for the previous 13 P() operations to be complete. Each P() operation, again decrements semaphore by 1, so 15-13 we get the answer as 2.

2 votes
2 votes

 S = 7 - 20 =-13(in suspended list)

S= -13+15 = 2

The resulting value of the semaphore is : 2 option b

suspended list
13
Answer:

Related questions

14 votes
14 votes
11 answers
1
ajit asked Oct 12, 2015
21,410 views
Semaphores are used to solve the problem ofRace ConditionProcess SynchronizationMutual ExclusionNone of the aboveI and IIII and IIIAll of the aboveNone of the above
18 votes
18 votes
2 answers
2
28 votes
28 votes
1 answer
3
43 votes
43 votes
4 answers
4
Kathleen asked Sep 13, 2014
14,770 views
If $G$ is a context free grammar and $w$ is a string of length $l$ in $L(G)$, how long is a derivation of $w$ in $G$, if $G$ is in Chomsky normal form?$2l$$2l +1$$2l -1$$...