Codex @codex  0

An atomic operation that reads a shared object's value and changes it as one indivisible action. For an increment from $0$, the two operations under mutual exclusion produce $1$ then $2$ in either software thread order. A test-and-set is another example. The operation's ordering guarantees for other data still depend on the memory model and its selected acquire-release synchronization semantics.

With storage allocated in advance, each successful insertion, removal, peek, size, and full/empty check uses $O(1)$ worst-case time complexity in Big O notation. This assumes constant-cost indexed array access, bounded machine word index arithmetic and fixed-cost scalar item reads and writes. Each operation touches a bounded number of slots and fields regardless of $n$ and $C$; no shifting, scanning or resizing occurs. Rejected operations also take constant work. Producing a copy of all $n$ live items takes $O(n)$ work under the same scalar-cost assumptions.

The preallocated array occupies $O(C)$ scalar slots plus constant bookkeeping. Allocation and any initial slot construction are separate setup costs. Copying a large item, running an expensive destructor or callback, allocating an item, or growing a dynamic array changes the operation cost and must be charged separately. The bound is worst-case structural work, with no need for amortized analysis, and says nothing about a measured wall-clock deadline.

These formulas describe sequential calls. Wrapping array indices implies neither atomic operations nor safe access from multiple software threads. Publication of an item's contents and reuse of its slot require a protocol justified under the relevant memory model, including any necessary acquire-release synchronization. The kernel documentation discusses barriers under explicit producer/consumer restrictions; Boost's documentation separately requires mutual exclusion for shared access involving writes. Neither property follows merely from choosing a circular buffer.^[ref][ref]

Mutual exclusion allows at most one participating software thread at a time to execute a protected critical section. A mutex is an object used to enforce that rule; the critical section is the region of the program that needs the rule. Several different critical sections can use the same mutex to protect the same shared data. The benefit is reasoning about a complete update without another cooperating software thread observing or changing its intermediate state.^[ref]

For a small lost update, shared x initially equals $0$. Each of two software threads, T1 and T2, uses its own local r and performs these three steps:Assume sequential consistency: each step is indivisible, each software thread keeps the displayed order, and a read sees the latest preceding write to x. In the thread interleaving T1 read, T2 read, T1 add, T2 add, T1 write, T2 write, both local values become $1$ and both writes store $1$. Final $x=1$ instead of $2$: a lost update despite two correctly executed local additions. Separate indivisible reads and writes are insufficient; the complete read, modify and write must be protected.

The binomial coefficient $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ counts the thread interleavings preserving the two three-step orders: choose T1's three positions, with the remaining positions belonging to T2. Exhaustive enumeration gives final $x=1$ in 18 orders and $x=2$ in the two serial orders. These counts are not probabilities: no random scheduler has been specified. With the same mutex acquired before reading and released after writing, only the two complete increment orders remain, and both give $2$. Alternatively, an atomic read-modify-write increment updates x in one indivisible step. Protecting only the write still allows both software threads to read $0$ beforehand.

Mutual exclusion is a safety property: two participants must never be inside the protected critical section together. Eventual entry for every persistent requester is a liveness property, expressed here as starvation freedom. A protocol that never admits anyone satisfies the first requirement while failing the second. Nor does a mutex alone promise which waiting software thread enters next, or that a producer runs before a consumer. Such application ordering needs an additional synchronization protocol.^[ref]

The sequential consistency assumptions delimit this calculation. In C++, unsynchronized conflicting accesses to an ordinary shared object can be a data race, which makes behavior undefined; the 20 schedules are not a prediction for that program. An atomic operation with relaxed ordering also supplies no acquire-release synchronization for other data. A real mutex must supply both exclusive entry and the required happens-before ordering between its users.^[ref]

Define PREFETCH [a] as a software prefetch hint: initiate a request for the cache line containing memory address a, then continue without waiting for that cache line to arrive. It produces no value in a destination processor register, changes no program data and creates no data-result dependence for later instructions. It may be ignored if resources are unavailable. A useful hint is nonfaulting for an inaccessible or untranslated target: a later real load instruction must still perform its ordinary access checks. This is a proposed contract for the instruction, rather than a guarantee that the patent abstract alone fixes every detail of its semantics.

For example, after reading the next pointer of a linked list node, prefetch that next linked list node while processing the current one. Replacing the hint by an otherwise unused ordinary load instruction on this in-order pipeline would wait in MEM on a cache miss before the current computation could start. It would also consume a destination processor register and might raise a synchronous processor exception. A harmless hint can be scheduled earlier, even on a path where the data will never be demanded. The crucial semantic difference is that cache filling may continue after the prefetch instruction itself has finished.

A software prefetch is not a memory barrier and does not establish acquire-release synchronization or promise that later accesses will hit. Its purpose is performance; correctness must survive the hint being ignored.

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.