To be pedantic (which I feel is fair because it's a concurrency question about possibilities):<p>><i>If we run P and Q concurrently, with ‘n’ initialized to zero, what would the value of ‘n’ be when the two processes finish executing their statements?</i><p>It depends a lot on the observer of `n` and what relationship it has with P and Q. Which isn't defined.<p>E.g. a trivial boundary-answer is that it can be 0, if nothing guarantees that P's and Q's threads' memory reaches the `n`-observer's thread. This is somewhat common if you try to synchronize via `sleep`, because that usually doesn't guarantee anything as all.<p>We also don't know the computer architecture. We can probably assume at least one byte moves between memory levels atomically, because basically every practical system does that, but that doesn't have to be true. If <i>bits</i> move between memory levels independently, this could observe <i>31</i>, because it can be any combination of the bits between `00000` and `10100`, which includes `01011` -> there can be a `1` in any position, including all positions, so you can observe a number that was <i>never</i> assigned. (IRL: multi-word values and partial initializations can do this, e.g. it's why double-checked locking is flawed without something to guarantee initialization completes before the pointer is exposed)
This implicitely assumes atomic assignments, meaning that during an assignment all bits representing a value are transfered in one atomic unit. This sounds a bit trivial, but if one would be working with large integers that are stored in multiple memory words, it is less trivial.<p>I think it is possible to implement locking with only atomic assigments.
Yeah, looking at the code my 'intuition' was "this is a classic data race, the program is broken" not "somewhere between 10 and 20".<p>I suppose if you assume all global accesses are atomic, it's a good demonstration that atomic operations don’t compose atomically (even in trivial cases) and aren't particularly useful as concurrency primitives.
This was fun to port over to PlusCal to verify it myself:<p><pre><code> EXTENDS Naturals, Sequences
(*--algorithm StateStore {
variables
n = 0; completions = <<>>;
define {
Invar == Len(completions) = 2 => n # 2
}
fair process (thing \in {"p", "q"})
variables i = 0, temp = 0;
{
Loop:
while (i < 10) {
First:
temp := n + 1;
Second:
n := temp;
Last:
i := i + 1;
};
Complete:
completions := Append(completions, 1)
}
}*)
</code></pre>
(I acknowledge that this isn't the most elegant Pluscal but I think it is a roughly accurate?)
Seems pretty clear that the result could be anything from 1 to 20.<p>(Assumes atomic assignments, as noted by someone else.)
The intuition I developed over the years says that result is unknown, it's a race condition, all bets are off. Specially since doing N+1.
[dead]