时间戳

首页 > 技术文章 > Java哲学家进餐问题|多线程

Java哲学家进餐问题|多线程

fisherss 2019-10-27 15:01 原文

Java实验三 多线程

哲学家进餐问题

5个哲学家共用一张圆桌，分别坐在周围的5张椅子上，

在圆桌上有5个碗和5只筷子（注意是5只筷子，不是5双），

碗和筷子交替排列。他们的生活方式是交替地进行思考（thinking）和进餐（eating）。

平时，一个哲学家进行思考，饥饿时便试图取用其左右最靠近他的两只筷子，规定他必须先取左边的筷子，再取右边的筷子。
只有在他拿到两只筷子时才能进餐。
进餐完毕，放下筷子继续进行思考。

假如5位哲学家同时饥饿，各自拿起左边的筷子时，再去拿各自右边的筷子，因为无筷子可拿而陷入无期限等待（死锁）。

进餐完毕释放他用过的两只筷子，从而使更多的哲学家能够进餐。使用Java的多线程同步技术，实现上述解决方案。


解决方法一：破坏循环等待条件

最多允许4个哲学家同时去拿左边的筷子，即死锁四大必要条件之一——破坏循环等待条件。

synchronized关键字易混淆处：
用法：synchronized(一个对象){同步代码块}
这里synchronized锁住的不是这"一个对象"，而是用这"一个对象"来当看门人，只允许一个线程来进入synchronized锁住的同步{代码块}，所以这个代码块被称作“同步代码块”，当代码块执行完后，会让这“一个对象”(看门人)，吼一声让其它线程进来。原理是：每一个java对象都关联了一个“ monitor lock”，当一个线程获取了 monitor lock 后,其它线程如果运行到获取同一个 monitor 的时候就会被 block 住。当这个线程执行完同步代码,则会释放 monitor lock。

下面代码，经过分析后能满足最多允许4个哲学家同时去拿左边的筷子的条件：

分析如下：

1.如果不加num<4，synchronized(left)后，如果另一个哲学家进程拿了right的筷子，另一个哲学家又拿了这个哲学家右边的筷子...依此类推，产生循环等待链，即产生死锁。就会产生死锁。

我们标记3个结点去分析各个代码块进入的最多线程数。

2.加了num<4这个条件后，可能会有5个线程，同时满足if判断语句(结点1)；而又因为synchronized了一个筷子(left)，所以最多有4个进程进入了synchronized(left){}代码块钟，执行了num++，(结点2)，那么虽然此时可能有5个进程进入了if(num<4)语句，但是第5个进程也会被阻挡在synchronized外面。在synchronized(right)后，最多有2个进程去吃东西(结点3),因为只有5个筷子，同时只能让两个人去吃，其它3个人等待，看图比较容易明白。


代码如下： 
class phiPerson implements Runnable{ //实现Runnable接口
	
	//全部使用static关键字 静态成员属于整个类，当系统第一次使用该类时，就会为其分配内存空间直到该类被卸载才会进行资源回收
	//为什么用static修饰 因为多线程多个哲学家需要共享筷子这个对象
	static Object[] chops;//static关键字修饰的变量 该类所有的对象共享同一个成员 
	static int Num = 0; //同时拿左手边筷子的人数 也是全局变量
	private int pos; //当前哲学家的编号 私有变量
	
	public phiPerson(int position,Object[] chops) { //构造函数
		// TODO Auto-generated constructor stub
		this.chops =  chops;
		this.pos = position;
	}

	@Override
	public void run() { //重写run方法
		// TODO Auto-generated method stub
		while(true) {
			int right = (pos+1)%5; //我右边筷子在数组中的下标
			int left = (pos)%5;//左边筷子在数组中的下标
			if(Num < 4) { //最多允许4个人同时拿左手边的筷子
                           //结点1：5个进程都有可能进入这个地方
					synchronized (chops[left]) { //锁 左手边的筷子 就是等待左边的人用我左手边的筷子吃完了后我再拿来吃。。
                                               Num++;//同时拿左手边筷子的人的数量+1 //这里没有锁住num，有可能会使得在没有num++时，5个进程都进来，
                                                //结点2：最多4个进程进到这个地方，因为synchronized (chops[left])后，需要left筷子的另1个进程要在外面等待
						System.out.println(Num);
						System.out.println("第"+(pos+1)+"个哲学家拿了左手边的筷子");
						synchronized(chops[right]) {//右手边的筷子 锁  就是等待右手边的筷子没人拿了我再拿
                                                        //结点3：最多有2个进程进入到这个地方，因为只有5个筷子，所以最多两个人同时拿。
							System.out.println("第"+(pos+1)+"个哲学家拿了右手边的筷子");
							System.out.println("第"+(pos+1)+"个哲学家正在eating");
							try {
								Thread.sleep(100);
							} catch (InterruptedException e) {
								// TODO Auto-generated catch block
								e.printStackTrace();
							}
							System.out.println("第"+(pos+1)+"个哲学家吃完了，把筷子放回了原处，开始thinking");
							Num--;//同时拿左手边筷子的人的数量-1
						}
					}
				
			}
		}
	}
}

public class phiEat {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Object [] chObject = new Object[5];
		for(int i=0;i<5;i++) chObject[i] = i; //object必须要初始化一下呀
		
		//5个哲学家
		phiPerson firThread = new phiPerson(0,chObject);
		phiPerson secThread = new phiPerson(1,chObject);
		phiPerson thirThread = new phiPerson(2,chObject);
		phiPerson fourThread = new phiPerson(3,chObject);
		phiPerson fifThread = new phiPerson(4,chObject);
		//开吃了 
		new Thread(firThread).start();
		new Thread(secThread).start();
		new Thread(thirThread).start();
		new Thread(fourThread).start();
		new Thread(fifThread).start();
	}

}

解决方法二：破坏请求和保持条件

方案：仅当一个哲学家左右两边的叉子都可用时才允许他抓起叉子，即破坏死锁四大条件之一——请求和保持条件

说明白点就是，不会出现某个哲学家拿一个筷子等一个筷子的情况，必须同时拿两个！

package philosopher;

public class ThreadTest {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Chop fiveChops = new Chop();
		new Philosopher(0,fiveChops).start();
		new Philosopher(1,fiveChops).start();
		new Philosopher(2,fiveChops).start();
		new Philosopher(3,fiveChops).start();
		new Philosopher(4,fiveChops).start();
	}

}


class Philosopher extends Thread{
	private int index;
	private Chop chop;
	public Philosopher(int index, Chop chop) {
		// TODO Auto-generated constructor stub
		this.index = index;
		this.chop = chop;
	}
	
	@Override
	public void run() {
		while(true) {
			thinking();
			chop.takeChop(index);
			eating();
			chop.putChop(index);
		}
	}
	private void thinking(){
		// TODO Auto-generated method stub
		System.out.println("第"+index + "个哲学家正在思考...");
		try {
			sleep(1000);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	private void eating(){
		// TODO Auto-generated method stub
		System.out.println("第"+index + "个哲学家正在吃饭...");
		try {
			sleep(1000);
		} catch (InterruptedException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}

}


class Chop {
	private Boolean[] chops = {false,false,false,false,false};

	public synchronized void takeChop(int index) {
		// TODO Auto-generated method stub
		while(chops[index] || chops[(index+1)%5]) {
			try {
				wait(); //拿不到筷子就会被阻塞 进入等待池 从而不会再来竞争
			} catch (Exception e) {
				// TODO: handle exception
			}
		}
		chops[index] = true;
		chops[(index+1)%5] = true;
	}

	public synchronized void putChop(int index) {
		// TODO Auto-generated method stub
		chops[index] = false;
		chops[(index+1)%5] = false;
		notifyAll();
	}
	
}

这里产生疑问点待解决，notifyAll和wait在此代码中如何工作。


参考文章：
[1] sunny_ss12 经典同步问题（二）---哲学家就餐问题
[2] Yun_Ge PV操作经典例题——哲学家进餐问题
[3] qiuhuilu JAVA多线程学习--哲学家就餐问题

推荐阅读