CAS принадлежит к классу объектов, называемых "консенсусными объектами", каждый из которых имеет консенсусное число; максимальное количество потоков, для которых данный согласованный объект может решить проблему согласованности.
Проблема консенсуса выглядит следующим образом: для некоторого числа потоков n
предложите некоторое значение p
и выберите одно из предложенных значений d
, чтобы n
потоков согласовалось с d
.
CAS является наиболее «мощным» консенсусным объектом, потому что его консенсусное число бесконечно. То есть CAS может использоваться для решения проблемы консенсуса среди теоретически бесконечного числа потоков. Он даже делает это без ожидания.
Этого нельзя сделать с помощью атомарных регистров, стеков test-and-set, fetch-add, стеков, поскольку все они имеют конечные согласованные числа. Есть доказательства для этих согласованных чисел, но это другая история ...
Значимость всего этого заключается в том, что можно доказать, что существует реализация без ожидания реализации объекта для потоков n
, использующая согласованный объект с согласованным числом не менее n
. CAS особенно мощен, потому что вы можете использовать его для реализации объектов без ожидания для произвольного числа потоков.
Откуда другие полезные операции RMW полезны? Некоторые проблемы в многопроцессорной обработке на самом деле не связаны с решением проблемы консенсуса для произвольного числа потоков. Например, взаимное исключение может быть решено с помощью менее мощных операций RMW, таких как test-and-set (простая блокировка TAS), fetch-add (блокировка билета) или атомарный обмен (блокировка CLH).
Подробнее о консенсусе для общей памяти в разделе Википедии «Консенсус (computer_science)»: In_shared-memory_systems
Также есть целая глава о консенсусе и универсальных конструкциях в книге Херлихи и Шавита Искусство многопроцессорного программирования ( WorldCat ), которую я очень рекомендую.