Google WorkStealingDequeue использует memory_order_seq_cst в качестве полного барьера памяти.Это действительно?

Question

Я изучаю систему накаливания Google.В настоящее время я изучаю реализованный ими WorkStealingDequeue.Вы можете посмотреть полный исходный код здесь .Эта структура данных основана на этой работе .В своих реализациях pop и steal они используют memory_order_seq_cst в качестве полного барьера памяти.

template <typename TYPE, size_t COUNT>
TYPE WorkStealingDequeue<TYPE, COUNT>::pop() noexcept {
    // mBottom is only written in push(), which cannot be concurrent with pop(),
    // however, it is read in steal(), so we need basic atomicity.
    //   i.e.: bottom = mBottom--;
    int32_t bottom = mBottom.fetch_sub(1, std::memory_order_relaxed) - 1;

    // we need a full memory barrier here; mBottom must be written and visible to
    // other threads before we read mTop.
    int32_t top = mTop.load(std::memory_order_seq_cst);

    if (top < bottom) {
        // Queue isn't empty and it's not the last item, just return it.
        return getItemAt(bottom);
    }

    TYPE item{};
    if (top == bottom) {
        // We took the last item in the queue
        item = getItemAt(bottom);

        // Items can be added only in push() which isn't concurrent to us, however we could
        // be racing with a steal() -- pretend to steal from ourselves to resolve this
        // potential conflict.
        if (mTop.compare_exchange_strong(top, top + 1,
                std::memory_order_seq_cst,
                std::memory_order_relaxed)) {
            // success: mTop was equal to top, mTop now equals top+1
            // We successfully poped an item, adjust top to make the queue canonically empty.
            top++;
        } else {
            // failure: mTop was not equal to top, which means the item was stolen under our feet.
            // top now equals to mTop. Simply discard the item we just poped.
            // The queue is now empty.
            item = TYPE();
        }
    }

    // no concurrent writes to mBottom possible
    mBottom.store(top, std::memory_order_relaxed);
    return item;
}

template <typename TYPE, size_t COUNT>
TYPE WorkStealingDequeue<TYPE, COUNT>::steal() noexcept {
    do {
        // mTop must be read before mBottom
        int32_t top = mTop.load(std::memory_order_seq_cst);

        // mBottom is written concurrently to the read below in pop() or push(), so
        // we need basic atomicity. Also makes sure that writes made in push()
        // (prior to mBottom update) are visible.
        int32_t bottom = mBottom.load(std::memory_order_acquire);

        if (top >= bottom) {
            // queue is empty
            return TYPE();
        }

        // The queue isn't empty
        TYPE item(getItemAt(top));
        if (mTop.compare_exchange_strong(top, top + 1,
                std::memory_order_seq_cst,
                std::memory_order_relaxed)) {
            // success: we stole a job, just return it.
            return item;
        }
        // failure: the item we just tried to steal was pop()'ed under our feet,
        // simply discard it; nothing to do.
    } while (true);
}

Чтобы реализация была правильной, требуется, чтобы mBottom выбирался перед mTop в pop () и mTop длябыть выбранным до того, как mBottom в Steal ().Если мы считаем memory_order_seq_cst полным барьером памяти, как это делает большинство реализаций, то приведенный выше код верен.Но, насколько я понимаю, C ++ 11 ничего не говорит о memory_order_seq_cst как о полном барьере памяти.Из того, что я понимаю для обеспечения правильного упорядочения, операция mBottom fetch_sub должна быть как минимум std :: memory_order_acq_rel.Мой анализ правильный?

И тогда необходим ли memory_order_seq_cst на mTop?memory_order_seq_cst заставляет все операции в mTop выполнять один общий заказ (STO).Но в этом случае единственным, кто участвует в СТО, является mTop.Я полагаю, что у нас уже есть гарантия порядка модификации, которая гласила, что каждый поток должен согласовать порядок модификации каждой переменной относительно себя.Достаточно ли memory_order_acq_rel в операции compare_exchange_strong?

Answer 1

Этот код имеет гонку данных в steal и, следовательно, неопределенное поведение, независимо от порядка памяти.

Ничто не мешает потоку кражи, вызывающему getItemAt(top), прочитать значение по заданному индексу, в то время как рабочий поток, которому принадлежит очередь, вызывает push достаточное количество раз, чтобы обернуться вокруг буфера и перезаписать запись, или вызывает pop достаточно раз для очистки очереди, а затем вызывает push для перезаписи этой записи.

например. mTop равно 0, mBottom равно 1 => очередь имеет один элемент.

Кража потока читает mTop и mBottom. top<bottom, поэтому он получает на вызов getItemAt(top) и приостанавливается ОС из-за переключения задач.

Рабочий поток вызывает pop. Он читает mBottom и устанавливает bottom в 0. Затем он читает top (0). 0==0, поэтому мы вызываем getItemAt(bottom), чтобы получить элемент. Затем он увеличивает mTop до 1 и устанавливает mBottom в 1.

Рабочий поток затем вызывает push и вызывает setItemAt(mBottom), чтобы установить следующий элемент, который теперь является элементом 1.

Рабочий поток теперь повторяет этот push / pop танец COUNT раз, поэтому в очереди никогда не бывает более одного элемента, но каждый раз увеличивается mTop и mBottom, поэтому активный элемент перемещается вокруг буфер до mBottom & MASK снова 0.

Рабочий поток вызывает push и, следовательно, setItemAt(mBottom), который обращается к элементу 0. ОС возобновляет поток кражи, который также обращается к элементу 0 => для чтения и записи в том же месте без упорядочивания => гонки данных и неопределенное поведение.

Это нормально только если TYPE равно std::atomic<T> для некоторых T.

Если предположить, что COUNT достаточно велико, чтобы на практике этого никогда не происходило, тогда push записывает в mBottom с memory_order_release, а steal читает с memory_order_acquire. Это означает, что запись в соответствующий элемент данных происходит до чтения элемента в steal, поэтому чтение элемента в порядке. Это видно даже при использовании fetch_sub в pop с использованием memory_order_relaxed из-за концепции, называемой «последовательность выпусков».

Использование memory_order_seq_cst для нагрузок и успешный сравнительный обмен mTop вынуждают операции на mTop в единый глобальный общий заказ. Однако комментарий о загрузке mTop в pop неверен: использование memory_order_seq_cst не препятствует переупорядочению вызова mBottom.fetch_sub, так как это load из mTop, а fetch_sub вызов использует memory_order_relaxed. memory_order_seq_cst в load не налагает никакого упорядочения на записи не-1076 * из того же потока в другие переменные.

В настоящее время я не уверен, какое влияние это может оказать на код.