如何只用互斥体解决哲学家就餐问题？

Question

我编写此程序是为了使用 Dijkstra 算法解决 dining philosophers problem，注意我使用的是布尔数组 (data->locked) 而不是二进制信号量数组。

我不确定这个解决方案是否有效（因此是 SO 问题）。

在 test 和 take_forks 函数中访问 data->locked 数组会导致数据竞争吗？如果是这样，是否有可能仅使用互斥体使用 Dijkstra 算法来解决此问题？

我只被允许使用互斥锁，不能使用信号量，不能使用条件变量（这是一个赋值）。

用法示例：

./a.out 4 1000 1000

#include <pthread.h>
#include <stdlib.h>
#include <stdio.h>
#include <unistd.h>
#include <stdbool.h>

#define NOT_HUNGRY  1
#define HUNGRY      2
#define EATING      3
#define RIGHT   ((i + 1) % data->n)
#define LEFT    ((i + data->n - 1) % data->n)

typedef struct s_data
{
    int             n;
    int             t_sleep;
    int             t_eat;
    int             *state;
    bool            *locked;
    pthread_mutex_t *state_mutex;
}   t_data;

typedef struct s_arg
{
    t_data  *data;
    int     i;
}   t_arg;

int ft_min(int a, int b)
{
    if (a < b)
        return (a);
    return (b);
}

int ft_max(int a, int b)
{
    if (a > b)
        return (a);
    return (b);
}

// if the LEFT and RIGHT threads are not eating
// and thread number i is hungry, change its state to EATING
// and signal to the while loop in `take_forks` to stop blocking.
// if a thread has a state of HUNGRY then it's guaranteed
// to be out of the critical section of `take_forks`.
void    test(int i, t_data *data)
{
    if (
        data->state[i] == HUNGRY
        && data->state[LEFT] != EATING
        && data->state[RIGHT] != EATING
    )
    {
        data->state[i] = EATING;
        data->locked[i] = false;
    }
}

// set the state of the thread number i to HUNGRY
// and block until the LEFT and RIGHT threads are not EATING
// in which case they will call `test` from `put_forks`
// which will result in breaking the while loop
void    take_forks(int i, t_data *data)
{
    pthread_mutex_lock(data->state_mutex);
    data->locked[i] = true;
    data->state[i] = HUNGRY;
    test(i, data);
    pthread_mutex_unlock(data->state_mutex);
    while (data->locked[i]);
}

// set the state of the thread number i to NOT_HUNGRY
// then signal to the LEFT and RIGHT threads
// so they can start eating when their neighbors are not eating
void    put_forks(int i, t_data *data)
{
    pthread_mutex_lock(data->state_mutex);
    data->state[i] = NOT_HUNGRY;
    test(LEFT, data);
    test(RIGHT, data);
    pthread_mutex_unlock(data->state_mutex);
}

void    *philosopher(void *_arg)
{
    t_arg   *arg = _arg;

    while (true)
    {
        printf("%d is thinking\n", arg->i);
        take_forks(arg->i, arg->data);
        printf("%d is eating\n", arg->i);
        usleep(arg->data->t_eat * 1000);
        put_forks(arg->i, arg->data);
        printf("%d is sleeping\n", arg->i);
        usleep(arg->data->t_sleep * 1000);
    }
    return (NULL);
}

void    data_init(t_data *data, pthread_mutex_t *state_mutex, char **argv)
{
    int i = 0;

    data->n = atoi(argv[1]);
    data->t_eat = atoi(argv[2]);
    data->t_sleep = atoi(argv[3]);
    pthread_mutex_init(state_mutex, NULL);
    data->state_mutex = state_mutex;
    data->state = malloc(data->n * sizeof(int));
    data->locked = malloc(data->n * sizeof(bool));
    while (i < data->n)
    {
        data->state[i] = NOT_HUNGRY;
        data->locked[i] = true;
        i++;
    }
}

int main(int argc, char **argv)
{
    pthread_mutex_t state_mutex;
    t_data          data;
    t_arg           *args;
    pthread_t       *threads;
    int             i;

    if (argc != 4)
    {
        fputs("Error\nInvalid argument count\n", stderr);
        return (1);
    }
    data_init(&data, &state_mutex, argv);
    args = malloc(data.n * sizeof(t_arg));
    i = 0;
    while (i < data.n)
    {
        args[i].data = &data;
        args[i].i = i;
        i++;
    }
    threads = malloc(data.n * sizeof(pthread_t));
    i = 0;
    while (i < data.n)
    {
        pthread_create(threads + i, NULL, philosopher, args + i);
        i++;
    }
    i = 0;
    while (i < data.n)
        pthread_join(threads[i++], NULL);
}

Answer 1

您的自旋循环 while (data->locked[i]); 是一场数据竞赛；您在读取它时不持有锁 data->locked[i]，因此另一个线程可以在您读取它时获取锁并写入同一个变量。事实上，你依赖于那件事的发生。但这是未定义的行为。

直接的实际后果是编译器可以删除测试（因为在没有数据竞争的情况下，data->locked[i] 无法在迭代之间更改），或者完全删除循环（因为它现在是无限循环，并且非平凡的无限循环是 UB）。当然也有可能出现其他不希望的结果。

所以你必须在测试标志时保持互斥锁。如果它是假的，那么你应该持有互斥锁直到你将它设置为真并做你的其他工作；否则会有一场比赛，另一个线程可以首先获得它。如果为真，则丢弃互斥量，稍等片刻，重新获取，然后重试。

（“一小段时间”有多长，以及您在这期间选择做什么工作，可能是您应该测试的事情。根据您的 pthread 实现使用的公平算法类型，您可能运行进入 take_forks 成功重新获取锁的情况，即使 put_forks 也在等待锁定它。）

当然，在“真正的”程序中，您一开始就不会这样做；你会使用条件变量。

如何只用互斥体解决哲学家就餐问题？

How to solve the dining philosophers problem with only mutexes?

c

multithreading

dining-philosopher