Load-link/store-conditional
In computer science, load-linked/store-conditional, sometimes known as load-reserved/store-conditional, are a pair of instructions used in multithreading to achieve synchronization. Load-link returns the current value of a memory location, while a subsequent store-conditional to the same memory location will store a new value only if no updates have occurred to that location since the load-link. Together, this implements a lock-free, atomic, read-modify-write operation.
"Load-linked" is also known as load-link, load-reserved, and load-locked.
LL/SC was originally proposed by Jensen, Hagensen, and Broughton for the S-1 AAP multiprocessor at Lawrence Livermore National Laboratory.
Comparison of LL/SC and compare-and-swap
If any updates have occurred, the store-conditional is guaranteed to fail, even if the value read by the load-link has since been restored. As such, an LL/SC pair is stronger than a read followed by a compare-and-swap, which will not detect updates if the old value has been restored.Real implementations of LL/SC do not always succeed even if there are no concurrent updates to the memory location in question. Any exceptional events between the two operations, such as a context switch, another load-link, or even another load or store operation, will cause the store-conditional to spuriously fail. Older implementations will fail if there are any updates broadcast over the memory bus. This is called weak LL/SC by researchers, as it breaks many theoretical LL/SC algorithms. Weakness is relative, and some weak implementations can be used for some algorithms.
LL/SC is more difficult to emulate than CAS. Additionally, stopping running code between paired LL/SC instructions, such as when single-stepping through code, can prevent forward progress, making debugging tricky.
Nevertheless, LL/SC is equivalent to CAS in the sense that either primitive can be implemented in terms of the other, in O(1) and in a wait-free manner.
Implementations
LL/SC instructions are supported by:- Alpha: ldl_l/stl_c and ldq_l/stq_c
- PowerPC/Power ISA: lwarx/stwcx and ldarx/stdcx
- MIPS: ll/sc and lld/scd
- ARM: ldrex/strex, and ldxr/stxr
- RISC-V: lr/sc
- ARC: LLOCK/SCOND
Typically, CPUs track the load-linked address at a cache-line or other granularity, such that any modification to any portion of the cache line is sufficient to cause the store-conditional to fail.
All of these platforms provide weak LL/SC. The PowerPC implementation allows an LL/SC pair to wrap loads and even stores to other cache lines. This allows it to implement, for example, lock-free reference counting in the face of changing object graphs with arbitrary counter reuse. RISC-V provides an architectural guarantee of eventual progress for LL/SC sequences of limited length.
Some ARM implementations define platform dependent blocks, ranging from 8 bytes to 2048 bytes, and an LL/SC attempt in any given block fails if there is between the LL and SC a normal memory access inside the same block. Other ARM implementations fail if there is a modification anywhere in the whole address space. The former implementation is the stronger and most practical.
LL/SC has two advantages over CAS when designing a load–store architecture: reads and writes are separate instructions, as required by the design philosophy ; and both instructions can be performed using only two registers, fitting naturally into common 2-operand ISAs. CAS, on the other hand, requires three registers and a dependency between the value read and the value written. 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.