Как возникает состояние гонки, когда ||Оператор используется вместо && в std :: atomic?

Question

Существует задача заставить 3 потока выполняться всегда в определенном порядке, например так:

zero  // prints 0s only
odd   // prints odd numbers    
even  // prints even numbers

каждая из функций (ноль, чет, нечет) передается в 3 потока, соответственно, поэтому выводдолжно быть:

0102     for n = 2
010203   for n = 3
01020304 for n = 4
and so on

В коде:

class ZeroEvenOdd {
    private:
        int n;
        std::atomic<int> turn{0};
        bool flag = false;

    public:
        ZeroEvenOdd(int n) {
            this->n = n;
        }

        void zero(std::function<void(int)> printNumber) {
            int i = 0;
            while (i < n) {
                while (turn > 0) {// 1 or 2
                    std::this_thread::yield();
                }
                printNumber(0);
                turn = !flag ? 1 : 2;
                flag = !flag;
                ++i;
            }
        }

        void even(std::function<void(int)> printNumber) {
            int i = 2;
            while (i <= n) {
                while (turn < 2) {// 0 or 1
                    std::this_thread::yield();
                }
                printNumber(i);
                turn = 0;
                i += 2;
            }
        }

        void odd(std::function<void(int)> printNumber) {
            int i = 1;
            while (i <= n) {
                //while (turn <= 2 && turn != 1) {// 0 or 2 // how does this expression eliminate the race ???
                while (turn == 0 || turn == 2) { // this causes race condition
                    std::this_thread::yield();
                }
                printNumber(i);
                turn = 0;
                i += 2;
            }
        }
    };

Давайте посмотрим на функцию odd:

Во внутреннем цикле while мне нужно проверить, если turn равно 0 или 2:

Если я проверю таким образом: while (turn == 0 || turn == 2) {...} состояние гонки появляется с неправильным и не полным выводом.

for n = 24
it might be:
010203040506709080110100130120150140170160190180210200230220...(waiting)

Здесь мы видим, что после 6 7 печатается, что неправильно ...

Но если я проверю этот способ, while (turn <= 2 && turn != 1) {...} не будет отображаться гонок, и вывод всегда будет правильным.

Аналогичные гонки появляются для других функций zero и even когда их внутренние циклы while изменяются для использования оператора ||.

Я знаю, что объединение атомарных операций в выражении не обязательно делает все выражение атомарным, но я просто не могу получить свойОбдумайте, какой сценарий может вызвать состояние гонки с этой проверкой while (turn == 0 || turn == 2) {...} ???

Обновление

Полный пример кода для воспроизведения проблемы:

#include <iostream>
#include <thread>
#include <atomic>
#include <functional>

class ZeroEvenOdd {
    private:
        int n;
        std::atomic<int> turn{0};
        bool flag = false;

    public:
        ZeroEvenOdd(int n) {
            this->n = n;
        }

        void zero(std::function<void(int)> printNumber) {
            int i = 0;
            while (i < n) {
                while (turn > 0) {// 1 or 2
                    std::this_thread::yield();
                }
                printNumber(0);
                turn = !flag ? 1 : 2;
                flag = !flag;
                ++i;
            }
        }

        void even(std::function<void(int)> printNumber) {
            int i = 2;
            while (i <= n) {
                while (turn < 2) {// 0 or 1
                    std::this_thread::yield();
                }
                printNumber(i);
                turn = 0;
                i += 2;
            }
        }

        void odd(std::function<void(int)> printNumber) {
            int i = 1;
            while (i <= n) {
                //while (turn <= 2 && turn != 1) {// 0 or 2 // how does this expression eliminate the race ???
                while (turn == 0 || turn == 2) { // this causes race condition
                    std::this_thread::yield();
                }
                printNumber(i);
                turn = 0;
                i += 2;
            }
        }
    };  

    int main() {
        int n = 24;
        std::function<void(int)> printNum = [](int x) {
            std::cout << x << std::flush;
        };
        ZeroEvenOdd zeroEvenOdd(n);
        std::thread t1(&ZeroEvenOdd::zero, &zeroEvenOdd, printNum);
        std::thread t2(&ZeroEvenOdd::even, &zeroEvenOdd, printNum);
        std::thread t3(&ZeroEvenOdd::odd,  &zeroEvenOdd, printNum);
        t1.join();
        t2.join();
        t3.join();
        return 0;
    }

Команда для компиляции:

g++ -std=c++14 -fsanitize=thread -pthread test.cpp -o test

Answer 1

Для тех, кто, как я, не смог сразу же найти это из объяснения / кода, вот краткое резюме:

zero может оставить только внутренний цикл while, если turn == 0. Затем он устанавливает turn на 1 или 2.

even может оставить только внутренний цикл while, если turn == 2. Затем он устанавливает turn в 0.

Намерение состоит в том, что odd может выйти из внутреннего цикла while, только если turn == 1 (тогда он устанавливает turn в 0.), Ноэто не реализовано правильно.

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

---

Проблема в том, что turn == 0 || turn == 2 не является атомарным. Может произойти следующее:

1. zero завершает одну итерацию и устанавливает turn = 2.

2. odd проверок turn == 0, чтоложно.

3. Между тем, even также видит turn == 2, выходит из цикла вращения, завершает итерацию и устанавливает turn = 0.

4. odd теперь проверяет правую часть оператора ||: turn == 2, что неверно.

5. odd выходит из цикла вращения (даже еслиturn == 0!) , что, конечно, непреднамеренно и приводит к гонке от нуля до нечетного.

Короче говоря, проблема в том, что левая часть ||может быть ложным, но станет истинным к тому времени, когда будет оценена правая часть. Ни в одном из вышеприведенных пунктов не было целого turn == 0 || turn == 2, равного false, если оценивать его атомарно, но, поскольку оно не является атомарным, вы получили «смесь» из false || true и true || false (а именно false || false).

Выражение turn <= 2 && turn != 1 не имеет этой проблемы, поскольку первое условие всегда true, а второе условие - это проверка, которую вы действительно хотите.

---

В общем случае решение состоит в том, чтобы один раз прочитать атомное в локальную tmp и проверить это. Это лучше для производительности, потому что позволяет компилятору совместно оптимизировать ваши условия или совместно оптимизировать то, что вы собираетесь делать.

    while (true) {
        int t = turn;
        if (!(t == 0 || t == 2)) break;
        yield();
    }

Или, возможно, взломать это в одну строку с помощью оператора запятой. Запятая является «точкой последовательности», поэтому вы можете присвоить t и затем прочитать ее. Но это не очень удобно для восприятия человеком.

    int tmp;
    while (tmp=turn, (tmp == 0 || tmp == 2)) {
        yield();
    }

Если вы действительно хотите подождать, пока turn будет нечетным, вы можете использовать turn % 2 == 0 или

    while ( turn&1 == 0 )
        yield();