c: как выявлять и устранять тупики? решение проблемы столовых философов

Question

Я пытаюсь решить проблему столовых философов как упражнение C. В упражнении утверждается, что число философов должно быть переменным (аргумент командной строки), и они должны повторять «думай-жди-ешь» l oop 100 раз (может быть постоянным). Как только я ввожу цикл для повторения операций (внутри потоков философов), он заходит в тупик. Я испробовал два (предложенных учителем!) Подхода: один использует массив мьютексов, другой - два разных массива состояний философии и условных переменных, совместно использующих один мьютекс. Я попытался отладки с использованием valgrind и GDB. Valgrind говорит мне, что в подходе 2 я делаю недопустимое чтение размера 4 при работе с массивом состояний, но я не думаю, что это связано с тупиком / голоданием. Разве это не тупик, а голод? Существуют ли какие-либо методы / хорошие практики gdb для определения источника тупиков?

Вот подход 1. В большинстве случаев он работает правильно, но иногда не возвращает:

static pthread_t *threadarr = NULL;
static pthread_mutex_t *fork_mutex = NULL;
static pthread_mutex_t ic_mutex = PTHREAD_MUTEX_INITIALIZER;


typedef struct _opt {
    int i;  /* Current philosopher */
    int n;  /* Total of philosophers */
    int *ic; /* Iteration count */
    int max_iter; /* Max iterations */
} opt_t;

static void* philosopher(void* arg) {
    opt_t opt = *((opt_t*) arg);
    int dorun = 1;

    while(dorun) {
        /* Take fork on the left, then on the right */
        LOG_DEBUG("Philosopher %d is waiting for left fork...\n", opt.i); fflush(stderr);
        pthread_mutex_lock(&fork_mutex[opt.i]);
        LOG_DEBUG("Philosopher %d got left fork...\n", opt.i); fflush(stderr);
        pthread_mutex_lock(&fork_mutex[(opt.i + 1) % opt.n]);
        LOG_DEBUG("Philosopher %d got forks and eating...\n", opt.i); fflush(stderr);

        sleep(0.1 * (rand()%5 + 1));

        pthread_mutex_unlock(&fork_mutex[opt.i]);
        LOG_DEBUG("Philosopher %d released left fork...\n", opt.i); fflush(stderr);
        pthread_mutex_unlock(&fork_mutex[(opt.i + 1) % opt.n]);
        LOG_DEBUG("Philosopher %d released right fork...\n", opt.i); fflush(stderr);

        LOG_DEBUG("Philosopher %d is thinking...\n", opt.i); fflush(stderr);

        sleep(0.1 * (rand()%5 + 1));

        pthread_mutex_lock(&ic_mutex);
        *(opt.ic) = *(opt.ic) + 1;
        if(*(opt.ic) >= opt.max_iter) {
            printf("Philosopher %d is FULL!\n", opt.i);
            dorun = 0;
        }
        pthread_mutex_unlock(&ic_mutex);

    }

    return NULL;
}

int main(int argc, char *const argv[]) {
    if(argc != 2) { ERR_DIE("usage: %s num\n", argv[0]); }
    int n = atoi(argv[1]);
    if(n <= 0) { ERR_DIE("num must be > 0\n");}

    fork_mutex = malloc(sizeof(pthread_mutex_t) * n);
    for(int i = 0; i < n; i++) pthread_mutex_init(&fork_mutex[i], NULL);

    int ic = 0;
    opt_t *opts = malloc(sizeof(opt_t) * n);
    for(int i = 0; i < n; i++) {
        opts[i].i = i;
        opts[i].n = n;
        opts[i].ic = &ic;
        opts[i].max_iter = 100;
    }

    threadarr = malloc(sizeof(pthread_t) * n);
    for(int i = 0; i < n; i++)
        pthread_create(&(threadarr[i]), NULL, philosopher, &opts[i]);

    for(int i = 0; i < n; i++)
        pthread_join(threadarr[i], NULL);

    for(int i = 0; i < n; i++)
        pthread_mutex_destroy(&fork_mutex[i]);

    return 0;
}

Здесь вместо этого используется подход 2. Макросы MUTEX_LOCK и MUTEX_UNLOCK et c .. предназначены только для того, чтобы сделать код короче, и определяются следующим образом в util.h:

/* Lock a mutex */
#define MUTEX_LOCK(mtx) \
    { int err = 0; if((err = pthread_mutex_lock(mtx)) != 0) {\
        ERR("error locking resource: %s\n", strerror(err)); pthread_exit((void*)&err);\
    } /* printf("locked\n"); */ }

Здесь остальная часть кода второго подхода.

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <pthread.h>
#include <errno.h>
#include <time.h>

#include <util.h>
#include <logger.h>

typedef enum {
    IDLE, /* 0, thinking */
    WAITING, /* 1, waiting for both forks */
    RUNNING /* 2, eating */
} state_t;

/* Options to be passed to philosopher thread */
typedef struct __philosopher_opt {
    /* Mutable data controlled by state MUTEX */
    state_t *state;                 /* Array of states */
    int *eat_count;
    int *think_count;
    int *iter_count;
    pthread_mutex_t *state_mutex;   /* State mutex */
    pthread_cond_t  *state_cond;    /* Array of cond variables */
    /* Immutable data */
    int state_size;                 /* Size of state and cond array */
    int position;                   /* Position of the current phil. in array */
    int iterations;                 /* How many think->wait->eat loop iterations */
} philosopher_opt;

static void* philosopher_worker(void* arg) {
    philosopher_opt opt = *((philosopher_opt*) arg);
    int err, i = opt.position, n = opt.state_size;
    int *ic = opt.iter_count;

    if(opt.iterations < 0
        || i < 0 || i > n) {
        err = EINVAL; pthread_exit(&err);
    }

    /* Loop iterations */
    while(1) {
        /* Philosopher is now hungry */
        MUTEX_LOCK(opt.state_mutex);
        opt.state[i] = WAITING;
        /* Wait until both phil on left and right are not eating */
        while(opt.state[(i-1) % n] == RUNNING || opt.state[(i+1) % n] == RUNNING) {
            if(*ic >= opt.iterations) {
                LOG_DEBUG("Philosopher %d exiting before eating\n", i);
                fflush(stderr);
                MUTEX_UNLOCK(opt.state_mutex);
                pthread_exit((void*)0);
            }
            if(opt.state[(i-1) % n] == RUNNING)
                LOG_DEBUG("Philosopher %d is waiting for fork %d\n", i, (i-1)%n);
            if(opt.state[(i+1) % n] == RUNNING)
                LOG_DEBUG("Philosopher %d is waiting for fork %d\n", i, (i+1)%n);
            fflush(stderr);
            pthread_cond_wait(&(opt.state_cond[i]), opt.state_mutex);
        }
        LOG_DEBUG("Philosopher %d eating...\n", i);
        fflush(stderr);
        /* Philosopher got two forks! */
        opt.state[i] = RUNNING;
        *(opt.eat_count) = *(opt.eat_count) + 1;
        if(*ic >= opt.iterations) {
            LOG_DEBUG("Philosopher %d exiting after eating\n", i);
            fflush(stderr);
            MUTEX_UNLOCK(opt.state_mutex);
            pthread_exit((void*)0);
        }
        MUTEX_UNLOCK(opt.state_mutex);

        sleep(0.1 * (random()%5 + 1));

        /* Think! */
        MUTEX_LOCK(opt.state_mutex);
        opt.state[i] = IDLE;
        *(opt.think_count) = *(opt.think_count) + 1;

        /* Test and set philosopher on the left */
        if(opt.state[(i - 1) % n] == WAITING && opt.state[(i - 2) % n] != RUNNING) {
        /* If opt.state[i-1] at the table is waiting and opt.state[i-2] is NOT eating, opt.state[i-1] can eat */
            //opt.state[(i - 1) % n] = RUNNING;
            LOG_DEBUG("Philosopher %d sent signal to %d\n", i, (i-1)%n);
            fflush(stderr);
            pthread_cond_signal(&opt.state_cond[(i - 1) % n]);
        }
        /* Test and set philosopher on the right */
        if(opt.state[(i + 1) % n] == WAITING && opt.state[(i + 2) % n] != RUNNING) {
        /* If opt.state[i+1] at the table is waiting and opt.state[i+2] is NOT eating, opt.state[i+1] can eat */
            //opt.state[(i + 1) % n] = RUNNING;
            LOG_DEBUG("Philosopher %d sent signal to %d\n", i, (i+1)%n);
            fflush(stderr);
            pthread_cond_signal(&opt.state_cond[(i + 1) % n]);
        }

        /* Looping logic */
        *ic = *ic + 1;

        /* The philosopher is done! Both forks are free */
        if(*ic >= opt.iterations) {
            LOG_DEBUG("Philosopher %d exiting after thinking\n", i);
            fflush(stderr);
            MUTEX_UNLOCK(opt.state_mutex);
            pthread_exit((void*)0);
        }
        MUTEX_UNLOCK(opt.state_mutex);

        sleep(0.1 * (random()%5 + 1));
    }
    pthread_exit((void*)0);
}

int main(int argc, char *const argv[]) {
    int err = 0, n = 0;
    if (argc != 2) {
        ERR_DIE("usage: %s NUM\n", argv[0]);
    }
    n = atoi(argv[1]);
    if(n <= 0) {
        ERR_DIE("Invalid argument: %s\n", argv[1]);
    }

    /* Initialize state mutex */
my    pthread_mutex_t state_mutex;

    if((err = pthread_mutex_init(&state_mutex, NULL)) != 0) {
        ERR_DIE("Error initializing mutex: %s\n", strerror(errno));
    }

    /* Initialize state */
    state_t *state = malloc(sizeof(state_t) * n);
    for(int i = 0; i < n; i++) state[i] = IDLE;

    /* Initialize array of cond variables */
    pthread_cond_t *state_cond = malloc(sizeof(pthread_cond_t) * n);
    for(int i = 0; i < n; i++) {
        if((err = pthread_cond_init(&state_cond[i], NULL)) != 0)
            {errno = err; ERR_DIE("Error initializing condition variables: %s\n", strerror(errno));}
    }

    /* Initialize each thread options and launch it*/
    philosopher_opt *opts = malloc(sizeof(philosopher_opt) * n);
    pthread_t *tid = malloc(sizeof(pthread_t) * n);
    pthread_attr_t *attr_p = malloc(sizeof(pthread_attr_t) * n);
    int iter_count = 0;

    for(int i = 0; i < n; i++) {
        opts[i].iterations = 5;
        opts[i].iter_count = &iter_count;
        opts[i].position = i;
        opts[i].state = state;
        opts[i].state_mutex = &state_mutex;
        opts[i].state_cond = state_cond;
        opts[i].state_size = n;

        opts[i].eat_count = calloc(1, sizeof(int));
        opts[i].think_count = calloc(1, sizeof(int));

        pthread_attr_init(&attr_p[i]);
        if((err = pthread_create(&tid[i], NULL, philosopher_worker, &opts[i])) != 0) {
            ERR_DIE("Error spawning thread %d: %s", i, strerror(err));
        }
    }

    int status;
    for(int i = 0; i < n; i++) {
        if((err = pthread_join(tid[i], (void*) &status)) != 0) {
            ERR_DIE("Error waiting for thread %d: %s", i, strerror(err));
        }
        //printf("Thread %d exited with status code %d\n", i, status);
        printf("Philosopher %d ate %d times and thought %d times\n", i, *(opts[i].eat_count), *(opts[i].think_count));
    }

    /* Cleanup */
    free(state);
    pthread_mutex_destroy(&state_mutex);
    free(state_cond);

    return 0;
}

Я не могу понять, делаю ли я что-то не так, так как я следовал обоим алгоритмам, изложенным проф.