Past exam of the computer science course of the University of Oxford / 2015 / Computer architecture / 3 / c

With O1, even readers must acquire and release the same mutex. Acquiring it normally uses an atomic read-modify-write on the lock's cache line; releasing writes that cache line again. As different CPU cores repeatedly read the data, ownership of the lock's cache line moves among them, causing cache coherence traffic and serializing the protected operations. If the lock shares a cache line with otherwise stable data, false sharing can also invalidate useful reader data. The actual data need not change for this lock traffic to occur.

With O2 and correctly ordered publication, readers perform only load instructions: copy p once into a processor register, then read that version of the data. Multiple CPU cores can keep read-only shared copies of its cache lines. No per-reader exclusive ownership transfer is needed. During an update, a writer fills newly allocated computer memory privately; the old version's cache lines remain unchanged for readers already using it. Publishing the new pointer writes p and invalidates cached copies of that pointer's cache line, but this occurs only on updates.

For many reads and rare updates, O2 avoids lock-line contention and permits concurrent readers, so it can be substantially faster. The costs are heap allocation, construction or copying of a whole replacement, first accesses to its newly populated cache lines, and deferred memory reclamation. Frequent updates or very large replacements can reverse the comparison. O1 can modify a small field in place and may then save copying and computer memory. These are workload-dependent comparisons, not a claim that removing every mutex always accelerates an operation.

O1 supplies mutual exclusion over each complete operation. A reader sees the protected state from a serial order of readers and writers; a writer can safely mutate the existing object while holding the common mutex. If an update reads the old state and modifies it, the entire read-modify-write can be protected against a lost update.

O2 has different semantics. Assume an indivisible aligned access to p, correct publication ordering, and no later mutation of a published version. A reader chooses one version when it loads p; the subsequent load instructions use the same saved pointer, so an overlapping writer need not block that reader. The reader may continue observing the old complete version after the writer has published the new one. A sufficiently specified snapshot read can still be linearizable, with the load of p as its linearization point: a read overlapping a write is allowed to come before that write in the abstract order. Thus reading an old version during overlap does not by itself prove failure of linearizability.

Multiple writers can each construct a valid replacement and race to publish it. If the operation is simply “replace the whole object”, atomic pointer stores give a last-publication order. If each writer instead computes a change from the previously published state, O2 alone does not preserve both changes. Two writers can both read a counter value zero, independently build a version containing one, and publish their respective versions; the final counter is one. A writer mutex or compare-and-swap with retry is needed when the required operation must avoid that lost update. Memory barriers alone do not provide this exclusion.

Releasing the old object's computer memory immediately after publishing a replacement is unsafe. For example:The final operation is a use-after-free: it may crash, see allocator metadata, or read a different object that reuses the same memory address. An atomic update of p does not update the reader's already copied pointer. Freeing the new object immediately would of course also invalidate p itself.

Publication and reclamation are separate: publish a fully initialized version, and retain every old version until all readers that might hold it have finished. A read-copy-update grace period or a suitable hazard pointer protocol can provide that lifetime guarantee; naive reference-count acquisition after loading an unprotected pointer can itself race with freeing. Correct memory barriers in part (iii) ensure visibility, not object lifetime.

Separate the two required orders. A writer must make all initialization store instructions to a fresh version visible before another CPU core can use the publication of its address. A reader must load p before the load instructions of fields addressed through the saved pointer. Assume ordinary coherent cacheable computer memory, atomic aligned pointer accesses, immutable published versions, and the lifetime guarantee from part (ii). The sequences below are architectural operations; a compiler must preserve the stated accesses and dependencies.

TSO. Total store order preserves store-to-store order, so initialization writes cannot become visible after the later pointer publication. It also preserves load-to-load order, so reading the pointer precedes reading its fields. Its store-to-load relaxation, illustrated in part (b), does not break either required ordering. ThereforeNo drain of every reader's store buffer and no explicit cache flush is required. This statement is about hardware ordering; unsynchronized ordinary C or C++ accesses to p would still need the language's atomic operation and acquire-release synchronization facilities to avoid a data race and unwanted compiler transformations.

Power/ARM. These weaker memory models can expose a new pointer before all the writer's initialization store instructions are visible. Put a write-ordering memory barrier between the last initialization write and the store of p. A sufficient sequence uses lwsync on POWER architecture or an appropriately scoped DMB, such as DMB ISH, on the ARMv7 ARM architecture family:The scope must include every participating CPU core. A broader full barrier is sufficient but can cost more. Without the writer barrier, observing the new p and stale initialization data is exactly the unwanted message-passing outcome.^[ref]

For the reader as actually specified, the saved pointer is an address dependency: the loaded value directly determines each subsequent field's memory address.Both POWER architecture and the relevant ARM memory models respect such dependent reads. Thus no additional reader hardware fence is needed when every data access retains this real address dependency. The writer's publication barrier together with the dependent reads supplies the necessary ordering. A mere test of p followed by unrelated fixed-address reads would be a control dependency, which is not sufficient here.^[ref]

If that address dependency is not retained, use an acquire operation or an explicit read-ordering memory barrier after loading p and before reading fields. DMB ISH on ARMv7 or lwsync on POWER architecture is a conservative sufficient choice for this load-to-load ordering; a suitable conditional branch followed by isync is another POWER acquire implementation. On later ARM instruction sets an acquire load instruction can express the reader requirement directly. Such stronger forms are often convenient even though they are not minimal for the dependent sequence in this question.

The minimal answer is a writer publication barrier on Power/ARM, with the stated reader's address dependence doing the read-side ordering; TSO needs neither extra hardware fence. None of these choices repairs an invalid pointer, premature memory reclamation, or a lost update between writers.