Read–modify–write

"RMW" redirects here. For other uses, see RMW (disambiguation).

In computer science, read–modify–write is a class of atomic operations (such as test-and-set, fetch-and-add, and compare-and-swap) that both read a memory location and write a new value into it simultaneously, either with a completely new value or some function of the previous value. These operations prevent race conditions in multi-threaded applications. Typically they are used to implement mutexes or semaphores. These atomic operations are also heavily used in non-blocking synchronization.

Read–modify–write instructions often produce unexpected results when used on I/O devices, as a write operation may not affect the same internal register that would be accessed in a read operation.^[1] This term is also associated with RAID levels that perform actual write operations as atomic read–modify–write sequences.^[2] Such RAID levels include RAID 4, RAID 5 and RAID 6.

Consensus number

Consensus number	Objects
${\displaystyle 1}$	atomic read/write registers, mutex
${\displaystyle 2}$	test-and-set, swap, fetch-and-add, wait-free queue or stack
...	...
${\displaystyle 2n-2}$	n-register assignment
...	...
${\displaystyle \infty }$	compare-and-swap, load-link/store-conditional,[5] memory-to-memory move and swap, queue with peek operation, fetch&cons, sticky byte

This section is an excerpt from Consensus (computer science) § Consensus number.[edit]

To solve the consensus problem in a shared-memory system, concurrent objects must be introduced. A concurrent object, or shared object, is a data structure which helps concurrent processes communicate to reach an agreement. Traditional implementations using critical sections face the risk of crashing if some process dies inside the critical section or sleeps for an intolerably long time. Researchers defined wait-freedom as the guarantee that the algorithm completes in a finite number of steps.

The consensus number of a concurrent object is defined to be the maximum number of processes in the system which can reach consensus by the given object in a wait-free implementation.^[3] Objects with a consensus number of ${\displaystyle n}$ can implement any object with a consensus number of ${\displaystyle n}$ or lower, but cannot implement any objects with a higher consensus number. The consensus numbers form what is called Herlihy's hierarchy of synchronization objects.^[4]

According to the hierarchy, read/write registers cannot solve consensus even in a 2-process system. Data structures like stacks and queues can only solve consensus between two processes. However, some concurrent objects are universal (notated in the table with ${\displaystyle \infty }$), which means they can solve consensus among any number of processes and they can simulate any other objects through an operation sequence.^[3]

See also

• Linearizability
• Read–erase–modify–write