Неужели магазин Atomi c переупорядочен перед выпуском? (аналогично с загрузкой / приобретением)

Question

Я прочитал в спецификациях en.cppreference.com упрощенные операции над атомами:

"[...] гарантирует только атомарность и порядок модификации согласованность. "

Итак, я спрашивал себя, будет ли работать такой" порядок модификации ", когда вы работаете с одной и той же переменной atomi c или разными.

In мой код У меня есть дерево атомов c, где поток сообщений с низким приоритетом, основанный на событиях, заполняет, какой узел должен быть обновлен, сохраняя некоторые данные на красном «1» атоме c (см. рисунок), используя memory_order_relaxed. Затем он продолжает писать в своем родителе, используя fetch_or, чтобы узнать, какой дочерний атом c был обновлен. Каждый атом c поддерживает до 64 бит, поэтому я заполняю бит 1 красной операцией '2'. Это продолжается до тех пор, пока root атомы c, которые также помечены с использованием fetch_or, но с использованием этого времени memory_order_release.

Затем быстрый, в режиме реального времени, не блокируемый, поток загружает управляющий атом c (с memory_order_acquire) и считывает, для каких битов он включен. Затем он рекурсивно обновляет дочернюю атомику с memory_order_relaxed. И именно так я синхронизирую c своих данных с каждым циклом потока с высоким приоритетом.

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

Другими словами, как говорит Титл, расслабленные магазины переупорядочены между ними до выпуска? Я не возражаю против не-атоми c переменные переупорядочены. Псевдокод, предположим, что [x, y, z, control] - это атомы c и с начальными значениями 0:

Event thread:
z = 1; // relaxed
y = 1; // relaxed
x = 1; // relaxed;
control = 0; // release

Real time thread (loop):
load control; // acquire
load x; // relaxed
load y; // relaxed
load z; // relaxed

Интересно, будет ли в потоке реального времени это всегда так: x < = y <= z. Чтобы проверить, что я написал эту небольшую программу: </p>

#define _ENABLE_ATOMIC_ALIGNMENT_FIX 1
#include <atomic>
#include <iostream>
#include <thread>
#include <assert.h>
#include <array>

using namespace std;
constexpr int numTries = 10000;
constexpr int arraySize = 10000;
array<atomic<int>, arraySize> tat;
atomic<int> tsync {0};

void writeArray()
{
    // Stores atomics in reverse order
    for (int j=0; j!=numTries; ++j)
    {
        for (int i=arraySize-1; i>=0; --i)
        {
            tat[i].store(j, memory_order_relaxed);
        }
        tsync.store(0, memory_order_release);
    }
}

void readArray()
{
    // Loads atomics in normal order
    for (int j=0; j!=numTries; ++j)
    {
        bool readFail = false;
        tsync.load(memory_order_acquire);

        int minValue = 0;
        for (int i=0; i!=arraySize; ++i)
        {
            int newValue = tat[i].load(memory_order_relaxed);
            // If it fails, it stops the execution
            if (newValue < minValue)
            {
                readFail = true;
                cout << "fail " << endl;
                break;
            }
            minValue = newValue;
        }

        if (readFail) break;
    }
}


int main()
{
    for (int i=0; i!=arraySize; ++i)
    {
        tat[i].store(0);
    }

    thread b(readArray);
    thread a(writeArray);

    a.join();
    b.join();
}

Как это работает: Существует массив атомов c. Одна нить хранится с упорядоченным упорядочением в обратном порядке и заканчивается хранением контрольных атомов c с упорядоченным выпуском.

Другой поток загружается с порядком получения, который управляет атомами c, затем он загружает с расслабленным атомом c остальные значения массива. Так как родители не должны обновляться раньше детей, newValue всегда должно быть равно или больше, чем oldValue.

Я выполнил эту программу на своем компьютере несколько раз, отладку и выпуск, и он не ' Т триггер неудачу. Я использую обычный x64 процессор Intel i7.

Итак, можно ли предположить, что расслабленные хранилища с несколькими атомами сохраняют «порядок модификации», по крайней мере, когда они синхронизируются c с элементом управления атоми c и приобретать / выпускать

Answer 1

К сожалению, вы очень мало узнаете о том, что поддерживает стандарт, экспериментально с x86_64, потому что x86_64 так хорошо себя ведет. В частности, если вы не укажете _seq_cst :

• все операции чтения действительно _acquire

• все записи фактически _release

, если они не пересекают границу строки кэша. И:

• все операции чтения-изменения-записи эффективно seq_cst

За исключением того, что компилятор (также) разрешен изменить порядок _relaxed операций.

Вы упомянули об использовании _relaxed fetch_or ... и если я правильно понимаю, вы можете быть разочарованы, узнав, что это не менее дорого чем seq_cst , и требует инструкции с префиксом LOCK, несущей все накладные расходы.

---

Но да, операции _relaxed atomi c неотличимо от обычных операций, что касается порядка. Так что да, они могут быть переупорядочены по другим _relaxed atomi c операциям, а также не-atomi c операциям - компилятором и / или машиной. [Хотя, как отмечалось, на x86_64, а не на машине.]

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

Теперь, ключевая вещь, которую нужно понять, это то, что просто сделать магазин _release недостаточно, значение то, что сохранено, должно быть однозначным сигналом для нагрузки _acquire о том, что хранилище произошло. В противном случае, как загрузка может сказать?

Обычно пара _release / _acquire , как эта, используется для синхронизации доступа к некоторому набору данных. Как только эти данные «готовы», магазин _release сообщает об этом. Любая нагрузка _acquire , которая видит сигнал (или все нагрузки _acquire , которые видят сигнал), знает, что данные «готовы», и они могут их прочитать. Конечно, любые записи в данные, которые идут после хранилища _release , могут (в зависимости от времени) также просматриваться нагрузкой (ами) _acquire . Здесь я пытаюсь сказать, что может потребоваться еще один сигнал для дальнейших изменений данных.

Ваша маленькая тестовая программа:

1. инициализирует tsync в 0

2. в записывающем устройстве: после tat[i].store(j, memory_order_relaxed), tsync.store(0, memory_order_release)

   , поэтому значение tsync не изменяется!

3. в считывателе: tsync.load(memory_order_acquire) перед выполнением tat[i].load(memory_order_relaxed)

   и игнорирует значение, считанное с tsync

Я здесь, чтобы сказать вам, что пары _release / _acquire не синхронизируются - все эти хранилища / загрузка также могут быть _relaxed . [Я думаю, что ваш тест «пройдет», если автору удастся опередить читателя. Потому что на x86-64 все записи выполняются в порядке следования, как и все чтения.]

Для того, чтобы это было тестом _release / _acquire семантика, я предложить:

1. инициализирует tsync в 0 и tat[] во все нули.

2. в модуле записи: запустите j = 1..numTries

   после всех tat[i].store(j, memory_order_relaxed), запишите tsync.store(j, memory_order_release)

   , это сигнализирует о завершении передачи и что все tat[] теперь j.

3. в считывателе: сделайте j = tsync.load(memory_order_acquire)

   проход через tat[] должен найти j <= tat[i].load(memory_order_relaxed)

   и после прохода j == numTries сигнализирует, что писатель закончил.

где сигнал, отправленный автором, состоит в том, что он только что завершил запись j и будет продолжать с j+1, если j == numTries. Но это не гарантирует порядок, в котором написаны tat[].

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

Answer 2

Цитата о непринужденной передаче согласованности порядка модификации. означает только то, что все потоки могут согласовать порядок модификации для этого одного объекта. то есть порядок существует. Более поздний релиз-хранилище, которое синхронизируется с загрузкой в ​​другом потоке, гарантирует его видимость. https://preshing.com/20120913/acquire-and-release-semantics/ имеет хорошую диаграмму.

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

В любом виде структуры данных на основе дерева / связанного списка / указателя, практически единственный раз, когда вы можете использовать relaxed, будет в недавно выделенные узлы, которые еще не были «опубликованы» в других потоках. (В идеале вы можете просто передать аргументы конструкторам, чтобы их можно было инициализировать, даже не пытаясь быть атомом c; конструктор для std::atomic<T>() сам по себе не является атомом c. Поэтому вы должны использовать хранилище релизов при публикации указатель на вновь созданный объект atomi c.)

---

В x86 / x86-64, mo_release не требует дополнительных затрат; У обычных asm-хранилищ порядок упорядочения уже такой же сильный, как и у релиза, поэтому компилятору нужно только заблокировать переупорядочение по времени компиляции для реализации var.store(val, mo_release); Это также довольно дешево для AArch64, особенно если вы не выполняете никаких операций загрузки в ближайшее время.

Это также означает, что вы не можете проверить, насколько расслабленным является небезопасное использование оборудования x86; во время компиляции компилятор выберет один заказ для расслабленных хранилищ, включив их в операции выпуска в любом порядке. (А операции x86 atomi c -RMW всегда являются полными барьерами, фактически seq_cst. Ослабление их в источнике позволяет только переупорядочение во время компиляции. Некоторые ISA не для x86 могут иметь более дешевые RMW, а также загружать или хранить для более слабых заказов, хотя даже acq_rel немного дешевле на PowerP C.)