本文最后编辑于 前，其中的内容可能需要更新。
力扣1226. 哲学家进餐题解
5 个沉默寡言的哲学家围坐在圆桌前，每人面前一盘意面。叉子放在哲学家之间的桌面上。（5 个哲学家，5 根叉子）
所有的哲学家都只会在思考和进餐两种行为间交替。哲学家只有同时拿到左边和右边的叉子才能吃到面，而同一根叉子在同一时间只能被一个哲学家使用。每个哲学家吃完面后都需要把叉子放回桌面以供其他哲学家吃面。只要条件允许，哲学家可以拿起左边或者右边的叉子，但在没有同时拿到左右叉子时不能进食。
假设面的数量没有限制，哲学家也能随便吃，不需要考虑吃不吃得下。
设计一个进餐规则（并行算法）使得每个哲学家都不会挨饿；也就是说，在没有人知道别人什么时候想吃东西或思考的情况下，每个哲学家都可以在吃饭和思考之间一直交替下去。
问题描述和图片来自维基百科 wikipedia.org
哲学家从 0 到 4 按 顺时针 编号。请实现函数 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)：
philosopher 哲学家的编号。
pickLeftFork 和 pickRightFork 表示拿起左边或右边的叉子。
eat 表示吃面。
putLeftFork 和 putRightFork 表示放下左边或右边的叉子。
由于哲学家不是在吃面就是在想着啥时候吃面，所以思考这个方法没有对应的回调。
给你 5 个线程，每个都代表一个哲学家，请你使用类的同一个对象来模拟这个过程。在最后一次调用结束之前，可能会为同一个哲学家多次调用该函数。
示例：
输入：n = 1
输出：[[4,2,1],[4,1,1],[0,1,1],[2,2,1],[2,1,1],[2,0,3],[2,1,2],[2,2,2],[4,0,3],[4,1,2],[0,2,1],[4,2,2],[3,2,1],[3,1,1],[0,0,3],[0,1,2],[0,2,2],[1,2,1],[1,1,1],[3,0,3],[3,1,2],[3,2,2],[1,0,3],[1,1,2],[1,2,2]]
解释:
n 表示每个哲学家需要进餐的次数。
输出数组描述了叉子的控制和进餐的调用，它的格式如下：
output[i] = [a, b, c] (3个整数)
- a 哲学家编号。
- b 指定叉子：{1 : 左边, 2 : 右边}.
- c 指定行为：{1 : 拿起, 2 : 放下, 3 : 吃面}。
如 [4,2,1] 表示 4 号哲学家拿起了右边的叉子。
题目中已经有暗示了，需要使用多线程，但是我们本着能摸鱼就摸鱼的想法来看这个题目，可以找到一个更简单的方法（但是违反了本题考察多线程的本意，
五位哲学家在同一时刻做出选择有可能是都选择进餐，这时候由于只有五个叉子，就导致出现了每位哲学家都只拿到了一个叉子，出现了题目中的不允许现象（即每个哲学家都会挨饿，那么我们可以简单的加一个同步锁，把这个并发问题改成顺序执行的问题，这个冲突就可以轻松解决了
简直不要太简单！
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| `class DiningPhilosophers {`
`private Object object = new Object();`
`public DiningPhilosophers() {`
`}`
`// call the run() method of any runnable to execute its code`
`public void wantsToEat(int philosopher,`
`Runnable pickLeftFork,`
`Runnable pickRightFork,`
`Runnable eat,`
`Runnable putLeftFork,`
`Runnable putRightFork) throws InterruptedException {`
`synchronized(object){ //直接加锁`
`pickLeftFork.run();`
`pickRightFork.run();`
`eat.run();`
`putLeftFork.run();`
`putRightFork.run();`
`}`
`}`
`}`
|
截图如下：
但是这个题目不是让我们这样解题的，所以我们再来看看这个题目
那么思路就是要防止这个死锁问题
在这里提供一种思路：
只要让进餐的时候加一个限制条件，比如只能四个哲学家同时进餐，那么总有一个人可以拿到两把叉子进餐，这样就避免了死锁问题，那么这个方法具体体现在代码里就需要模拟一下，可以用五个信号来模拟五把叉子，在每一时刻确保叉子只能呗一个人抢到，这样就能达到上面的行为，那我们来具体实现一下
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
|
> class DiningPhilosophers {
>
> //使用五个信号量模拟五把叉子，保证每个叉子只能被一个人拿起
>
> private volatile Semaphore[] forks = new Semaphore[]{
>
> new Semaphore(1),
>
> new Semaphore(1),
>
> new Semaphore(1),
>
> new Semaphore(1),
>
> new Semaphore(1)
>
> };
>
> //限制同时就餐的哲学家人数，防止出现五个人一起用餐的死锁情况
>
> private volatile Semaphore limit = new Semaphore(4);
>
>
>
>
>
> public DiningPhilosophers() {
>
>
>
> }
>
>
>
> // call the run() method of any runnable to execute its code
>
> public void wantsToEat(int philosopher,
>
> Runnable pickLeftFork,
>
> Runnable pickRightFork,
>
> Runnable eat,
>
> Runnable putLeftFork,
>
> Runnable putRightFork) throws InterruptedException {
>
> //获取进入的条件，最多4人同时拿起叉子
>
> limit.acquire();
>
> //拿起左手叉子
>
> forks[philosopher-1<0?4:philosopher-1].acquire();
>
> pickLeftFork.run();
>
> //拿起右手叉子
>
> forks[philosopher].acquire();
>
> pickRightFork.run();
>
> //开始吃面
>
> eat.run();
>
> //左手释放叉子
>
> forks[philosopher-1<0?4:philosopher-1].release();
>
> putLeftFork.run();
>
> //右手释放叉子
>
> forks[philosopher].release();
>
> putRightFork.run();
>
> //释放进入条件
>
> limit.release();
>
>
>
>
>
> }
>
> }
>
>
|
果不其然，轻松翻车
怎么回事呢？我感觉这个判定方式有问题，当我修改上限为1的时候代码又能通过了，
总之就是非常奇怪，嘛反正也过了