5 个沉默寡言的哲学家围坐在圆桌前，每人面前一盘意面。叉子放在哲学家之间的桌面上。（5 个哲学家，5 根叉子）
所有的哲学家都只会在思考和进餐两种行为间交替。哲学家只有同时拿到左边和右边的叉子才能吃到面，而同一根叉子在同一时间只能被一个哲学家使用。每个哲学家吃完面后都需要把叉子放回桌面以供其他哲学家吃面。只要条件允许，哲学家可以拿起左边或者右边的叉子，但在没有同时拿到左右叉子时不能进食。
假设面的数量没有限制，哲学家也能随便吃，不需要考虑吃不吃得下。
设计一个进餐规则（并行算法）使得每个哲学家都不会挨饿；也就是说，在没有人知道别人什么时候想吃东西或思考的情况下，每个哲学家都可以在吃饭和思考之间一直交替下去。
哲学家从 0 到 4 按 顺时针 编号。请实现函数 void wantsToEat(philosopher, pickLeftFork, pickRightFork, eat, putLeftFork, putRightFork)：
philosopher 哲学家的编号。
pickLeftFork 和 pickRightFork 表示拿起左边或右边的叉子。
eat 表示吃面。
putLeftFork 和 pickRightFork 表示放下左边或右边的叉子。
由于哲学家不是在吃面就是在想着啥时候吃面，所以思考这个方法没有对应的回调。
给你 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 号哲学家拿起了右边的叉子。
这道题本质上其实是想考察如何避免死锁。
因为当 5 个哲学家都拿着其左边(或右边)的叉子时，会进入死锁。
死锁的 4 个必要条件：
互斥条件：一个资源每次只能被一个进程使用，即在一段时间内某 资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
请求与保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源 已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
不可剥夺条件:进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能 由获得该资源的进程自己来释放（只能是主动释放)。
循环等待条件: 若干进程间形成首尾相接循环等待资源的关系。
故最多只允许 4个哲学家去持有叉子，可保证至少有 1个哲学家能吃上意大利面（即获得到 2 个叉子）。
因为最差情况下是：44 个哲学家都各自持有1个叉子，此时还 剩余 11 个叉子 可供使用，这 4个哲学家中必然有1人能获取到这个 剩余的 1个叉子，从而手持 2 个叉子，可以吃意大利面。
即：4 个人中，1个人有 2 个叉子，3 个人各持 1个叉子，共计 5 个叉子。
既然最多只允许4个哲学家去持有叉子，那么如果只允许3个哲学家去持有叉子是否可行呢？
当然可行，3个哲学家可以先都各自持有1把叉子，此时还剩余2把叉子；接下来，这3个哲学家中必有2人能获取到这剩余的2把叉子，从而手持2把叉子，可以吃意大利面。而必然剩余1人只能持有1把叉子。
即：3个人中，2个人各自持有 2个叉子，1 个人持有 1个叉子，共计 5 个叉子。
因此，如果只允许4个哲学家去持有叉子，在头1轮中只能有1人能吃上意大利面；如果只允许3个哲学家去持有叉子，在头一轮中能有2个人能吃上意大利面。直觉上来讲，一轮能有2个人完成吃面 在时间上 显然优于 一轮只有1个人吃面。
用Semaphore去实现上述的限制：Semaphore eatLimit = new Semaphore(4);
一共有5个叉子，视为5个ReentrantLock，并将它们全放入1个数组中。
给叉子编号 0, 1, 2, 3, 4（对应数组下标）。
写法1：
class DiningPhilosophers {
public DiningPhilosophers() {
}
Semaphore eatLimit = new Semaphore(4);//限制最多只有4个哲学家去持有叉子
private ReentrantLock[] lockList = {
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock()
}; //1个Fork视为1个ReentrantLock，5个叉子即5个ReentrantLock，将其都放入数组中
// 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 {
//如果哲学家编号为0 ，则左边叉子编号为1，右边为0
int leftFork = (philosopher + 1) % 5; //左边叉子编号
int rightFork = philosopher;//右边叉子编号
eatLimit.acquire();
lockList[leftFork].lock();//拿起左边叉子，锁定
lockList[rightFork].lock(); //拿起右边叉子，锁定
pickLeftFork.run();
pickRightFork.run();
//开始吃
eat.run();
putLeftFork.run();//放下左边叉子
putRightFork.run();//放下右边叉子
lockList[leftFork].unlock();//释放锁
lockList[rightFork].unlock();
eatLimit.release();
}
}
写法2：设置 11 个临界区以实现 11 个哲学家 “同时”拿起左右 22 把叉子的效果。
即进入临界区之后，保证成功获取到左右 22 把叉子 并 执行相关代码后，才退出临界区。
class DiningPhilosophers {
public DiningPhilosophers() {
}
private ReentrantLock[] lockList = {
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock()
}; //1个Fork视为1个ReentrantLock，5个叉子即5个ReentrantLock，将其都放入数组中
ReentrantLock pickFork = new ReentrantLock();//设置一个临界区，可以让 1个哲学家 “同时”拿起2个叉子
// 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 {
//如果哲学家编号为0 ，则左边叉子编号为1，右边为0
int leftFork = (philosopher + 1) % 5; //左边叉子编号
int rightFork = philosopher;//右边叉子编号
pickFork.lock();
lockList[leftFork].lock();//拿起左边叉子，锁定
lockList[rightFork].lock(); //拿起右边叉子，锁定
pickLeftFork.run();
pickRightFork.run();
pickFork.unlock();
//开始吃
eat.run();
putLeftFork.run();//放下左边叉子
putRightFork.run();//放下右边叉子
lockList[leftFork].unlock();//释放锁
lockList[rightFork].unlock();
}
}
写法3：而当5个哲学家都左手持有其左边的叉子 或 当5个哲学家都右手持有其右边的叉子时，会发生死锁。
故只需设计1个避免发生上述情况发生的策略即可。
即可以让一部分哲学家优先去获取其左边的叉子，再去获取其右边的叉子；再让剩余哲学家优先去获取其右边的叉子，再去获取其左边的叉子。
class DiningPhilosophers {
public DiningPhilosophers() {
}
private ReentrantLock[] lockList = {
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock(),
new ReentrantLock()
}; //1个Fork视为1个ReentrantLock，5个叉子即5个ReentrantLock，将其都放入数组中
// 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 {
//如果哲学家编号为0 ，则左边叉子编号为1，右边为0
int leftFork = (philosopher + 1) % 5; //左边叉子编号
int rightFork = philosopher;//右边叉子编号
if(philosopher % 2 == 0){
lockList[leftFork].lock();//拿起左边叉子，锁定
lockList[rightFork].lock(); //拿起右边叉子，锁定
} else {
lockList[rightFork].lock();//拿起右边叉子，锁定
lockList[leftFork].lock(); //拿起左边叉子，锁定
}
pickLeftFork.run();
pickRightFork.run();
//开始吃
eat.run();
putLeftFork.run();//放下左边叉子
putRightFork.run();//放下右边叉子
lockList[leftFork].unlock();//释放锁
lockList[rightFork].unlock();
}
}
网友评论