哲学家就餐问题是在计算机科学中的一个经典问题，用来演示在并行计算中多线程同步时产生的问题。在1971年，著名的计算机科学家艾兹格·迪科斯彻提出了一个同步问题，即假设有五台计算机都试图访问五份共享的磁带驱动器。稍后，这个问题被托尼·霍尔重新表述为哲学家就餐问题。这个问题可以用来解释死锁和资源耗尽
从百度百科上解释来看：哲学家就餐问题可以这样表述，假设有五位哲学家围坐在一张圆形餐桌旁，做以下两件事情之一：吃饭，或者思考。吃东西的时候，他们就停止思考，思考的时候也停止吃东西。餐桌中间有一大碗意大利面，每两个哲学家之间有一只餐叉。因为用一只餐叉很难吃到意大利面，所以假设哲学家必须用两只餐叉吃东西。他们只能使用自己左右手边的那两只餐叉。哲学家就餐问题有时也用米饭和筷子而不是意大利面和餐叉来描述，因为很明显，吃米饭必须用两根筷子。总结来看哲学家问题就是：
接下来我们就将上述描述抽象出来，并用Java并发基础来解决哲学家就餐问题。
初步解决
针对上述问题我们可以简单定个协议规则：
- 规则1：每个哲学家(线程)先拿起左边的叉子，再拿右边的叉子。
- 规则2：如果拿不到就等待。
那么我可以抽象如下：
- id（1-5）用来描述不同的哲学家
- state三种状态：thinking、hungry、eating
- 方法有拿起和放下叉子：takeLeft、takeRight、putLeft和putRight
那么我们可以得到如下程序：
哲学家抽象
public class Philosopher implements Runnable{
public String getState() {
return state;
}
public void setState(String state) {
this.state = state;
}
String state;
int id;
// 用来统计哲学家完成的次数
int count = 0;
// 用来统计总共完成的次数
static AtomicInteger total = new AtomicInteger(0);
// 开始时间
static long startMills = System.currentTimeMillis();
public Philosopher(int id){
this.id = id;
this.state = "Thinking";
}
public void thinking() throws InterruptedException {
if(this.state == "Thinking") {
Thread.sleep((long)(Math.random()*100));
this.state = "Hungry";
}
}
public void eating() throws InterruptedException {
this.state = "Eating";
if(Math.random() > 0.9) {
Thread.sleep(100000);
} else {
Thread.sleep((long)(Math.random()*100));
}
}
public int left(){
return this.id - 1;
}
public int right(){
// %5是因为哲学家id是从1-5，方便下标操作
return this.id % 5;
}
private boolean _take(int[] forks, int fork) {
if(forks[fork] == 0) {
forks[fork] = this.id;
return true;
}
return false;
}
protected boolean takeLeft(int[] forks) {
return this._take(forks, this.left());
}
protected boolean takeRight(int[] forks) {
return this._take(forks, this.right());
}
protected void putRight(int[] forks) {
if(forks[this.right()] == this.id) {
forks[this.right()] = 0;
}
}
protected void putLeft(int[] forks) {
if(forks[this.left()] == this.id) {
forks[this.left()] = 0;
}
}
protected boolean checkLeft(int[] forks) {
return forks[this.left()] == 0;
}
protected boolean checkRight(int[] forks) {
return forks[this.right()] == 0;
}
public void finished(){
count ++;
int t = total.incrementAndGet();
// 计算每秒完成就餐的哲学家数量
double speed = (t * 1000.0) / (System.currentTimeMillis() - startMills);
this.state = "Thinking";
System.out.format("Philosopher %d finished %d times, speed = %.2f.n",
this.id,
this.count,
speed
);
}
}
模拟就餐
public class DiningPhilosophersDeadlock {
// 定义5个哲学家
Phi[] phis = new Phi[5];
// 定义5把叉子
volatile int[] forks = new int[5];
public DiningPhilosophersDeadlock(){
// 初始化
for(int i = 0; i < 5; i++) {
phis[i] = new Phi(i+1);
forks[i] = 0;
}
}
class Phi extends Philosopher {
public Phi(int id) {
super(id);
}
@Override
protected synchronized boolean takeLeft(int[] forks) {
return super.takeLeft(forks);
}
@Override
protected synchronized boolean takeRight(int[] forks) {
return super.takeRight(forks);
}
public void run(){
while(true) {
try {
this.thinking();
this.takeLeft(forks)
Thread.sleep(100);
this.takeRight(forks)
this.eating();
this.putLeft(forks);
this.putRight(forks);
this.finished();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
public void run(){
ExecutorService pool = Executors.newFixedThreadPool(5);
for(int i = 0; i< 5; i++) {
pool.submit(phis[i]);
}
}
public static void main(String[] argv) {
DiningPhilosophersDeadlock solver = new DiningPhilosophersDeadlock();
solver.run();
}
通过模拟开启5个线程，运行发现发生了死锁，其实通过分析可以知道当5个哲学家(即5个线程）同时拿起叉子时，此时都在等待拿起右叉子，所有5个线程都在等待，陷入了死循环，这不发生死锁才怪。乍一看，我们可以通过简单的逻辑来处理，比如下面的：
while(!this.takeLeft(forks)) {
Thread.sleep(0);
}
Thread.sleep(100);
int c = 0;
while(!this.takeRight(forks)) {
c++;
if(c > 100) {
this.putLeft(forks);
continue;
}
Thread.sleep(0);
}
我们知道死锁产生需要4个必要条件：
- 互斥
- 占有且等待
- 不可抢占
- 循环等待
此时我们可以通过打破循环等待来解决死锁问题：
即通过简单的标志位c来判断，当拿不到右叉则累计达到100主动放下左叉
但重新运行程序，我们又会发现程序停止不动了，一波分析后发现可能产生了这种情况，当5个线程同时拿起左叉，后面又同时放下了左叉，不断同时拿起和放下，这便是所谓的活锁(livelock)
当产生了上述活锁的问题后，我们不想去通过逻辑解决了，还是直接加锁吧。便有了下面的想法：
添加成员
ReentrantLock lock = new ReentrantLock(); Condition wait = lock.newCondition();
通过Lock解决
this.thinking(); lock.lockInterruptibly(); this.takeLeft(forks) Thread.sleep(100); this.takeRight(forks) this.eating(); this.putLeft(forks); this.putRight(forks); this.finished(); lock.unlock();
但我们发现速度很慢：
"C:Program FilesJavajdk1.8.0_211binjava.exe" "- Philosopher 5 finished 1 times, speed = 6.80. Philosopher 4 finished 1 times, speed = 5.43. Philosopher 2 finished 1 times, speed = 5.36. Philosopher 3 finished 1 times, speed = 5.97. Philosopher 1 finished 1 times, speed = 5.98. Philosopher 5 finished 2 times, speed = 5.89. Philosopher 4 finished 2 times, speed = 6.23. Philosopher 2 finished 2 times, speed = 6.19. Philosopher 3 finished 2 times, speed = 6.25. Philosopher 1 finished 2 times, speed = 6.21.
这确实很慢了，每秒仅仅能处理很少的哲学家就餐，通过进一步分析可以发现，我们是不是可以先每次检查一下，没拿到就释放锁，没必要执行后面代码。当拿到左叉后，再拿不到右叉是不是可以主动去探测下这个右叉的状态，当已经不是Eating状态后，我们可以不等它放下，直接拿过来，那么可以做到如下优化：
this.thinking();
lock.lockInterruptibly();
boolean takeLeft = this.checkLeft(forks);
if(!takeLeft) {
// 直接释放
lock.unlock();
continue;
}
this.takeLeft(forks);
boolean takeRight = this.checkRight(forks);
if(takeRight) {
this.takeRight(forks);
} else {
int rid = this.right();
Phi rPhi = phis[forks[rid] - 1];
// 探测下，是不是直接可以传递
if(dirty[rid] && rPhi.getState() != "Eating") {
forks[rid] = this.id;
dirty[rid] = false;
} else {
lock.unlock();
continue;
}
}
lock.unlock();
this.eating();
lock.lockInterruptibly();
this.putLeft(forks);
this.putRight(forks);
dirty[this.left()] = true;
dirty[this.right()] = true;
lock.unlock();
this.finished();
发现执行后，执行速度有了显著提升：
Philosopher 2 finished 1 times, speed = 8.06. Philosopher 3 finished 1 times, speed = 23.53. Philosopher 1 finished 1 times, speed = 20.13. Philosopher 5 finished 1 times, speed = 14.60. Philosopher 4 finished 1 times, speed = 23.92. Philosopher 1 finished 2 times, speed = 20.69. Philosopher 3 finished 2 times, speed = 21.94. Philosopher 4 finished 2 times, speed = 19.37. Philosopher 4 finished 3 times, speed = 15.76. Philosopher 4 finished 4 times, speed = 16.05.延迟队列实现
我们也可以通过延迟队列来实现，具体可以借助linkedBlockingQueue完成队列的进出，延迟队列DelayQueue来实现延迟中断（即超时后主动退出，放下刀叉）可以有如下流程：
主要代码
// 声明的变量
Philosopher[] phis;
volatile int forks[];
// 工作队列
linkedBlockingQueue workingQueue;
// 待处理队列
linkedBlockingQueue managerQueue;
// 延迟队列
DelayQueue delayQueue = new DelayQueue<>();
class ContentionManager implements Runnable {
@Override
public void run() {
while(true) {
try {
Philosopher phi = managerQueue.take();
if(phi.checkLeft(forks) && phi.checkRight(forks)) {
phi.takeLeft(forks);
phi.takeRight(forks);
workingQueue.offer(phi);
} else {
managerQueue.offer(phi);
}
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}
class Worker implements Runnable {
@Override
public void run() {
while (true) {
Philosopher phi = null;
try{
phi = workingQueue.take();
if(phi.getState()=="Hungry") {
DelayInterruptingThread delayItem = new DelayInterruptingThread(Thread.currentThread(), 1000);
delayQueue.offer(delayItem);
phi.eating();
delayItem.commit();
phi.putLeft(forks);
phi.putRight(forks);
phi.finished();
workingQueue.offer(phi);
} else {
phi.thinking();
managerQueue.offer(phi);
}
} catch (InterruptedException e) {
if(phi != null) {
phi.putLeft(forks);
phi.putRight(forks);
if(phi.getState() == "Eating") {
phi.setState("Hungry");
}
managerQueue.offer(phi);
}
}
}
}
}
