哲学家就餐问题
本文对多线程中经典问题-哲学家就餐问题用Java语言描述，给出了三种常见的解决方法，实现了其中的两种。
一、问题描述：
在一个圆桌上，有n个哲学家，n只筷子，每个哲学家左右两边各返一只筷子。哲学家可以进行思考和吃饭，思考时，不获取筷子。吃饭时，必须同时获得左右两只筷子才能吃饭（先获取左边的再获取右边的）。
二、Java实现哲学家就餐问题
实现Chopstick类，每个筷子有个编号index，还有个属性isUsing表示是否正在使用，如果isUsing为true，后访问的哲学家对象就必须等待直到isUsing为false才能访问
package Blog.philosopher;
public class Chopstick {
private int index;
private boolean isUsing = false;
public Chopstick(int index){
this.index = index;
}
//修改toString方法，因为System.out.println()输出对象都是调用toString方法
@Override
public String toString() {
return "Chopstick [index = " + index + "]";
}
//对于一个成员方法加synchronized关键字，作用范围是从调用该方法开始，作用对象是该方法所在的对象
public synchronized void take() throws InterruptedException{
while(isUsing){
wait();
}
isUsing = true;
}
//使用结束，通知所有其他线程
public synchronized void drop(){
isUsing = false;
notifyAll();
}
public int getIndex() {
return index;
}
public boolean getIsUsing(){
return isUsing;
}
}
实现Philosopher类
package Blog.philosopher;
public class Philosopher implements Runnable{
protected Chopstick left;
protected Chopstick right;
protected int index;
protected int thinkTime;
protected int eatTime;
public Philosopher(Chopstick left, Chopstick right, int index) {
this.left = left;
this.right = right;
this.index = index;
}
//sleep()方法让出CPU，不释放资源。
public void thinking() throws InterruptedException{
System.out.println(this + "thinking");
Thread.sleep(thinkTime);
}
public void eating() throws InterruptedException{
System.out.println(this + "eating");
Thread.sleep(eatTime);
}
@Override
public void run() {
try{
while ( !Thread.interrupted() ){
thinking();
System.out.println(this + "take the left");
left.take();
Thread.sleep(10);
System.out.println(this + "going to take the right");
right.take();
System.out.println(this + "has took the right");
eating();
left.drop();
right.drop();
}
}catch (Exception e){
e.printStackTrace();
}
}
@Override
public String toString() {
return "Philosopher [index = " + index + "]";
}
}
哲学家先进行思考，思考结束先获取左边的筷子，如果获取了左边的，再获取右边的筷子，如果没有获得则一直等待直到获得为止，获得到左右两只筷子随后进行吃，吃完则继续思考，继续循环。
修改：这里为了看到现象，可以将思考时间和吃饭时间设置为0，更加容易出现死锁
还有可以在取左筷子和右筷子间添加一段sleep()时间，虽然不符合正常人（谁会拿了左筷子再sleep然后拿右筷子），但是符合操作系统，因为某个线程获取资源A，会进行一小段时间访问，访问之后才会去访问资源B。
测试类：
package Blog.philosopher;
public class PhilosopherTest {
public static void main(String[] args) {
int size=5;
Chopstick[] chopstick = new Chopstick[size];
for(int i=0;i<size;i++){
chopstick[i] = new Chopstick(i);
}
for(int i=0;i<size;i++){
Thread thread = new Thread(new Philosopher(chopstick[(i+1)%size], chopstick[i], i));
thread.start();
//这里不能用join()方法，因为这会等待该进程结束了才会调用主进程，创造余下的进程
//thread.join();
}
System.out.println("main线程已经结束");
}
}
结果：出现了死锁
main线程已经结束
Philosopher [index = 0]thinking
Philosopher [index = 1]thinking
Philosopher [index = 0]take the left
Philosopher [index = 2]thinking
Philosopher [index = 1]take the left
Philosopher [index = 3]thinking
Philosopher [index = 4]thinking
Philosopher [index = 2]take the left
Philosopher [index = 3]take the left
Philosopher [index = 4]take the left
Philosopher [index = 0]going to take the right
Philosopher [index = 1]going to take the right
Philosopher [index = 2]going to take the right
Philosopher [index = 4]going to take the right
Philosopher [index = 3]going to take the right
三、解决方法
先看死锁的四个必要条件：
l 互斥
l 请求保持
l 不可剥夺
l 循环等待
要解决死锁，就至少要破坏其中一个条件，然后“互斥”一般是不能破坏的，所以针对其他三个条件采用合适的方法。
1. 资源分级解法：
另一个简单的解法是为资源（这里是餐叉）分配一个偏序或者分级的关系，并约定所有资源都按照这种顺序获取，按相反顺序释放，而且保证不会有两个无关资源同时被同一项工作所需要。在哲学家就餐问题中，资源（餐叉）按照某种规则编号为1至5，每一个工作单元（哲学家）总是先拿起左右两边编号较低的餐叉，再拿编号较高的。用完餐叉后，他总是先放下编号较高的餐叉，再放下编号较低的。破坏了循环等待条件。
代码：
继承了Philosopher为Philosopher2，重写了PhilosopherTest为PhilosopherTest2
package Blog.philosopher;
public class Philosopher2 extends Philosopher{
//构造方法
public Philosopher2(Chopstick left, Chopstick right, int index) {
super(left, right, index);
}
@Override
public void run() {
try{
while ( !Thread.interrupted() ){
thinking();
System.out.println(this + "take the small");
Chopstick small = left.getIndex() < right.getIndex() ? left : right;
small.take();
Thread.sleep(10);
Chopstick big = left.getIndex() > right.getIndex() ? left : right;
System.out.println(this + "going to take the big chopstick" + big.getIndex());
big.take();
System.out.println(this + "has took the big right" + big.getIndex());
eating();
big.drop();
small.drop();
}
}catch (Exception e){
e.printStackTrace();
}
}
}package Blog.philosopher;
public class PhilosopherTest2 {
public static void main(String[] args) {
int size=5;
int thinkTime= 0;
int eatTime = 0;
Chopstick[] chopstick = new Chopstick[size];
for(int i=0;i<size;i++){
chopstick[i] = new Chopstick(i);
}
for(int i=0;i<size;i++){
Thread thread = new Thread(new Philosopher2(chopstick[(i+1)%size], chopstick[i], i));
thread.start();
//这里不能用join()方法，因为这会等待该进程结束了才会调用主进程，创造余下的进程
//thread.join();
}
System.out.println("main线程已经结束");
}
}
2. 服务生解法：
一个简单的解法是引入一个餐厅服务生，哲学家必须经过他的允许才能拿起餐叉。因为服务生知道哪只餐叉正在使用，所以他能够作出判断避免死锁。可以采用一次性分配资源的方法来避免死锁。破坏请求保持条件，线程不可能保持资源的同时继续申请新的资源。代码中我没有引入服务生，采用了一种简化，直接在Philosopher3中利用哲学家自己判断，如果右筷子可用则去获取，如果不可用则放弃左筷子。
代码：
重写了Philosopher为Philosopher3，重写了PhilosopherTest为PhilosopherTest3
package Blog.philosopher;
public class Philosopher3 extends Philosopher{
public Philosopher3(Chopstick left, Chopstick right, int index) {
super(left, right, index);
}
@Override
public void run() {
try{
while ( !Thread.interrupted() ){
thinking();
System.out.println(this + "take the left");
left.take();
Thread.sleep(10);
System.out.println(this + "going to take the right");
//如果右筷子正在使用，则放弃左筷子
if(right.getIsUsing()){
left.drop();
System.out.println(this + "give up");
}else {
right.take();
System.out.println(this + "has took the right");
eating();
left.drop();
right.drop();
}
}
}catch (Exception e){
e.printStackTrace();
}
}
}package Blog.philosopher;
public class PhilosopherTest3 {
public static void main(String[] args) {
int size=5;
int thinkTime= 10;
int eatTime = 10;
Chopstick[] chopstick = new Chopstick[size];
for(int i=0;i<size;i++){
chopstick[i] = new Chopstick(i);
}
for(int i=0;i<size;i++){
Thread thread = new Thread(new Philosopher3(chopstick[(i+1)%size], chopstick[i], i));
thread.start();
}
//提供一个服务生
System.out.println("main线程已经结束");
}
}3. Chandy/Misra解法：
1984年，K. Mani Chandy和J. Misra提出了哲学家就餐问题的另一个解法，允许任意的用户（编号P1, ..., Pn）争用任意数量的资源。与迪科斯彻的解法不同的是，这里编号可以是任意的。
1.对每一对竞争一个资源的哲学家，新拿一个餐叉，给编号较低的哲学家。每只餐叉都是“干净的”或者“脏的”。最初，所有的餐叉都是脏的。
2.当一位哲学家要使用资源（也就是要吃东西）时，他必须从与他竞争的邻居那里得到。对每只他当前没有的餐叉，他都发送一个请求。
3.当拥有餐叉的哲学家收到请求时，如果餐叉是干净的，那么他继续留着，否则就擦干净并交出餐叉。
4.当某个哲学家吃东西后，他的餐叉就变脏了。如果另一个哲学家之前请求过其中的餐叉，那他就擦干净并交出餐叉。
这个解法允许很大的并行性，适用于任意大的问题。
这个方法略复杂，我没有实现，可以参考以下链接
http://bbs.csdn.net/topics/390754385?page=1