RMW

Read-modify-write (RMW) is a class of atomic instructions used in concurrent computing. In an RMW operation, a processor reads a memory location, computes a modification based on that value, and writes the result back in one indivisible step. The operation appears atomic to other threads, preventing interleaved reads or writes.

Hardware and primitives: RMW is exposed through hardware primitives such as compare-and-swap (CAS), fetch-and-add, fetch-and-sub, test-and-set, and fetch-and-or. CAS is the most widely used primitive for building lock-free data structures; it succeeds when the location currently contains an expected value and updates it to a new value. Fetch-and-add increments the value atomically and returns the previous value, useful for counters. Some architectures provide swap or bitwise variants; others allow atomic updates via dedicated instructions in memory models.

Memory model and ordering: RMW operations are atomic with respect to a single memory location, but their ordering relative to other memory operations is governed by the system's memory model. To maintain correctness in multi-threaded programs, developers often insert memory fences or use language-provided atomic constructs that specify sequencing and visibility guarantees.

ABA problem and correctness: In RMW loops, the ABA problem can occur when a value changes from A to B and back to A, misleading a CAS into success. Solutions include version counters, pointer tagging, or hazard pointers.

Applications and tradeoffs: RMW is central to lock-free and wait-free data structures, such as stacks, queues, and counters. Compared to coarse-grained locking, RMW-based approaches can offer higher scalability under contention but require careful design to avoid livelock, starvation, or memory-order bugs.

See also: atomic operations, lock-free programming, memory model, ABA problem.