Intel introduced the first non-blocking concurrency primitive for desktop PCs

In 1989, Intel shipped the i486DX with a new instruction: CMPXCHG — Compare and Exchange.

The core idea is dead simple. Given a memory location, an expected value, and a new value, the CPU does this atomically:

if (*addr == expected) {
    *addr = new_value   // swap succeeded
} else {
    expected = *addr    // load what's actually there
}

“Atomically” is the key word. No other CPU core or thread can observe or interrupt the operation mid-way. Either the swap happened or it didn’t — no in-between state is ever visible.

Before this, sharing mutable state across threads meant taking a lock: one thread enters, others spin or sleep. Locks are coarse — even a thread that only wants to read must wait on a writer. Under contention they kill throughput.

CMPXCHG enables a different pattern: optimistic concurrency. Read the current value, compute the new one, then race to install it. If something else changed the value in the meantime, the CAS fails and you retry. No lock acquired, no thread suspended.

This building block is enough to implement:

• lock-free queues and stacks
• reference counting without mutexes
• atomic counters (AtomicInteger, std::atomic<int>)
• database MVCC — check a version stamp, write only if unchanged

Java picked this up in Java 5 (2004) via java.util.concurrent (AtomicInteger, ConcurrentLinkedQueue, etc.), all built on sun.misc.Unsafe.compareAndSwap*, which JIT-compiles straight down to CMPXCHG.

The instruction is 35 years old and still the foundation of every lock-free data structure written today.