compare-and-swap atomic operation vs Load-link/store-conditional operation

Question

Under an x86 processor I am not sure of the difference between compare-and-swap atomic operation and Load-link/store-conditional operation. Is the latter safer than the former? Is it the case that the first is better than the second?

Cathexis

Answer 1

x86 does not provide LL/SC instructions. Check out wikipedia for platforms that do. Also see this SO question.

Catamite

" x86, being a CISC architecture, does not have this constraint — though modern chips may well translate a CAS instruction into separate LL/SC micro-operations internally", according to wikipedia. does the author refer to LOCK Signal Prefix ? – Cathexis

I'm guessing this refers to the fact that x86 ISA nowadays is implemented in micro-code on top of some secret RISC core. Otherwise it's not really clear. – Catamite

The wikipedia author who said "modern chips may well translate a CAS instruction into separate LL/SC micro-operations internally" talks of which he knows little. Indeed, I may have been the source of the quote, since I pointed out in the 1980s that microcode could implement an LL/SC spinloop. But, instead, microcode does better: no spinloop required. Guaranteed forward progress. Which many LL/SC implementations do not guarantee. – Coastwise

@krazyglew, care to enlighten us just a little bit more? – Catamite

Not much to say. Microcode could use LL/SC, but no x86 does. Instead ucode looks like tmp=ldlock A, tmp++ or whatever, stunlock A, tmp. The bad old days used bus locks, then cache locks, then address locks. Forward progress and fairness guaranteed, unlike ll/sc. – Coastwise

Hey, thanks! Both your websites are broken, by the way. – Catamite

Answer 2

There are three common styles of atomic primitive: Compare-Exchange, Load-Linked/Store-Conditional, and Compare-And-Swap.

A CompareExchange operation will atomically read a memory location and, if it matches a compare value, store a specified new value. If the value that was read does not match the compare value, no store takes place. In any case, the operation will report the original value read.

A Compare-And-Swap operation is similar to CompareExchange, except that it does not report what value was read--merely whether whatever value was read matched the compare value. Note that a CompareExchange may be used to implement Compare-And-Swap by having it report whether the value read from memory matched the specified compare value.

The LL/SC combination allows a store operation to be conditioned upon whether some outside influence might have affected the target since its value was loaded. In particular, it guarantees that if the store succeeds, the location has not been written at all by outside code. Even if outside code wrote a new value and then re-wrote the original value, that would be guaranteed to cause the conditional code to fail. Conceptually, this might make LL/SC seem more powerful than other methods, since it wouldn't have the "ABA" problem. Unfortunately, LL/SC semantics allow for stores to spontaneously fail, and the probability of spontaneously failure may go up rapidly as the complexity of the code between the load and store is increased. While using LL/SC to implement something like an atomic increment directly would be more efficient than using it to implement a compare-and-swap, and then implementing an atomic increment using that compare-and-swap implementation, in situations where one would need to do much between a load and store, one should generally use LL-SC to implement a compare-and-swap, and then use that compare-and-swap method in a load-modify-CompareAndSwap loop.

Of the three primitives, the Compare-And-Swap is the least powerful, but it can be implemented in terms of either of the other two. CompareAndSwap can do a pretty good job of emulating CompareExchange, though there are some corner cases where such emulation might live-lock. Neither CompareExchange nor Compare-And-Swap can offer guarantees quite as strong as LL-SC, though the limited amount of code one can reliably place within an LL/SC loop limits the usefulness of its guarantees.

Ratable