Введение

Двойной сравнитель и обмен (DCAS или CAS2) — это атомарный примитив, предложенный для поддержки определенных методов конкурентного программирования. DCAS принимает два не обязательно смежных участка памяти и записывает в них новые значения только в том случае, если они соответствуют предварительно заданным «ожидаемым» значениям; таким образом, это расширение гораздо более популярной операции сравнения и обмена (CAS). DCAS иногда путают с двойным по ширине сравнителем и обменом (DWCAS), реализованным инструкциями, такими как x86 CMPXCHG16B. DCAS, как обсуждается здесь, обрабатывает два разрозненных участка памяти, как правило, размером с указатель, в то время как DWCAS обрабатывает два соседних участка памяти размером с указатель. В своей докторской диссертации Майкл Гринвальд рекомендовал добавить DCAS в современное аппаратное обеспечение, показав, что его можно использовать для создания простой в применении и эффективной транзакционной памяти программного обеспечения (STM). Гринвальд отмечает, что преимущество DCAS перед CAS заключается в том, что CASn более высокого порядка (для нескольких элементов) может быть реализован за O(n) с помощью DCAS, но требует O(n log p) времени с унитарным CAS, где p — количество конкурирующих процессов. Одним из преимуществ DCAS является возможность относительно легко реализовать атомарные двусторонние очереди (т. е. двусвязные списки). Однако в последнее время было показано, что STM может быть реализован с сопоставимыми свойствами, используя только CAS. В целом, однако, DCAS не является панацеей: реализация алгоритмов без блокировок и без ожидания с его использованием обычно так же сложна и подвержена ошибкам, как и для CAS. Motorola в какой-то момент включила DCAS в набор инструкций для своей серии 68k; однако, медленная работа DCAS по сравнению с другими примитивами (видимо, из-за проблем с обработкой кэша) привела к его избежанию в практических контекстах. DCAS не поддерживается аппаратно в серийно выпускаемых процессорах. Обобщение DCAS на более чем два адреса иногда называют MCAS (multi word CAS); MCAS может быть реализован с помощью вложенного LL/SC, но такой примитив не доступен непосредственно в аппаратном обеспечении. В 2013 году Тревор Браун, Фейт Эллен и Эрик Руперт реализовали в программном обеспечении многоадресное расширение LL/SC (которое они называют LLX/SCX), которое, будучи более ограничительным, чем MCAS, позволило им, с помощью некоторой автоматической генерации кода, реализовать одно из наиболее производительных параллельных двоичных деревьев поиска (фактически, хроматическое дерево), немного превзойдя реализацию skip-list на основе CAS в JDK. В целом, DCAS может быть обеспечен более выразительной аппаратной транзакционной памятью. IBM POWER8 и Intel TSX предоставляют рабочие реализации транзакционной памяти. Отмененный процессор Rock от Sun также должен был поддерживать его.