4. 编程练习

哲学家就餐问题是一个经典的死锁问题。这个问题是由Dijkstra提出的，用来演示死锁。问题描述如下：

有5个哲学家围坐在一张圆桌旁，每个哲学家面前有一碗饭，每两个哲学家之间有一根筷子。哲学家在思考时不需要任何资源，当他饿了时，需要拿起他左右两边的筷子才能吃饭。如果筷子被其他哲学家拿着，他就必须等待，直到其他哲学家放下筷子。当一个哲学家吃饱后，他会放下筷子继续思考。

请编写程序模拟这个场景，要求：

每个哲学家是一个线程
使用互斥锁模拟筷子
使用条件变量实现哲学家等待筷子的机制
使用usleep(3)函数来观察死锁现象
修改算法以避免死锁

示例输出：

Philosopher 0 is thinking
Philosopher 1 is thinking
Philosopher 2 is thinking
Philosopher 3 is thinking
Philosopher 4 is thinking
Philosopher 0 is hungry
Philosopher 0 picks up chopstick 0
Philosopher 0 picks up chopstick 1
Philosopher 0 is eating
Philosopher 0 puts down chopstick 1
Philosopher 0 puts down chopstick 0
Philosopher 0 is thinking
...

提示：

可以使用pthread_mutex_t数组来表示筷子
可以使用pthread_cond_t数组来表示哲学家等待筷子的条件变量
可以使用pthread_mutex_t来表示哲学家状态的互斥锁
可以使用usleep(3)函数来模拟哲学家思考和吃饭的时间
可以使用pthread_cond_wait(3)函数来实现哲学家等待筷子的机制
可以使用pthread_cond_signal(3)函数来唤醒等待筷子的哲学家

参考代码：

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

#define N 5
#define LEFT (i + N - 1) % N
#define RIGHT (i + 1) % N

#define THINKING 0
#define HUNGRY 1
#define EATING 2

int state[N];
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond[N];
pthread_mutex_t chopstick[N];

void test(int i)
{
    if (state[i] == HUNGRY &&
        state[LEFT] != EATING &&
        state[RIGHT] != EATING) {
        state[i] = EATING;
        pthread_cond_signal(&cond[i]);
    }
}

void take_chopsticks(int i)
{
    pthread_mutex_lock(&mutex);
    state[i] = HUNGRY;
    printf("Philosopher %d is hungry\n", i);
    test(i);
    while (state[i] != EATING)
        pthread_cond_wait(&cond[i], &mutex);
    pthread_mutex_unlock(&mutex);
}

void put_chopsticks(int i)
{
    pthread_mutex_lock(&mutex);
    state[i] = THINKING;
    printf("Philosopher %d is thinking\n", i);
    test(LEFT);
    test(RIGHT);
    pthread_mutex_unlock(&mutex);
}

void *philosopher(void *arg)
{
    int i = *(int *)arg;
    while (1) {
        printf("Philosopher %d is thinking\n", i);
        usleep(rand() % 1000000);
        take_chopsticks(i);
        printf("Philosopher %d is eating\n", i);
        usleep(rand() % 1000000);
        put_chopsticks(i);
    }
}

int main()
{
    int i;
    pthread_t tid[N];
    int id[N];

    srand(time(NULL));

    for (i = 0; i < N; i++) {
        pthread_cond_init(&cond[i], NULL);
        pthread_mutex_init(&chopstick[i], NULL);
        state[i] = THINKING;
    }

    for (i = 0; i < N; i++) {
        id[i] = i;
        pthread_create(&tid[i], NULL, philosopher, &id[i]);
    }

    for (i = 0; i < N; i++)
        pthread_join(tid[i], NULL);

    return 0;
}

这个程序可能会发生死锁。为了避免死锁，可以修改算法，让哲学家总是先拿编号小的筷子，再拿编号大的筷子。这样就不会出现循环等待的情况。

修改后的代码：

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

#define N 5
#define LEFT (i + N - 1) % N
#define RIGHT (i + 1) % N

#define THINKING 0
#define HUNGRY 1
#define EATING 2

int state[N];
pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;
pthread_cond_t cond[N];
pthread_mutex_t chopstick[N];

void test(int i)
{
    if (state[i] == HUNGRY &&
        state[LEFT] != EATING &&
        state[RIGHT] != EATING) {
        state[i] = EATING;
        pthread_cond_signal(&cond[i]);
    }
}

void take_chopsticks(int i)
{
    pthread_mutex_lock(&mutex);
    state[i] = HUNGRY;
    printf("Philosopher %d is hungry\n", i);
    test(i);
    while (state[i] != EATING)
        pthread_cond_wait(&cond[i], &mutex);
    pthread_mutex_unlock(&mutex);
}

void put_chopsticks(int i)
{
    pthread_mutex_lock(&mutex);
    state[i] = THINKING;
    printf("Philosopher %d is thinking\n", i);
    test(LEFT);
    test(RIGHT);
    pthread_mutex_unlock(&mutex);
}

void *philosopher(void *arg)
{
    int i = *(int *)arg;
    while (1) {
        printf("Philosopher %d is thinking\n", i);
        usleep(rand() % 1000000);
        take_chopsticks(i);
        printf("Philosopher %d is eating\n", i);
        usleep(rand() % 1000000);
        put_chopsticks(i);
    }
}

int main()
{
    int i;
    pthread_t tid[N];
    int id[N];

    srand(time(NULL));

    for (i = 0; i < N; i++) {
        pthread_cond_init(&cond[i], NULL);
        pthread_mutex_init(&chopstick[i], NULL);
        state[i] = THINKING;
    }

    for (i = 0; i < N; i++) {
        id[i] = i;
        pthread_create(&tid[i], NULL, philosopher, &id[i]);
    }

    for (i = 0; i < N; i++)
        pthread_join(tid[i], NULL);

    return 0;
}

这个修改后的程序不会发生死锁，因为哲学家总是按照固定的顺序拿筷子，不会出现循环等待的情况。

4. 编程练习 ​

4. 编程练习