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

Ответ 1

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

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

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

Типичный шаблон A

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

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

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

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

Типичный шаблон B

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

expected = false;
// !expected: if expected is set to true by another thread, it 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 LL
 |  thread 1 (LL)
 |  thread 2 (compare, SC), fails spuriously due to thread 1 LL
 |  thread 2 (LL)
 v  ..

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

Это не произойдет навсегда, к счастью, благодаря тому, что требует С++ 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() также должен быть помещен в цикл, что возвращает нас к предыдущему случаю.

Ответ 2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Из Wikipedia:

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

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

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

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

Итак, в двух словах, С++ дает вам две семантики, "лучшее усилие" (weak) и "Я сделаю это наверняка, независимо от того, сколько плохих вещей может произойти между ними" (strong). Как это реализовано на разных типах данных и платформах, это совершенно другая тема. Не связывайте свою ментальную модель с реализацией на вашей конкретной платформе; стандартная библиотека предназначена для работы с большим количеством архитектур, чем вы могли бы знать. Единственный общий вывод, который мы можем сделать, состоит в том, что гарантировать успех обычно сложнее (и, следовательно, может потребоваться дополнительная работа), чем просто попытка и выход из комнаты для возможного отказа.

Ответ 3

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

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

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

Да.

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

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

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

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

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

Edit:

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

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

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

Ответ 4

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

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));
}

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

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

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

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

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

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