哲学家就餐问题是在计算机科学中的一个经典问题,用来演示在并行计算中多线程同步时产生的问题。在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[]; // 工作队列 linkedBlockingQueueworkingQueue; // 待处理队列 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); } } } } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)