死锁

电话面试 操作系统

死锁的条件

死锁的去除

写一段synchronized可能发生死锁的代码

synchronized和lock的区别

O、什么是死锁

先举一个生活中的例子：在一条河上有一座桥，桥面较窄，只能容纳一辆汽车通过，无法让两辆汽车并行。如果有两辆汽车A和B分别由桥的两端驶上该桥，则对于A车来说，它走过桥面左面的一段路（即占有了桥的一部分资源），要想过桥还须等待B车让出右边的桥面，此时A车不能前进；对于B车来说，它走过桥面右边的一段路（即占有了桥的一部分资源），要想过桥还须等待A车让出左边的桥面，此时B车也不能前进。两边的车都不倒车，结果造成互相等待对方让出桥面，但是谁也不让路，就会无休止地等下去。这种现象就是死锁。
如果把汽车比做进程，桥面作为资源，那麽上述问题就描述为：进程A占有资源R1，等待进程B占有的资源Rr；进程B占有资源Rr，等待进程A占有的资源R1。而且资源R1和Rr只允许一个进程占用，即：不允许两个进程同时占用。结果，两个进程都不能继续执行，若不采取其它措施，这种循环等待状况会无限期持续下去，就发生了进程死锁。

操作系统中就有用 互斥信号量解决问题
所谓死锁，是指多个进程循环等待它方占有的资源而无限期地僵持下去的局面。很显然，如果没有外力的作用，那麽死锁涉及到的各个进程都将永远处于封锁状态。
计算机系统产生死锁的根本原因就是资源有限且操作不当。

一、死锁原因

死锁产生的四个必要条件。

1>互斥条件，即当资源被一个线程使用(占有)时，别的线程不能使用
2>不可抢占条件，资源请求者不能强制从资源占有者手中夺取资源，资源只能由资源占有者主动释放。
3>请求和保持条件，即当资源请求者在请求其他的资源的同时保持对原有资源的资源。
4>循环等待条件，即存在一个等待队列：P1占有P2的资源，P2占有P3的资源，P3占有P1的资源。这样就形成了一个等待环路。

**通常是打破第4个条件**

二、死锁例子

当上述四个条件都成立的时候，便形成死锁。当然，死锁的情况下如果打破上述任何一个条件，便可让死锁消失。下面用java代码来模拟一下死锁的产生。

package com.lu.simulation;

/**
 * 该类存放两个资源等待被使用
 * @author lu
 *
 */
public class Resource {

    public static Object o1 = new Object();
    public static Object o2 = new Object();

}



package com.lu.simulation;

/**
 * 线程启动调用run(),run()调用fun()方法
 * @author lu
 *
 */
public class DeadThread1 implements Runnable {

    @Override
    public void run() {
        fun();
    }

    //fun()方法首先占用o1资源,然后休眠1秒,让给其他线程执行。
    //然后请求o2资源
    public void fun() {
        synchronized (Resource.o1) {
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
            }
            synchronized (Resource.o2) {
                System.out.println("DeadThread1里的fun()被执行");
            }
        }
    }

}

'''

package com.lu.simulation;

/**
 * 线程启动调用run(),run()调用fun()方法
 * @author lu
 *
 */
public class DeadThread2 implements Runnable {

    @Override
    public void run() {
        fun();
    }

    //fun()方法首先占用o2资源,然后休眠1秒,让给其他线程执行。
    //然后请求o1资源
    public void fun() {
        synchronized (Resource.o2) {
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
            }

            synchronized (Resource.o1) {
                System.out.println("DeadThread1里的fun()被执行");
            }
        }
    }

}


package com.lu.simulation;

/**
 * 客户端
 * @author lu
 *
 */
public class Client {

    public static void main(String[] args) {
        DeadThread1 dt1 = new DeadThread1();
        DeadThread2 dt2 = new DeadThread2();

        Thread t1 = new Thread(dt1);
        Thread t2 = new Thread(dt2);

        //启动两个线程
        t1.start();
        t2.start();

    }   
}

当启动线程t1后，执行t1的fun方法，占用o1资源，然后t1休眠确保能够让t2来执行。t2执行fun()方法，占有o2资源。此时就形成了死锁产生的第四个必要条件。即线程t1占有了t2所需的资源，t2占有了t1所需的资源，双方都不释放，即形成死锁。

三、解除死锁

解决死锁的方法分为死锁的预防，避免，检测与恢复三种

死锁的预防是使产生死锁的四个必要条件不能同时具备，保证系统不进入死锁状态的一种策略

1〉打破互斥条件XXX。即允许进程同时访问某些资源。但是，有的资源是不允许被同时访问的，像打印机等等，这是由资源本身的属性所决定的。所以，这种办法并无实用价值。
2〉打破不可抢占条件。即允许进程强行从占有者那里夺取某些资源。就是说，当一个进程已占有了某些资源，它又申请新的资源，但不能立即被满足时，它必须释放所占有的全部资源，以后再重新申请。
3〉打破请求和 保持条件。可以实行资源预先分配策略。即进程在运行前一次性地向系统申请它所需要的全部资源。如果某个进程所需的全部资源得不到满足，则不分配任何资源，此进程暂不运行。
4〉破循环等待条件，实行资源有序分配策略。采用这种策略，即把资源事先分类编号，按号分配，使进程在申请，占用资源时不会形成环路。所有进程对资源的请求必须严格按资源序号递增的顺序提出。进程占用了小号资源，才能申请大号资源，就不会产生环路，从而预防了死锁。

死锁的避免，它不限制进程有关申请资源的命令，而是对进程所发出的每一个申请资源命令加以动态地检查，并根据检查结果决定是否进行资源分配。这种方法的关键是确定资源分配的安全性。

1.安全序列
2.银行家算法
这是一个著名的避免死锁的算法，是由Dijstra首先提出来并加以解决的。考试考了，忘不了

死锁的恢复

（1）最简单，最常用的方法就是进行系统的重新启动

（2）撤消进程，剥夺资源。终止参与死锁的进程，收回它们占有的资源，从而解除死锁。这时又分两种情况：一次性撤消参与死锁的全部进程，剥夺全部资源；或者逐步撤消参与死锁的进程，逐步收回死锁进程占有的资源。

Java中 一般时采用 预防死锁 的 破坏循环等待条件 写程序

但是如果真的已经出现死锁，要用死锁 恢复 中的撤销进程

Java死锁检测和解除？？？？

1. 最简单、最常用的方法就是进行系统的重新启动，不过这种方法代价很大，它意味着在这之前所有的进程已经完成的计算工作都将付之东流，包括参与死锁的那些进程，以及未参与死锁的进程；
2. 撤消进程，剥夺资源。终止参与死锁的进程，收回它们占有的资源，从而解除死锁。这时又分两种情况：一次性撤消参与死锁的全部进程，剥夺全部资源；或者逐步撤消参与死锁的进程，逐步收回死锁进程占有的资源。一般来说，选择逐步撤消的进程时要按照一定的原则进行，目的是撤消那些代价最小的进程，比如按进程的优先级确定进程的代价；考虑进程运行时的代价和与此进程相关的外部作业的代价等因素；
3. 进程回退策略，即让参与死锁的进程回退到没有发生死锁前某一点处，并由此点处继续执行，以求再次执行时不再发生死锁。虽然这是个较理想的办法，但是操作起来系统开销极大，要有堆栈这样的机构记录进程的每一步变化，以便今后的回退，有时这是无法做到的。