What is Compare-And-Swap (CAS), and how does AtomicInteger use it?

Compare-And-Swap is a single, hardware-supported CPU instruction (CMPXCHG on x86) that atomically does the following: if the current value in memory equals some expected value, replace it with a new value and report success; otherwise leave memory unchanged and report failure. AtomicInteger's incrementAndGet() method uses this in a retry loop: it reads the current value, computes current-plus-one, and then attempts a CAS that only succeeds if nobody else has changed the value in the meantime. If another thread modified the value between the read and the CAS attempt, the CAS fails and the loop simply retries with the new current value. Under low contention this loop typically succeeds on its very first try; under heavy contention it may retry a handful of times, but crucially it never blocks and can never deadlock. This style is called lock-free programming, because forward progress is still guaranteed overall -- a CAS failure for one thread always means some other thread successfully made progress.