my peterson_lock failed in this situation

Question

Code:
[peterson_lock.h]

#include <pthread.h>

typedef struct {
    volatile bool flag[2];
    volatile int victim;
} peterson_lock_t;

void peterson_lock_init(peterson_lock_t &lock) {
    lock.flag[0] = lock.flag[1] = false;
    lock.victim = 0;
}

void peterson_lock(peterson_lock_t &lock, int id) {
    lock.victim = id; // Mark as A
    lock.flag[id] = true; // Mark as B
    asm volatile ("mfence" : : : "memory");
    while (lock.flag[1 - id] && lock.victim == id);
}

void peterson_unlock(peterson_lock_t &lock, int id) {
    lock.flag[id] = false;
    lock.victim = id;
}

[main.cpp]

#include <stdio.h>
#include "peterson_lock.h"

peterson_lock_t lock;
int count = 0;

void *routine0(void *arg) {
    int *cnt = (int *)arg;
    for (int i = 0; i < *cnt; ++i) {
        peterson_lock(lock, 0);
        ++count;
        peterson_unlock(lock, 0);
    }

    return NULL;
}

void *routine1(void *arg) {
    int *cnt = (int *)arg;
    for (int i = 0; i < *cnt; ++i) {
        peterson_lock(lock, 1);
        ++count;
        peterson_unlock(lock, 1);
    }
}

int main(int argc, char **argv) {
    peterson_lock_init(lock);
    pthread_t thread0, thread1;
    int count0 = 10000;
    int count1 = 20000;
    pthread_create(&thread0, NULL, routine0, (void *)&count0);
    pthread_create(&thread1, NULL, routine1, (void *)&count1);

    pthread_join(thread0, NULL);
    pthread_join(thread1, NULL);

    printf("Expected: %d\n", (count0 + count1));
    printf("Reality : %d\n", count);

    return 0;
}

Run this program 1000 times, sometimes the result is not 30000. But is I switch A and B, the result is always 30000. But how could this happend?

[please ignore this line, only to make this question could be submitted.please ignore this line, only to make this question could be submitted.please ignore this line, only to make this question could be submitted.]

Answer 1

The algorithm requires that you do swap your A and B. In other words your posted code isn't a correct implementation of Peterson's algorithm.

Let us see what goes wrong.

First take this code:

void peterson_lock(peterson_lock_t &lock, int id) {
    lock.victim = id; // Mark as A
    lock.flag[id] = true; // Mark as B
    asm volatile ("mfence" : : : "memory");
    while (lock.flag[1 - id] && lock.victim == id);
}

and write it as a function per process:

void peterson_lock_0(peterson_lock_t &lock) {
    lock.victim = 0;
    lock.flag[0] = true;
    asm volatile ("mfence" : : : "memory");
    while (lock.flag[1] && lock.victim == 0);
}

void peterson_lock_1(peterson_lock_t &lock) {
    lock.victim = 1;
    lock.flag[1] = true;
    asm volatile ("mfence" : : : "memory");
    while (lock.flag[0] && lock.victim == 1);
}

Then let process 0 execute the first line, then switch to process 1 (executing the whole function) and then back to process 0.

peterson_lock_0:                       peterson_lock_1:
-------------------------------------------------------
lock.victim = 0;
                                      lock.victim = 1;
                                      lock.flag[1] = true;
                                      asm volatile ("mfence" : : : "memory");
                                      while (lock.flag[0] && lock.victim == 1);
                                      // lock.flag[0] is false so
                                      // the process enters critical
                                      // section
lock.flag[0] = true;
asm volatile ("mfence" : : : "memory");
while (lock.flag[1] && lock.victim == 0);
// lock.victim is 1 so
// the process enters critical
// section

Now both processes are in the critical section. That's bad.

See https://en.wikipedia.org/wiki/Peterson%27s_algorithm for more information