Read-modify-write
Wikipedia Read-modify-write
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.
NOTE: "simultaneously"其实就意味着 "原子性" 。"some function of previous value" 的意思是 将previous value作为入参输入到一个function中而得到一个新value，然后将这个新value写入到memory中
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.
NOTE: 我们平时所使用的mutex、semaphore都是基于这些atomic operation而实现的。
Maurice Herlihy (1991) ranks atomic operations by their consensus numbers, as follows:
NOTE: 在CPU中，也可以使用multiple model来进行描述，因此它也可以使用consensus得到概念
| rank | |
|---|---|
| ∞ | memory-to-memory move and swap, augmented queue, compare-and-swap, fetch-and-cons, sticky byte, load-link/store-conditional (LL/SC)[1] |
| 2n - 2: | n-register assignment |
| 2 | test-and-set, swap, fetch-and-add, queue, stack |
| 1 | atomic read and atomic write |
NOTE:上述自底向上依次增长
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.[2]
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.[3]
stackoverflow Why it's termed read-modify-write but not read-write?
A
Because that is exactly the sequence of events on a typical architecture such as X86.
- read: The value is read from a memory location (cache) into a CPU register
- modify: The value is incremented inside the CPU register
- write: The updated register value is written back to memory (cache).
In order to create the perception of atomicity, the cache line is locked between the read and the write operation.
For example, incrementing a C++ atomic variable:
g.fetch_add(1);
Is compiled by gcc into:
0x00000000004006c0 <+0>: lock addl $0x1,0x200978(%rip) # 0x601040 <g>
Despite being a single instruction, addl is not atomic by itself. The lock prefix is necessary to guarantee that the updated register value is written back to the cache line before it can be accessed by other cores (the store buffer is flushed, but bypassed for RMW operations).
The MESI cache coherence protocol ensures that all cores observe the updated memory value after the lock on the cache line has been released. This guarantees that all threads observe the latest value in the modification order which is required for RMW operations by the C++ standard.
NOTE: 解释得非常好。
Compare-and-swap VS test-and-set
stackoverflow compare and swap vs test and set
A:
test-and-setmodifies the contents of a memory location and returns its old value as a single atomic operation.
compare-and-swapatomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to a given new value.The difference marked in bold.
A:
Test and set operates on a bit, compare and swap operates on a 32-bit field.