почему этот код c вызывает состояние гонки? - PullRequest
Новая
       16

почему этот код c вызывает состояние гонки?

0 голосов
/ 22 мая 2019

Я пытаюсь подсчитать количество простых чисел до 10 миллионов, и мне нужно сделать это, используя несколько потоков с использованием потоков Posix (чтобы каждый поток вычислял подмножество из 10 миллионов). Однако мой код не проверяет условие 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.

1 Ответ

2 голосов
/ 22 мая 2019

Счетчик primeCount изменяется несколькими потоками и поэтому должен быть атомарным.Чтобы исправить это, используя стандартную библиотеку (которая теперь также поддерживается POSIX), вы должны #include <stdatomic.h>, объявить primeCount как atomic_int и увеличить его на atomic_fetch_add() или atomic_fetch_add_explicit().

Еще лучше, если вы не заботитесь о результате до конца, каждый поток может сохранить свой счет в отдельной переменной, а основной поток может сложить все счетчики после завершения потоков.Вам потребуется создать в основном потоке атомарный счетчик для каждого потока (чтобы обновления не забивали другие данные в той же строке кэша), передать каждому потоку указатель на его выходной параметр, а затем вернуть частичный подсчет восновной поток через этот указатель.

Это похоже на упражнение, которое вы хотите решить самостоятельно, поэтому я не буду писать код для вас, но подход будет использовать для объявления массива счетчиков, таких какмассив идентификаторов потоков и передайте &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 ); один раз до завершения процедуры потока.

...