c - 为什么此 C 代码会导致竞争条件？

Question

我正在尝试计算最多 1000 万个素数的数量，我必须使用多个线程使用 Posix 线程来完成此操作(因此，每个线程计算 1000 万个子集)。但是，我的代码没有检查条件 IsPrime。我认为这是由于竞争条件。如果是，我可以做些什么来改善这个问题？

我试过使用一个包含 k 个元素的全局整数数组，但由于 k 未定义，所以我无法在文件范围内声明它。

我正在使用 gcc -pthread 运行我的代码:

/*
Program that spawns off "k" threads
k is read in at command line each thread will compute
a subset of the problem domain(check if the number is prime)

to compile: gcc -pthread lab5_part2.c -o lab5_part2
*/
#include <math.h>
#include <stdio.h>
#include <time.h>
#include <pthread.h>
#include <stdlib.h>

typedef int bool;
#define FALSE 0
#define TRUE 1

#define N 10000000  // 10 Million

int k; // global variable k willl hold the number of threads
int primeCount = 0; //it will hold the number of primes.

//returns whether num is prime
bool isPrime(long num) {
    long limit = sqrt(num);
    for(long i=2; i<=limit; i++) {
        if(num % i == 0) {
             return FALSE;
        }
     }
     return TRUE;
}

//function to use with threads
void* getPrime(void* input){
    //get the thread id
    long id = (long) input;
    printf("The thread id is: %ld \n", id);

    //how many iterations each thread will have to do
    int numOfIterations = N/k;

  //check the last thread. to make sure is a whole number.
  if(id == k-1){
    numOfIterations = N - (numOfIterations * id);
  }

  long startingPoint = (id * numOfIterations);
  long endPoint = (id + 1) * numOfIterations;
  for(long i = startingPoint; i < endPoint; i +=2){
    if(isPrime(i)){
      primeCount ++;
    }
  }
  //terminate calling thread.
  pthread_exit(NULL);
}

int main(int argc, char** args) {
    //get the num of threads from command line
    k = atoi(args[1]);
    //make sure is working
   printf("Number of threads is: %d\n",k );

   struct timespec start,end;

    //start clock
    clock_gettime(CLOCK_REALTIME,&start);

    //create an array of threads to run
    pthread_t* threads = malloc(k * sizeof(pthread_t));
    for(int i = 0; i < k; i++){
      pthread_create(&threads[i],NULL,getPrime,(void*)(long)i);
    }

    //wait for each thread to finish
    int retval;
    for(int i=0; i < k; i++){
      int * result = NULL;
      retval = pthread_join(threads[i],(void**)(&result));
    }

    //get the time time_spent
    clock_gettime(CLOCK_REALTIME,&end);
    double time_spent = (end.tv_sec - start.tv_sec) +
                    (end.tv_nsec - start.tv_nsec)/1000000000.0f;

    printf("Time tasken: %f seconds\n", time_spent);

    printf("%d primes found.\n", primeCount);

}

我得到的当前输出:(使用 2 个线程)

线程数为:2

任务时间:0.038641 秒

找到 2 个素数。

Answer 1

计数器 primeCount 被多个线程修改，因此必须是原子的。要使用标准库(现在也受 POSIX 支持)修复此问题，您应该 #include <stdatomic.h> ，将 primeCount 声明为 atomic_int ，并用 atomic_fetch_add() 或 atomic_fetch_add_explicit() 递增它。

更好的是，如果直到最后才关心结果，每个线程都可以将自己的计数存储在一个单独的变量中，主线程可以在线程完成后将所有计数加在一起。您将需要在主线程中为每个线程创建一个原子计数器(这样更新就不会破坏同一缓存行中的其他数据)，向每个线程传递一个指向其输出参数的指针，然后将部分计数返回给通过该指针的主线程。

这看起来像是一个你想自己解决的练习，所以我不会为你编写代码，但使用方法是声明一个计数器数组，如线程 ID 数组，并将 &counters[i] 作为arg 的 pthread_create() 参数类似于您传递 &threads[i] 的方式。每个线程都需要自己的计数器。在线程过程结束时，您将编写类似 atomic_store_explicit( (atomic_int*)arg, localTally, memory_order_relaxed ); 的内容。这在所有现代架构上应该是完全无等待的。

您可能还认为不值得为避免每个线程进行一次原子更新而费心，将 primeCount 声明为 atomic_int ，然后在线程过程终止之前将 atomic_fetch_add_explicit( &primeCount, localTally, memory_order_relaxed ); 声明一次。