Not sure if I need a mutex or not

Question

I am new to parallel programming, so be nice. I have a basic sequential program (for homework) and I'm trying to turn it into a multi-threaded program. I'm not sure if I need a lock for my second shared variable. Threads should change my variable, but never read them. A single countdown should be read after the loop that spawns all my threads has completed the key distribution.

#define ARRAYSIZE 50000 #include <pthread.h> #include <stdlib.h> #include <stdio.h> #include <sys/time.h> void binary_search(int *array, int key, int min, int max); int count = 0; // count of intersections int l_array[ARRAYSIZE * 2]; //array to check for intersection int main(void) { int r_array[ARRAYSIZE]; //array of keys int ix = 0; struct timeval start, stop; double elapsed; for(ix = 0; ix < ARRAYSIZE; ix++) { r_array[ix] = ix; } for(ix = 0; ix < ARRAYSIZE * 2; ix++) { l_array[ix] = ix + 500; } gettimeofday(&start, NULL); for(ix = 0; ix < ARRAYSIZE; ix++) { //this is where I will spawn off separate threads binary_search(l_array, r_array[ix], 0, ARRAYSIZE * 2); } //wait for all threads to finish computation, then proceed. fprintf(stderr, "%d\n", count); gettimeofday(&stop, NULL); elapsed = ((stop.tv_sec - start.tv_sec) * 1000000+(stop.tv_usec-start.tv_usec))/1000000.0; printf("time taken is %f seconds\n", elapsed); return 0; } void binary_search(int *array, int key, int min, int max) { int mid = 0; if (max < min) return; else { mid = (min + max) / 2; if (array[mid] > key) return binary_search(array, key, min, mid - 1); else if (array[mid] < key) return binary_search(array, key, mid + 1, max); else { //this is where I'm not sure if I need a lock or not count++; return; } } } 

Answer 1

Actually, the code that you wrote it performs both reading and changing the variable. If you looked at the machine code that is generated for a string like

 count++ 

you will see that it consists of something like

 fetch count into register increment register store count 

So you should use the mutex. (And even if you can leave without it, why not take the opportunity?)

Answer 2

As you suspect, count++; requires synchronization. Actually, this is not something that you should try to "leave", and not do. Sooner or later, the second thread will count the countdown after the first thread reads it, but before it increases it. Then you will miss the score. It is impossible to predict how often this will happen. This can happen once in the blue moon or thousands of times per second.

Answer 3

If you just need the exact increments for count for multiple threads, these one-time updates are exactly what locked memory functions are for.

For this, I would use: __ sync_add_and_fetch if you are using gcc. There you can perform many locking operations, most of which are platform dependent, so check your documentation. However, for updating counters like this, they can save a ton of hassle. Other examples include InterlockedIncrement on Windows, OSAtomicIncrement32 on OS X, etc.