Editing Linearizability (section)

=== Fetch-and-increment ===
{{Main|Fetch-and-increment}}
Many systems provide an atomic fetch-and-increment instruction that reads from a memory location, unconditionally writes a new value (the old value plus one), and returns the old value.
We can use this to fix the non-atomic counter algorithm as follows:

:# Use fetch-and-increment to read the old value and write the incremented value back.

Using fetch-and increment is always better (requires fewer memory references) for some algorithms—such as the one shown here—than compare-and-swap,<ref name="cond-sync">{{cite book| last1=Fich | first1=Faith | title=Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing – PODC '04 | last2=Hendler | first2=Danny | last3=Shavit | first3=Nir | year=2004 | publisher=ACM | location=New York, NY | pages=80–87 | isbn=978-1-58113-802-3 |doi=10.1145/1011767.1011780| chapter=On the inherent weakness of conditional synchronization primitives | s2cid=9313205 }}</ref> even though Herlihy earlier proved that compare-and-swap is better for certain other algorithms that can't be implemented at all using only fetch-and-increment.
So [[CPU design]]s with both fetch-and-increment and compare-and-swap (or equivalent instructions) may be a better choice than ones with only one or the other.<ref name="cond-sync" />