[原创]关于死锁的分析_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 2826 | 回复: 0   主题: [原创]关于死锁的分析        下一篇 
yang.liu
注册用户
等级:少校
经验:1182
发帖:77
精华:1
注册:2014-1-3
状态:离线
发送短消息息给yang.liu 加好友    发送短消息息给yang.liu 发消息
发表于: IP:您无权察看 2014-4-1 16:11:44 | [全部帖] [楼主帖] 楼主

死锁
由于线程能被阻塞,更由于synchronized方法能阻止其它线程访问本对象,因此有可能会出现如下这种情况:线程一在等线程二(释放某个对象),线程二又在等线程三,这样依次排下去直到有个线程在等线程一。这样就形成了一个环,每个线程都在等对方释放资源,而它们谁都不能运行。这就是所谓的死锁(deadlock)。

如果程序一运行就死锁,那倒也简单了。你可以马上着手解决这个问题。但真正的麻烦在于,程序看上去能正常运行,但是却潜伏着会引起死锁的隐患。或许你认为这里根本就不可能会有死锁,而bug也就这样潜伏下来了。直到有一天,让某个用户给撞上了(而且这种bug还很可能是不可重复的)。所以对并发编程来说,防止死锁是设计阶段的一个重要任务。

下面我们来看看由Dijkstra发现的经典的死锁场景:哲学家吃饭问题。原版的故事里有五个哲学家(不过我们的例程里允许有任意数量)。这些哲学家们只做两件事,思考和吃饭。他们思考的时候,不需要任何共享资源,但是吃饭的时候,就必须坐到餐桌旁。餐桌上的餐具是有限的。原版的故事里,餐具是叉子,吃饭的时候要用两把叉子把面条从碗里捞出来。但是很明显,把叉子换成筷子会更合理,所以:一个哲学家需要两根筷子才能吃饭。

现在引入问题的关键:这些哲学家很穷,只买得起五根筷子。他们坐成一圈,两个人的中间放一根筷子。哲学家吃饭的时候必须同时得到左手边和右手边的筷子。如果他身边的任何一位正在使用筷子,那他只有等着。

这个问题之所以有趣就在于,它演示了这么一个程序,它看上去似乎能正常运行,但是却容易引起死锁。你可以自己试试,用命令行参数调节哲学家的数量和思考的时间。如果有很多哲学家,而且/或者他们思考的时间很长,或许你永远也碰不到死锁,但是死锁的可能性总还是在的。默认的命令行参数会让它很快地死锁:

//: c13:DiningPhilosophers.java
// Demonstrates how deadlock can be hidden in a program.
// {Args: 5 0 deadlock 4}
import java.util.*;
class Chopstick {
      private static int counter = 0;
      private int number = counter++;
      public String toString() {
            return "Chopstick " + number;
      }
}
class Philosopher extends Thread {
      private static Random rand = new Random();
      private static int counter = 0;
      private int number = counter++;
      private Chopstick leftChopstick;
      private Chopstick rightChopstick;
      static int ponder = 0; // Package access
      public Philosopher(Chopstick left, Chopstick right) {
            leftChopstick = left;
            rightChopstick = right;
            start();
      }
      public void think() {
            System.out.println(this + " thinking");
            if(ponder > 0)
            try {
                  sleep(rand.nextInt(ponder));
            } catch(InterruptedException e) {
                  throw new RuntimeException(e);
            }
      }
      public void eat() {
            synchronized(leftChopstick) {
                  System.out.println(this + " has "
                  + this.leftChopstick + " Waiting for "
                  + this.rightChopstick);
                  synchronized(rightChopstick) {
                        System.out.println(this + " eating");
                  }
            }
      }
      public String toString() {
            return "Philosopher " + number;
      }
      public void run() {
            while(true) {
                  think();
                  eat();
            }
      }
}
public class DiningPhilosophers {
      public static void main(String[] args) {
            if(args.length < 3) {
                  System.err.println("usage:\n" +
                  "java DiningPhilosophers numberOfPhilosophers " +
                  "ponderFactor deadlock timeout\n" +
                  "A nonzero ponderFactor will generate a random " +
                  "sleep time during think().\n" +
                  "If deadlock is not the string " +
                  "'deadlock', the program will not deadlock.\n" +
                  "A nonzero timeout will stop the program after " +
                  "that number of seconds.");
                  System.exit(1);
            }
            Philosopher[] philosopher =
            new Philosopher[Integer.parseInt(args[0])];
            Philosopher.ponder = Integer.parseInt(args[1]);
            Chopstick
            left = new Chopstick(),
            right = new Chopstick(),
            first = left;
            int i = 0;
            while(i < philosopher.length - 1) {
                  philosopher[i++] =
                  new Philosopher(left, right);
                  left = right;
                  right = new Chopstick();
            }
            if(args[2].equals("deadlock"))
            philosopher[i] = new Philosopher(left, first);
            else // Swapping values prevents deadlock:
            philosopher[i] = new Philosopher(first, left);
            // Optionally break out of program:
            if(args.length >= 4) {
                  int delay = Integer.parseInt(args[3]);
                  if(delay != 0)
                  new Timeout(delay * 1000, "Timed out");
            }
      }
} ///:~


Chopstick和Philosopher都包含一个能自动递增的static counter。每个Philosopher有两个reference,一个表示左边那根Chopstick,另一个表示右边那根;Philosopher吃饭之前必须拿到这两根筷子。

static的ponder表示哲学家要花多长时间思考。如果这个值非零,则think( )会用它来生成一个随机的休眠时间。我们用这种方法证明,如果线程(也就是哲学家)花在其它事情上(思考)的时间多了,那么它们使用共享资源(筷子)的机会就少了,因而程序就不太容易死锁了,但事实并非如此。

请看eat( )。Philosopher先synchronized 左边那根筷子。如果得不到,他就等,这时他处于阻塞状态。得到左边那根筷子之后,他又用相同的方法去申请右边的筷子。吃完之后,他也是先放左边的,再放右边的。

Philosopher在run( )里不停的思考和吃饭。

main( )至少需要三个参数,如果没给够,它就打印使用的信息。第三个参数可以是"deadlock"字符串,这时程序会启动会引发死锁的版本。任何其它字符串都会运行其非死锁的版本。最后一个参数(可选的)是一个时限,程序运行这段时间之后(以秒为单位,不论是否死锁都会)都会退出。为了能自动地进行测试,这个时限参数是必须的。

除了创建Philosopher数组,设置ponder的值,main( )还创建了两个Chopstick对象,第一个对象放在first变量里。除了最后一个对象,其他Philosopher的初始化过程都一样:先新建一个Philosopher,把left和right Chopstick传给他,然后把right的Chopstick传到left,再为right创建一个新的Chopstick。下一个Philosopher再继续用这两根筷子。

在会死锁版本里,我们把先前存在first里的那根筷子放在最后那个Philosopher的左边。由于最后一位Philosopher正好坐在第一位的旁边,这样他们就必须共享first筷子了。这种安排有可能会造成这种情况:每个哲学家手里都攥着一根筷子,他在等他旁边那位放下手里的筷子,这样他才能吃饭,但程序已经死锁了。

试着用各种命令行参数来运行程序,看看程序会怎样运行,特别是要注意在哪些情况下程序不会死锁。

在告诉你如何修补这个问题之前,先了解一下只有在下述四个条件同时满足的情况下,死锁才会发生:

互斥:也许线程会用到很多资源,但其中至少要有一项是不能共享的。这里,一根筷子同一时刻只能供一个哲学家使用。
至少要有一个进程会在占用一项资源的同时还在等另一项正被其它进程所占用的资源。也就是说,要想让死锁发生,哲学家必须攥着一根筷子等另一根。
(调度系统或其他进程)不能从进程里抢资源。所有进程都必须正常的释放资源。我们的哲学家都彬彬有礼,不会从他的邻座手里抢筷子。
必需要有等待的环。一个进程在一个已经被另一进程抢占了的资源,而那个进程又在等另一个被第三个进程抢占了的资源,以此类推,直到有个进程正在等被第一个进程抢占了的资源,这样就形成了瘫痪性的阻塞了。这里,由于每个哲学家都是先左后右的拿筷子,所以有可能会造成等待的环。在例程中,我们修改了最后一位哲学家的构造函数,让他先右后左地拿筷子,从而破解了死锁。
由于死锁要同时满足这四个条件,所用只要去掉其中一个就能防止死锁。对于这个程序,预防死锁最简单的办法是破掉第四条。之所以会死锁,是因为每个哲学家都以固定的次序拿筷子:先左后右。因此就有可能会发生每个人的左手都捏着一根筷子,然后等右边那根,这样就形成了等待环了。如果初始化的时候让最后那位哲学家先右后左的拿筷子,那他就不会再碍着他左边那位去拿右边的筷子了,因此等待环就被破了。这只是这个问题的解决方法之一,你还可以用破解其它条件的办法来解决这个问题(要想学得更细,可以去看更高级的教课书)。

Java语言没有提供任何能预防死锁的机制,所以只能靠你来设计了。对于那些排错的人来说,这可不是什么好消息。

停止线程的正确方法
为了降低死锁的发生几率,Java 2放弃了Thread类stop( ),suspend( )和resume( )方法。

之所以要放弃stop( )是因为,它不会释放对象的锁,因此如果对象正处于无效状态(也就是被破坏了),其它线程就可能会看到并且修改它了。这个问题的后果可能非常微秒,因此难以察觉。所以别再用stop( )了,相反你应该设置一个旗标(flag)来告诉线程什么时候该停止。下面是一个简单的例子:

//: c13:Stopping.java
// The safe way to stop a thread.
import java.util.*;
class CanStop extends Thread {
      // Must be volatile:
      private volatile boolean stop = false;
      private int counter = 0;
      public void run() {
            while(!stop && counter < 10000) {
                  System.out.println(counter++);
            }
            if(stop)
            System.out.println("Detected stop");
      }
public void requestStop() { stop = true; }
}
public class Stopping {
      public static void main(String[] args) {
            final CanStop stoppable = new CanStop();
            stoppable.start();
            new Timer(true).schedule(new TimerTask() {
                  public void run() {
                        System.out.println("Requesting stop");
                        stoppable.requestStop();
                  }
            }, 500); // run() after 500 milliseconds
      }
} ///:~


stop必须是volatile的,这样才能确保run( )方法能看到它(否则它会使用本地的缓存值)。这个线程的"任务"是打印10,000个数字,所以当counter >= 10000或有人要它停下来的时候,它就结束了。注意requestStop( )不是synchronized,因为stop既是boolean(改成true是一个原子操作)又是volatile的。

main( )启动完CanStop之后设置了一个Timer,让它过半秒自动调用requestStop( )。Timer的构造函数里的true参数的任务是,把这个线程设成守护线程,这样它就不会阻止程序退出了。

打断受阻的线程
有时线程受阻之后就不能再做轮询了,比如在等输入,这时你就不能像前面那样去查询旗标了。碰到这种情况,你可以用Thread.interrupt( )方法打断受阻的线程:

//: c13:Interrupt.java
// Using interrupt() to break out of a blocked thread.
import java.util.*;
class Blocked extends Thread {
      public Blocked() {
            System.out.println("Starting Blocked");
            start();
      }
      public void run() {
            try {
                  synchronized(this) {
                        wait(); // Blocks
                  }
            } catch(InterruptedException e) {
                  System.out.println("Interrupted");
            }
            System.out.println("Exiting run()");
      }
}
public class Interrupt {
      static Blocked blocked = new Blocked();
      public static void main(String[] args) {
            new Timer(true).schedule(new TimerTask() {
                  public void run() {
                        System.out.println("Preparing to interrupt");
                        blocked.interrupt();
                        blocked = null; // to release it
                  }
            }, 2000); // run() after 2000 milliseconds
      }
} ///:~


Blocked.run( )里面的wait( )使线程受阻。Timer期满之后,会调用blocked的interrupt( )方法。最后要把blocked的 reference设成null,这样垃圾回收器才能把它给回收了(在我们这个程序里,这一步不是必须的,但对会运行很长时间的程序来说,这一步很重要)。

线程组
线程组是一个装线程的容器(collection)。用Joshua Bloch[72],也就是负责修补和改进JDK 1.2的Java容器类库的那位Sun的软件架构师,的话来讲,它的意义可以概括为:

"最好把线程组看成是一次不成功的实验,或者就当它根本不存在。"

如果你(和我一样)曾经在线程组上花了很多时间和精力,你就会觉得很奇怪,为什么Sun没有在此之前就这个问题发表过更多的官方申明呢(过去几年里,Java方面的类似问题还有很多)。对于这种问题,诺贝尔经济学奖得主Joseph Stiglitz有一条人生哲学可以解释,[73] 这就是所谓的承诺升级理论:

"延续错误的代价是别人付的,但是承认错误的代价是由你付的。"

线程组还剩一个小用途。如果组里的线程抛出一个没有被(异常处理程序)捕捉到的异常,就会启动ThreadGroup.uncaughtException( )。而它会在标准错误流上打印出栈的轨迹。要想修改这个行为,你必须覆写这个方法。

总结
要懂得什么时候用什么时候用并发,什么时候不用并发,这点非常重要。使用并发的主要理由包括:要管理大量的任务,让它们同时运行以提高系统的利用率(包括在多CPU上透明的分配负载);更合理的组织代码;以及方便用户。平衡负载的一个经典案例是在等待I/O的同时做计算。方便用户的经典案例是在用户下载大文件的时候监控"stop"按钮。

线程还有一个额外的好处,那就是它提供了"轻型"(100个指令级的)运行环境(execution context)的切换,而进程环境(process context)的切换则是"重型"的(数千个指令)。由于所有线程会共享进程的内存空间,所以轻型的环境切换只会改变程序执行顺序和本地变量。而重型的进程环境切换则必须交换全部的内存空间。

多线程的主要缺点包括:

等待共享资源的时候,运行速度会慢下来。
线程管理需要额外的CPU开销。
如果设计得不不合理,程序会变得异常负责。
会引发一些不正常的状态,像饥饿(starving),竞争(racing),死锁(deadlock),活锁(livelock)。
不同平台上会有一些不一致。比如我在开发本书例程时发现,在有些平台下竞争很快就出现,但是换了台机器,它根本就不出现。如果你在后者搞开发,然后发布到前者,那可就惨了。
线程的难点在于多个线程会共享同一项资源——比如对象的内存——而你又必须确保同一时刻不会有两个或两个以上的线程去访问那项资源。这就需要合理地使用synchronized关键词了,但是用之前必须完全理解,否则���会悄悄地地把死锁了带进来。

此外线程的运用方面还有某种艺术。Java的设计思想是,让你能根据需要创建任意多的对象来解决问题,至少理论上如此。(对Java来说创建数以百万计的对象,比如工程方面的有限元分析,还不太现实。)但是你能创建的线程数量应该还是有一个上限的,因为到了这个数量,线程就僵掉了。这个临界点很难找,通常由OS和JVM决定;或许是一百以内,也可能是几千。不过通常你只需创建几个线程就能解决问题了,所以这还不算是什么限制;但是对于更为通用的设计,这就是一个限制了。

线程方面一个重要,但却不那么直观的结论。那就是,通常你可以在run( )的主循环里插上yield( ),然后让线程调度机制帮你加快程序的运行。这绝对是一种艺术,特别是当等待延长之后,性能却上升了。之所以会这样是因为,较短的延迟会使正在运行的线程还没准备好休眠就收到休眠结束的信号,这样为了能让线程干完工作之后再休眠,调度机制不得不先把它停下来再唤醒它。额外的运行环境的切换会导致运行速度的下降,而yield( )和sleep( )则可以防止这种多余的切换。要理解这个问题有多麻烦还真得好好想想。

要想更深入地探讨多线程问题,推荐你看Concurrent Programming in Java, 2nd Edition,作者Doug Lea, Addison-Wesley, 2000出版。

--------------------------------------------------------------------------------

[68] Runnable在Java 1.0里就有了,而内部类是Java 1.1新加的。这一点部分地解释了为什么会有Runnable。此外,传统的多线程架构较少涉及对象,它关注的主要是函数该如何运行。就我个人的习惯,只要有机会就继承Thread,我觉得这么做更有条理,灵活性也高。

[69] 有些例子是在双CPU的Win2K系统上开发的,所以冲突很快就产生了。但是在单CPU的机器上,很可能要等很长时间才会有冲突——多线程之所以会这么难,就是因为它经常会有这种让人很恼火的问题。试想你在单CPU的机器上开发了多线程的程序,测试下来一切正常,但是当你把程序部署到多CPU系统时,一运行它就崩溃了。

[70] 受Joshua Bloch的Effective Java, Addison-Wesley 2001,190页的启发。

[71] 参见由Gamma等著的Design Patterns, Addison-Wesley 1995.

[72] Effective Java,作者Joshua Bloch, Addison-Wesley 2001, 第 211页。

[73] 在Java的发展史上,类似的项目还有很多。为什么要半途而废?——我曾经不止一次地问过这个问题。看来这就是答案。




赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论