×

就餐 哲学家 线程 同步 经典

经典的线程同步问题:哲学家就餐

jnlyseo998998 jnlyseo998998 发表于2023-03-21 08:14:02 浏览28 评论0

抢沙发发表评论

场景

有五位沉默的哲学家围坐在一张圆桌旁,他们一生都在吃东西和思考。

有五只筷子供他们使用,哲学家需要双手拿到一双筷子之后才能吃饭;吃完后会将筷子放下继续思考。

那么现在有一个问题,我们需要想出一种方案,如何保证哲学家们可以交替吃饭和思考,而不会被饿死。

上面这个问题是由Dijkstra提出的一个经典的线程同步问题。

解决方案

我们在开始想如何解决问题之前,可以先将这个场景通过代码还原,在程序中进行建模。

通过上面的分析,我们的代码实现如下:

接下来,我们思考一下,如何实现哲学家吃饭的逻辑。

当一个哲学家需要吃饭时,他要拿起左右两边的筷子。所以:

哲学家A(0)需要筷子0和4哲学家B(1)需要筷子1和0哲学家C(2)需要筷子2和1哲学家D(3)需要筷子3和2哲学家E(4)需要筷子4和3

所以每个哲学家线程都应该有个编号,所以我在DiningPhilosophers中定义了属性id表示哲学家的编号。

左手边的筷子可以有用fork[id]表示;

右手边的筷子用fork[(id+4)%5]表示。

那么我们的eat方法的实现如下:

我们接着来测试我们的完整代码。

该如何避免出现这种死锁问题呢?

方法一:限制吃饭的哲学家人数

要实现这种方法,我们可以再定义一个许可数为4的信号量Semaphore,表示剩余可以吃饭的哲学家名额。

代码实现如下:

方法二:找到一个左撇子哲学家

这种方法是让其中一个哲学家和其他哲学家拿筷子的顺序和其他哲学家不一样。

比如其他人都是先拿右手边再拿左手边,而这个左撇子哲学家则先拿左手边再拿右手边。

而哪一位哲学家被选为左撇子并不重要,因为桌子是圆的,所以我们就选择0号哲学家为左撇子。

代码实现如下:

小结