Compare-and-swap

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

Інструкція compare-and-swap (CAS) використовується в інформатиці як атомарна (тобто безперервна) операція для такої послідовності дій: порівняння значення у пам'яті із заданим значенням і якщо вони рівні, то запис у пам'ять нового значення.

Ця інструкція може використовуватись для реалізації таких примітивів синхронізації, як семафор та м'ютекс, а також для алгоритмів без блокувань. CAS еквівалентна load-link/store-conditional, в тому сенсі, що існує алгоритм без блокувань з фіксованою кількістю викликів однієї з них, що реалізує функціональність іншої.

Зазвичай, алгоритми, що використовують CAS, зчитують старе значення і на його основі обчислюють нове, а потім використовують CAS для збереження нового значення. Якщо операція CAS завершується невдачею (оскільки зчитане значення вже устаріло), тоді потрібно почати все спочатку.

Операція CAS може застосовуватись для реалізації атомарного інкременту.

ABA проблема[ред. | ред. код]

Може так статись, що між зчитування старого значення та встановленням нового (за допомогою CAS) значення буде змінене, а потім повернуте до початкового значення. Для захисту від таких випадків потрібно використовувати подвійний CAS, друге значення повинне бути лічильником змін.

Реалізації[ред. | ред. код]

Більшість компіляторів C11 підтримують compare_and_swap використовуючи <stdatomic.h>

Джерела[ред. | ред. код]