Questions on semaphores


#1

Can somebody please provide links to all the questions asked based on semaphores in previous years in gate and some good semaphores questions to practice,every year gate has one question from this topic ?
Also how to approach and solve these questions.I have lot of confusion in them.


#2

A shared variable x, initialized to zero, is operated on by four concurrent processes W, X, Y, Z as follows. Each of the processes W and X reads x from memory, increments by one, stores it to memory, and then terminates. Each of the processes Y and Z reads x from memory, decrements by two, stores it to memory, and then terminates. Each process before reading x invokes the P operation (i.e., wait) on a counting semaphore S and invokes the V operation (i.e., signal) on the semaphore S after storing x to memory. Semaphore S is initialized to two. What is the maximum possible value of x after all processes complete execution?(Gate CSE 2013)

A) -2
B) -1
C) 1
D) 2


#3

This is a trick question but at the time it’s simple too, now in the question it is given that initial value of semaphore is 2,so 2 process can enter and read and write x, we are talking about multiprogramming so let’s say X and Y are those processes, now X performs P(s) and then cpu transfers execution to Y, it also performs P(s) and then cpu transfers to X again it reads X whose value is zero and increments it by 1, and then cpu transfers again to Y it decrement X value and writes - 2,control returns to X which has already read the X value which was 0,and then it increments by 1 and then when X and Y finishes the value of x in memory is 1 not - 1 if you think like Y writes - 2 then x reads and increment by 1,beacuse the interleaving can be at any point, and we have to decide when they should interleave so that X value becomes maximum. Similarly W and Z so final maximum value X can take is 2,some users might argue that why you took pair X and Y, see there are only 3 kind of combinations like 2 are adding, 2 are subtracting, and one combination is one adds and one subtracts, now to find max value, where we can have advantage it’s when when we take one process which adds, one which subtracts.

Bonus- what’s the minimum value possible??