c++ - 我可以在 C++ 中仅使用 std::atomic 而不使用 std::mutex 安全地跨线程共享变量吗？

Question

我制作了一个在多核上计算素数的程序。(请忽略该算法并非完全有效，这里将数字 0 和 1 视为质数。目的只是练习使用线程。)

变量 taken(接下来要测试的数字)正在 8 个线程之间共享。

问题是它可以由一个线程递增，紧接着由另一个线程递增，并在它已经递增两次(或更多次)时被它们读取，因此可以跳过一些值，这是一件坏事。

我以为它可以通过使用 std::atomic_uint 作为变量类型来解决，但我显然错了。

有什么方法可以在不需要使用 std::mutex 的情况下解决这个问题，因为我听说它会导致相当大的开销？源代码:

#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <thread>
#include <atomic>

int main()
{
    const uint MAX = 1000;

    std::vector<bool> isPrime(MAX), done(MAX);
    std::fill(done.begin(), done.end(), false);
    std::atomic_uint taken{0}; //shared variable
    std::vector<std::thread> threads;
    auto start = std::chrono::system_clock::now();

    for (uint i = 0; i < 8; ++i) {
        threads.emplace_back(
            [&](){
                bool res;
                for (uint tested; (tested = taken.fetch_add(1)) < MAX; ) { //taken should be incremented and copied atomically
                    res = true;
                    for (uint k = 2; k < tested; ++k) {
                        if (tested % k == 0) {
                            res = false;
                            break;
                        }
                    }
                    isPrime[tested] = res;
                    done[tested] = true;
                }
            }
        );
    }
    for (auto & t : threads) {
        t.join();
    }

    auto end = std::chrono::system_clock::now();
    auto milliseconds = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    uint num = std::count_if(isPrime.begin(), isPrime.end(), [](bool b){return b;});
    uint nDone = std::count_if(done.begin(), done.end(), [](bool b){return !b;});
    std::cout << "number: " << num << " duration: " << milliseconds.count() << '\n';
    std::cout << "not done: " << nDone << '\n';
    for (uint i = 0; i < MAX; ++i) { //Some numbers are always skipped
        if (!done[i]) {
            std::cout << i << ", ";
        }
    }
    std::cout << '\n';
    return 0;
}

代码是使用 g++ 编译的，带有 -O3 和 -pthread 参数。输出:

number: 169 duration: 1
not done: 23
143, 156, 204, 206, 207, 327, 328, 332, 334, 392, 393, 396, 502, 637, 639, 671, 714, 716, 849, 934, 935, 968, 969,

每次的输出都不一样。

Answer 1

专业std::vector<bool>将值压缩为单个位。因此，单个字节中有多个 vector 元素，即在单个内存位置中。因此，您的线程会在没有同步的情况下更新相同的内存位置，这是一种数据竞争(因此根据标准是未定义的行为)。

尝试改变std::vector<bool>至 std::vector<char> .