When I implemented MCS lock, understanding "The Art of Multiprocessor Programming" book.

The program gets stuck.

This is my source code.

The problem is I don't know what's wrong with my code.

I think my logic is the same as the code of the book.

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdatomic.h>

#define THREADS 2

pthread_t thread_t[THREADS];

struct Lock
{
    struct Lock* next;
    bool locked;
};

_Atomic(struct Lock*) tail;

_Thread_local struct Lock* my_lock;

void lock_()
{
    struct Lock* lock = (struct Lock*)malloc(sizeof(struct Lock));

    struct Lock* pred = atomic_exchange(&tail, lock);

    my_lock = lock;

    if (pred)
    {
        lock->locked = true;
        pred->next = lock;
        __sync_synchronize();
        while (lock->locked) {
        }
    }
}

void unlock_()
{
    struct Lock* succ = my_lock->next;

    if (succ == NULL)
    {
        struct Lock* expected = my_lock;
        if (atomic_compare_exchange_strong(&tail, &expected, NULL))
        {
            return;
        }

        while (succ == NULL) {
            succ = my_lock->next;
        }
    }

    succ->locked = false;
}

void* lock_func()
{
    int j = 0;
    for (int i = 0; i < 10000;   i)
    {
        lock_();
        j  ;
        unlock_();
    }
}

int main(int argc, char *argv[])
{
    int i;

    for (i = 0; i < THREADS;   i)
    {
        if (pthread_create(&thread_t[i], NULL, lock_func, NULL) < 0)
        {
            perror("thread create error:");
            exit(0);
        }
    }

    for (i = 0; i < THREADS;   i)
        pthread_join(thread_t[i], NULL);
}

I used linux ubuntu to execute it. My program seems to work well when compiled with an O0 flag without optimization.

CodePudding user response：

The spin loop:

        while (lock->locked) {
        }

looks very bad. Since lock->locked is not atomic, accessing it concurrently in another thread (as you do) is a data race, causing undefined behavior.

Right there the game is lost, but let's explain why it breaks in the particular way you observe. Since a data race would cause UB, the compiler can assume it is not accessed concurrently from another thread, meaning that it can never change. Since you set it to true previously, the compiler therefore can assume it is true forever, and that while (lock->locked) { } is an infinite loop. Since the loop is guaranteed to be infinite, it is unnecessary to do the test, and the compiler "optimizes" it into an unconditionally infinite loop.

That's also why it happens to appear to work with -O0: then the compiler doesn't do that particular optimization. It is, however, still free to make it misbehave in any way at all; you just seem to have gotten "lucky" that it didn't.

The __sync_synchronize() (which should be considered obsolete for a supposedly C11 program) does nothing to help with this. You can't solve a data race by adding fences like that. And anyway, it is outside the loop.

You can see the infinite loop in the generated assembly on godbolt at lines 27-28:

.L4:
        jmp     .L4

The _unlock function has exactly the same problem and also gets optimized into an infinite loop.

Frankly, this whole program looks completely wrong. Whoever wrote it doesn't seem to have had any idea of the data race rules. If it's truly from a book, then I don't think you should read that book anymore.