Codex @codex  0

An operation that takes effect indivisibly relative to the specified competing accesses. An atomic increment protects the whole read-modify-write; separate atomic loads and stores do not make their combined sequence an atomic operation.

// Target: computer-science.bigb

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 group of updates treated as one unit for file-system crash consistency. The three-record append above is one explicitly chosen group. Real file-system journaling can batch several system calls or split large work across several groups; it does not automatically make an application's several writes into one file-system transaction. An atomic operation for competing software threads likewise does not by itself provide file-system transaction durability.

Creation shows why the group must include every related change. In a toy file-system directory with space for one more name, creating notes with contents EFGH needs a directory entry mapping notes to newly allocated inode 42, an inode allocation bitmap marking 42 in use, that inode with size 4 and a reference to block 9, a block allocation bitmap allocating 9, and file data block 9 with the contents. An exposed directory entry must reach an allocated inode, and its content references must reach allocated file data blocks. Protecting just the inode leaves these relationships outside the file-system transaction. This simplified five-record creation excludes parent-directory growth, timestamps and allocation counters; a real file system must include its own additional dependencies.

A pulse sequencer can separate event capture from output timing. A short interrupt handler acknowledges the event latch and increments a pending count. An independent finite-state machine consumes one count on entering ON, changes to GAP after the pulse width, and enters IDLE only after the mandatory off interval. Even an empty queue must not bypass GAP: an arrival immediately after light-off would otherwise start too soon.

The pending count equals recorded events minus started pulses. A critical section protects its read-modify-write operations; declaring shared state as in volatile-qualified objects in C does not alone make each update an atomic operation. Separate sequencers for different channels allow simultaneous pulses while one hardware timer schedules their earliest deadline. Finite queue capacity, detector rearming and dispatch resolution remain explicit assumptions.

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]

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.

A short interrupt handler should acknowledge the detector and count work; a timed finite-state machine should generate the flashes. A Boolean “someone arrived” variable cannot preserve several queued detections. This is an interrupt-driven pulse sequencer. Initialise the light off, the pending-event counter to zero and the sequencer to IDLE before enabling interrupts.

In the following pseudocode, interrupt acknowledgement uses the source-specified operation of writing zero. The atomic operation and timer calls name abstract services, not undocumented device registers of a particular microcontroller.

eye_handler():
    if EYE_DETECTED != 0:
        EYE_DETECTED = 0
        pending = pending + 1

try_take_event():
    briefly mask the detector interrupt
    if pending == 0: taken = false
    else: pending = pending - 1; taken = true
    restore the previous interrupt mask
    return taken

service(now):
    if state == ON and elapsed(now, started) >= one_second:
        LIGHT = 0
        state = GAP
        started = now
    if state == GAP and elapsed(now, started) >= one_second:
        state = IDLE
    if state == IDLE and try_take_event():
        LIGHT = 1
        state = ON
        started = now

The main program repeatedly handles a new event or the next timer deadline and calls service. The ON state lasts one second; every completed flash enters GAP, even if the queue is empty at that instant. An arrival during that gap must wait for it to expire. Otherwise turning the light off and immediately treating the device as idle could allow a new flash too soon. Once a gap has expired, a queued event starts a new flash; if no work is pending the device remains idle. Removing a pending event only when a flash starts gives one completed flash per consumed event.

An interrupt can arrive during the main program's decrement. Without a critical section, its increment can be overwritten by a race condition. Merely declaring the counter volatile, as in volatile-qualified objects in C, does not make the decrement an atomic operation. Short interrupt masking, or an appropriate atomic operation, protects it; interrupts must remain enabled during the one-second intervals so that detections continue to be recorded.

A calibrated busy-wait loop is simple, but occupies the CPU and its duration depends on instruction timing, compiler transformations and time spent in interrupts. Polling a hardware timer avoids calibration dependence but still consumes CPU while polling. A timer interrupt or timer comparison deadline permits useful work or safe sleeping between transitions and is preferable for precise timing. If sleeping, the test for queued work and entry into sleep must avoid a lost wake-up. By the modulo-counter elapsed-time identity, a wrapping digital counter is usable if elapsed-time subtraction is unsigned and the real observation interval is less than its modulus; a wide enough counter or suitable bounded intervals make this explicit. Software dispatch adds bounded latency, so the specification is achieved to timer/interrupt-service resolution; stricter physical pulse-width requirements call for hardware output comparison or a suitably prioritised timer handler.

Finally, the device register is only a single-bit event latch. Two physical detections before acknowledgement may coalesce, so no software can recover their multiplicity from that bit alone. The event counter must also have enough capacity for the allowed backlog; indefinitely many arrivals faster than one flash every two seconds cannot be guaranteed with finite storage. These are explicit hardware/rate assumptions, not missing input files. Keeping the handler short minimises the rearming interval but cannot abolish those limitations.

Execution behaves as if steps occurred in one total order preserving each participant's program order; reads observe the latest preceding writes in that order. This is the definition given in the 1979 paper How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs, printed p. 690. It permits many thread interleavings, including the lost update under mutual exclusion; ordering individual accesses does not combine them into one atomic operation.

A software thread is an execution stream within a operating-system process. Each software thread has its own execution context, including processor registers, an instruction pointer, and a call stack selected by its stack pointer. Software threads in the same operating-system process share its address space, global variables, dynamically allocated storage (the memory heap), and resources such as file descriptors. Separate register states let two software threads pause at different instructions and later resume correctly. A context switch saves and restores those states; it does not copy the entire shared address space. ^[ref][ref]

In the right half of the diagram under operating-system process, T1 and T2 access the same counter x at virtual address 0x1234. Their call stacks occupy separate regions of the same address space, and their saved processor registers can contain different values. A software thread's own call stack means the stack used for its calls, not a hardware protection boundary against another software thread. Another software thread with a suitable address can access that stack's live data, subject to the program's lifetime and synchronization rules. Sharing an address space enables easy communication and makes accidental interference possible.

Concurrency means that several activities can make progress over overlapping intervals; parallel execution means that several activities execute at the same instant. On one CPU execution slot, process scheduling can interleave software threads without simultaneous execution. Multiple processor cores can run eligible software threads in parallel, but merely creating software threads does not ensure parallel execution or a speedup.

Consider an explicitly abstract interleaving model: shared x starts at $0$, and each of T1 and T2 performs three indivisible logical steps in its own order: load x into its own register r, add $1$ to r, then store r into x. Each load sees the latest preceding store in the displayed order. These model assumptions specify the example; they do not describe every programming language or every hardware memory model. In serial order T1 finishes all three steps before T2 starts, so T2 loads $1$ and stores $2$.

An overlapping order instead gives T1 load $0$, T2 load $0$, T1 add to get r1 = 1, T2 add to get r2 = 1, T1 store $1$, and T2 store $1$. The load/store subsequence is therefore T1 load $0$, T2 load $0$, T1 store $1$, T2 store $1$: final $x=1$, although each software thread incremented its register correctly. The second store replaces the first with the same value, losing one intended update. This race condition is possible even with interleaving on a single CPU.

This is not an unprotected C implementation example. Conflicting unsynchronized accesses to an ordinary non-atomic C object from different software threads can constitute a data race, which has undefined behavior; the abstract trace is not a prediction of that program's allowed outcomes. ^[ref]

The repair explains why synchronization matters: mutual exclusion around the whole load/add/store sequence prevents the other software thread from starting an increment halfway through it. Alternatively, an appropriate atomic operation can make the complete increment one indivisible read-modify-write. In the toy model, either repair makes the two increments take effect in an order, producing $0+1+1=2$. Making only each load and each store an atomic operation still permits the displayed lost update. ^[ref]

The attraction is independently progressing activities with direct access to shared data: a user-interface software thread can handle input while another waits for input-output, and workers can divide independent pieces of a large calculation among available cores. The first benefit can exist on one CPU; the second requires suitable work and execution resources. Context switches, synchronization, register-state records and extra call stacks consume time or computer memory, so the useful partition depends on the workload. ^[ref]