四月 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 操作）。如果信号量的值为零，则调用线程将被阻塞，直到信号量值大于零。
继续阅读