Преимущества и недостатки программирования CAS

Может ли кто-нибудь рассказать мне о преимуществах и недостатках программирования Compare And Swap? (например, производительность многоядерного процессора)

Здесь и пример на Java:

/**
 * Atomically increments by one the current value.
 *
 * @return the updated value
 */
public final int incrementAndGet() {
    for (;;) {
        int current = get();
        int next = current + 1;
        if (compareAndSet(current, next))
            return next;
    }
}

=== РЕДАКТИРОВАТЬ===

Пожалуйста, расскажите об этом специально для одноядерных процессоров.


c++ java compare-and-swap lock-free lockless
person WoooHaaaa    schedule 03.06.2013    source источник
comment
@Neyt: спасибо за удаление неправильного тега, но, пожалуйста, добавьте правильный, когда он есть. Есть тег [compare-and-swap].   -  person Peter Cordes    schedule 29.11.2018
comment
@PeterCordes Действительно, не думал, что у него будет собственный тег, спасибо.   -  person Neyt    schedule 29.11.2018
comment
@Neyt: я не уверен, почему cmpxchg также нуждается в собственном теге, но CAS и load-linked + store-conditional являются двумя основными строительными блоками для атомарных операций RMW; аппаратное обеспечение обычно обеспечивает одно или другое. en.wikipedia.org/wiki/Compare-and-swap И это так. приходят с проблемами, характерными для CAS, такими как проблема ABA. Таким образом, это не так произвольно, как наличие тегов для каждого возможного атомарного RMW, которое предоставляет аппаратное обеспечение (например, x86 может выполнять атомарное приращение и различные другие вещи без цикла повторных попыток CAS).   -  person Peter Cordes    schedule 30.11.2018

Ответы (2)


arrow_upward
3
arrow_downward

Преимущество: нет блокировок, следовательно, нет взаимоблокировок и, как правило, лучшая масштабируемость.

Недостаток: риск голодания (если алгоритм еще и без ожидания, но это в общем-то не так)

Алгоритмы edit:wait-free выполняют некоторые операции, когда проигрывают гонку CAS. Вместо занятой попытки/запуска.

person Zim-Zam O'Pootertoot    schedule 03.06.2013

arrow_upward
0
arrow_downward

Создавайте цикл повторных попыток CAS в исходном коде только в том случае, если нет встроенного языка, реализующего требуемую атомарную операцию. Аппаратное обеспечение (особенно x86) часто работает лучше.

Java AtomicInteger имеет getAndIncrement() и incrementAndGet() (по крайней мере, начиная с Java 7), который упрощает для JVM JIT-компиляцию в asm, что более эффективно, чем фактический цикл повторных попыток CAS. Это похоже на std::atomic::fetch_add() С++ 11. См. также Практическое использование AtomicInteger.

В x86 вы хотите, чтобы ваша JVM использовала преимущества аппаратной поддержки x86 для этой операции. Это гораздо более вероятно, если вы используете функцию, которая сопоставляется непосредственно с ней, вместо цикла повторных попыток CAS. что оптимизатору придется много работать, чтобы оптимизировать реализацию без циклов.

(Существует аппаратный арбитраж шины/кэша для операций locked, когда несколько ядер ЦП соревнуются за одну и ту же строку кэша; только один поток за раз может фактически владеть строкой кэша и выполнять приращение. Можно возразить, что это wait-free, даже если «шаги» — это тактовые циклы, а не инструкции процессора: вероятно, нижняя верхняя граница того, как долго операция locked может ждать в любой данной системе, даже если все другие ядра работают с одной и той же строкой кэша.)

; possible x86 implementation of incrementAndGet() for a 32-bit integer
; which you'd hopefully get (after inlining and so on)

mov    eax,1
lock   xadd [mem], eax       ; atomically do [mem]+=eax, and put the old value in eax
inc    eax                   ; old_value += 1 to get the new value
; result in EAX

Не требуется петля.

На машинах LL/SC (большинство не-x86, таких как ARM, PowerPC, MIPS) будет цикл повторных попыток, но это не совсем CAS. И цикл повторных попыток CAS на машине LL/SC имеет дополнительные накладные расходы. Это очень незначительно, но определенно лучше позволить JVM видеть атомарную операцию, которую вы хотите напрямую. См. Атомарная очистка младшего ненулевого бита целого числа без знака для более подробного обсуждения CAS и LL/SC. Цикл CAS может оптимизироваться в чистую петлю LL/SC.

Этот вопрос также является примером случая, когда лучшим выбором (в исходном коде C++ или Java) является цикл повторных попыток CAS, потому что в языке нет атомарного примитива, который делает то, что вы хотите. (Как и любое обычное оборудование).

person Peter Cordes    schedule 16.08.2018