利用信号量机制解决哲学家进餐问题实验报告

哲学家进餐问题是经典的并发编程问题，其场景为五位哲学家围坐在一个圆桌旁，每位哲学家需要交替地进行思考和进餐，而进餐需要使用两个相邻的叉子，因此如果每位哲学家都拿起自己左边的叉子，就会导致死锁。

解决这个问题的方法之一就是利用信号量机制。我们可以为每个叉子都创建一个信号量，表示该叉子是否可用。在每位哲学家进行进餐时，先判断其左右两个叉子是否都可用，如果都可用，则分别将左右两个叉子的信号量减1，表示占用了这两个叉子，然后开始进餐。进餐完成后，将左右两个叉子的信号量加1，表示释放了这两个叉子。

以下是使用信号量机制解决哲学家进餐问题的实验报告：

一、实验目的

掌握信号量机制在解决并发编程问题中的应用，理解哲学家进餐问题的场景和解决方法。

二、实验环境

操作系统：Linux

编程语言：C语言

三、实验原理

1. 信号量机制

信号量是一种特殊的变量，用于在多进程或多线程之间同步和互斥访问共享资源。信号量的值可以被多个进程或线程访问和修改，但只能通过特定的操作进行修改。一般来说，信号量可以用于以下两个目的：

(1) 用于同步进程或线程，保证它们按照某种顺序执行。

(2) 用于互斥访问共享资源，保证同时只有一个进程或线程访问共享资源。

信号量的操作包括两种：P操作和V操作。P操作用于申请信号量，V操作用于释放信号量。具体来说，P操作会将信号量的值减1，如果减1后的值为负数，则表示资源已被占用，进程或线程需要等待；V操作会将信号量的值加1，如果加1后的值为非负数，则表示资源已释放，进程或线程可以继续执行。

2. 哲学家进餐问题

哲学家进餐问题是一种典型的并发编程问题，场景为五位哲学家围坐在一个圆桌旁，每位哲学家需要交替地进行思考和进餐，而进餐需要使用两个相邻的叉子，因此如果每位哲学家都拿起自己左边的叉子，就会导致死锁。为了避免死锁，需要采用一定的算法来保证哲学家们能够交替地进餐，而不会出现所有哲学家都在等待叉子的情况。

一种常用的解决方法是利用信号量机制，为每个叉子都创建一个信号量，表示该叉子是否可用。在每位哲学家进行进餐时，先判断其左右两个叉子是否都可用，如果都可用，则分别将左右两个叉子的信号量减1，表示占用了这两个叉子，然后开始进餐。进餐完成后，将左右两个叉子的信号量加1，表示释放了这两个叉子。

四、实验步骤

1. 定义信号量和哲学家的结构体：

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

#define N 5 // 哲学家数量

typedef struct {
    sem_t fork_left; // 左边的叉子
    sem_t fork_right; // 右边的叉子
    int id; // 哲学家编号
} philosopher_t;

2. 创建哲学家和叉子的信号量：

int main() {
    philosopher_t philosophers[N];
    sem_t forks[N];

    for (int i = 0; i < N; i++) {
        sem_init(&forks[i], 0, 1); // 初始化叉子的信号量为1，表示可用
    }

    for (int i = 0; i < N; i++) {
        philosophers[i].id = i;
        sem_init(&philosophers[i].fork_left, 0, 1); // 初始化左边叉子的信号量为1，表示可用
        sem_init(&philosophers[i].fork_right, 0, 1); // 初始化右边叉子的信号量为1，表示可用
    }
    // ...
}

3. 创建哲学家线程和进餐函数：

void *eat(void *arg) {
    philosopher_t *p = (philosopher_t *) arg;
    int id = p->id;
    sem_t *fork_left = &p->fork_left;
    sem_t *fork_right = &p->fork_right;

    while (1) {
        printf("Philosopher %d is thinking\n", id);
        sleep(1);

        printf("Philosopher %d is hungry\n", id);
        sem_wait(fork_left); // 申请左边的叉子
        printf("Philosopher %d picks up fork %d\n", id, id);
        sem_wait(fork_right); // 申请右边的叉子
        printf("Philosopher %d picks up fork %d\n", id, (id + 1) % N);

        printf("Philosopher %d is eating\n", id);
        sleep(1);

        sem_post(fork_left); // 释放左边的叉子
        sem_post(fork_right); // 释放右边的叉子
        printf("Philosopher %d puts down fork %d and fork %d\n", id, id, (id + 1) % N);
    }
}

int main() {
    philosopher_t philosophers[N];
    sem_t forks[N];

    // ...

    for (int i = 0; i < N; i++) {
        philosophers[i].id = i;
        sem_init(&philosophers[i].fork_left, 0, 1);
        sem_init(&philosophers[i].fork_right, 0, 1);
        pthread_t tid;
        pthread_create(&tid, NULL, eat, &philosophers[i]); // 创建哲学家线程
    }

    pthread_exit(NULL);
}

五、实验结果

运行程序后，可以看到五位哲学家交替地进行思考和进餐，没有出现死锁的情况。

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 fork 0
Philosopher 0 picks up fork 1
Philosopher 0 is eating
Philosopher 1 is hungry
Philosopher 1 picks up fork 1
Philosopher 1 picks up fork 2
Philosopher 1 is eating
Philosopher 2 is hungry
Philosopher 2 picks up fork 2
Philosopher 2 picks up fork 3
Philosopher 2 is eating
Philosopher 3 is hungry
Philosopher 3 picks up fork 3
Philosopher 3 picks up fork 4
Philosopher 3 is eating
Philosopher 4 is hungry
Philosopher 4 picks up fork 4
Philosopher 4 picks up fork 0
Philosopher 4 is eating
Philosopher 0 puts down fork 0 and fork 1
Philosopher 0 is thinking
Philosopher 1 puts down fork 1 and fork 2
Philosopher 1 is thinking
Philosopher 2 puts down fork 2 and fork 3
Philosopher 2 is thinking
Philosopher 3 puts down fork 3 and fork 4
Philosopher 3 is thinking
Philosopher 4 puts down fork 4 and fork 0
Philosopher 4 is thinking
Philosopher 0 is hungry
Philosopher 0 picks up fork 0
Philosopher 0 picks up fork 1
Philosopher 0 is eating
Philosopher 1 is hungry
Philosopher 1 picks up fork 1
Philosopher 1 picks up fork 2
Philosopher 1 is eating
Philosopher 2 is hungry
Philosopher 2 picks up fork 2
Philosopher 2 picks up fork 3
Philosopher 2 is eating
Philosopher 3 is hungry
Philosopher 3 picks up fork 3
Philosopher 3 picks up fork 4
Philosopher 3 is eating
Philosopher 4 is hungry
Philosopher 4 picks up fork 4
Philosopher 4 picks up fork 0
Philosopher 4 is eating
Philosopher 0 puts down fork 0 and fork 1
Philosopher 0 is thinking
Philosopher 1 puts down fork 1 and fork 2
Philosopher 1 is thinking
Philosopher 2 puts down fork 2 and fork 3
Philosopher 2 is thinking
Philosopher 3 puts down fork 3 and fork 4
Philosopher 3 is thinking
Philosopher 4 puts down fork 4 and fork 0
Philosopher 4 is thinking

六、实验结论

本实验利用信号量机制解决了哲学家进餐问题，保证了每位哲学家交替地进行思考和进餐，避免了死锁的情况。通过实验可以看出，信号量机制是一种非常有效的并发编程解决方法，具有很高的实用性。