OpenMP素数计数程序竞态条件排查求助：结果偶发错误

问题描述 #

使用OpenMP编写的统计2到N之间素数个数的程序，执行OMP_NUM_THREADS=2 ./main 10时，输出大多为4，但偶尔会得到5，存在未发现的竞态条件，需要定位并解决。

程序代码 #

#include <iostream>
#include <omp.h>
#include <vector>

int main(int argc, char *argv[])
{
    if (argc != 2)
        return -1;

    const unsigned long N = std::atoi(argv[1]);

    unsigned counter = 0;
    std::vector<bool> numbers(N + 1, true);
    numbers[0] = numbers[1] = false;

#pragma omp parallel shared(numbers, counter)
    {
#pragma omp single
        {
            for (size_t i = 2; i * i <= N; ++i)
            {
                if (numbers[i] == true)
#pragma omp task
                {
                    for (size_t j = i * i; j <= N; j += i)
                        numbers[j] = false;
                }
            }
#pragma omp taskwait
        }
#pragma omp for reduction(+ \
                          : counter)
        for (size_t i = 1; i <= N; ++i)
            if (numbers[i] == true)
                counter++;
    }

    std::cout << counter << std::endl;

    return 0;
}

补充说明 #

通过sanitizer检测到数据竞态条件，为numbers[j]=false添加#pragma omp critical可解决大N下多线程写入同一位置的问题，但N=10时不存在多线程写同一位置的情况：循环size_t i = 2; i * i <= N; ++i得到i=2、3，对应任务遍历j=4、6、8、10、9，这些索引互不重叠。当输出5时，numbers向量状态为0 0 1 1 0 1 0 1 0 1 0（对应0到10，1表示素数）。虽添加了#pragma omp taskwait确保single线程等待所有任务完成，但异常结果仍出现。

问题原因与解决方法 #

根本原因 #

问题出在std::vector<bool>的实现特性上：它是比特位压缩存储的特殊容器，并非真正的bool数组。每个元素仅占用1个比特位，多个元素会被打包到同一个机器字（比如64位CPU中，8个bool元素占1个64位字）。即使两个任务修改的是不同索引（比如j=6和j=9），它们可能处于同一个机器字中，多线程修改不同比特位时，CPU会以字为单位进行加载、修改、存储操作，这会触发缓存一致性冲突，导致比特值被错误覆盖，最终出现统计错误。

解决方法 #

1. 替换容器类型：将std::vector<bool>替换为std::vector<char>或std::vector<uint8_t>，让每个元素占用1个字节。这样不同索引的修改操作完全独立，不会共享机器字，从根源避免比特级竞态。修改后的容器初始化代码如下：

std::vector<char> numbers(N + 1, true);

2. 原子操作（备选）：如果必须使用std::vector<bool>，可以将元素改为原子类型，比如std::vector<std::atomic<bool>>，确保每个比特位的修改是原子操作。但这种方式性能不如替换容器高效，且代码复杂度更高。

验证效果 #

替换为std::vector<char>后，执行OMP_NUM_THREADS=2 ./main 10会稳定输出4（正确素数为2、3、5、7），不再出现异常结果。

内容的提问来源于stack exchange，提问作者hiotareq