Как C ++ Standard предотвращает взаимоблокировку в мьютексе спин-блокировки с помощью memory_order_acquire и memory_order_release? - PullRequest
Новая
       96

Как C ++ Standard предотвращает взаимоблокировку в мьютексе спин-блокировки с помощью memory_order_acquire и memory_order_release?

3 голосов
/ 19 апреля 2020

TL: DR: если в реализации мьютекса используются операции получения и освобождения, может ли реализация выполнять переупорядочение во время компиляции, как это обычно разрешается, и перекрывать две критические секции, которые должны быть независимыми, от разных блокировок? Это может привести к потенциальной тупиковой ситуации.

Предположим, что мьютекс является реализацией std::atomic_flag: 

struct mutex
{
   void lock() 
   {
       while (lock.test_and_set(std::memory_order_acquire)) 
       {
          yield_execution();
       }
   }

   void unlock()
   {
       lock.clear(std::memory_order_release);
   }

   std::atomic_flag lock; // = ATOMIC_FLAG_INIT in pre-C++20
};

Пока все выглядит нормально, если использовать один такой мьютекс: std::memory_order_release синхронизируется с std::memory_order_acquire.

Использование std::memory_order_acquire / std::memory_order_release здесь не должно вызывать вопросов на первый взгляд. Они похожи на пример cppreference https://en.cppreference.com/w/cpp/atomic/atomic_flag

Теперь есть два мьютекса, защищающие разные переменные, и два потока, обращающиеся к ним в разном порядке: 

mutex m1;
data  v1;

mutex m2;
data  v2;

void threadA()
{
    m1.lock();
    v1.use();
    m1.unlock();

    m2.lock();
    v2.use();
    m2.unlock();
}

void threadB()
{
    m2.lock();
    v2.use();
    m2.unlock();

    m1.lock();
    v1.use();
    m1.unlock();
}

Операции освобождения может быть переупорядочен после несвязанной операции получения (несвязанная операция == более поздняя операция над другим объектом), поэтому выполнение может быть преобразовано следующим образом: 

mutex m1;
data  v1;

mutex m2;
data  v2;

void threadA()
{
    m1.lock();
    v1.use();

    m2.lock();
    m1.unlock();

    v2.use();
    m2.unlock();
}

void threadB()
{
    m2.lock();
    v2.use();

    m1.lock();
    m2.unlock();

    v1.use();
    m1.unlock();
}

Таким образом, похоже, что существует тупик.

Вопросы:

  1. Как Standard предотвращает наличие таких мьютексов?
  2. Каков наилучший способ, чтобы мьютекс спин-блокировки не страдал от этой проблемы?
  3. Может ли немодифицированный мьютекс из верхней части этого поста использоваться в некоторых случаях?

(не является дубликатом семантик C ++ 11 memory_order_acquire и memory_order_release? , хотя он находится в та же область)

1 Ответ

4 голосов
/ 19 апреля 2020

В стандарте ISO C ++ нет проблем; он не различает guish время компиляции и переупорядочение во время выполнения, и код все еще должен выполнить , как если бы выполнялся в исходном порядке на абстрактной машине C ++. Таким образом, эффекты m2.test_and_set(std::memory_order_acquire) попытки захватить 2-ю блокировку могут стать видимыми для других потоков, в то же время удерживая первый (т. Е. До m1.reset), но неудача там не может помешать освобождению m1.

Единственный способ, которым у нас возникнет проблема, - это если время компиляции переупорядочить, прибавив этот порядок в asm для некоторой машины, так что m2 повторная попытка блокировки l oop должна была завершиться до того, как фактически освобождая m1.

Кроме того, ISO C ++ определяет порядок только в терминах синхронизаций и того, что можно увидеть, а не в терминах операций re , относящихся к некоторому новому порядку. , Это будет означать, что существует какой-то порядок. Ни один порядок, с которым могут согласиться несколько потоков, даже не гарантированно существует для отдельных объектов, если только вы не используете операции seq_cst. (И порядок модификации для каждого объекта в отдельности гарантированно существует.)

Односторонняя барьерная модель операций захвата и выпуска (как на диаграмме в https://preshing.com/20120913/acquire-and-release-semantics) представляет собой удобный способ думать о вещах и соответствует реальности для чистых загрузок и чистых хранилищ, например, на x86 и AArch64. Но что касается языковой адвокатуры, это не то, как стандарт ISO C ++ определяет вещи.

Вы переупорядочиваете целую повторную попытку l oop, а не просто одно приобретение

Переупорядочение операции atomic через длительный l oop является теоретической проблемой, допускаемой стандартом C ++. P0062R1: Когда компиляторы должны оптимизировать атомарность? указывает на то, что задержка магазина до долгого времени l oop технически разрешена формулировкой стандарта 1.10p28:

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

Но потенциально бесконечное l oop может нарушить это, не будучи конечным, например, в случае тупика, поэтому компиляторы не должны этого делать.

Это не "просто" качество - Внедрение вопроса. успешная блокировка мьютекса - это операция получения, но вы должны , а не смотреть на попытку l oop как одну операцию получения. Любой здравомыслящий компилятор не будет.

(Классифицированный пример того, что агрессивная атомная оптимизация может сломать, - это индикатор выполнения, где компилятор отбирает все расслабленные хранилища из всех oop, а затем сворачивает все мертвые хранилища в одном окончательном хранилище на 100%. См. также этот вопрос и ответ - текущие компиляторы этого не делают, и в основном обрабатывают atomic как volatile atomic до тех пор, пока C ++ не решит проблему предоставления программистам возможности сообщите компилятору, когда атомика может / не может быть оптимизирована безопасно.)

...