Что такое Compare And Swap?

Недавно я читал об Compare and Swap атомарном действии (CMPXCHG,.NET Interlocked.CompareExchange, что угодно).

Я понимаю, как он работает внутри, и как он используется от клиента.

Что я не могу понять, когда кто-то использует CAS?

Википедия говорит:

CAS используется для реализации примитивов синхронизации, таких как семафоров и мьютексов, а также более сложные блокировки и безжизненные алгоритмы.

Итак, может ли кто-нибудь дать мне более общий реальный прецедент с кодом и описанием использования CAS?

Этот вопрос предназначен для языковой агностики, поэтому любой язык будет делать (желательно сборка на основе C или x86).

Спасибо!

Ответ 1

Это легко увидеть на примере. Скажем, мы хотим атомизировать и одновременно устанавливать бит в общей переменной:

int shared = 0;

void Set(int index) {
 while (true) {
  if (Interlocked.CompareExchange<int>(ref shared, shared | (1 << index), shared) == shared)
   break; //success
 }
}

Мы обнаруживаем отказ, если видим, что "старое значение" (которое является возвращаемым значением) изменилось за это время.

Если этого не произошло, мы не имели одновременной модификации, поэтому наша собственная модификация прошла успешно.

Вы можете реализовать довольно сложные вещи, используя эту технику. Чем сложнее, тем больше потери производительности при вращении.

Я хочу подчеркнуть, что ключевым свойством CAS является то, что он может выйти из строя и что отказ может быть обнаружен надежно.

Ответ 2

Вы используете CAS для установки значения (бит или слово) атомарно в одном потоке или процессе, проверяя, что другой поток/процесс еще этого не сделал. Таким образом, он использовался для получения флага или счетчика в многопоточной среде.