多线程之死锁

了解死锁

死锁的 4个必要条件：

互斥条件：一个资源每次只能被一个进程使用，即在一段时间内某资源仅为一个进程所占有。此时若有其他进程请求该资源，则请求进程只能等待。
请求与保持条件：进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源已被其他进程占有，此时请求进程被阻塞，但对自己已获得的资源保持不放。
不可剥夺条件:进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的进程自己来释放（只能是主动释放)。
循环等待条件: 若干进程间形成首尾相接循环等待资源的关系。

补充：饥饿

饥饿（Starvation）指一个进程一直得不到资源。饥饿一般不占有资源，死锁进程一定占有资源。

典型案例-必然死锁

public class MustDead implements Runnable {
    int flag = 1;

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

    @Override
    public void run() {
        System.out.println("falg=" + flag);
        if(flag == 1){
            synchronized (o1){
                try {
                    System.out.println("a线程拿到了O1锁");
                    Thread.sleep(500);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                synchronized (o2){
                    System.out.println("a都拿到了");
                }
            }
        }
        if(flag == 0){
            synchronized (o2){
                try {
                    System.out.println("b线程拿到了O2锁");
                    Thread.sleep(500);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                synchronized (o1){
                    System.out.println("b都拿到了");
                }
            }
        }
    }

    public static void main(String[] args){
        MustDead r1 = new MustDead();
        MustDead r2 = new MustDead();
        r1.flag = 1;
        r2.flag = 0;
        Thread a = new Thread(r1);;
        Thread b = new Thread(r2);
        a.start();
        b.start();
    }
}

运行结果（不唯一，但是能死锁）：

falg=1
a线程拿到了O1锁
falg=0
b线程拿到了O2锁

死锁的解决方式

A：死锁预防
只要打破四个必要条件之一就能有效预防死锁的发生：

打破互斥条件：一般无法破坏此条件
打破不可抢占条件：拿不到想要的资源，就把自己获得的资源释放掉。
打破占有且申请条件：采用资源预先分配策略，即进程运行前申请全部资源，满足则运行，不然就等待，这样就不会占有且申请。
打破循环等待条件：实现资源有序分配策略，对所有设备实现分类编号，所有进程只能采用按序号递增的形式申请资源。（比如只能按abc顺序申请，就不会有拿了b再申请a，从而形成死锁）

B:避免死锁
死锁预防是排除死锁的静态策略，它使产生死锁的四个必要条件不能同时具备，从而对进程申请资源的活动加以限制，以保证死锁不会发生。而死锁避免使指：在资源分配过程中若预测有发生死锁的可能性，则加以避免。
1.安全序列
2.银行家算法

死锁解除

主要方法有：

1) 资源剥夺法。挂起某些死锁进程，并抢占它的资源，将这些资源分配给其他的死锁进程。但应防止被挂起的进程长时间得不到资源，而处于饥饿的状态。
2) 撤销进程法。强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。撤销的原则可以按进程优先级和撤销进程代价的高低进行。
3) 进程回退法。让一（多）个进程回退到足以回避死锁的地步，进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息，设置还原点。