實現無繁忙等待的互斥鎖

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上的競爭很可能是導致段錯誤的原因。