经典并发编程问题之哲学家进餐

JRQZ

四月 24, 2024

施工中…

原题：https://leetcode.cn/problems/the-dining-philosophers/description/

题解参考：https://leetcode.cn/problems/the-dining-philosophers/solutions/2130703/li-shun-xian-cheng-zheng-qiang-xin-hao-l-gzb1/

5 个沉默寡言的哲学家围坐在圆桌前，每人面前一盘意面。叉子放在哲学家之间的桌面上。（5 个哲学家，5 根叉子）

所有的哲学家都只会在思考和进餐两种行为间交替。哲学家只有同时拿到左边和右边的叉子才能吃到面，而同一根叉子在同一时间只能被一个哲学家使用。每个哲学家吃完面后都需要把叉子放回桌面以供其他哲学家吃面。只要条件允许，哲学家可以拿起左边或者右边的叉子，但在没有同时拿到左右叉子时不能进食。

假设面的数量没有限制，哲学家也能随便吃，不需要考虑吃不吃得下。

设计一个进餐规则（并行算法）使得每个哲学家都不会挨饿；也就是说，在没有人知道别人什么时候想吃东西或思考的情况下，每个哲学家都可以在吃饭和思考之间一直交替下去。

哲学家从 0 到 4 按 顺时针 编号。请实现函数 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)：

philosopher 哲学家的编号。
pickLeftFork 和 pickRightFork 表示拿起左边或右边的叉子。
eat 表示吃面。
putLeftFork 和 putRightFork 表示放下左边或右边的叉子。
由于哲学家不是在吃面就是在想着啥时候吃面，所以思考这个方法没有对应的回调。

给你 5 个线程，每个都代表一个哲学家，请你使用类的同一个对象来模拟这个过程。在最后一次调用结束之前，可能会为同一个哲学家多次调用该函数。

解法

前置知识

该问题本质上是线程同步中的死锁问题，常用线程同步方式有互斥锁、条件变量、信号量法；这里使用信号量的方法

P-V信号量

经典的死锁问题解决方案，对于信号量m，P(m)检查m是否为0，为0阻塞，否则将其减1，表示占用资源；V(m)将m加1，表示释放资源

C++方法

sem_init, sem_wait, sem_post 是与信号量（semaphore）相关的函数，常用于进程或线程间的同步。信号量是一种高级的同步机制，用于控制对共享资源的访问数量。

这些函数属于 POSIX 线程库（Pthreads），在多种编程环境中可用，尤其是在 UNIX、Linux 系统中。下面是这些函数的基本用途和如何使用它们的简要说明：

sem_init

用途：初始化一个未命名的信号量。
原型
```
int sem_init(sem_t *sem, int pshared, unsigned int value);
```
- sem：指向信号量结构的指针。
- pshared：如果这个值非零，信号量在进程间共享；如果为零，信号量只在创建它的进程的所有线程之间共享。
- value：信号量的初始值。

sem_wait

用途：减少信号量的值（P 操作）。如果信号量的值为零，则调用线程将被阻塞，直到信号量值大于零。
原型
```
int sem_wait(sem_t *sem);
```
- sem：指向信号量的指针。

sem_post

用途：增加信号量的值（V 操作）。如果有其他线程因为信号量的值为零而阻塞，这个操作可能会唤醒这些线程。
原型
```
int sem_post(sem_t *sem);
```
- sem：指向信号量的指针。

除此之外，也可以使用互斥锁（mutex）类。std::mutex 类是标准库中提供的一种基础的互斥锁机制，用于同步多线程对共享资源的访问。以下是mutex的一些常用成员函数

lock()
- 用途：锁定互斥锁。如果互斥锁已被另一个线程锁定，则当前线程将阻塞，直到该互斥锁被释放。
unlock()

用途：解锁互斥锁。线程完成对共享资源的访问后，应调用此方法释放互斥锁，使得其他线程能够获取互斥锁。
注意：只有锁定了互斥锁的线程才能解锁它。

try_lock()

用途：尝试锁定互斥锁，但不会阻塞线程。如果在调用时互斥锁已被另一线程锁定，则立即返回 false，如果成功锁定，则返回 true。
优点：非阻塞，可以用于需要避免长时间等待的场景。

解题思路

由于五位哲学家应相互独立，因此可以创建五个线程分别代表五位哲学家，相互独立（异步），依次编号为0~4。

对于资源（筷子），应该认为这是五种临界资源，而不是一种临界资源。因为每位哲学家只能使用自己面前的两个筷子。同样对五只筷子进行资源编号0~4，并且定义第i位哲学家左侧的筷子编号为i，哲学家右侧的筷子编号为（i+1）%5（这里要注意对编号为0的进行特殊处理）。

临界资源的定义，一次只允许一个线程使用的公共资源。所以当一只筷子被一位哲学家使用时应该加锁。

只允许四个哲学家都拿起同一边的筷子

我们可以只允许四个哲学家都拿起同一边的筷子，这样会保证一位哲学家可以得到两边筷子完成进食，释放临界资源，保证别的哲学家可以进行相应的线程

while(1){
    think()
    hungry()
    p(还可以拿起一边筷子)
    p(左筷子)
    p(右筷子)
    eat()
    v(左筷子)
    v(右筷子)
    v(拿起一边筷子的名额)
}

只允许一个哲学家一次性那两边的筷子，否则都不拿

采用AND信号量机制，即当一个线程要执行时一次性将所需的资源全部给他，否则不分给他资源。

while(1){
	think()
	hungry()
	Swait(左筷子，右筷子)
	eat()
	Spost(左筷子，右筷子)
}

很明显，该方法并发性能较低

区分奇数偶数哲学家

区分奇数偶数哲学家，规定奇数号哲学家先拿起他左边的筷子，然后再去拿他右边的筷子，而偶数号的哲学家则相反，这样的话总能保证一个哲学家能获得两根筷子完成进餐，从而释放其所占用的资源

while(1){
	think(i)
	hungry(i)
	if(i % 2 == 0){
        p(左筷子)
        p(右筷子)
        eat()
        v(右筷子)
        v(左筷子)
    }
    else{
    	p(右筷子)
    	p(左筷子)
        eat()
        v(左筷子)
        v(右筷子)
    }
}

C++实现

只允许四个哲学家都拿起同一边的筷子

#include<semaphore.h>
class DiningPhilosophers {
public:
    DiningPhilosophers() {
        fork = vector<sem_t>(5);
        sem_init(&room,0,4);
        for(int i = 0;i < 5;i++){
            sem_init(&(fork[i]),0,1);
        }
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        sem_wait(&room);
        sem_wait(&(fork[philosopher]));
        sem_wait(&(fork[(philosopher+1)%5]));
        pickLeftFork();
        pickRightFork();
        eat();
        putRightFork();
        putLeftFork();
        sem_post(&(fork[(philosopher+1)%5]));
        sem_post(&(fork[philosopher]));
        sem_post(&room);
    }
    vector<sem_t> fork;
    sem_t room;
};

只允许一个哲学家一次性那两边的筷子，否则都不拿

#include<semaphore.h>
class DiningPhilosophers {
public:
    DiningPhilosophers() {
        fork = vector<sem_t>(5);
        for(int i = 0;i < 5;i++){
            sem_init(&(fork[i]),0,1);
        }
        sem_init(&mutex,0,1);
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        sem_wait(&mutex);
        sem_wait(&(fork[philosopher]));
        sem_wait(&(fork[(philosopher+1)%5]));
        pickLeftFork();
        pickRightFork();
        sem_post(&mutex);
        eat();
        putRightFork();
        putLeftFork();
        sem_post(&(fork[(philosopher+1)%5]));
        sem_post(&(fork[philosopher]));
    }
    vector<sem_t> fork;
    sem_t mutex;
};

区分奇偶数哲学家

#include<semaphore.h>
class DiningPhilosophers {
public:
    DiningPhilosophers() {
        fork = vector<sem_t>(5);
        for(int i = 0;i < 5;i++){
            sem_init(&(fork[i]),0,1);
        }
    }

    void wantsToEat(int philosopher,
                    function<void()> pickLeftFork,
                    function<void()> pickRightFork,
                    function<void()> eat,
                    function<void()> putLeftFork,
                    function<void()> putRightFork) {
        if(philosopher % 2 == 0){
            sem_wait(&(fork[philosopher]));
            sem_wait(&(fork[(philosopher+1)%5]));
            pickLeftFork();
            pickRightFork();
            eat();
            putRightFork();
            putLeftFork();
            sem_post(&(fork[(philosopher+1)%5]));
            sem_post(&(fork[philosopher]));
        }
        else{
            sem_wait(&(fork[(philosopher+1)%5]));
            sem_wait(&(fork[philosopher]));
            pickLeftFork();
            pickRightFork();
            eat();
            putRightFork();
            putLeftFork();
            sem_post(&(fork[philosopher]));
            sem_post(&(fork[(philosopher+1)%5]));
        }
    }
    vector<sem_t> fork;
};