In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, read–modify–write is a class of
atomic operation
In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events (event), that may be extended by adding response events such that:
# The extended list can be re-e ...
s (such as
test-and-set In computer science, the test-and-set instruction is an instruction used to write (set) 1 to a memory location and return its old value as a single atomic (i.e., non-interruptible) operation. The caller can then "test" the result to see if the stat ...
,
fetch-and-add In computer science, the fetch-and-add CPU instruction (FAA) atomically increments the contents of a memory location by a specified value.
That is, fetch-and-add performs the operation
:increment the value at address by , where is a memory loca ...
, and
compare-and-swap
In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of tha ...
) that both read a
memory location
In computing, a memory address is a reference to a specific memory location used at various levels by software and hardware. Memory addresses are fixed-length sequences of digits conventionally displayed and manipulated as unsigned integers. Su ...
and
write
Writing is a medium of human communication which involves the representation of a language through a system of physically inscribed, mechanically transferred, or digitally represented symbols.
Writing systems do not themselves constitute h ...
a new value into it simultaneously, either with a completely new value or some function of the previous value. These operations prevent
race conditions
A race condition or race hazard is the condition of an electronics, software, or other system where the system's substantive behavior is dependent on the sequence or timing of other uncontrollable events. It becomes a bug when one or more of t ...
in multi-threaded applications. Typically they are used to implement
mutex
In computer science, a lock or mutex (from mutual exclusion) is a synchronization primitive: a mechanism that enforces limits on access to a resource when there are many threads of execution. A lock is designed to enforce a mutual exclusion concu ...
es or
semaphores. These atomic operations are also heavily used in
non-blocking synchronization
In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking im ...
.
Maurice Herlihy
Maurice Peter Herlihy (born 4 January 1954) is a computer scientist active in the field of multiprocessor synchronization. Herlihy has contributed to areas including theoretical foundations of wait-free synchronization, linearizable data structu ...
(1991) ranks atomic operations by their ''
consensus numbers,'' as follows:
* : memory-to-memory move and swap, augmented queue,
compare-and-swap
In computer science, compare-and-swap (CAS) is an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of tha ...
,
fetch-and-cons,
sticky byte,
load-link/store-conditional
In computer science, load-linked/store-conditional (LL/SC), sometimes known as load-reserved/store-conditional (LR/SC), are a pair of instructions used in multithreading to achieve synchronization. Load-link returns the current value of a memory l ...
(LL/SC)
* : -register assignment
* :
test-and-set In computer science, the test-and-set instruction is an instruction used to write (set) 1 to a memory location and return its old value as a single atomic (i.e., non-interruptible) operation. The caller can then "test" the result to see if the stat ...
, swap,
fetch-and-add In computer science, the fetch-and-add CPU instruction (FAA) atomically increments the contents of a memory location by a specified value.
That is, fetch-and-add performs the operation
:increment the value at address by , where is a memory loca ...
, queue, stack
* : atomic read and atomic write
It is impossible to implement an operation that requires a given consensus number with only operations with a lower consensus number, no matter how many of such operations one uses. 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
Register or registration may refer to:
Arts entertainment, and media Music
* Register (music), the relative "height" or range of a note, melody, part, instrument, etc.
* ''Register'', a 2017 album by Travis Miller
* Registration (organ), the ...
that would be accessed in a read operation.
This term is also associated with
RAID
Raid, RAID or Raids may refer to:
Attack
* Raid (military), a sudden attack behind the enemy's lines without the intention of holding ground
* Corporate raid, a type of hostile takeover in business
* Panty raid, a prankish raid by male college ...
levels that perform actual write operations as
atomic read–modify–write sequences.
Such RAID levels include
RAID 4,
RAID 5
In computer storage, the standard RAID levels comprise a basic set of RAID ("redundant array of independent disks" or "redundant array of inexpensive disks") configurations that employ the techniques of striping, mirroring, or parity to create la ...
and
RAID 6
In computer storage, the standard RAID levels comprise a basic set of RAID ("redundant array of independent disks" or "redundant array of inexpensive disks") configurations that employ the techniques of striping, mirroring, or parity to create larg ...
.
See also
*
Linearizability
In concurrent programming, an operation (or set of operations) is linearizable if it consists of an ordered list of invocation and response events (event), that may be extended by adding response events such that:
# The extended list can be re-e ...
*
Read–erase–modify–write
References
Concurrency control
Computer memory
{{comp-sci-stub