当前位置: 首页 > Thinking in Java > 正文

第21章 – 并发 – 死锁,哲学家进餐问题

1. 哲学家问题

 

   5个哲学家围城一圈就餐,因为哲学家都比较穷,每个人只能买得起一根筷子,所以5个哲学家就餐

   只有5根筷子.因为哲学家通常都是在思考,所以5个哲学家并不是同时进餐.但是当他们进餐时,

   必须获取放置在他们左边和右边的筷子,如果他们左边或者右边的筷子已经被别人拿去了,那他就

   只有等待别人放下筷子时才能获取筷子.

 

   所有哲学家都有可能希望进餐,从而等待其临近的哲学家放下它们的筷子,这将使得程序死锁.

 

2. 死锁发生的条件

 

  (1) 互斥条件.任务使用的资源中至少有一个是不能共享的.这里一根筷子一次只能被一个哲学家使用.

  (2) 至少有一个任务它必须持有一个资源并且正在等待获取一个当前被别的任务持有的资源.也就是说,

      要发生死锁,必须有一个哲学家拿着一根筷子并且在等待另一根.

  (3) 资源不能被任务抢占,任务必须把资源释放当初普通时间.这里可以任务哲学家都很有礼貌,他们不会

      从其他哲学家那里抢筷子.

  (4) 必须有循环等待,这时,一个任务等待其他任务,后者又在等待另一个任务,这样循环下去,直到有一个

      任务在等待第一个任务持有的资源,导致大家都被锁住.

 

  要发生死锁,上面4个条件必须同时具备.

 

  代码:

package concurrency;

	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();
	  }
	} 

 

package concurrency;

	import java.util.concurrent.*;
	import java.util.*;
	import static net.mindview.util.Print.*;
	
	public class Philosopher implements Runnable
	{
	  private Chopstick left;
	  private Chopstick right;
	  private final int id;
	  private final int ponderFactor;
	  private Random    rand = new Random(47);
	
	  private void pause() throws InterruptedException
	  {
	    if (ponderFactor == 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.interrupted())
	      {
	        print(this + " " + "thinking");
	        pause();
	        // Philosopher becomes hungry
	        print(this + " " + "grabbing right");
	        right.take();
	        print(this + " " + "grabbing left");
	        left.take();
	        print(this + " " + "eating");
	        pause();
	        right.drop();
	        left.drop();
	      }
	    }
	    catch (InterruptedException e)
	    {
	      print(this + " " + "exiting via interrupt");
	    }
	  }
	
	  public String toString()
	  {
	    return "Philosopher " + id;
	  }
	} 

 

package concurrency;

	import java.util.concurrent.*;
	
	public class DeadlockingDiningPhilosophers
	{
	  public static void main(String[] args) throws Exception
	  {
	    int ponder = 0; //表示思考时间为0,这样可以尽快的出现死锁
	    if (args.length > 0) ponder = Integer.parseInt(args[0]);
	    int size = 5;
	    if (args.length > 1) size = Integer.parseInt(args[1]);
	    ExecutorService exec = Executors.newCachedThreadPool();
	    Chopstick[] sticks = new Chopstick[size];
	    for (int i = 0; i < size; i++)
	      sticks[i] = new Chopstick();
	    for (int i = 0; i < size; i++)
	      exec.execute(new Philosopher(sticks[i], sticks[(i + 1) % size], i, ponder));
	    //每个哲学家都那其两侧的筷子,先拿右边的,后拿左边的(0号筷子放在0号哲学家的右侧)
	    if (args.length == 3 && args[2].equals("timeout")) TimeUnit.SECONDS.sleep(5);
	    else
	    {
	      System.out.println("Press 'Enter' to quit");
	      System.in.read();
	    }
	    exec.shutdownNow();
	  }
	} 

 

3. 死锁问题解决

 

   只要破坏死锁的4个条件当中的一个即可解决死锁问题.

   对于哲学家问题来说,条件4最容易破解,让最后一个哲学家先拿其左边的筷子,然后拿右边筷子.

 

   避免死锁的代码:

package concurrency;

	import java.util.concurrent.*;
	
	public class FixedDiningPhilosophers
	{
	  public static void main(String[] args) throws Exception
	  {
	    int ponder = 0;
	    if (args.length > 0) ponder = Integer.parseInt(args[0]);
	    int size = 5;
	    if (args.length > 1) size = Integer.parseInt(args[1]);
	    ExecutorService exec = Executors.newCachedThreadPool();
	    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.execute(new Philosopher(sticks[i], sticks[i + 1], i, ponder));
	      else exec.execute(new Philosopher(sticks[0], sticks[i], i, ponder));
	      //让最后一个哲学家先拿其左边的筷子,然后拿右边筷子.
	    if (args.length == 3 && args[2].equals("timeout")) TimeUnit.SECONDS.sleep(5);
	    else
	    {
	      System.out.println("Press 'Enter' to quit");
	      System.in.read();
	    }
	    exec.shutdownNow();
	  }
	} 

 

4. 其他死锁情况

 

   (1) 多生产者,多消费者 在同一个锁上同步,当消费者调用notifyAll()时(表示一个条件达到了,所有消费者必须等待)

       可能唤醒的唯一线程还是消费者线程,这样这个唯一唤醒的消费者也进入等待状态了.造成所有线程都等待.

 

       这种问题有一定的出现几率

 

   (2) 以下代码同时运行时会出现死锁

 

      线程1:

synchronized(A)
      {
      	...
      	synchronized(B)
      	{
      		
      	}
      }

 线程2:

synchronized(B)
      {
      	...
      	synchronized(A)
      	{
      		
      	}
      }

 

赞 赏

   微信赞赏  支付宝赞赏


本文固定链接: https://www.jack-yin.com/coding/thinking-in-java/2138.html | 边城网事

该日志由 边城网事 于2015年03月18日发表在 Thinking in Java 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 第21章 – 并发 – 死锁,哲学家进餐问题 | 边城网事
关键字: ,

第21章 – 并发 – 死锁,哲学家进餐问题 暂无评论

发表评论

快捷键:Ctrl+Enter