时间戳

首页 > 解决方案 > 为什么这个 c 代码会导致竞争条件？

c - 为什么这个 c 代码会导致竞争条件？

问题描述

我正在尝试计算多达 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个线程）

Number of threads is: 2

Time tasken: 0.038641 seconds

2 primes found.

标签： cmultithreadingpthreads

解决方案

计数器primeCount由多个线程修改，因此必须是原子的。要使用标准库（现在 POSIX 也支持）解决此问题，您应该#include <stdatomic.h>声明primeCount为 an并使用oratomic_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 );在线程过程终止之前执行一次是不值得的。

推荐阅读