Incorrect Peterson Algorithm Implementation?

Question

I was trying to learn something about parallel programming, so I tried to implement the Peterson algorithm for a simple example, when one common counter is incremented by 2 threads. I know that Peterson is not optimal due to lively expectations, but I tried it only for study reasons.

I suggested that the critical part of this code is in the add thread function, where the total counter incremented. Therefore, I call the enter_section function before the increment of the counter, after which I call leave_function . Is this part wrong? Am I really mistaken in the critical section? The problem is that the counter sometimes gives an undefined value when these 2 threads are executed. It should be a synchronization problem between threads, but I just don't see it ... Thanks for any help.

 #include <stdio.h> #include <stdlib.h> #include <pthread.h> int counter; /* global shared counter */ int flag[2] = {0, 0}; /* Variables for Peterson algorithm */ int turn = 0; typedef struct threadArgs { pthread_t thr_ID; int num_of_repeats; int id; } THREADARGS; void enter_section (int thread) { int other = 1 - thread; flag[thread] = 1; turn = thread; while ((turn == thread) && (flag[other] == 1)); return; } void leave_section (int thread) { flag[thread] = 0; return; } void * add (void * arg) { int i; THREADARGS * a = (THREADARGS *) arg; for (i = 0; i < a->num_of_repeats; i++) { enter_section(a->id); counter++; leave_section(a->id); } return NULL; } int main () { int i = 1; pthread_attr_t thrAttr; THREADARGS threadargs_array[2]; pthread_attr_init (&thrAttr); pthread_attr_setdetachstate (&thrAttr, PTHREAD_CREATE_JOINABLE); /* creating 1st thread */ threadargs_array[0].id = 0; threadargs_array[0].num_of_repeats = 1000000; pthread_create(&threadargs_array[0].thr_ID, &thrAttr, add, &threadargs_array[0]); /* creating 2nd thread */ threadargs_array[1].id = 1; threadargs_array[1].num_of_repeats = 2000000; pthread_create(&threadargs_array[1].thr_ID, &thrAttr, add, &threadargs_array[1]); /* free resources for thread attributes */ pthread_attr_destroy (&thrAttr); /* waiting for 1st thread */ pthread_join (threadargs_array[0].thr_ID, NULL); printf("First thread is done.\n"); /* waiting for 2nd thread */ pthread_join (threadargs_array[1].thr_ID, NULL); printf("Second thread is done.\n"); printf("Counter value is: %d \n", counter); return (EXIT_SUCCESS); } 

Answer 1

You have a few problems:

• access to your variables will be subject to optimization, so you will have to declare them volatile , at least.
• Such algorithms allow you to access data between threads without any blocking data structure that is provided by POSIX and can only work if your primitive operations are guaranteed to be atomic, which is usually not the case with modern processors. In particular, the ++ operator is not atomic.

There would be several ways around this, in particular, the new C11 standard C11 offers atomic primitives. But if it really means that you are starting to learn parallel programming, I highly recommend that you first study mutexes, state variables, etc., to find out how POSIX is designed to work.