Jump to content

Read–modify–write

From Wikipedia, the free encyclopedia

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

[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 can implement any object with a consensus number of 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]

Consensus
number
Objects
atomic read/write registers, mutex
test-and-set, swap, fetch-and-add, wait-free queue or stack
... ...
n-register assignment
... ...
compare-and-swap, load-link/store-conditional,[5] memory-to-memory move and swap, queue with peek operation, fetch&cons, sticky byte
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 ), 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

[edit]

References

[edit]
  1. ^ Massmind: "The read–modify–write problem"
  2. ^ "Basic RAID Organizations". umass.edu. Archived from the original on 2021-02-24. Retrieved 2013-10-04.
  3. ^ a b Herlihy, Maurice (January 1991). "Wait-Free Synchronization" (PDF). ACM Transactions on Programming Languages and Systems. 11 (1): 124–149. doi:10.1145/114005.102808. S2CID 2181446. Archived (PDF) from the original on 5 June 2011. Retrieved 19 December 2011.
  4. ^ Imbs, Damien; Raynal, Michel (25 July 2010). "The multiplicative power of consensus numbers" (PDF). Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing. Association for Computing Machinery. pp. 26–35. doi:10.1145/1835698.1835705. ISBN 978-1-60558-888-9. S2CID 3179361. Archived (PDF) from the original on 27 January 2022. Retrieved 22 April 2021.
  5. ^ Fich, Faith; Hendler, Danny; Shavit, Nir (25 July 2004). "On the inherent weakness of conditional synchronization primitives". Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing. Association for Computing Machinery. pp. 80–87. CiteSeerX 10.1.1.96.9340. doi:10.1145/1011767.1011780. ISBN 1-58113-802-4. S2CID 9313205.