Two processors share a counter in memory. Each increments it a million times: read the value, add one, write it back. At the end the counter should read two million. It reads about 1.3 million. Hundreds of thousands of increments vanished, because one processor's read landed between the other's read and write, and one of the two writes overwrote the other.
How does a protocol make a read-modify-write indivisible when many requesters share the data?
The obvious fix is to stop everyone else while you do it: lock the bus, read, modify, write, unlock. On a single shared bus with two masters that works. In a modern fabric with many paths, many targets and many requests in flight, "stop everyone" means stalling traffic that has nothing to do with the counter, across the whole fabric, for a full read round trip. It is correct and it does not scale.
Method | How | Cost | Scales? |
|---|---|---|---|
Locked transfers | Hold the path (or the target) from the read until the write; nobody else gets in | Blocks unrelated traffic for a round trip | Poorly |
Exclusive pair (load-linked / store-conditional) | Exclusive read marks the location; exclusive write succeeds only if nobody wrote it in between, and reports success or failure; software retries on failure | A monitor per target; retries under contention | Well, while contention is low |
Far atomic | Send the operation itself (fetch-and-add, swap, compare-and-swap) to the target, which does it in one step and returns the old value | Atomic logic at the target; a non-posted request | Very well: one round trip, no retries |
A monitor near the target (or in the interconnect) remembers, per requester, the address of its last exclusive read. Any ordinary write to that address by someone else clears the mark. When the exclusive write arrives, the monitor checks the mark: still set, the write goes ahead and the response says success; cleared, the write is dropped and the response says failure. The response status is the only way the requester learns which, so it must be a distinct status, not just "OK".
Situation | Choose | Because |
|---|---|---|
Single bus, two masters, rare atomics | Locked transfers are tolerable | There is little traffic to block |
Processors synchronising through caches or memory | Exclusive pairs | Cheap when uncontended; needs only a monitor |
Many requesters hammering one counter or queue index | Far atomics | No retries; one round trip each, however many contend |
Devices updating shared counters across a link | Far atomics | The device has no cache and no cheap way to retry |
Protocol | Atomics |
|---|---|
AXI | Exclusive accesses: an exclusive read and an exclusive write (AxLOCK). Success returns EXOKAY; failure returns OKAY and leaves memory unchanged. AXI4 removed locked transfers. |
PCI Express | AtomicOps: FetchAdd, Swap and CAS, non-posted; the completion returns the original value. Every switch on the path must support routing them. |
AHB | Locked transfers (HMASTLOCK): the locked sequence is not interrupted by other masters. |
The lost increment in the opening: plain read-modify-write on shared data. Any of the three methods fixes it.
Livelock with exclusives: two requesters (illustrative) keep clearing each other's marks, so both keep failing. Real systems add back-off, or guarantee forward progress in the monitor.
A bridge that drops the exclusive bit (lesson 5.17): the target treats the exclusive write as an ordinary write and answers with plain success. Depending on the protocol, that either reads as "failed" for ever (software loops) or as success without atomicity (silent corruption).
The requester must distinguish success from failure to know whether to retry; that needs a distinct status (in AXI, EXOKAY for success, OKAY for failure).
Far atomics: one round trip each with no retries. Exclusives would fail and retry heavily under that contention.
Atomicity can come from locking the path, from an exclusive pair that detects interference, or from sending the operation to the data.
Exclusive accesses need a monitor and a distinct success status; software retries on failure.
Far atomics scale best under contention; locked transfers scale worst.