Несколько потоков, пытающихся что-то CAS, не заблокированы (но не без ожидания). Один из потоков будет прогрессировать каждый раз, когда все будут пытаться использовать одно и то же значение old . https://en.wikipedia.org/wiki/Non-blocking_algorithm.
(Независимо от того, все ли потоки читают одно и то же значение old или кто-то видит результат CAS другого потока, зависит от времени и в основном от этого зависит, насколько много конфликтов.)
Это не похоже на обычный цикл ожидания ожидания, который просто ожидает какой-то операции неизвестной длины и может зависнуть на неопределенное время, если поток, удерживающий блокировку, не запланирован. В этом случае вы определенно захотите отступить, если ваш CAS не сможет получить блокировку, потому что вам определенно нужно подождать, пока другой поток что-то сделает, прежде чем вы сможете добиться успеха.
Обычно алгоритмы без блокировки используются в ситуациях с низким уровнем конкуренции, когда сложный экспоненциальный откат на самом деле не нужен. Это то, что говорит связанный ответ SO.
В этом ключ отличается от ситуации, упомянутой в статье Wiki: , когда многие потоки постоянно обновляют некоторую конкретную общую переменную . Это ситуация с высокой конкуренцией, поэтому, вероятно, лучше позволить одному потоку делать кучу обновлений подряд и поддерживать горячую строку в их L1d-кэше. (Предполагая, что вы используете CAS для реализации элементарной операции, которую аппаратное обеспечение не поддерживает напрямую, например, добавление FP с атомарной двойной точностью, где вы shared.CAS(old, old+1.0) или что-то в этом роде. Или как часть очереди без блокировки или чего-то еще.)
Если бы вы использовали цикл CAS, который на практике был весьма спорным, это могло бы помочь снизить общую пропускную способность, например: перед тем, как повторить попытку, выполните инструкцию x86 pause об ошибке, чтобы в строке кэша было меньше ядер. Или для очереди без блокировки, если вы обнаружите, что она заполнена или пуста, то это в основном ситуация с ожиданием другого потока, поэтому вам определенно следует вернуться назад.
Большинство архитектур, отличных от x86, имеют LL / SC в качестве атомарного примитива RMW , а не прямой аппаратный CAS. Построение CAS из LL / SC может неожиданно завершиться неудачей, если другие потоки даже читают строку кэша во время попытки CAS, поэтому не может быть гарантировано, что хотя бы один поток завершится успешно.
Надеюсь, разработчики аппаратного обеспечения пытаются заставить ЦП, которые делают LL / SC, противостоять случайным сбоям из-за конфликтов, но я не знаю подробностей. В этом случае откат может помочь избежать потенциальной блокировки.
(На оборудовании, где CAS не может внезапно выйти из строя из-за конфликта, livelock невозможен для чего-то вроде while(!shared.CAS(old, old<<1)){}.)
Руководство по оптимизации Intel содержит пример ожидания освобождения блокировки, когда они зацикливаются 1 << retry_count раз (до некоторого максимального коэффициента отката). Обратите внимание, что это , а не обычный цикл CAS, который является частью алгоритма без блокировки; это для реализации блокировки.
Откат ожидает освобождения блокировки , а не только из-за конкуренции за доступ к строке кэша, содержащей саму блокировку.
/// Intel's optimization manual
/// Example 2-2. Contended Locks with Increasing Back-off Example
/// from section 2.2.4 Pause Latency in Skylake Microarchitecture
/// (~140 cycles, up from ~10 in Broadwell, thus max backoff should be shorter)
/*******************/
/*Baseline Version */
/*******************/
// atomic {if (lock == free) then change lock state to busy}
while (cmpxchg(lock, free, busy) == fail)
{
while (lock == busy)
_mm_pause();
}
/*******************/
/*Improved Version */
/*******************/
int mask = 1;
int const max = 64; //MAX_BACKOFF
while (cmpxchg(lock, free, busy) == fail)
{
while (lock == busy)
{
for (int i=mask; i; --i){
_mm_pause();
}
mask = mask < max ? mask<<1 : max; // mask <<= 1 up to a max
}
}
Я обычно думал, что в ожидании блокировки вы хотите вращать только для чтения, а не пытаться продолжить с помощью cmpxchg. Я думаю, что этот пример от Intel только демонстрирует откат, а не другие части того, как оптимизировать блокировку, чтобы избежать задержки разблокировки потока.
В любом случае, помните, что пример не , как то, о чем мы говорим с очередью без блокировки или реализацией CAS-повторения атомарного добавления или другого примитива. Он ожидает, что другой поток снимет блокировку, , а не , просто отказ от использования нового значения, которое появилось между чтением старого значения и попыткой CAS в новом значении.