尝试解决哲学家进餐问题(Java实现)

一. 问题描述

5个哲学家，5跟筷子，哲学家必须用两只筷子吃东西。他们只能使用自己左右手边的那两只筷子。做到不产生死锁以及要求高并发性。

二. 资源加锁法

直接给所请求的资源加锁，其他人想访问必须等待；

package psy;

/**
 * 哲学家线程
 * @author stephenluu
 *
 */
public class PerThread extends Thread {

	private static int[] chopstick = { 1, 1, 1, 1, 1 };
	private int i;

	public PerThread(int i) {
		this.i = i;
	}

	@Override
	public void run() {

		synchronized (chopstick) {  //若注释此行，打开下行，不同步，5个per只拿到左筷子
		//{	 
		eat(this.getName());

		think(this.getName());
		}

	}

	private void think(String name) {
		chopstick[i] = 1;
		chopstick[(i + 1) % 5] = 1;
		System.out.println("per"+name+" is thinking...");
		
	}

	private void eat(String string) {

			while (true) {

				if (chopstick[i] != 0) {
					chopstick[i]--;
					System.out.println("per" + this.getName()
							+ " got left chopstick.");
					break;
				}

			}

			try {
				Thread.sleep(1000);
			} catch (InterruptedException e) {
				e.printStackTrace();
			}

			while (true) {
				if (chopstick[(i + 1) % 5] != 0) {
					chopstick[(i + 1) % 5]--;
					System.out.println("per" + this.getName()
							+ " got right chopstick.");
					break;
				}

			}
		System.out.println("per" + string + " is eating...");
	}
}

测试类

package psy;

/**
 * 解决哲学家进餐问题
 * @author stephenluu
 *
 */
public class MainTest {

	public static void main(String[] args) {

		
        for (int i = 0; i < 5; i++) {
			
        	Thread t = new PerThread(i);

            t.start();
		}		
	}

} 

效果：

perThread-0 got left chopstick.
perThread-0 got right chopstick.
perThread-0 is eating...
perThread-0 is thinking...
perThread-4 got left chopstick.
perThread-4 got right chopstick.
perThread-4 is eating...
perThread-4 is thinking...
perThread-3 got left chopstick.
perThread-3 got right chopstick.
perThread-3 is eating...
perThread-3 is thinking...
perThread-2 got left chopstick.
perThread-2 got right chopstick.
perThread-2 is eating...
perThread-2 is thinking...
perThread-1 got left chopstick.
perThread-1 got right chopstick.
perThread-1 is eating...
perThread-1 is thinking...

这样死锁就不会产生的了，但是会不会太浪费资源啊？！ 还有效率也慢。

三.超时释放法

假设规定当哲学家等待另一只餐叉超过五分钟后就放下自己手里的那一只筷子，并且再等五分钟后进行下一次尝试。这个策略也消除了死锁。

package perEat;

/**
 * 哲学家线程
 * @author stephenluu
 *
 */
public class PerThread extends Thread {

	private static int[] chopstick = {1,1,1,1,1};
	private int i;
	private int n = 5;

	public PerThread(int i) {
		this.i = i;
	}

	@Override
	public void run() {

		//拿左筷子
		synchronized (chopstick) {
			while (chopstick[i] == 0) {

				try {
					chopstick.wait();
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
			}
			

			chopstick[i]--;
			System.out.println("per" + this.getName()
					+ " got left chopstick.");

			chopstick.notify();
			
			
			
		}
		// 睡一下产生死锁
		try {
			Thread.sleep((long) (Math.random()*1000));
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	
		//拿右筷子
		synchronized (chopstick) {
			while (chopstick[(i + 1) % n] == 0) {

				try {
					chopstick.wait(3*1000);
				} catch (InterruptedException e) {
					e.printStackTrace();
				}
				finally{
					System.out.println(this.getName()+" waited 3s ,free left chopstick");
					chopstick[i] ++;
				}
			}
			

			chopstick[(i + 1) % n]--;
			System.out.println("per" + this.getName()
					+ " got right chopstick.");

			System.out.println("per" + this.getName() + " is eating...");
			
			chopstick[i]++;
			chopstick[(i + 1) % n]++;
			System.out.println("per"+this.getName()+" is thinking...");
			
			chopstick.notify();
		}
		
	}

}

测试类

package perEat;

/**
 * 解决哲学家进餐问题
 * @author stephenluu
 *
 */
public class MainTest {

	public static void main(String[] args) {

		
        for (int i = 0; i < 5; i++) {
			
        	Thread t = new PerThread(i);

            t.start();
		}		
	}

} 

效果：

perThread-0 got left chopstick.
perThread-2 got left chopstick.
perThread-3 got left chopstick.
perThread-4 got left chopstick.
perThread-1 got left chopstick.
Thread-3 waited 3s ,free left chopstick
Thread-0 waited 3s ,free left chopstick
Thread-1 waited 3s ,free left chopstick
Thread-4 waited 3s ,free left chopstick
perThread-4 got right chopstick.
perThread-4 is eating...
perThread-4 is thinking...
Thread-2 waited 3s ,free left chopstick
perThread-2 got right chopstick.
perThread-2 is eating...
perThread-2 is thinking...
Thread-3 waited 3s ,free left chopstick
perThread-3 got right chopstick.
perThread-3 is eating...
perThread-3 is thinking...
Thread-0 waited 3s ,free left chopstick
perThread-0 got right chopstick.
perThread-0 is eating...
perThread-0 is thinking...
Thread-1 waited 3s ,free left chopstick
perThread-1 got right chopstick.
perThread-1 is eating...
perThread-1 is thinking...

并发性比第一种好。这个策略消除了死锁（系统总会进入到下一个状态），但仍然有可能发生“活锁”。如果五位哲学家在完全相同的时刻进入餐厅，并同时拿起左边的筷子，那么这些哲学家就会等待五分钟，同时放下手中的筷子，再等五分钟，又同时拿起这些筷子。。。。。。

四.

最初是张龙说，5个哲学家都拿起左筷子，产生死锁，最后全部哲学家都饿死了! 觉得挺有趣，加上《操作系统》课程有提到，今天下午研究了一下，能力有限，只写出“资源加锁”和“超时释放”两种方法，至于百度百科的三种“正确”的解决方法：服务生解法，资源分级法，和Chandy/Misra解法，有机会在尝试下。