Multi Threading - Peterson's algorithm not working

Question

Here I use Peterson's algorithm to implement mutual exclusion.

I have two very simple threads, one to increase a counter by 1, another to reduce it by 1.

const int PRODUCER = 0,CONSUMER =1;
int counter;
int flag[2];
int turn;

void *producer(void *param)
{

    flag[PRODUCER]=1;
    turn=CONSUMER;
    while(flag[CONSUMER] && turn==CONSUMER);

    counter++;

    flag[PRODUCER]=0;
}

void *consumer(void *param)
{
    flag[CONSUMER]=1;
    turn=PRODUCER;
    while(flag[PRODUCER] && turn==PRODUCER);

    counter--;

    flag[CONSUMER]=0;
}

They works fine when I just run them once.

But when I run them again again in a loop, strange things happen.

Here is my main function.

int main(int argc, char *argv[])
{
    int case_count =0;
    counter =0;
    while(counter==0)
    {
        printf("Case: %d\n",case_count++);
        pthread_t tid[2];
        pthread_attr_t attr[2];

        pthread_attr_init(&attr[0]);
        pthread_attr_init(&attr[1]);

        counter=0;
        flag[0]=0;
        flag[1]=0;
        turn = 0;

        printf ("Counter is intially set to %d\n",counter);

        pthread_create(&tid[0],&attr[0],producer,NULL);
        pthread_create(&tid[1],&attr[1],consumer,NULL);

        pthread_join(tid[0],NULL);
        pthread_join(tid[1],NULL);

        printf ("counter is now %d\n",counter);
    }

    return 0;
}

I run the two threads again and again, until in one case the counter isn't zero.

Then, after several cases, the program will always stop! Some times after hundreds of cases, some times thousands, or event tens of thousand.

It means in one case the counter isn't zero. But why??? the two threads modify the counter in critical session, and increase and decrease it only once. Why will the counter not be zero?

Then I run this code in other computers, more strange things happen - in some computers the program seems has no problem, and the others have the same problem with me! Why?

By the way, in my computer, I run this code in VM ware's virtual computer, Ubuntu 16.04. Others' computer is also Ubuntu 16.04, but not all of them are in virtual machines. And the computer with problem contains both virtual machines and real machines.

Answer 1

Peterson's algorithm only works on single core processors/single CPU systems.

That's because they don't do real parallel processing. Two atomar operations never get executet at the same time there.

If you got 2 or more CPUs/CPU cores the amount of atomar operations who can be executed at the same time increase by one for each cpu(core). This means, even if an integer assignment is atomar it can be executed multiple times at the same time in different CPUs/Cores.

In your case turn=CONSUMER/PRODUCER; is just called twice at the same time in different CPUs/cores.

Deacitvate all CPU cores but one for your program and it should work fine.