Synchronisation formulas

Number of distinct interleavings of two independent sequences of m and n instructions, each sequence keeping its own order. Different interleavings may still give the same output.

R(S) is the set of variables statement S reads and W(S) the set it writes. If all three intersections are empty, S1 and S2 give the same result whichever runs first or if they run in parallel.

For the blocking form above: S_0 is the initial value, n_w the number of wait operations executed (including blocked ones) and n_s the number of signal operations executed. If S < 0 then -S processes are blocked. (In the busy-waiting form, n_w counts completed waits only.) Some questions use a form in which wait blocks without decrementing when S = 0, and signal wakes a blocked process instead of incrementing. There the final value is max(0, S_0 + n_s - n_w) and the number blocked is max(0, n_w - n_s - S_0).