c++ - 为什么竞赛条件的输出不是随机的？

Question

我设置以下竞争条件来生成一些随机位。但是，据我所知，输出不是随机的。我想了解原因(出于学习目的)。这是我的代码:

#include <iostream>
#include <vector>
#include <atomic>
#include <thread>
#include <cmath>

using namespace std;

void compute_entropy(const vector<bool> &randoms) {

    int n0 = 0, n1 = 0;

    for(bool x: randoms) {
        if(!x) n0++;
        else n1++;
    }

    double f0 = n0 / ((double)n0 + n1), f1 = n1 / ((double)n0 + n1);

    double entropy = - f0 * log2(f0) - f1 * log2(f1);

    for(int i = 0; i < min((int)randoms.size(), 100); ++i)
        cout << randoms[i];
    cout << endl;
    cout << endl;

    cout << f0 << " " << f1 << " " << endl;
    cout << entropy << endl;

    return;
}

int main() {

    const int N = 1e7;

    bool x = false;
    atomic<bool> finish1(false), finish2(false);
    vector<bool> randoms;

    thread t1([&]() {
        for(int i = 0; !finish1; ++i)
            x = false;
    });

    thread t2([&]() {
        for(int i = 0; !finish2; ++i)
            x = true;
    });

    thread t3([&]() {
        for(int i = 0; i < N; ++i)
            randoms.push_back(x);
        finish1 = finish2 = true;
    });

    t3.join();
    t1.join();
    t2.join();

    compute_entropy(randoms);

    return 0;
}

我这样编译并运行它:

$ g++ -std=c++14 threads.cpp -o threads -lpthread
$ ./threads 
0101001011000111110100101101111101100100010001111000111110001001010100011101110011011000010100001110

0.473792 0.526208 
0.998017

不管我运行多少次，结果都是歪斜的。
拥有一千万个数字，适当的随机数生成器产生的结果与人们期望的一样:

>>> np.mean(np.random.randint(0, 2, int(1e7)))
0.5003456
>>> np.mean(np.random.randint(0, 2, int(1e7)))
0.4997095

Answer 1

Why is the output from race conditions not random?

无法保证竞争条件会产生随机输出。不能保证它是纯随机的，甚至也不是任何质量的伪随机的。

as far as I can tell, the output is NOT random.

没有可以肯定地证明随机性的测试。
有测试可以显示一个序列可能不包含某些特定模式-因此通过多个此类测试的序列可能是随机的。但是，据我所知，您还没有执行过这样的测试。您似乎正在测量输出的分布是否均匀-这是与随机性不同的属性。因此，您得出的输出不是随机的结论不是基于相关的度量。

此外，您的程序存在数据争用。因此，整个程序的行为是不确定的，并且不能保证该程序的行为与原本可以合理预期的一样。