A shared variable x, initialized to zero, is operated on by four concurrent…

Concept

A counting semaphore initialized to k lets up to k processes hold a permit at the same time, so up to k of them can be inside the critical section concurrently. When several processes execute a non-atomic read-modify-write on a shared variable concurrently, their updates can race: a later store can overwrite (lose) the effect of an earlier store. The extreme outcomes of x come from choosing the interleaving that loses as many unwanted writes as possible.

Application

Here S is initialized to 2, so at most two of the four processes are in the critical section at once. W and X each do x = x + 1; Y and Z each do x = x - 2. To make x as large as possible, we want the two increments to count and the two decrements to be overwritten. Run the processes in two overlapping pairs, pairing one incrementer with one decrementer each time:

1. Start: x = 0. W and Y are admitted together (S = 2 permits both). Both read x = 0.

2. Y stores its result first: x = 0 - 2 = -2. Then W stores its result, computed from the value it read (0): x = 0 + 1 = 1. W's store overwrites Y's, so the decrement by Y is lost. Both signal S.

3. Now x = 1. X and Z are admitted together. Both read x = 1.

4. Z stores first: x = 1 - 2 = -1. Then X stores its result, computed from the value it read (1): x = 1 + 1 = 2. X's store overwrites Z's, so the decrement by Z is lost. Both signal S.

After all four terminate, x = 2.

Cross-check

Each increment that survives without being overwritten adds 1, and there are exactly two incrementers (W and X), so the largest reachable value is bounded by 0 + 1 + 1 = 2. The interleaving above attains this bound by letting each increment land last in its pair and discard a concurrent decrement, so 2 is both achievable and maximal. (For contrast, the minimum is obtained by the mirror-image interleaving where the decrements overwrite the increments, giving x = -4 if both increments are lost.)