How deeply does Latency cover compare-and-exchange operation?

Defines conditional atomic replacement and notes failed linked-list updates require a restart or error, without detailing an implementation workflow.

Compare-and-exchange operation

As explained in Latency

A compare-and-swap instruction atomically compares a memory value with an expected value and conditionally replaces it with a new value.

A compare-and-exchange operation atomically compares a memory value with an expected value and replaces it with a new value only if they match. This conditional update is a building block for synchronization algorithms. section 8.3.1

In a concurrent linked list, an insertion may use compare-and-swap to update a pointer. If the operation fails because the pointer changed, the insertion must restart or return an error, limiting the wait-free guarantee. section 8.5.5

Table 8.1 Consensus numbers of wait-free primitives that you’ll typically use. The consensus number represents the maximum number of threads or processes a primitive can guarantee consensus for.

Wait-free primitive	Consensus number
Atomic registers	1
Test-and-set	2
Fetch-and-add	2
Queues	2
Stacks	2
Queues with peek	∞
Compare-and-swap (CAS)	∞

Compare-and-swap has an infinite consensus number in this comparison of wait-free primitives. section 8.5.2

How Latency covers it

liveBook manning.com

Read Latency on liveBook Get the book at manning.com

Also explained in

liveBook manning.com

Learn Concurrent Programming with GoCompare-and-swap is an atomic operation that compares a memory location with an expected value and replaces it with a new value only when they match, returning whether the replacement occurred.
liveBook manning.com

C++ Concurrency in Action, Second EditionAn operation that atomically compares an object's value with an expected value and conditionally replaces it with a desired value.

Compare how 3 books explain compare-and-exchange operation →

Related concepts

atomicitykind of · Atomicity is the property that an operation or group of operations takes effect as an indivisible, all-or-nothing unit, without observable partial effects.
bitwise comparisonuses · A bitwise comparison determines equality by comparing the object representations of values rather than applying their value-level comparison operators.
spinlockused by · A spinlock is a mutual-exclusion synchronization primitive in which a waiting thread repeatedly checks or attempts to acquire the lock rather than blocking.

This explainer was generated by Manning's knowledge graph from the text of Latency. The section links point to the parts of the book it draws on.