1 问题概述
哲学家就餐问题，是并行程序中的一个经典问题，其描述如下。
1. 圆桌上有五位哲学家，每两人中间有一个筷子。
2. 每个哲学家有两件事情要做：
(1) 思考；
(2) 吃饭。哲学家必须同时拿到两只筷子，才能吃饭。
3. 哲学家之间并不知道对方何时要吃饭，何时要思考，不能协商制定分时策略。
4. 设计一个拿筷子的策略，使得哲学家之间不会因为拿筷子而出现死锁或者活锁。
2代码实现
- 版本一（没有很好的解决死锁问题）
当五个哲学家同时拿起左筷子，进入死锁状态
package com.cch;public class Philosopher extends Thread{private static int[] chopsticks = {1,1,1,1,1};private int id;public Philosopher(int id){this.id = id;}@Overridepublic synchronized void run() {this.eat();this.think();}public void think(){//左筷子放下this.chopsticks[this.id] = 1;//右筷子放下this.chopsticks[(this.id+1)%this.chopsticks.length] = 1;System.out.println("哲学家_" + this.id + "正在思考");//思考一秒时间try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}}public void eat(){//拿起左筷子while(true){if(this.chopsticks[this.id] != 0){chopsticks[this.id] = 0;System.out.println("哲学家_" + this.id + "拿起了左筷子");break;}else{try {this.wait(1000);} catch (InterruptedException e) {e.printStackTrace();}finally{System.out.println("哲学家_" + this.id + "的左筷子正在被哲学家_"+((this.id-1+this.chopsticks.length)%this.chopsticks.length)+"使用,等待1000ms");}}}//拿起右筷子while(true){if(this.chopsticks[(this.id+1)%this.chopsticks.length] != 0){chopsticks[(this.id+1)%this.chopsticks.length] = 0;System.out.println("哲学家_" + this.id + "拿起了右筷子");break;}else{try {this.wait(1000);} catch (InterruptedException e) {e.printStackTrace();}finally{System.out.println("哲学家_" + this.id + "的右筷子正在被哲学家_"+((this.id+1)%this.chopsticks.length)+"使用,等待1000ms");}}}System.out.println("哲学家_" + this.id + "正在吃饭");//吃饭花一秒时间try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}this.notify();}public static void main(String[] args) {new Philosopher(0).start();new Philosopher(1).start();new Philosopher(2).start();new Philosopher(3).start();new Philosopher(4).start();}
}
- 版本二（超时释放法）
当五个哲学家同时拿起左筷子时，线程进入死锁，等待2s后，就会有哲学家会放下右筷子，死锁解除
package com;public class Philosopher extends Thread{private static int[] chopsticks = {1,1,1,1,1};private int id;public Philosopher(int id){this.id = id;}@Overridepublic synchronized void run() {this.eat();this.think();}public void think(){//左筷子放下this.chopsticks[this.id] = 1;//右筷子放下this.chopsticks[(this.id+1)%this.chopsticks.length] = 1;System.out.println("哲学家_" + this.id + "正在思考");//思考一秒时间try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}}public void eat(){//拿起左筷子while(true){if(this.chopsticks[this.id] != 0){chopsticks[this.id] = 0;System.out.println("哲学家_" + this.id + "拿起了左筷子");break;}else{try {this.wait(1000);} catch (InterruptedException e) {e.printStackTrace();}finally{System.out.println("哲学家_" + this.id + "的左筷子正在被哲学家_"+((this.id-1+this.chopsticks.length)%this.chopsticks.length)+"使用,等待1000ms");}}}//拿起右筷子while(true){if(this.chopsticks[(this.id+1)%this.chopsticks.length] != 0){chopsticks[(this.id+1)%this.chopsticks.length] = 0;System.out.println("哲学家_" + this.id + "拿起了右筷子");break;}else{try {this.wait(1000);} catch (InterruptedException e) {e.printStackTrace();}finally{System.out.println("哲学家_" + this.id + "的右筷子正在被哲学家_"+((this.id+1)%this.chopsticks.length)+"使用,等待1000ms");}}}System.out.println("哲学家_" + this.id + "正在吃饭");//吃饭花一秒时间try {Thread.sleep(1000);} catch (InterruptedException e) {e.printStackTrace();}this.notify();}public static void main(String[] args) {new Philosopher(0).start();new Philosopher(1).start();new Philosopher(2).start();new Philosopher(3).start();new Philosopher(4).start();}
}
- 版本三（服务生解法）
添加一个服务生，只有当经过服务生同意之后才能拿筷子，服务生负责避免死锁发生。
package com.cch.Philosopher;class Philosopher extends Thread{private String name;private Fork fork;public Philosopher(String name,Fork fork){super(name);this.name=name;this.fork=fork;}public void run(){while(true){thinking();fork.takeFork();eating();fork.putFork();}}public void eating(){System.out.println("I am Eating:"+name);try {sleep(1000);//吃饭花一秒} catch (InterruptedException e) {// TODO Auto-generated catch blocke.printStackTrace();}}public void thinking(){System.out.println("I am Thinking:"+name);try {sleep(1000);//思考花一秒} catch (InterruptedException e) {// TODO Auto-generated catch blocke.printStackTrace();}}
}class Fork{private boolean[] used={false,false,false,false,false,false};/*只有当左右手的筷子都未被使用时，才允许获取筷子，且必须同时获取左右手筷子*/public synchronized void takeFork(){String name = Thread.currentThread().getName();int i = Integer.parseInt(name);while(used[i]||used[(i+1)%5]){try {wait();//如果左右手有一只正被使用，等待} catch (InterruptedException e) {// TODO Auto-generated catch blocke.printStackTrace();}}used[i ]= true;used[(i+1)%5]=true;}/*必须同时释放左右手的筷子*/public synchronized void putFork(){String name = Thread.currentThread().getName();int i = Integer.parseInt(name);used[i ]= false;used[(i+1)%5]=false;notifyAll();//唤醒其他线程}
}public class ThreadTest {public static void main(String []args){Fork fork = new Fork();new Philosopher("0",fork).start();new Philosopher("1",fork).start();new Philosopher("2",fork).start();new Philosopher("3",fork).start();new Philosopher("4",fork).start();}
}- 版本四（资源分级法）
请自行百度
- 版本五（Chandy/Misra解法）
请自行百度