实现无繁忙等待的互斥锁

Question

我得到了一个大学任务来实现无需等待的互斥锁。我试图实施它，但没有取得太大的成功。有时，它会引发分段溢出，但是当它在gdb中运行时，它会一直运行得很完美。

mutex.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; 
} 

stack.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数据结构是不同步的。

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

该数据在Stack上的竞争很可能是导致段错误的原因。