Why is the output from race conditions not random?

user_3887393 0
Viewed 176

I set up the following race condition to generate some random bits. However, as far as I can tell, the output is NOT random. I want to understand why (for learning purposes). Here is my code:

#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;
}

I compile and run it like this:

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

0.473792 0.526208 
0.998017

No matter how many times I run it, the results are skewed.

With 10 million numbers, the results from a proper random number generator are as one would expect:

>>> np.mean(np.random.randint(0, 2, int(1e7)))
0.5003456
>>> np.mean(np.random.randint(0, 2, int(1e7)))
0.4997095
race-condition multithreading c++
1 Answers

Why is the output from race conditions not random?

There is no guarantee that a race condition would produce random output. It is not guaranteed to be purely random nor even pseudo random of any quality.

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

There exists no test that can definitely disprove randomness.

There are tests that can show that a sequence probably doesn't contain some specific patterns - and thus a sequence passing multiple such tests is probably random. However, you haven't performed such test as far as I can tell. You seem to be measuring whether the distribution of the output is even - which is a separate property from randomness. As such, your conclusion that the output isn't random is not based on a relevant measurement.

Furthermore, your program has a data race. As such, the behaviour of the entire program is undefined and here is no guarantee that the progam would behave as one might otherwise have reasonably expected.

user_20793030
Related