Понимание std :: atomic :: compare_exchange_weak () в C ++ 11

Question 1

bool compare_exchange_weak (T& expected, T val, ..);

compare_exchange_weak()является одним из примитивов сравнения-обмена, представленных в C ++ 11. Он слабый в том смысле, что возвращает false, даже если значение объекта равно expected. Это происходит из-за ложного сбоя на некоторых платформах, где для его реализации используется последовательность инструкций (вместо одной, как на x86). На таких платформах переключение контекста, перезагрузка того же адреса (или строки кэша) другим потоком и т. Д. Могут привести к сбою примитива. Дело в том, что операция spuriousне выполняется из-за значения объекта (не равного expected). Вместо этого, это проблемы со сроками.

Но меня озадачивает то, что сказано в стандарте C ++ 11 (ISO / IEC 14882),

29.6.5. Последствием ложного отказа является то, что почти все случаи использования слабого сравнения и обмена будут замкнутыми.

Почему он должен быть замкнутым почти во всех случаях ? Означает ли это, что мы будем зацикливаться, когда он выйдет из строя из-за ложных отказов? Если это так, то зачем мы сами используем compare_exchange_weak()и пишем цикл? Мы можем просто использовать то, compare_exchange_strong()что, я думаю, должно избавить нас от ложных сбоев. Каковы распространенные варианты использования compare_exchange_weak()?

Другой вопрос по теме. В своей книге «Параллелизм в C ++ в действии» Энтони говорит:

//Because compare_exchange_weak() can fail spuriously, it must typically
//be used in a loop:

bool expected=false;
extern atomic<bool> b; // set somewhere else
while(!b.compare_exchange_weak(expected,true) && !expected);

//In this case, you keep looping as long as expected is still false,
//indicating that the compare_exchange_weak() call failed spuriously.

Почему !expectedесть условие цикла? Есть ли это для предотвращения того, чтобы все потоки могли голодать и не продвигаться в течение некоторого времени?

Изменить: (последний вопрос)

На платформах, на которых не существует единой аппаратной инструкции CAS, как слабая, так и сильная версии реализованы с использованием LL / SC (например, ARM, PowerPC и т. Д.). Так есть ли разница между следующими двумя циклами? Зачем, если есть? (На мой взгляд, они должны иметь аналогичную производительность.)

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_weak(..))
{ .. }

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_strong(..)) 
{ .. }

Я подхожу к этому последнему вопросу, который вы, ребята, все упомянули, что, возможно, внутри цикла есть разница в производительности. Это также упоминается в стандарте C ++ 11 (ISO / IEC 14882):

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

Но, как было проанализировано выше, две версии в цикле должны давать одинаковую / похожую производительность. Что мне не хватает?

Question 2

Зачем делать обмен в цикле?

Обычно вы хотите, чтобы ваша работа была выполнена до того, как вы двинетесь дальше, поэтому вы включаете compare_exchange_weakцикл, чтобы он пытался обмениваться до тех пор, пока не завершится успешно (то есть не вернется true).

Обратите внимание, что также compare_exchange_strongчасто используется в цикле. Он не дает сбоя из-за ложного сбоя, но сбой происходит из-за одновременной записи.

Зачем использовать `weak`вместо `strong`?

Довольно просто: ложные отказы случаются не часто, поэтому это не сильно снижает производительность. Напротив, терпимость к такому отказу позволяет гораздо более эффективно реализовать weakверсию (по сравнению с strong) на некоторых платформах: strongвсегда необходимо проверять ложный отказ и маскировать его. Это дорого.

Таким образом, weakиспользуется, потому что он намного быстрее, чем strongна некоторых платформах.

Когда `weak`и когда использовать `strong`?

В справочнике указаны подсказки, когда использовать, weakа когда использовать strong:

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

Так что ответ кажется довольно простым для запоминания: если вам придется ввести цикл только из-за ложного сбоя, не делайте этого; использовать strong. Если у вас все равно есть петля, используйте weak.

Почему `!expected`в примере

Это зависит от ситуации и ее желаемой семантики, но обычно не требуется для корректности. Если его опустить, семантика будет очень похожа. Только в том случае, если другой поток может сбросить значение до false, семантика может немного измениться (но я не могу найти значимого примера, в котором вы бы этого хотели). См. Комментарий Тони Д. для подробного объяснения.

Это просто быстрый способ, когда другой поток пишет true: Затем мы прерываем работу вместо того, чтобы пытаться написать trueснова.

О вашем последнем вопросе

Но, как было проанализировано выше, две версии в цикле должны давать одинаковую / похожую производительность. Что мне не хватает?

Из Википедии :

Реальные реализации LL / SC не всегда оказываются успешными, если нет одновременных обновлений в рассматриваемой области памяти. Любые исключительные события между двумя операциями, такие как переключение контекста, другая ссылка загрузки или даже (на многих платформах) другая операция загрузки или сохранения, вызовут ложный сбой условия сохранения. Старые реализации потерпят неудачу, если будут передаваться какие-либо обновления по шине памяти.

Так, например, LL / SC ложно откажет при переключении контекста. Теперь сильная версия принесет свой «небольшой цикл», чтобы обнаружить этот ложный отказ и замаскировать его, повторив попытку. Обратите внимание, что этот собственный цикл также более сложен, чем обычный цикл CAS, поскольку он должен различать ложный отказ (и маскировать его) и сбой из-за одновременного доступа (что приводит к возврату со значением false). В слабой версии такого собственного шлейфа нет.

Поскольку в обоих примерах вы предоставляете явный цикл, для сильной версии просто не нужно иметь маленький цикл. Следовательно, в примере с strongверсией проверка на сбой выполняется дважды; один раз compare_exchange_strong(что более сложно, поскольку он должен различать ложный сбой и одновременный доступ) и один раз вашим циклом. В этой дорогой проверке нет необходимости, и поэтому здесь weakбудет быстрее.

Также обратите внимание, что ваш аргумент (LL / SC) - всего лишь одна возможность реализовать это. Есть другие платформы, которые имеют даже разные наборы команд. Вдобавок (и что более важно) обратите внимание, что std::atomicдолжны поддерживаться все операции для всех возможных типов данных , поэтому, даже если вы объявите структуру в десять миллионов байт, вы можете использовать compare_exchangeее. Даже на ЦП, у которого есть CAS, вы не можете CAS десять миллионов байтов, поэтому компилятор сгенерирует другие инструкции (возможно, получение блокировки, за которым следует неатомарное сравнение и свопинг, за которым следует снятие блокировки). А теперь подумайте, сколько всего может произойти при обмене десятью миллионами байтов. Таким образом, хотя ложная ошибка может быть очень редкой для 8-байтовых обменов, в этом случае она может быть более распространенной.

Вкратце, C ++ дает вам две семантики: one ( weak) и «я сделаю это обязательно, независимо от того, сколько плохих вещей может случиться между ними» one ( strong). Как это реализовано на разных типах данных и на разных платформах - это совершенно другая тема. Не привязывайте свою ментальную модель к реализации на вашей конкретной платформе; стандартная библиотека предназначена для работы с большим количеством архитектур, чем вы можете себе представить. Единственный общий вывод, который мы можем сделать, заключается в том, что гарантировать успех обычно труднее (и, следовательно, может потребоваться дополнительная работа), чем просто попытаться оставить место для возможной неудачи.

Question 3

Почему он должен быть замкнутым почти во всех случаях ?

Потому что, если вы не зацикливаетесь и он ложно терпит неудачу, ваша программа не сделала ничего полезного - вы не обновили атомарный объект и не знаете, каково его текущее значение (исправление: см. Комментарий Кэмерона ниже). Если звонок не делает ничего полезного, какой смысл это делать?

Означает ли это, что мы будем зацикливаться, когда он выйдет из строя из-за ложных отказов?

Да.

Если это так, то зачем мы сами используем compare_exchange_weak()и пишем цикл? Мы можем просто использовать compare_exchange_strong (), который, я думаю, должен избавить нас от ложных сбоев. Каковы распространенные варианты использования compare_exchange_weak ()?

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

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

Почему !expectedесть условие цикла?

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

Редактировать:

Но, как было проанализировано выше, две версии в цикле должны давать одинаковую / похожую производительность. Что мне не хватает?

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

Слабая форма просто возвращается при ложном сбое, она не пытается повторить попытку.

Question 4

Я сам пытаюсь ответить на этот вопрос, просмотрев различные онлайн-ресурсы (например, этот и этот ), стандарт C ++ 11, а также ответы, приведенные здесь.

Связанные вопросы объединяются (например, « почему! Ожидается? » Объединяется с «зачем помещать compare_exchange_weak () в цикл? »), И даются соответствующие ответы.

Почему compare_exchange_weak () должен быть в цикле почти во всех случаях использования?

Типичный образец A

Вам нужно добиться атомарного обновления на основе значения атомарной переменной. Ошибка означает, что переменная не обновлена до желаемого значения, и мы хотим повторить попытку. Обратите внимание, что нас действительно не волнует, произойдет ли сбой из-за одновременной записи или ложного сбоя. Но мы все равно , что это нам , что сделать это изменение.

expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));

Реальный пример - несколько потоков одновременно добавляют элемент в односвязный список. Каждый поток сначала загружает указатель головы, выделяет новый узел и добавляет заголовок к этому новому узлу. Наконец, он пытается поменять местами новый узел с головой.

Другой пример - реализация мьютекса с использованием std::atomic<bool>. По большей мере один поток может войти в критическую секцию в то время, в зависимости от того, какой поток первого набора , currentчтобы trueи выйти из цикла.

Типичный образец B

Это на самом деле образец, упомянутый в книге Энтони. В отличие от шаблона A, вы хотите, чтобы атомарная переменная обновлялась один раз, но вам все равно, кто это делает. Пока он не обновлен, попробуйте еще раз. Обычно это используется с логическими переменными. Например, вам нужно реализовать триггер для движения конечного автомата. Независимо от того, какая нить нажимает на курок.

expected = false;
// !expected: if expected is set to true by another thread, it's done!
// Otherwise, it fails spuriously and we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

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

Тем не менее, использование compare_exchange_weak()вне цикла должно быть редкостью . Напротив, есть случаи, когда используется сильная версия. Например,

bool criticalSection_tryEnter(lock)
{
  bool flag = false;
  return lock.compare_exchange_strong(flag, true);
}

compare_exchange_weak здесь не подходит, потому что, когда он возвращается из-за ложного сбоя, вероятно, что никто еще не занимает критическую секцию.

Голодающая нить?

Стоит упомянуть один момент: что произойдет, если ложные сбои будут продолжать происходить, что приведет к истощению потока? Теоретически это могло произойти на платформах, когда compare_exchange_XXX()реализовано как последовательность инструкций (например, LL / SC). Частый доступ к одной и той же строке кэша между LL и SC приведет к постоянным ложным сбоям. Более реалистичный пример связан с тупым планированием, при котором все параллельные потоки чередуются следующим образом.

Time
 |  thread 1 (LL)
 |  thread 2 (LL)
 |  thread 1 (compare, SC), fails spuriously due to thread 2's LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1's LL
 |  thread 2 (LL)
 v  ..

Это может случиться?

К счастью, это не произойдет вечно, благодаря тому, что требует C ++ 11:

Реализации должны гарантировать, что слабые операции сравнения и обмена не будут последовательно возвращать false, если только атомарный объект не имеет значение, отличное от ожидаемого, или если не происходят одновременные модификации атомарного объекта.

Почему мы не используем compare_exchange_weak () и сами пишем цикл? Мы можем просто использовать compare_exchange_strong ().

Это зависит.

Случай 1: Когда оба должны использоваться внутри цикла. С ++ 11 говорит:

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

На x86 (по крайней мере, в настоящее время. Возможно, однажды для повышения производительности он прибегнет к такой же схеме, как LL / SC, когда будет добавлено больше ядер), слабая и сильная версии по сути одинаковы, потому что обе сводятся к одной инструкции cmpxchg. На некоторых других платформах, где compare_exchange_XXX()это не реализовано атомарно (это означает, что не существует единого аппаратного примитива), слабая версия внутри цикла может выиграть битву, потому что сильная версия должна будет обрабатывать ложные сбои и соответственно повторять попытки.

Но,

в редких случаях мы можем предпочесть compare_exchange_strong()вариант compare_exchange_weak()даже в цикле. Например, когда есть много дел между загрузкой атомарной переменной и обменом вычисленного нового значения (см. function()Выше). Если сама атомарная переменная не меняется часто, нам не нужно повторять дорогостоящие вычисления для каждого ложного отказа. Вместо этого мы можем надеяться, что compare_exchange_strong()«поглотим» такие сбои, и мы повторяем расчет только тогда, когда он терпит неудачу из-за реального изменения значения.

Случай 2: когда compare_exchange_weak() нужно использовать только внутри цикла. С ++ 11 также говорит:

Когда для слабого сравнения и обмена требуется петля, а для сильного - нет, предпочтительнее сильное.

Обычно это случается, когда вы выполняете цикл только для устранения ложных отказов слабой версии. Вы повторяете попытку до тех пор, пока обмен не будет успешным или неудачным из-за одновременной записи.

expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

В лучшем случае это изобретает колеса заново и работает так же, как compare_exchange_strong(). Хуже? Этот подход не позволяет в полной мере использовать все преимущества машин, которые обеспечивают аппаратное непостоянное сравнение и обмен .

Наконец, если вы выполняете цикл для других вещей (например, см. «Типичный шаблон A» выше), то есть хороший шанс, что он compare_exchange_strong()также будет помещен в цикл, что возвращает нас к предыдущему случаю.

Question 5

Хорошо, мне нужна функция, которая выполняет атомарный сдвиг влево. У моего процессора нет встроенной операции для этого, а в стандартной библиотеке нет функции для этого, поэтому похоже, что я пишу свою собственную. Вот оно:

void atomicLeftShift(std::atomic<int>* var, int shiftBy)
{
    do {
        int oldVal = std::atomic_load(var);
        int newVal = oldVal << shiftBy;
    } while(!std::compare_exchange_weak(oldVal, newVal));
}

Теперь есть две причины, по которым цикл может выполняться более одного раза.

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

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

Однако менее быстрым является дополнительный код, который требуется сильному CAS, чтобы обернуть слабый CAS, чтобы быть сильным. Этот код мало что делает, когда слабый CAS работает успешно ... но когда он терпит неудачу, сильному CAS нужно проделать некоторую детективную работу, чтобы определить, был ли это Случай 1 или Случай 2. Эта детективная работа принимает форму второго цикла, эффективно внутри моего собственного цикла. Две вложенные петли. Представьте, что ваш учитель алгоритмов смотрит на вас прямо сейчас.

И как я уже упоминал, меня не волнует результат этой детективной работы! В любом случае я собираюсь переделать CAS. Таким образом, использование сильного CAS абсолютно ничего не дает мне и теряет небольшую, но измеримую эффективность.

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

Question 6

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

Видно, что слабая версия в большинстве случаев быстрее, но в случае ложного сбоя она становится медленнее. А сильная версия - это версия, у которой нет возможности ложного отказа, но она почти всегда работает медленнее.

Для меня главное различие в том, как эти две версии решают проблему ABA:

слабая версия будет успешной только в том случае, если никто не коснулся строки кеша между загрузкой и сохранением, поэтому она на 100% обнаружит проблему ABA.

сильная версия потерпит неудачу только в случае неудачного сравнения, поэтому она не обнаружит проблему ABA без дополнительных мер.

Итак, теоретически, если вы используете слабую версию в слабоупорядоченной архитектуре, вам не нужен механизм обнаружения ABA, и реализация будет намного проще, что даст лучшую производительность.

Но на x86 (строго упорядоченная архитектура) слабая и сильная версии одинаковы, и обе страдают от проблемы ABA.

Таким образом, если вы пишете полностью кросс-платформенный алгоритм, вам все равно необходимо решить проблему ABA, поэтому использование слабой версии не дает выигрыша в производительности, но снижает производительность за обработку ложных сбоев.

В заключение - по причинам переносимости и производительности сильная версия всегда является лучшим или равным вариантом.

Слабая версия может быть лучшим вариантом, только если она позволяет полностью пропустить контрмеры ABA или ваш алгоритм не заботится о ABA.

Answer 1

bool compare_exchange_weak (T& expected, T val, ..);

compare_exchange_weak()является одним из примитивов сравнения-обмена, представленных в C ++ 11. Он слабый в том смысле, что возвращает false, даже если значение объекта равно expected. Это происходит из-за ложного сбоя на некоторых платформах, где для его реализации используется последовательность инструкций (вместо одной, как на x86). На таких платформах переключение контекста, перезагрузка того же адреса (или строки кэша) другим потоком и т. Д. Могут привести к сбою примитива. Дело в том, что операция spuriousне выполняется из-за значения объекта (не равного expected). Вместо этого, это проблемы со сроками.

Но меня озадачивает то, что сказано в стандарте C ++ 11 (ISO / IEC 14882),

29.6.5. Последствием ложного отказа является то, что почти все случаи использования слабого сравнения и обмена будут замкнутыми.

Почему он должен быть замкнутым почти во всех случаях ? Означает ли это, что мы будем зацикливаться, когда он выйдет из строя из-за ложных отказов? Если это так, то зачем мы сами используем compare_exchange_weak()и пишем цикл? Мы можем просто использовать то, compare_exchange_strong()что, я думаю, должно избавить нас от ложных сбоев. Каковы распространенные варианты использования compare_exchange_weak()?

Другой вопрос по теме. В своей книге «Параллелизм в C ++ в действии» Энтони говорит:

//Because compare_exchange_weak() can fail spuriously, it must typically
//be used in a loop:

bool expected=false;
extern atomic<bool> b; // set somewhere else
while(!b.compare_exchange_weak(expected,true) && !expected);

//In this case, you keep looping as long as expected is still false,
//indicating that the compare_exchange_weak() call failed spuriously.

Почему !expectedесть условие цикла? Есть ли это для предотвращения того, чтобы все потоки могли голодать и не продвигаться в течение некоторого времени?

Изменить: (последний вопрос)

На платформах, на которых не существует единой аппаратной инструкции CAS, как слабая, так и сильная версии реализованы с использованием LL / SC (например, ARM, PowerPC и т. Д.). Так есть ли разница между следующими двумя циклами? Зачем, если есть? (На мой взгляд, они должны иметь аналогичную производительность.)

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_weak(..))
{ .. }

// use LL/SC (or CAS on x86) and ignore/loop on spurious failures
while (!compare_exchange_strong(..)) 
{ .. }

Я подхожу к этому последнему вопросу, который вы, ребята, все упомянули, что, возможно, внутри цикла есть разница в производительности. Это также упоминается в стандарте C ++ 11 (ISO / IEC 14882):

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

Но, как было проанализировано выше, две версии в цикле должны давать одинаковую / похожую производительность. Что мне не хватает?

Answer 2

4

Что касается первого вопроса, во многих случаях вам все равно нужно зацикливаться (независимо от того, используете ли вы сильную или слабую версию), а слабая версия может иметь лучшую производительность, чем сильная.

TC

Answer 3

2

И слабая, и сильная CAS реализуются «с использованием LL / SC», точно так же, как и пузырьковая, и быстрая сортировка реализованы «с использованием свопа»; то есть в том смысле, что это примитивная операция, используемая для выполнения задачи. То, что они оборачивают вокруг LL / SC, очень отличается. Слабый CAS - это просто LL / SC. Strong CAS - это LL / SC с множеством других вещей.

Sneftel 08

Answer 4

1

forum.manning.com/posts/list/33062.page помогает?

Вт Xiaomi

Answer 5

@TuXiaomi с ответом в этой ссылке, я не могу понять, почему «слабая версия даст лучшую производительность на некоторых платформах», как указано в Стандарте.

Deqing

Answer 6

@Deqing В других случаях compare_exchange_weak может ложно выйти из строя из-за прерываний или действий других процессоров или потоков. На этих платформах compare_exchange_strong фактически представляет собой цикл для compare_exchange_weak - если он ошибочно завершился неудачно, он снова зацикливается. Помогает? Может я ошибаюсь

Вт Xiaomi

Answer 7

Зачем делать обмен в цикле?

Обычно вы хотите, чтобы ваша работа была выполнена до того, как вы двинетесь дальше, поэтому вы включаете compare_exchange_weakцикл, чтобы он пытался обмениваться до тех пор, пока не завершится успешно (то есть не вернется true).

Обратите внимание, что также compare_exchange_strongчасто используется в цикле. Он не дает сбоя из-за ложного сбоя, но сбой происходит из-за одновременной записи.

Зачем использовать `weak`вместо `strong`?

Довольно просто: ложные отказы случаются не часто, поэтому это не сильно снижает производительность. Напротив, терпимость к такому отказу позволяет гораздо более эффективно реализовать weakверсию (по сравнению с strong) на некоторых платформах: strongвсегда необходимо проверять ложный отказ и маскировать его. Это дорого.

Таким образом, weakиспользуется, потому что он намного быстрее, чем strongна некоторых платформах.

Когда `weak`и когда использовать `strong`?

В справочнике указаны подсказки, когда использовать, weakа когда использовать strong:

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

Так что ответ кажется довольно простым для запоминания: если вам придется ввести цикл только из-за ложного сбоя, не делайте этого; использовать strong. Если у вас все равно есть петля, используйте weak.

Почему `!expected`в примере

Это зависит от ситуации и ее желаемой семантики, но обычно не требуется для корректности. Если его опустить, семантика будет очень похожа. Только в том случае, если другой поток может сбросить значение до false, семантика может немного измениться (но я не могу найти значимого примера, в котором вы бы этого хотели). См. Комментарий Тони Д. для подробного объяснения.

Это просто быстрый способ, когда другой поток пишет true: Затем мы прерываем работу вместо того, чтобы пытаться написать trueснова.

О вашем последнем вопросе

Но, как было проанализировано выше, две версии в цикле должны давать одинаковую / похожую производительность. Что мне не хватает?

Из Википедии :

Реальные реализации LL / SC не всегда оказываются успешными, если нет одновременных обновлений в рассматриваемой области памяти. Любые исключительные события между двумя операциями, такие как переключение контекста, другая ссылка загрузки или даже (на многих платформах) другая операция загрузки или сохранения, вызовут ложный сбой условия сохранения. Старые реализации потерпят неудачу, если будут передаваться какие-либо обновления по шине памяти.

Так, например, LL / SC ложно откажет при переключении контекста. Теперь сильная версия принесет свой «небольшой цикл», чтобы обнаружить этот ложный отказ и замаскировать его, повторив попытку. Обратите внимание, что этот собственный цикл также более сложен, чем обычный цикл CAS, поскольку он должен различать ложный отказ (и маскировать его) и сбой из-за одновременного доступа (что приводит к возврату со значением false). В слабой версии такого собственного шлейфа нет.

Поскольку в обоих примерах вы предоставляете явный цикл, для сильной версии просто не нужно иметь маленький цикл. Следовательно, в примере с strongверсией проверка на сбой выполняется дважды; один раз compare_exchange_strong(что более сложно, поскольку он должен различать ложный сбой и одновременный доступ) и один раз вашим циклом. В этой дорогой проверке нет необходимости, и поэтому здесь weakбудет быстрее.

Также обратите внимание, что ваш аргумент (LL / SC) - всего лишь одна возможность реализовать это. Есть другие платформы, которые имеют даже разные наборы команд. Вдобавок (и что более важно) обратите внимание, что std::atomicдолжны поддерживаться все операции для всех возможных типов данных , поэтому, даже если вы объявите структуру в десять миллионов байт, вы можете использовать compare_exchangeее. Даже на ЦП, у которого есть CAS, вы не можете CAS десять миллионов байтов, поэтому компилятор сгенерирует другие инструкции (возможно, получение блокировки, за которым следует неатомарное сравнение и свопинг, за которым следует снятие блокировки). А теперь подумайте, сколько всего может произойти при обмене десятью миллионами байтов. Таким образом, хотя ложная ошибка может быть очень редкой для 8-байтовых обменов, в этом случае она может быть более распространенной.

Вкратце, C ++ дает вам две семантики: one ( weak) и «я сделаю это обязательно, независимо от того, сколько плохих вещей может случиться между ними» one ( strong). Как это реализовано на разных типах данных и на разных платформах - это совершенно другая тема. Не привязывайте свою ментальную модель к реализации на вашей конкретной платформе; стандартная библиотека предназначена для работы с большим количеством архитектур, чем вы можете себе представить. Единственный общий вывод, который мы можем сделать, заключается в том, что гарантировать успех обычно труднее (и, следовательно, может потребоваться дополнительная работа), чем просто попытаться оставить место для возможной неудачи.

Answer 8

«Используйте сильный, только если вы ни в коем случае не можете терпеть ложный отказ». - действительно ли существует алгоритм, который различает сбои из-за одновременной записи и ложные сбои? Все, о чем я могу думать, либо позволяет нам иногда пропускать обновления, либо нет, и в этом случае нам все равно нужен цикл.

Voo

Answer 9

3

@Voo: Обновленный ответ. Теперь подсказки из ссылки включены. Может быть алгоритм, который делает различие. Например, рассмотрим семантику «необходимо обновить»: обновление чего-либо должно быть выполнено ровно один раз, поэтому, если мы терпим неудачу из-за одновременной записи, мы знаем, что это сделал кто-то другой, и можем прервать выполнение. Если мы потерпели неудачу из-за ложного сбоя, значит, никто не обновил его, поэтому мы должны повторить попытку.

gexicide

Answer 10

8

« Почему в примере ожидается!? Это не нужно для правильности. Если это не будет, то будет получена та же семантика». - не так ... если, скажем, первый обмен терпит неудачу, потому что он bуже находит true, тогда - с expectedсейчас true- без && !expectedэтого зацикливается и пробует другой (глупый) обмен, trueи trueкоторый вполне может "успешно", тривиально выходя из whileцикла, но может показать осмысленно другое поведение , если bбы в то время изменился назад false, и в этом случае цикл будет продолжаться , и , возможно , в конечном счете , установить b true еще раз , прежде чем нарушать.

Тони Делрой

Answer 11

@TonyD: Хорошо, я должен это прояснить.

gexicide

Answer 12

Извините, ребята, я добавил еще один последний вопрос;)

Eric Z

Answer 13

Почему он должен быть замкнутым почти во всех случаях ?

Потому что, если вы не зацикливаетесь и он ложно терпит неудачу, ваша программа не сделала ничего полезного - вы не обновили атомарный объект и не знаете, каково его текущее значение (исправление: см. Комментарий Кэмерона ниже). Если звонок не делает ничего полезного, какой смысл это делать?

Означает ли это, что мы будем зацикливаться, когда он выйдет из строя из-за ложных отказов?

Да.

Если это так, то зачем мы сами используем compare_exchange_weak()и пишем цикл? Мы можем просто использовать compare_exchange_strong (), который, я думаю, должен избавить нас от ложных сбоев. Каковы распространенные варианты использования compare_exchange_weak ()?

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

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

Почему !expectedесть условие цикла?

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

Редактировать:

Но, как было проанализировано выше, две версии в цикле должны давать одинаковую / похожую производительность. Что мне не хватает?

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

Слабая форма просто возвращается при ложном сбое, она не пытается повторить попытку.

Answer 14

2

+1 Фактически точен по всем пунктам (в котором отчаянно нуждается Q).

Тони Делрой

Answer 15

Примерно you don't know what its current value isв 1-й точке, когда происходит ложный отказ, не должно ли текущее значение равняться ожидаемому значению в этот момент? В противном случае это был бы настоящий провал.

Eric Z

Answer 16

ИМО, как слабая, так и сильная версия реализованы с использованием LL / SC на платформах, на которых не существует единого аппаратного примитива CAS. Так почему для меня разница в производительности между while(!compare_exchange_weak(..))и while(!compare_exchange_strong(..))?

Eric Z

Answer 17

Извините, ребята, я добавил еще один последний вопрос.

Eric Z

Answer 18

1

@ Джонатан: Просто придираться, но вы делаете знать текущее значение , если оно не поддельно (конечно, независимо от того , что по - прежнему текущее значение к тому времени , когда Вы читаете переменную является другой вопрос полностью, но это независимо от того, слабый / сильный). Я использовал это, например, чтобы попытаться установить переменную, предполагая, что ее значение равно нулю, и в случае неудачи (ложной или нет) продолжайте попытки, но только в зависимости от фактического значения.

Кэмерон

Answer 19

Я сам пытаюсь ответить на этот вопрос, просмотрев различные онлайн-ресурсы (например, этот и этот ), стандарт C ++ 11, а также ответы, приведенные здесь.

Связанные вопросы объединяются (например, « почему! Ожидается? » Объединяется с «зачем помещать compare_exchange_weak () в цикл? »), И даются соответствующие ответы.

Почему compare_exchange_weak () должен быть в цикле почти во всех случаях использования?

Типичный образец A

Вам нужно добиться атомарного обновления на основе значения атомарной переменной. Ошибка означает, что переменная не обновлена до желаемого значения, и мы хотим повторить попытку. Обратите внимание, что нас действительно не волнует, произойдет ли сбой из-за одновременной записи или ложного сбоя. Но мы все равно , что это нам , что сделать это изменение.

expected = current.load();
do desired = function(expected);
while (!current.compare_exchange_weak(expected, desired));

Реальный пример - несколько потоков одновременно добавляют элемент в односвязный список. Каждый поток сначала загружает указатель головы, выделяет новый узел и добавляет заголовок к этому новому узлу. Наконец, он пытается поменять местами новый узел с головой.

Другой пример - реализация мьютекса с использованием std::atomic<bool>. По большей мере один поток может войти в критическую секцию в то время, в зависимости от того, какой поток первого набора , currentчтобы trueи выйти из цикла.

Типичный образец B

Это на самом деле образец, упомянутый в книге Энтони. В отличие от шаблона A, вы хотите, чтобы атомарная переменная обновлялась один раз, но вам все равно, кто это делает. Пока он не обновлен, попробуйте еще раз. Обычно это используется с логическими переменными. Например, вам нужно реализовать триггер для движения конечного автомата. Независимо от того, какая нить нажимает на курок.

expected = false;
// !expected: if expected is set to true by another thread, it's done!
// Otherwise, it fails spuriously and we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

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

Тем не менее, использование compare_exchange_weak()вне цикла должно быть редкостью . Напротив, есть случаи, когда используется сильная версия. Например,

bool criticalSection_tryEnter(lock)
{
  bool flag = false;
  return lock.compare_exchange_strong(flag, true);
}

compare_exchange_weak здесь не подходит, потому что, когда он возвращается из-за ложного сбоя, вероятно, что никто еще не занимает критическую секцию.

Голодающая нить?

Стоит упомянуть один момент: что произойдет, если ложные сбои будут продолжать происходить, что приведет к истощению потока? Теоретически это могло произойти на платформах, когда compare_exchange_XXX()реализовано как последовательность инструкций (например, LL / SC). Частый доступ к одной и той же строке кэша между LL и SC приведет к постоянным ложным сбоям. Более реалистичный пример связан с тупым планированием, при котором все параллельные потоки чередуются следующим образом.

Time
 |  thread 1 (LL)
 |  thread 2 (LL)
 |  thread 1 (compare, SC), fails spuriously due to thread 2's LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1's LL
 |  thread 2 (LL)
 v  ..

Это может случиться?

К счастью, это не произойдет вечно, благодаря тому, что требует C ++ 11:

Реализации должны гарантировать, что слабые операции сравнения и обмена не будут последовательно возвращать false, если только атомарный объект не имеет значение, отличное от ожидаемого, или если не происходят одновременные модификации атомарного объекта.

Почему мы не используем compare_exchange_weak () и сами пишем цикл? Мы можем просто использовать compare_exchange_strong ().

Это зависит.

Случай 1: Когда оба должны использоваться внутри цикла. С ++ 11 говорит:

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

На x86 (по крайней мере, в настоящее время. Возможно, однажды для повышения производительности он прибегнет к такой же схеме, как LL / SC, когда будет добавлено больше ядер), слабая и сильная версии по сути одинаковы, потому что обе сводятся к одной инструкции cmpxchg. На некоторых других платформах, где compare_exchange_XXX()это не реализовано атомарно (это означает, что не существует единого аппаратного примитива), слабая версия внутри цикла может выиграть битву, потому что сильная версия должна будет обрабатывать ложные сбои и соответственно повторять попытки.

Но,

в редких случаях мы можем предпочесть compare_exchange_strong()вариант compare_exchange_weak()даже в цикле. Например, когда есть много дел между загрузкой атомарной переменной и обменом вычисленного нового значения (см. function()Выше). Если сама атомарная переменная не меняется часто, нам не нужно повторять дорогостоящие вычисления для каждого ложного отказа. Вместо этого мы можем надеяться, что compare_exchange_strong()«поглотим» такие сбои, и мы повторяем расчет только тогда, когда он терпит неудачу из-за реального изменения значения.

Случай 2: когда compare_exchange_weak() нужно использовать только внутри цикла. С ++ 11 также говорит:

Когда для слабого сравнения и обмена требуется петля, а для сильного - нет, предпочтительнее сильное.

Обычно это случается, когда вы выполняете цикл только для устранения ложных отказов слабой версии. Вы повторяете попытку до тех пор, пока обмен не будет успешным или неудачным из-за одновременной записи.

expected = false;
// !expected: if it fails spuriously, we should try again.
while (!current.compare_exchange_weak(expected, true) && !expected);

В лучшем случае это изобретает колеса заново и работает так же, как compare_exchange_strong(). Хуже? Этот подход не позволяет в полной мере использовать все преимущества машин, которые обеспечивают аппаратное непостоянное сравнение и обмен .

Наконец, если вы выполняете цикл для других вещей (например, см. «Типичный шаблон A» выше), то есть хороший шанс, что он compare_exchange_strong()также будет помещен в цикл, что возвращает нас к предыдущему случаю.

Answer 20

Хорошо, мне нужна функция, которая выполняет атомарный сдвиг влево. У моего процессора нет встроенной операции для этого, а в стандартной библиотеке нет функции для этого, поэтому похоже, что я пишу свою собственную. Вот оно:

void atomicLeftShift(std::atomic<int>* var, int shiftBy)
{
    do {
        int oldVal = std::atomic_load(var);
        int newVal = oldVal << shiftBy;
    } while(!std::compare_exchange_weak(oldVal, newVal));
}

Теперь есть две причины, по которым цикл может выполняться более одного раза.

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

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

Однако менее быстрым является дополнительный код, который требуется сильному CAS, чтобы обернуть слабый CAS, чтобы быть сильным. Этот код мало что делает, когда слабый CAS работает успешно ... но когда он терпит неудачу, сильному CAS нужно проделать некоторую детективную работу, чтобы определить, был ли это Случай 1 или Случай 2. Эта детективная работа принимает форму второго цикла, эффективно внутри моего собственного цикла. Две вложенные петли. Представьте, что ваш учитель алгоритмов смотрит на вас прямо сейчас.

И как я уже упоминал, меня не волнует результат этой детективной работы! В любом случае я собираюсь переделать CAS. Таким образом, использование сильного CAS абсолютно ничего не дает мне и теряет небольшую, но измеримую эффективность.

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

Answer 21