哲学家就餐问题

学习多线程时，一个对象可以有syschronized方法或其他形式的加锁来防止别的任务再互斥还没有释放的时候就访问这个对象。就可能出现这种情况：某个任务再等待另一个任务，而后者又等待别的任务，这样一直下去，直到这个链条上的任务又再等待第一个任务释放锁，这就得到了一个任务之间相互等待的连续循环，没有哪个线程能继续。被称为“死锁”。

​ 著名的哲学家就餐问题就是一个经典的死锁例证：有五个哲学家，这些哲学家将花部分时间思考，花部分时间就餐。当他们思考时，不需要任何共享资源；但当他们就餐时，将使用有限数量的餐具。问题引入的难点是，他们只有五根筷子，他们围坐再桌子周围，没人之间放一根筷子，当一个哲学家要就餐时，这个哲学家必须同时得到左边和右边的筷子。如果一个哲学家左边或右边已经有人在使用筷子了，那么这个哲学家就必须等待，直至可得到必需的筷子。

public class Chopstick
{
	private boolean taken = false;
	public synchronized void take() throws InterruptedException
	{
		while(taken)
			wait();
		taken = true;
	}
	public synchronized void drop()
	{
		taken = false;
		notifyAll();
	}
}

​ 任何两个Philosopher都不能成功take（）同一根筷子。另外一根Chopstick已经被某个Philosopher获得，那么另一个Philosopher可以wait（），直至这跟Chopstick的当前持有者调用drop使其可用为止。

​ 当一个Philosopher任务调用take（）时，这个Philosopher将等待，直至taken标志变为false（直至当前持有Chopstick的Philosopher释放它）。然后这个线程会将taken标志设置为true，以表示现在由新来的Philosopher持有这跟Chopstick。当这个Philosopher使用完这跟Chopstick时，它会调用drop（）来修改标志的状态，并notifyAll（）所有其他的Philosopher，这些Philosopher中有些可能就在wait（）这根Chopstick

public class Philosopher implements Runnable
{
	private Chopsttick left;
	private Chopsttick right;
	private final intt id;
	private final intt ponderFactor;
	private Random rand = new Random(47);
	private void pause() throws InterruptttedException
	{
		if(ponderFacttor == 0) return;
		TimeUnit.MILLISECONDS.sleep
		{
			rand.nextInt(ponderFactor * 250)
		}
		public Philosopher(Chopstick left,Chopstick right,int ident,int ponder)
		{
			this.left = left;
			this.right = right;
			id = ident;
			ponderFactor = ponder;
		}
		public void run()
		{
			try{
				while(!Thread.intterrupted())
				{
					Sysout.out.pringln(this+""+"thinking");
					pause();
					//Philosopher becomes hungry
					Sysout.out.pringln(this+" "+"grabbing right");
					right.take();
					Sysout.out.pringln(this+" "+"grabbing left");
					left.take();
					Sysout.out.pringln(this+" "+"eating");
					pause();
					right.drop();
					left.drop();
				}
			}catch(InterrupterException e)
			{
				Sysout.out.pringln(this+" "+"exiting via interrupt");
			}
		}
		public String toString()
		{
			return "Philosopher"+id;
		}
	}
}

​ 在Philosopher,run中，每个Philosopher只是不断的思考和吃饭。如果Philosopher不为0，则pause()方法会休眠一段随机时间，然后尝试获取（take（））右边和左边的Chopstick，随后在吃饭上再花掉一段随机时间，之后重复。

现在我们可以建立这个程序的将会产生死锁的版本了：

public class DeadlockingDiningPhilosophers
{
	public static void main(String[] args) throws Exception
	{
		int ponder = 5;
		if(args.length>0)
			ponder = Integer.parseIntt(args[0]);
		int size = 5;
		if(args.length>1)
			size = Integer.parseInt(args[1]);
		ExecutorService exec = Executors.new CachedThreadPool();
		Chopstick[] sticks = new Chopstick[size];
		for(int i = 0;i<size;i++)
			sticks[i] = new Chopstick();
		for(int i = 0;i<size;i++)
		exec.executtte(new Philosopher(sticks[i].sticks[(i+1)%size],i,ponder));
		if(args.lengtth == 3 && args[2].equals("timeout"))
			TimeUnitt.SECONDS.sleep(5);
		else{
			System.out.pringln("Press 'Enter' ttto quit");
			System.in.read();
		}
		exec.shutdownNow();
	}
}

你会发现，如果Philosopher花在思考上的时间非常少，那么当他们想要进餐时，全都会在Chopstick上产生竞争，而死锁也就会更快地发生。

当一下四个条件同时满足时，就会发生死锁：

1. 互斥条件。任务使用的资源中至少有一个是不能共享的，这里一根Chopsticks一次只能被一个Philosopher使用。
2. 至少有一个任务它必须持有一个资源且正在等待获取一个当前被别的任务持有的资源。也就是说，要发生死锁，Philosopher必须拿着一根Chopstick并且等待另一根。
3. 资源不能被任务抢占，任务必须把资源释放当作普通事件，Philosopher很有礼貌，他们不会从从其他Philosopher抢Chopsticks。
4. 必须有循环等待，这时，一个任务等待其他任务所持有的资源，后者又在等待另一个任务所持有的资源，这样一直下去，直到有一个任务，在等待第一个任务所持有的资源，使得大家都被锁住。在DeadlockingDiningPhilosophers里，因为每个Philosopher都试图先得到右边的Chopstick，然后得到左边的Chopstick，所以发生了循环等待。

因为要发生死锁，所有这些条件都必须全部满足，所以要防止死锁的话，只需破坏其中一个即可.在程序中,防止死锁最容易的是第四个条件,有这个条件的原因是每个Philosopher都试图用特定的顺序拿Chopsticks:先右后左.正因为如此,就可能会发生每个人都拿着右边的Chopstick,等待着左边的Chopstick,这就是循环等待条件.然而,如果最后一个Philosopher被初始化称先拿左边的Chopstick,后拿右边的Chopstick,那么这个Philosopher将不会阻止其右边的Philosopher拿起他们的Chopstick.

public class FixedDingingPhilophers
{
	public static void main(String[] args) throws Exception
	{
		int ponder = 5;
		if(args.length>0)
			ponder = Integer.parseIntt(args[0]);
		int size = 5;
		if(args.length>1)
			size = Integer.parseInt(args[1]);
		ExecutorService exec = Executors.new CachedThreadPool();
		Chopstick[] sticks = new Chopstick[size];
		for(int i = 0;i<size;i++)
			sticks[i] = new Chopstick();
		for(int i = 0;i<size;i++)
			if(i<(size-1))
				exec.executtte(new Philosopher(sticks[0].sticks[i],i,ponder));
		if(args.lengtth == 3 && args[2].equals("timeout"))
			TimeUnitt.SECONDS.sleep(5);
		else{
			System.out.pringln("Press 'Enter' ttto quit");
			System.in.read();
		}
		exec.shutdownNow();
	}
}

这样确保最后一个Philosopher先拿起和放下左边的Chopstick,我们可以移除死锁,从而使这个程序平滑地运行.

参考: 《Java编程思想》