Load-Link/Store-Conditional

Load-Link/Store-Conditional

In computer science, load-link (LL, also known as "load-linked" or "load and reserve") and store-conditional (SC) are a pair of instructions that together implement a lock-free atomic read-modify-write operation.

Load-link returns the current value of a memory location. 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. 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 (CAS), which will not detect updates if the old value has been restored.

Weak LL/SC

Real implementations of LL/SC do not always succeed 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 (on many platforms) 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 often 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.

Some limitations of weak LL/SC versus CAS are that:
* The latter is usually guaranteed to be fair, while the former is not. This is also true of strong LL/SC.
* Weak LL/SC can prevent forward progress when single-stepping.
* LL/SC is more difficult to emulate.

Implementations

All of Alpha, PowerPC, MIPS, and ARM have LL/SC instructions: ldl_l/stl_c and ldq_l/stq_c (Alpha), lwarx/stwcx (PowerPC), ll/sc (MIPS), and ldrex/strex (ARM version 6 and above).

Most platforms provide multiple sets of instructions for different data sizes, e.g. ldarx/stdcx for doubleword on the PowerPC.

Some CPUs require the address being accessed exclusively to be configured in write-through mode.

All of these platforms provide weak LL/SC. The PowerPC implementation is the strongest, allowing 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 (which otherwise requires DCAS).

ee also

*Non-blocking synchronization
*Compare-and-swap

References

* D. Detlefs, P. Martin, M. Moir and Guy L. Steele, Jr. "Lock-free reference counting", 20th annual ACM symposium on Principles of Distributed Computing, 2001, pp. 190-199 [http://portal.acm.org/citation.cfm?id=383962.384016]
* Kirk Reinholtz. "Atomic Reference Counting Pointers", C/C++ Users Journal, December, 2004 [http://www.cuj.com/documents/s=9724/cuj0412f/]


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Load-Link/Store-Conditional — (LL/SC) (engl. etwa „Referenz Laden/bedingt Schreiben“) ist ein Paar von Prozessor Befehlen, die eine read modify write Operation implementieren. Der LL Befehl lädt eine Speicherstelle, ihr Inhalt kann verändert werden, und der SC Befehl schreibt …   Deutsch Wikipedia

  • Compare-and-swap — In computer science, the compare and swap (CAS) CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, only if they are the same, modifies the contents of that memory location to… …   Wikipedia

  • Transactional memory — attempts to simplify parallel programming by allowing a group of load and store instructions to execute in an atomic way. It is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in… …   Wikipedia

  • Non-blocking algorithm — In computer science, a non blocking algorithm ensures that threads competing for a shared resource do not have their execution indefinitely postponed by mutual exclusion. A non blocking algorithm is lock free if there is guaranteed system wide… …   Wikipedia

  • Test-and-set — In computer science, the test and set instruction is an instruction used to both test and (conditionally) write to a memory location as part of a single atomic (i.e. non interruptible) operation. This means setting a value, but first performing… …   Wikipedia

  • Peterson's algorithm — is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single use resource without conflict, using only shared memory for communication. It was formulated by Gary Peterson in 1981 at the University of… …   Wikipedia

  • Lock-free and wait-free algorithms — In contrast to algorithms that protect access to shared data with locks, lock free and wait free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it. Lock free refers to the …   Wikipedia

  • Linearizability — In concurrent programming, an operation is atomic, or linearizable, if it appears to take effect instantaneously. An atomic object can be understood immediately and completely from its sequential definition, as a set of operations run in parallel …   Wikipedia

  • Fetch-and-add — In computer science, the fetch and add CPU instruction is a special instruction that atomically modifies the contents of a memory location. It is used to implement Mutual exclusion and concurrent algorithms in multiprocessor systems.In… …   Wikipedia

  • Atomic operation — An atomic operation in computer science refers to a set of operations that can be combined so that they appear to the rest of the system to be a single operation with only two possible outcomes: success or failure.ConditionsTo accomplish this,… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”