Movatterモバイル変換

[0]ホーム

Jump to content

Read–modify–write

Edit links

From Wikipedia, the free encyclopedia

(Redirected fromRead-modify-write)

CPU instruction to simultaneously read and write a value in memory

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

Incomputer science,read–modify–write is a class ofatomic operations (such astest-and-set,fetch-and-add, andcompare-and-swap) that both read amemory location and write a new value into it simultaneously, either with a completely new value or some function of the previous value. These operations preventrace conditions in multi-threaded applications. Typically they are used to implementmutexes orsemaphores. These atomic operations are also heavily used innon-blocking synchronization.

Read–modify–write instructions often produce unexpected results when used onI/O devices, as a write operation may not affect the same internalregister that would be accessed in a read operation.^[1] This term is also associated withRAID levels that perform actual write operations asatomic read–modify–write sequences.^[2] Such RAID levels includeRAID 4,RAID 5 andRAID 6.

Consensus number

[edit]

This section is an excerpt fromConsensus (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 usingcritical sections face the risk of crashing if some process dies inside the critical section or sleeps for an intolerably long time. Researchers definedwait-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 $n {\displaystyle n}$ can implement any object with a consensus number of $n {\displaystyle n}$ or lower, but cannot implement any objects with a higher consensus number. The consensus numbers form what is calledHerlihy's hierarchy of synchronization objects.^[4]

Consensus number	Objects
$1 {\displaystyle 1}$	atomic read/write registers,mutex
$2 {\displaystyle 2}$	test-and-set,swap,fetch-and-add, wait-freequeue orstack
...	...
$2n-2$	n-register assignment
...	...
$\infty$	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

\infty

), which means they can solve consensus among any number of processes and they can simulate any other objects through an operation sequence.^[3]

References

[edit]

^Massmind: "The read–modify–write problem"
^"Basic RAID Organizations".umass.edu. Archived fromthe original on 2021-02-24. Retrieved2013-10-04.
^^a ^bHerlihy, 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. Retrieved19 December 2011.
^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. Retrieved22 April 2021.
^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.