c - Wrong implementation of Peterson's algorithm?

Question

I was trying to learn something about parallel programming, so I tried to implement Peterson's algorithm for an easy example where one shared counter is incremented by 2 threads. I know that Peterson's isn't optimal due to busy waiting but I tried it only for study reasons.

I supposed that the critical section of this code is in the thread function add where the shared counter is incremented. So i call the enter_section function before the counter incrementation and after it I called the leave_function. Is this part wrong? Did I asses the critical section wrong? Problem is that the counter sometimes gives an unexpectable value when these 2 threads are done. It has to 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's 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.
");

    /* waiting for 2nd thread */
    pthread_join (threadargs_array[1].thr_ID, NULL);
    printf("Second thread is done.
");


    printf("Counter value is: %d 
", counter);
    return (EXIT_SUCCESS);
}

Answer 1

You have several problems here:

• the access to your variables will we subject to optimization, so you'd have to declare them volatile, at least.
• Algorithms like this that access data between threads without any of the lock data structures that are provided by POSIX can only work if your primitive operations are guaranteed to be atomic, which they usually aren't on modern processors. In particular the ++ operator is not atomic.

There would be several ways around this, in particular the new C standard C11 offers atomic primitives. But if this is really meant for you as a start to learn parallel programming, I'd strongly suggest that you first look into mutexes, condition variables etc, to learn how POSIX is intended to work.