Load-Link/Store-Conditional
- Load-Link/Store-Conditional
-
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 den neuen Wert zurück in die referenzierte Speicherstelle, unter der Bedingung, dass diese nicht verändert wurde. Wurde die Speicherstelle verändert, schlägt die Schreiboperation fehl. Für den Grad der Veränderung gibt es eine starke und eine schwache Semantik (s.u.).
LL/SC Operationen dienen zur Implementierung von atomaren Operationen ohne die Verwendung von Locks (lock-free). Durch die Verknüpfung von Lese- und Schreiboperation ist ihre Semantik ist enger gefasst als bei der Compare-and-swap Operation, da diese keinen (nicht-verändernden) Zugriff auf die referenzierte Speicherstelle erkennen kann.
Implementierungen des LL/SC Befehlspaares existieren auf verschiedenen Rechnerarchitekturen, u.a.: ldl_l/stl_c und ldq_l/stq_c (Alpha-Prozessor), lwarx/stwcx (PowerPC), ll/sc (MIPS-Architektur), und ldrex/strex (ARM-Architektur ab Version 6). Diese Architekturen basieren meist auf der RISC Philosophie, deren Befehlssatz die Speicherzugriffe auf Lese- und Schreibbefehle reduziert.
Starke und Schwache Semantik
In der engen Auslegung der Semantik schlägt das LL/SC Befehlspaar nur dann fehl, wenn zwischen dem LL und dem SC Befehl eine Zugriff auf die referenzierte Speicherstelle stattfindet.
Auf vielen Architekturen führen aber auch andere Ereignisse zu einem überflüssigen Fehlschlag, z.B. bei Kontextwechseln, Interrupts oder auch anderen Speicherzugriffen.
Siehe auch
Wikimedia Foundation.
Schlagen Sie auch in anderen Wörterbüchern nach:
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… … 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
