Correctness: Locks, Atomicity, and CAS
Two bank transfers arrive concurrently. Transfer A reads account 42's balance as $1,000 and plans to deduct $800. Transfer B also reads $1,000 and plans to deduct $700. Without coordination, both writes succeed: A writes $200, B writes $300. The account that should have been overdrawn ends the day with a positive balance; $500 in withdrawals was not recorded.
The previous article defined the relevant vocabulary: race condition, critical section, atomicity. This article covers the tools that enforce atomicity in practice — mutual exclusion locks, atomic hardware operations, compare-and-set (CAS), and immutability — and describes when each applies.
The sequence below shows how the lost-update unfolds when two transfers run concurrently without coordination.
Mutual exclusion with locks
A lock (mutex) is the most direct tool. The thread acquires it before entering the critical section and releases it when done. Every other thread that tries to acquire the same lock blocks until the holder releases it. The critical section executes as if only one thread exists.
The classic implementation uses synchronized in Java or threading.Lock in Python. Both
provide the same guarantee: the block between acquire and release is mutually exclusive.
1import threading
2
3# Bad: read-modify-write on balance without a lock — two transfers
4# can both read the same starting balance and both "succeed"
5class Account:
6 def __init__(self, account_id: str, balance: float) -> None:
7 self.account_id = account_id
8 self._balance = balance
9
10 def withdraw(self, amount: float) -> None:
11 if self._balance < amount: # Thread A reads 1000 ──┐
12 raise ValueError("insufficient") # Thread B reads 1000 ◄─┘
13 self._balance -= amount # both threads subtract; one overdrafts silently
1import threading
2
3# Good: lock makes the check-then-subtract atomic
4class Account:
5 def __init__(self, account_id: str, balance: float) -> None:
6 self.account_id = account_id
7 self._balance = balance
8 self._lock = threading.Lock()
9
10 def withdraw(self, amount: float) -> None:
11 with self._lock:
12 if self._balance < amount:
13 raise ValueError("insufficient funds")
14 self._balance -= amount
15
16 @property
17 def balance(self) -> float:
18 with self._lock:
19 return self._balance
Two transfers contending for the same accounts
The sequence diagram below shows what happens when two transfers try to move money from account 42 at the same time — first without a lock, then with one.
Transfer B's rejection is the correct outcome: there was only $200 left after Transfer A completed.
Atomic operations and compare-and-set
Locks are general but carry overhead: blocking a thread, context-switching, and cache invalidation all add up when thousands of threads compete. For a single counter or flag, the CPU itself provides a lighter tool: atomic hardware instructions that read, modify, and write a memory word in one uninterruptible step.
The most useful of these is compare-and-set (CAS). It takes three arguments — the memory address, the expected current value, and the new value — and writes the new value only if the current value still matches the expectation. If another thread changed the value in the meantime, CAS fails without writing and reports that the swap did not happen; the caller re-reads the current value and retries from the new starting point. This is called optimistic concurrency: assume no contention, proceed, and back off only when a collision is detected.
A concrete trace shows the loop. Two threads both want to bump a counter holding 5. Thread A reads
5, computes 6, and calls compareAndSet(5, 6) — but Thread B slipped in first and the value is now
7, so A's call sees 7 != 5, fails, and writes nothing. A re-reads (now 7), computes 8, calls
compareAndSet(7, 8), and this time the expected value still matches, so the swap succeeds. No
update is lost: a failed CAS just means "start over from the value you missed," and the loop spins
until one attempt lands uncontended.
AtomicInteger in Java wraps a single integer and exposes CAS through compareAndSet,
getAndIncrement, and similar methods. The JVM compiles them to CPU-level atomic
instructions — no lock, no blocking. The exact failure contract varies by API: Java's
compareAndSet returns a boolean — true if the swap happened, false if it did not — so
the retry loop re-reads the value with a separate call, while compareAndExchange (Java 9+)
returns the value it actually found — handing the retry its new starting point without a separate
re-read. Either way the pattern is the same: detect the collision, re-read, and try again.