In computer science, the compare-and-swap CPU instruction ("CAS") (or the Compare & Exchange - CMPXCHG instruction in the x86 and Itanium architectures) 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.

PropertyValue
dbpprop:abstract
  • In computer science, the compare-and-swap CPU instruction ("CAS") (or the Compare & Exchange - CMPXCHG instruction in the x86 and Itanium architectures) 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 (this variant is often called compare-and-set), or by returning the value read from the memory location (not the value written to it).
  • Compare-and-Swap (CAS) (engl. für „Vergleichen und Tauschen“) -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.
  • コンペア・アンド・スワップ（Compare-and-Swap、CAS）とは、アトミックに、あるメモリ位置の内容と指定された値を比較し、等しければそのメモリ位置に別の指定された値を格納するCPUの特別な命令の一種である。この操作の結果、置換が行われたかどうかを示す必要があり、単純な真理値を返すか、そのメモリ位置から読み込んだ内容（書き込んだ内容ではない）を返す。 CAS命令はマルチプロセッサシステムでセマフォなどを実装するのに使われる。 また、マルチプロセッサシステムでLock-freeとWait-freeアルゴリズムを実装するのにも使われる。Maurice Herlihy(1993年)はこれが単なるリード、ライトやテスト・アンド・セットでは実装できないことを示した。 CAS命令を利用したアルゴリズムは、一般にあるキーとなるメモリ位置を読み取り、その古い値を記憶しておく。その古い値に基づいて、新しい値を計算する。その後、CAS命令でそのメモリ位置に新しい値を格納するが、そのときにCAS命令の比較によって計算に用いた古い値が置換時にもそのまま入っていることを確認する。CAS命令が比較に失敗した場合、最初から処理をやり直す。メモリ位置を再度読み取って、値を計算し、CAS命令を再実行するのである。 このようなアルゴリズムは False Positive（偽陽性）という問題（あるいは ABA問題）に対処しなければならない。古い値を読み取った後、CAS命令を実行するまでの間に、そのメモリ位置の内容が複数回書き換えられて偶然もとの古い値と同じビットパターンになっている可能性がある。CAS命令だけではこの事実を検出できない。その値はパターンは同じでも全く異なった意味かもしれない。 CAS命令はシングルプロセッサのシステムには不要である。その場合、単に割り込みを不可にすることでアトミック性が達成される。しかし、マルチプロセッサシステムでは同時に全てのプロセッサで割り込みを不可とすることは困難だし、不十分でもある。他のプロセッサでも同じメモリ位置にアクセスしようとしているかもしれない。CAS命令はそのようなプロセッサ間の衝突を防ぎ、アトミックにメモリ位置をチェックして変更することを可能にする。
  • Сравнение с обменом (англ. compare and set, compare and swap) — атомарная инструкция семейств процессоров x86, Itanium, Sparc. Как и другие атомарные инструкции, она предназначена для синхронизации между параллельными агентами (на разных процессорах или на одном, но без возможности монопольного захвата). Основное применение сравнения с обменом — реализация спинлоков и неблокирующих алгоритмов. Подход атомарных инструкций противостоит подходу с «условной записью» . Наиболее известная инструкция для сравнения с обменом — CMPXCHG семейства процессоров x86. CMPXCHG выполняется следующим образом: 1. Процессор читает область памяти, указанную в команде первым операндом, не снимая по завершении чтения блокировку шины. 2. Процессор сравнивает прочтённое значение со значением в аккумуляторе (регистр AL, AX, EAX или RAX). Флагу ZF присваивается значение в зависимости от результата сравнения (1 — если значение в памяти равно значению в аккумуляторе, 0 — если они отличаются). 3. Если значение в памяти было равно значению в аккумуляторе, процессор записывает значение из второго операнда в область памяти, указанную первым операндом. По завершении записи, блокировка шины снимается. Далее программист обязан закодировать проверку флага ZF для выяснения, выполнилась операция успешно или к моменту её начала значение в памяти было заменено другим агентом. Для Sparc, инструкции для данной операции называются CASA и CASXA.
dbpprop:date
  • April 2009
dbpprop:hasPhotoCollection
dbpprop:member
  • compareAndSet(T, V, V)
dbpprop:reason
  • how large is large?
dbpprop:reference
dbpprop:wikiPageUsesTemplate
rdfs:comment
  • In computer science, the compare-and-swap CPU instruction ("CAS") (or the Compare & Exchange - CMPXCHG instruction in the x86 and Itanium architectures) 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.
  • Compare-and-Swap (CAS) (engl. für „Vergleichen und Tauschen“) -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.
  • Сравнение с обменом (англ. compare and set, compare and swap) — атомарная инструкция семейств процессоров x86, Itanium, Sparc.
rdfs:label
  • Compare-and-swap
  • Compare-and-swap
  • コンペア・アンド・スワップ
  • Сравнение с обменом
owl:sameAs
skos:subject
foaf:page
is dbpprop:redirect of