I am trying to write a multithreaded C program that finds all prime numbers in an interval.
The single-thread version works perfectly, but the multi-thread one has important issues particularly caused by thread lifecycles.
This is the code:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <pthread.h>
#define THREADS_NUM 4
struct ipp_args{
int id; // ID of the thread
int stop; // Max number to test
};
void *prime_checker(void*);
pthread_t threads[THREADS_NUM];
int count = 0;
int main(int argc, char const *argv[]) {
int start, end;
if (argc == 1) {
start = 2;
end = 100;
} else if (argc == 3) {
start = atoi(argv[1]);
end = atoi(argv[2]);
} else {
printf("Usage:\n\tprimes <from> <to>\n");
exit(1);
}
if (start < 2) start = 2;
// Launch threads
for (int thread_id = 0; thread_id < THREADS_NUM; thread_id) {
struct ipp_args args;
args.id = thread_id;
args.stop = end;
printf("[MAIN] Starting T_%d\n", thread_id);
int error = pthread_create(&threads[thread_id], NULL, prime_checker, (void*)&args);
if (error) {
printf("[MAIN] Cannot create thread %d\n", thread_id);
exit(3);
}
}
// Join threads
for (int thread_id = 0; thread_id < THREADS_NUM; thread_id ) {
printf("[MAIN] Joining T_%d\n", thread_id);
int error = pthread_join(threads[thread_id], NULL);
if (error) {
printf("[MAIN] Cannot join thread %d\n", thread_id);
exit(4);
}
}
printf("%d primes found\n", count);
pthread_exit(NULL);
return 0;
}
void *prime_checker(void *_args) {
struct ipp_args *args = _args;
int id = args->id;
int stop = args->stop;
printf("[T_%d] Started!\n", id);
for (int n = 2 id; n < stop; n = THREADS_NUM) {
//printf("[T_%d] Checking %d\n", id, n);
int limit = sqrt(n);
bool prime = true;
for (int i = 2; i <= limit; i ) {
if (n % i == 0) {
prime = false;
break;
}
}
if (prime) count ;
}
pthread_exit(NULL);
return NULL;
}
Running the code returns a different output at each run, here are some examples:
[MAIN] Starting T_0
[MAIN] Starting T_1
[MAIN] Starting T_2
[MAIN] Starting T_3
[MAIN] Joining T_0
[T_3] Started!
[T_3] Started!
[T_3] Started!
[T_3] Started!
[MAIN] Joining T_1
[MAIN] Joining T_2
[MAIN] Joining T_3
44 primes found
[MAIN] Starting T_0
[MAIN] Starting T_1
[T_1] Started!
[T_2] Started!
[MAIN] Starting T_2
[MAIN] Starting T_3
[MAIN] Joining T_0
[T_3] Started!
[MAIN] Joining T_1
[MAIN] Joining T_2
[T_3] Started!
[MAIN] Joining T_3
35 primes found
[MAIN] Starting T_0
[MAIN] Starting T_1
[MAIN] Starting T_2
[T_2] Started!
[T_2] Started!
[MAIN] Starting T_3
[T_3] Started!
[MAIN] Joining T_0
[T_3] Started!
[MAIN] Joining T_1
[MAIN] Joining T_2
[MAIN] Joining T_3
22 primes found
Some threads are sometimes called multiple times and others are not called at all. If someone has an idea about how this could be fixed or what the cause could be, please let me know.
CodePudding user response:
Two problems:
struct ipp_args args;
in main() is a local variable in a loop in main() which goes out of scope soon as all threads are created. You need to make itstatic
or allocate it dynamically instead.count
isn't protected from race conditions and access to it cannot be assumed to be atomic, so all manner of strange things might happen, particularly when two threads tries to update it at the same time.
As for the prime number algorithm, it's very slow to have it iterate over even numbers and then include an expensive check if a number is even inside the loop. A less naive version of the for loop is for (int i = 1; i <= limit; i =2)
, then you don't need to worry about even numbers.