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?
(A) –2
(B) –1
(C) 1
(D) 2
Answer: (D)
Explanation :
S is a counting semaphore initalized to 2 i.e., Two process can go inside a critical section protected by S.
W, X read the variable, increment by 1 and write it back.
Y, Z can read the variable, decrement by 2 and write it back.
Pseudo code W
1. Wait(S)
2. Read(x) //into a register
3. x++
4. Write(x)
5. Release(S)
Pseudo code X
1. Wait(S)
2. Read(x) //into a register
3. x++
4. Write(x)
5. Release(S)
Pseudo code Y
1. Wait(S)
2. Read(x) //into a register
3. x = x - 2
4. Write(x)
5. Release(S)
Pseudo code Z
1. Wait(S)
2. Read(x) //into a register
3. x = x - 2
4. Write(x)
5. Release(S)
Whenever Y or Z runs the count gets decreased by 2. So, to have the maximum sum, we should copy the variable into one of the processes which increases the count, and at the same time the decrementing processed should run in parallaly, so that whaterver they write back into memory can be overridden by incrementing process. So, in effect decrement would never happen.
This is how it should be done:
W executes statement 1 : Decreases the semaphone count by 1. S = 1 now.
W executes statement 2 : Reads x from memory and copies into internal register.
Y executes statement 1 : Decreases the semaphore count by 1. S = 0 now. Now, both W, Y are in critical section and no other process can go inside it.
Y executes statements 2-4 : Reads x (i.e. 0), decrements it by 2 and writes back. Now, x = -2
Y executes statement 5 : Releases semaphore i.e., increments by 1. So, S = 1. Now, some other process can go inside ciritcal section.
Z executes statement 1 : Decreases the semaphore count by 1. S = 0 now. Now, both W, Z are in critical section and no other process can go inside it.
Z executes statements 2-4 : Reads x (i.e. -2), decrements it by 2 and writes back. Now, x = -4
Z executes statement 5 : Releases semaphore i.e., increments by 1. So, S = 1. Now, some other process can go inside cirtical section.
W executes statement 3-4 : Increments x (i.e., 0, which it read long back) to 1, writes it back to memory. x = 1.
W executes statement 5 : Releases semaphore i.e., increments by 1. So, S = 2. Now, some other processes can go inside cirtical section.
X executes statement 1-5 : X reads the value of x (i.e., 1) and increments it by 1 and writes back to memory. x = 2 now.
this way the value of x gets maximized. Thus the answer is (D)
Topics to Revise :
Semaphores
Critical Section
Concurrent Executions
References :
