In computer science, the compare-and-swap CPU instruction ("CAS") is a special instruction that atomically compares the contents of a memory location to a given value and, if they are the same, modifies the contents of that memory location to a given new value. The result of the operation must indicate whether it performed the substitution; this can be done either with a simple boolean response, or by returning the value read from the memory location . CAS is used to implement synchronization primitives like semaphores and mutexes, as well as more sophisticated lock-free and wait-free algorithms.

PropertyValue
p:abstract
  • In computer science, the compare-and-swap CPU instruction ("CAS") is a special instruction that atomically compares the contents of a memory location to a given value and, if they are the same, modifies the contents of that memory location to a given new value. The result of the operation must indicate whether it performed the substitution; this can be done either with a simple boolean response, or by returning the value read from the memory location . CAS is used to implement synchronization primitives like semaphores and mutexes, as well as more sophisticated lock-free and wait-free algorithms. Maurice Herlihy (1991) proved that CAS can implement more of these algorithms than atomic read, write, and fetch-and-add, and that, assuming a fairly large amount of memory, it can implement all of them . Algorithms built around CAS typically read some key memory location and remember the old value. Based on that old value, they compute some new value. Then they try to swap in the new value using CAS, where the comparison checks for the location still being equal to the old value. If CAS indicates that the attempt has failed, it has to be repeated from the beginning: the location is re-read, a new value is computed and the CAS is tried again. Some of these algorithms are affected by and must handle the problem of a false positive match, or the ABA problem. It's possible that between the time the old value is read and the time CAS is attempted, some other processors or threads change the memory location two or more times such that it acquires a bit pattern which matches the old value. The problem arises if this new bit pattern, which looks exactly like the old value, has a different meaning: for instance, it could be a recycled address, or a wrapped version counter. CAS, and other atomic instructions, are unnecessary in uniprocessor systems, because the atomicity of any sequence of instructions can be achieved by disabling interrupts while executing it. However, often disabling interrupts is too expensive to be practical, so even programs only intended to run on uniprocessor machines will benefit by using them, as in the case of Linux's futexes. In multiprocessor systems, it is impossible and undesirable to disable interrupts on all processors at the same time. Even with interrupts disabled, two or more processors could be attempting to access the same semaphore's memory at the same time. The compare-and-swap instruction allows any processor to atomically test and modify a memory location, preventing such multiple processor collisions. (en)
  • Compare-and-Swap (CAS) -Instruktionen werden in der Informatik verwendet, um Locking- und Synchronisationsoperationen zu implementieren. Eine Speicherstelle wird mit einem vorgegebenen Wert verglichen, und bei Übereinstimmung mit einem neuen Wert überschrieben. Am Rückgabewert muss abzulesen sein, ob der Tausch ausgeführt wurde. Die CAS-Instruktion ist eine atomare Operation der CPU, d.h. ihr Ablauf kann und darf von keiner anderen Operation unterbrochen werden. Auf Intel x86 und Itanium Prozessoren ist dies die CMPXCHG-Instruktion. Andere atomare CPU-Instruktionen, die in ähnlicher Weise verwendet werden können, sind z.B. test-and-set und fetch-and-add. Auf RISC-Architekturen ist diese Operation meist als Load-Link/Store-Conditional (LL/SC) implementiert, da die RISC-Philosophie kombinierte read-modify-write Befehle nicht erlaubt. LL/SC hat auch eine etwas enger gefasste Semantik, da es auch nicht-verändernde Zugriffe auf die referenzierte Speicherstelle erkennen kann. (de)
p:hasPhotoCollection
p:member
  • compareAndSet(T, V, V) (en)
p:wikiPageUsesTemplate
rdfs:comment
  • In computer science, the compare-and-swap CPU instruction ("CAS") is a special instruction that atomically compares the contents of a memory location to a given value and, if they are the same, modifies the contents of that memory location to a given new value. The result of the operation must indicate whether it performed the substitution; this can be done either with a simple boolean response, or by returning the value read from the memory location . CAS is used to implement synchronization primitives like semaphores and mutexes, as well as more sophisticated lock-free and wait-free algorithms. (en)
  • Compare-and-Swap (CAS) (engl. für „Vergleichen und Tauschen“) -Instruktionen werden in der Informatik verwendet, um Locking- und Synchronisationsoperationen zu implementieren. (de)
rdfs:label
  • Compare-and-swap (en)
  • コンペア・アンド・スワップ (ja)
  • Compare-and-swap (de)
owl:sameAs
skos:subject
foaf:page
is p:redirect of