c program

Goal: multithreaded sieve of eratosthenes

I need help with multithreading (please edit the code so that it works, thanks). This program will seg fault if I use default values ( -t 1 -u 10240) by simply calling ./a.out or if I do something like ./a.out -t 2 -u 5000

#include #include #include #include #include

typedef struct BitBlock { uint32_t bits; pthread_mutex_t mutex; } BitBlock_t;

static uint32_t val = 10240; static BitBlock_t b[4]; static int num_threads = 1; static unsigned short isVerbose;

void setbit(BitBlock_t a[], uint32_t k, int tid) { pthread_mutex_lock(&a[tid * (val / num_threads) / 32 + k / 32].mutex);

// someone suggested this vv but ended up breaking the program more //a[tid * (val / num_threads) / 32 + k / 32].bits |= 1 << (k % 32);

// originally:

a[k / 32].bits |= 1 << (k % 32); pthread_mutex_unlock(&a[tid * (val / num_threads) / 32 + k / 32].mutex); }

void clearbit(BitBlock_t a[], uint32_t k, int tid) { pthread_mutex_lock(&a[tid * (val / num_threads) / 32 + k / 32].mutex); // a[tid * (val / num_threads) / 32 + k / 32].bits &= ~(1 << (k % 32));

a[k / 32].bits &= ~(1 << (k % 32)); pthread_mutex_unlock(&a[tid * (val / num_threads) / 32 + k / 32].mutex); }

int testbit(BitBlock_t a[], uint32_t k, int tid) { int test = -1; pthread_mutex_lock(&a[tid * (val / num_threads) / 32 + k / 32].mutex); // test = ((a[tid * (val / num_threads) / 32 + k / 32].bits & (1 << (k % 32))) != 0);

test = ((a[k / 32].bits & (1 << (k % 32))) != 0); pthread_mutex_unlock(&a[tid * (val / num_threads) / 32 + k / 32].mutex); return test; }

void* sieveoferatosthenes(void* vid) { long tid = (long)vid; uint32_t start = tid * (val / num_threads) + 2; uint32_t end = (tid == num_threads - 1) ? val : (tid + 1) * (val / num_threads) + 1; for (uint32_t j = start; j <= end; j++) { for (uint32_t p = 2; p * p <= j; p++) { if (testbit(b, p, tid) != 1) { for (uint32_t i = p * p; i <= j; i += p) { setbit(b, i, tid); } } } } pthread_exit(EXIT_SUCCESS); }

int main(int argc, char* argv[]) { int opt = -1; pthread_t* threads = NULL; long tid = 0; for (int i = 0; i < 4; i++) {

pthread_mutex_init(&b[i].mutex, NULL);

b[i].bits = 0;

}

while ((opt = getopt(argc, argv, "t:u:hv")) != -1) {

switch (opt) {

case 't':

num_threads = atoi(optarg);

break;

case 'u':

val = atoi(optarg);

break;

case 'h':

printf("%s: -t # -u # -h -v ", argv[0]);

printf("\t-t # for number of threads ");

printf("\t-u # for the upper bound of largest number "); exit(0); break; case 'v': isVerbose = 1; break; default: /* '?' */ exit(EXIT_FAILURE); break; }

}

threads = malloc(num_threads * sizeof(pthread_t)); if(isVerbose) { fprintf(stderr, "number of threads: %d", num_threads); fprintf(stderr, "upper bound: %d", val); }

for (tid = 0; tid < num_threads; tid++) { pthread_create(&threads[tid], NULL, sieveoferatosthenes, (void *) tid); }

for (tid = 0; tid < num_threads; tid++) { pthread_join(threads[tid], NULL); }

for (uint32_t p = 2; p <= val; p++) { if (testbit(b, p, tid) != 1) printf("%u ", p); }

free(threads); for(int i = 0; i < 4; i++) { pthread_mutex_destroy(&b[i].mutex); }

return EXIT_SUCCESS; }