c - 在不忙等待的情况下实现互斥锁

Question

我得到了一项大学作业，无需忙等待即可实现互斥锁。我正在尝试实现它，但收效甚微。有时，它会在其他时候抛出分段溢出，但它会一直挂起，但是，当我在 gdb 中运行它时，它每次都能完美运行。

互斥锁.c

#define _GNU_SOURCE 

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <signal.h>
#include <stdbool.h>
#include <sys/syscall.h>
#include "stack.h"

#define NUM_THREADS 2

// shared data structure
int sum = 0;

struct Stack waiting_q;

bool mutex_locked = false;

void * got_signal(int x) { return NULL; }

void acquire()
{
    bool first_time = true;
    while (!__sync_bool_compare_and_swap(&mutex_locked, false, true))
    {
        if (first_time)
        {
            push(&waiting_q, pthread_self());
            first_time = false;
        }
        printf("%ld is waiting for mutex\n", syscall(SYS_gettid));
        pause();
    }
    printf("Mutex acquired by %ld\n", syscall(SYS_gettid));
}

void release()
{
    int thread_r = pop(&waiting_q);
    if (waiting_q.size != 0 && thread_r != INT_MIN)
        pthread_kill(thread_r, SIGCONT);

    mutex_locked = false;
    printf("Mutex released by = %ld\n", syscall(SYS_gettid));
}

void * work()
{
    acquire();

    for (int i = 0; i < 10000; i++)
    {
        sum = sum + 1;
    }
    release();
    return NULL;
}

int main()
{
    init_stack(&waiting_q);
    pthread_t threads[NUM_THREADS];
    for (int i = 0; i < NUM_THREADS; i++)
    {
        int rc = pthread_create(&threads[i], NULL, work, NULL);
        if (rc != 0)
            printf("Error creating thread\n");
    }

    for (int i = 0; i < NUM_THREADS; i++)
    {
        pthread_join(threads[i], NULL);
    }

    printf("Value of Sum = %d\n", sum);
    return 0;
}

堆栈.h

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <pthread.h>

struct Node{
    struct Node * next;
    pthread_t x;
};

struct Stack{
    struct Node * head;
    int size;
};

void push(struct Stack * s, pthread_t n)
{
    struct Node * new_head = malloc(sizeof(struct Node));
    new_head->next = s->head;
    new_head->x = n;
    s->head = new_head;
    s->size++;
}

pthread_t pop(struct Stack * s)
{
    pthread_t rc = INT_MIN;
    if (s->head != NULL)
    {
        rc = s->head->x;
        struct Node * next = s->head->next;
        free(s->head);
        s->head = next;
        return rc;
    }
    s->size--;
    return rc;
}

void init_stack(struct Stack * s)
{
    s->head = 0;
    s->size = 0;
}

Answer 1

从互斥锁实现中访问您的 Stack 数据结构是不同步的。

多个线程可能同时尝试获取互斥量，这将导致它们同时访问waiting_q。同样，释放线程的 pop() 访问 waiting_q 与获取线程的 push() 访问不同步。

堆栈 上的这种数据竞争很可能是导致段错误的原因。