Compare-and-swap
Інструкція compare-and-swap (CAS) використовується в інформатиці як атомарна (тобто безперервна) операція для такої послідовності дій: порівняння значення у пам'яті із заданим значенням і якщо вони рівні, то запис у пам'ять нового значення.
Ця інструкція може використовуватись для реалізації таких примітивів синхронізації, як семафор та м'ютекс, а також для алгоритмів без блокувань. CAS еквівалентна load-link/store-conditional, в тому сенсі, що існує алгоритм без блокувань з фіксованою кількістю викликів однієї з них, що реалізує функціональність іншої.
Зазвичай, алгоритми, що використовують CAS, зчитують старе значення і на його основі обчислюють нове, а потім використовують CAS для збереження нового значення. Якщо операція CAS завершується невдачею (оскільки зчитане значення вже устаріло), тоді потрібно почати все спочатку.
Операція CAS може застосовуватись для реалізації атомарного інкременту.
ABA проблема
Може так статись, що між зчитування старого значення та встановленням нового (за допомогою CAS) значення буде змінене, а потім повернуте до початкового значення. Для захисту від таких випадків потрібно використовувати подвійний CAS, друге значення повинне бути лічильником змін.
Реалізації
- CAS є в IBM System/370 та її наступниках.
- CMPXCHG є в інструкціях x86, починаючи з Intel 80486.
- SPARC 32 та PA-RISC єдині архітектури, що не підтримують CAS.
Більшість компіляторів C11 підтримують compare_and_swap використовуючи <stdatomic.h>
Джерела
- .NET Class methods Interlocked::CompareExchange.