= Solution
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:
``
reader: q := LOAD [p] // gets the old object
writer: STORE [p], new_object
writer: free(old_object)
reader: LOAD [q + field] // accesses freed storage
``
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.
\b[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.
$$
\boxed{\text{Retain old versions until every possible reader has finished.}}
$$
Back to article page
