A strange thing about vector<atomic<bool>> under multi-thread circumstance in C++

Question

I was using vector<atomic<bool>> in C++, the code is here:

#include <iostream>
#include <thread>
#include <atomic>
#include <vector>
using namespace std;

int main() {
    int n = 10;
    int count = 20;
    vector<atomic<bool>> flags(n);
    vector<thread> jobs;
    for (int i = 0; i < count; i++) {
        jobs.emplace_back([&](){
            bool old_val = false;
            for (int i = 0; i < n; i++) {
                if (flags[i].compare_exchange_strong(old_val, true)) {
                    cout<<1;
                    break;
                }
            }
        });
    }
    for (int i = 0; i < count; i++) {
        jobs[i].join();
    }
    return 0;
}

I don't know why, no matter what the value of variable count is, the output content is always "11111", which means that the compare_exchange_strong() only succeeds 5 times, half of the length of the vector<atomic<bool>>.

I expect the output would be 1111111111(ten 1s).

Can anyone tell me why? Thanks!!!!

Answer 1

Your threads are in a race with each other but not for thread-safety reasons. What we see is a perfectly mathematical statistic of flipping vaue to "yes" and "no" (and sometimes it's done intentionally).

#include <iostream>
#include <thread>
#include <atomic>
#include <vector>
using namespace std;

int main() {
    int n = 2;
    int count = 4;
    vector<atomic<bool>> flags(n);
    vector<thread> jobs;
    atomic<int> k  {};

    for (int i = 0; i < n; i++) {
        cout  << flags[i] << " ";
    } 
    cout << "\n";
    
    for (int i = 0; i < count; i++) {
        jobs.emplace_back([&,i](){
            bool old_val = false;
            for (int j = 0; j < n; j++) {
                if (flags[j].compare_exchange_strong(old_val, true)) {
                    string s = to_string(i) + " :" + to_string(j) + "-" +  to_string(k++) + "(1)\t ";
                    cout << s;
                    break;
                } else {
                    string s = to_string(i) + " :" + to_string(j) + "-" +  to_string(k++) + "(0)\t ";
                    cout << s;
                }
            }
        });
    }
    
    for (int i = 0; i < count; i++) {
        jobs[i].join();
    }

    cout << "\n";
    for (int i = 0; i < n; i++) {
        cout  << flags[i] << " ";
    } 
    return 0;
}

Output:

0 0 
0 :0-0(1)    1 :0-1(0)   1 :1-2(0)   2 :0-3(0)   2 :1-4(0)   3 :0-5(0)   3 :1-6(0)   
1 0  

Do you see what's going on? compare_exchange_strong got a side-effect upon it's argument, it save detected value. It's a state race (not to be confused with racing condition), because even if other thread "flips" the flag, your thread skips it and then skips next one because it wants to find 1.

Atomically compares the object representation(until C++20)value representation(since C++20) of *this with that of expected. If those are bitwise-equal, replaces the former with desired (performs read-modify-write operation). Otherwise, loads the actual value stored in *this into expected (performs load operation).

Your code should be:

        for (int i = 0; i < n; i++) {
            bool old_val = false;
            if (flags[i].compare_exchange_strong(old_val, true)) {
                cout<<1;
                break;
            }
        }