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]

A memory operation's execution is conditional on a preceding value. A control dependency alone does not generally order two reads on POWER architecture or the relevant ARM memory models; it must not be substituted for an address dependency in pointer-publication reasoning.

An ordering binary relation used by a memory model to constrain observation of shared data. For the mutex example, T1's write precedes its release, that release synchronizes with T2's successful acquisition, and that acquisition precedes T2's read. Together these steps order the write before the read. Wall-clock timing alone does not establish happens-before.^[ref]

Lamport's bakery algorithm is a mutual exclusion concurrent algorithm in which each participating process chooses a numbered ticket before entering a critical section. Process $i$ announces that it is choosing, sets its ticket to one more than the largest observed ticket, and finishes choosing. It then waits for each other process to finish choosing and for every smaller nonzero pair $(\text{ticket},\text{process identifier})$ to leave. Comparing identifiers breaks ties between equal tickets; setting one's ticket to zero announces departure.^[ref]

For example, simultaneous choices can give processes 2 and 5 the same ticket 7; pair $(7,2)$ precedes $(7,5)$. The choosing flag prevents treating an unfinished choice as an absent contender. Leslie Lamport's 1974 proof even permits an overlapping read to return an arbitrary value under the specified shared-register model. The mathematical model uses unbounded tickets; a bounded machine implementation must also address overflow and its memory model.^[ref]

Rules specifying which shared-data observations and operation orders are allowed. Sequential consistency is the model used in the two diagrams. A language memory model can permit weaker ordering and impose additional conditions on conflicting accesses. Correct use of an indivisible flag must therefore be checked against that memory model, including happens-before relationships for the data guarded by the flag.

A processor with several CPU cores that can execute instruction streams concurrently. Shared computer memory requires attention to cache coherence and the architecture's memory model.

A store buffer holds the memory address and value of a store instruction while the memory cache or backing computer memory completes the write. The in-order pipeline can continue after enqueueing the write, rather than waiting for a possibly long memory access latency. A full store buffer eventually causes a pipeline stall; buffering hides finite delays, not an indefinitely inadequate service rate.

Without a memory management unit, the comparison can use the actual physical addresses; there is no address translation or synonym problem to solve. Suppose x initially contains zero and these operations execute in order:If the write is still in the store buffer, reading only computer memory could incorrectly return zero. The load instruction searches older buffered store instructions for an overlapping memory address. If the newest matching write covers the requested bytes and its data are ready, store-to-load forwarding returns seven directly. With several pending writes to x, the youngest older matching write wins. If the relevant data are not ready, the load instruction waits; partial overlaps require merging the covered bytes or conservatively waiting for the writes to drain.

A load instruction from an unrelated address y can bypass those buffered writes, subject to the architecture's memory model. Buffer writes to overlap them with useful execution, but preserve each load's dependence on older writes to the same bytes. Device accesses through memory-mapped input-output need their specified ordering and should not be treated as ordinary cacheable computer memory.

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.

An ordered execution obtained by mixing steps of several software threads while retaining each one's own step order. In the sequential consistency model of mutual exclusion, an indivisible step finishes before the next begins. Selecting the step boundaries is part of the model: an atomic read-modify-write increment has one boundary, whereas a separate read, local addition and write have three. Enumerating all such orders checks this specified model, not an arbitrary memory model or a real mutex implementation.

An architectural memory model preserving store-to-store and load-to-load ordering while allowing a later load to a different address to bypass a locally buffered store. This permits the two-zero store-buffering outcome while requiring no extra hardware fence for simple immutable pointer publication.

Primary research article: www.cl.cam.ac.uk/~pes20/ppc-supplemental/pldi105-sarkar.pdf

Section 2.1 introduces store buffering and message passing. Section 2.2 explains barriers and dependencies, including why a genuine address dependency can order reads while a bare control dependency does not. This source corroborates the general memory model discussion, not the availability of examination answers.