|| 时如何导致竞争条件在 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

对于像我这样无法立即从 explanation/code 中收集到它的人，这里有一个快速摘要：

zero 如果 turn == 0 只能离开内部 while 循环。然后将 turn 设置为 1 或 2.

even 如果 turn == 2 只能离开内部 while 循环。然后将 turn 设置为 0.

的意图是odd如果turn == 1只能离开内部while循环（然后将turn设置为0），但这并没有实现正确。

由于离开自旋循环的条件是（应该）互斥的，在给定时间不应有超过一个线程在其自旋循环之外，因此不可能有并发修改（并且程序那么应该是无种族的。

问题是 turn == 0 || turn == 2 不是原子的。可能会发生以下情况：

zero 完成一次迭代并设置 turn = 2.
odd 检查 turn == 0，这是错误的。
同时，even也看到turn == 2，退出自旋循环，完成一次迭代并设置turn = 0.
odd 现在检查 || 运算符的右侧：turn == 2，这是错误的。
odd 离开它的自旋循环（即使 turn == 0!） 这当然是无意的，并导致之间的竞争零和奇数。

简而言之，问题在于 || 的左侧可能为假，但在评估右侧时变为真。如果以原子方式计算，上面的任何一点都不等于 false，但由于它不是原子的，所以你得到了 false || true 和 true || false 的 "mix"（即 false || false).

表达式turn <= 2 && turn != 1没有这个问题，因为第一个条件总是true，第二个条件是你真正想要的检查。

在一般情况下，解决方案是将原子读取一次，放入本地 tmp，然后进行检查。这对性能更好，因为它允许编译器一起优化您的条件，或者一起优化您要做的任何事情。

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

或者用逗号运算符将其拼成一行。逗号是 "sequence point" 所以你可以分配给 t 然后读取它。但这不是很适合人类阅读。

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

如果你真的想等待 turn 成为奇数，你可以使用 turn % 2 == 0 或

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

|| 时如何导致竞争条件在 std::atomic? 中使用运算符代替 &&

How is race condition caused when || operator is used instead of && within the std::atomic?

c++

multithreading

race-condition

c++11

stdatomic