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 which 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.
Maurice Herlihy (1991) ranks atomic operations by "consensus number", as follows:
- ∞: memory-to-memory move and swap, augmented queue, compare-and-swap, fetch-and-cons, sticky byte, Load-Link/Store-Conditional[1]
- 2n-2: n-register assignment
- 2: test-and-set, swap, fetch-and-add, queue, stack
- 1: 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. [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]
[edit] References
- ^ "Writing Lock-Free Code: A Corrected Queue" by Herb Sutter: "Compare-and-swap (CAS) is ... widely available ... However, some systems instead provide the equivalently powerful load-linked/store-conditional (LL/SC) instead."
- ^ Herlihy, Maurice (January, 1991). "Wait-free synchronization". ACM Trans. Program. Lang. Syst. 13 (1): 124–149. doi:10.1145/114005.102808. http://www.cs.brown.edu/~mph/Herlihy91/p124-herlihy.pdf. Retrieved 2007-05-20.
- ^ Massmind: "The Read-Modify-Write problem"
 |
This computer science article is a stub. You can help Wikipedia by expanding it. |
