25-Comp-A3 Computer Architecture, December 2016, Q6

Question 6 (15 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. cnt initialised to 10 at 0x1000; main's W1–W4 non-atomically increments it in a loop; the interrupt handler's I0–I3 decrements it, and—because interrupts are disabled for its whole duration—runs as one uninterruptible, atomic read-decrement-write unit; interrupts can only ever land between two of main's instructions.

Find. Whether each proposed 3-value write sequence is achievable, with a concrete instruction interleaving if so, or a proof of impossibility if not.

Approach. Note that the handler's read-then-write is atomic (nothing else can execute between I1 and I3), so any handler-issued store always decrements whatever value memory currently holds at that instant; main's read (W1) and write (W3) are not atomic and can straddle an interrupt, which is the only source of "stale" writes and non-monotonic behaviour.

Sequence (i): 11, 12, 13. This is achievable with no interrupts at all: the main loop alone, run three times back-to-back with zero interrupts, produces exactly this sequence — W1(reads 10), W2, W3(writes 11); W4,W1(reads 11),W2,W3(writes 12); W4,W1(reads 12),W2,W3(writes 13). Possible — instruction sequence: W1,W2,W3,W4,W1,W2,W3,W4,W1,W2,W3 (no interrupt required).
Sequence (ii): 11, 9, 12. The first write (11) must come from main incrementing the initial value 10 (the only two things that can happen to a starting value of 10 are $+1=11$ or $-1=9$; since 11 is required first, this store is W3, and it commits the value 11 to memory immediately and for real — a completed store is not "tentative"). Immediately after this commit, memory genuinely holds 11. The next store in the trace, whatever produces it, must be either: (a) another handler invocation, which is atomic and therefore reads whatever memory currently holds (11) and writes $11-1=10$, never 9; or (b) another main store, which can only ever write (something it read)$+1$—never a value lower than what it most recently read, and it cannot have read anything below 10 at any earlier point (10 is the very first value memory ever held, and no store below 10 could exist before this point without itself appearing earlier in the observed sequence, which none does). Either way, the value immediately following an observed 11 cannot be 9. Impossible — once a store commits 11 to memory, the only next store an atomic decrement can produce is 10 (from 11−1), and the only next store an increment can produce is $\ge$12; no execution interleaving can insert a 9 immediately after an observed 11.

Final results — Question 6
Sequence	Possible?	Reasoning
(i) 11, 12, 13	$\boxed{\text{Yes}}$	Pure main-loop increments, zero interrupts needed
(ii) 11, 9, 12	$\boxed{\text{No}}$	An atomic handler decrement right after a committed 11 can only produce 10, never 9

Topic: Read-modify-write races between a non-atomic main loop and an atomic (interrupts-disabled) handler sharing one memory location.

Key relations: an atomic RMW unit always transforms the current memory value ($v\to v\pm1$ with no staleness possible); a non-atomic RMW (read, then later write) can only produce a stale result if something else writes memory between its read and its write, and that result is always (its own stale read)$\pm1$, never an arbitrary value.

Why this works: because the handler disables interrupts for its own duration, it can never itself be interrupted, so its read and write are effectively simultaneous from any outside observer's perspective — it can never "miss" an update that happened before it started, nor can anything sneak in during it. Main, by contrast, is interruptible between every pair of its own instructions, which is exactly what allows its write to reflect stale data (a lost-update hazard) — but that staleness always shows up as "write = (an earlier, valid memory value) + 1," never as an arbitrary drop.

Common pitfall: assuming "interrupts can happen at any time" means literally any value sequence is possible; it does not — the direction and magnitude of each store is still constrained by which instruction (main vs. handler) produced it and what that instruction had actually read.

Source: Patterson & Hennessy, Computer Organization and Design, 6th ed., Ch.5/App. (synchronization, atomic operations); Tanenbaum, Modern Operating Systems, 5th ed., Ch.2 (race conditions, critical sections).

Question 6 of 6

Question 6 (15 marks)