多线程死锁、活锁、饥饿

一、死锁

1、死锁：所谓死锁是指多个线程因竞争资源而造成的一种僵局（互相等待），若无外力作用，这些进程都将无法向前推进。

理解的例子：

　　生活中的一个实例，2个人一起吃饭但是只有一双筷子，2人轮流吃（同时拥有2只筷子才能吃）。某一个时候，一个拿了左筷子，一人拿了右筷子，2个人都同时占用一个资源，等待另一个资源，这个时候甲在等待乙吃完并释放它占有的筷子，同理，乙也在等待甲吃完并释放它占有的筷子，这样就陷入了一个死循环，谁也无法继续吃饭。。。

2、死锁产生的四个必要条件：

（1）死锁产生的条件：产生死锁必须同时满足以下四个条件，只要其中任一条件不成立，死锁就不会发生。

互斥：某种资源一次只允许一个线程访问，即该资源一旦分配给某个线程，其他线程就不能再访问，直到该线程访问结束。
占有且等待：一个线程本身占有资源（一种或多种），同时还有资源未得到满足，正在等待其他线程释放该资源。
不可抢占：别人已经占有了某项资源，你不能因为自己也需要该资源，就去把别人的资源抢过来。
循环等待：存在一个线程链，使得每个线程都占有下一个线程所需的至少一种资源。

3、死锁预防：

我们可以通过破坏死锁产生的4个必要条件来预防死锁，由于资源互斥是资源使用的固有特性是无法改变的。

（1）破坏“占有且等待”条件

方法1：所有的线程在开始运行之前，必须一次性地申请其在整个运行过程中所需要的全部资源。
优点：简单易实施且安全。
缺点：因为某项资源不满足，进程无法启动，而其他已经满足了的资源也不会得到利用，严重降低了资源的利用率，造成资源浪费。
使进程经常发生饥饿现象。

方法2：该方法是对第一种方法的改进，允许线程只获得运行初期需要的资源，便开始运行，在运行过程中逐步释放掉分配到的已经使用完毕的资源，然后再去请求新的资源。这样的话，资源的利用率会得到提高，也会减少进程的饥饿问题。

（2）破坏“不可抢占”条件

当一个已经持有了一些资源的线程在提出新的资源请求没有得到满足时，它必须释放已经保持的所有资源，待以后需要使用的时候再重新申请。这就意味着线程已占有的资源会被短暂地释放或者说是被抢占了。

该种方法实现起来比较复杂，且代价也比较大。释放已经保持的资源很有可能会导致线程之前的工作失效等，反复的申请和释放资源会导致线程的执行被无限的推迟，这不仅会延长进程的周转周期，还会影响系统的吞吐量。

（3）破坏“循环等待”条件

采用资源有序分配其基本思想是将系统中的所有资源顺序编号，将紧缺的，稀少的采用较大的编号，在申请资源时必须按照编号的顺序进行（从小往大申请），一个进程只有获得较小编号的线程才能申请较大编号的线程。
4、死锁避免：

死锁避免：在使用前进行判断，只允许不会产生死锁的进程申请资源；

死锁避免是利用额外的检验信息，在分配资源时判断是否会出现死锁，只在不会出现死锁的情况下才分配资源。
两种避免办法：
1、如果一个进程的请求会导致死锁，则不启动该进程
2、如果一个进程的增加资源请求会导致死锁，则拒绝该申请。
避免死锁的具体实现通常利用银行家算法
银行家算法
a、银行家算法的相关数据结构
　　可利用资源向量Available：用于表示系统里边各种资源剩余的数目。由于系统里边拥有的资源通常都是有很多种（假设有m种），所以，我们用一个有m个元素的数组来表示各种资源。数组元素的初始值为系统里边所配置的该类全部可用资源的数目，其数值随着该类资源的分配与回收动态地改变。
　　最大需求矩阵Max：用于表示各个进程对各种资源的额最大需求量。进程可能会有很多个（假设为n个），那么，我们就可以用一个nxm的矩阵来表示各个进程多各种资源的最大需求量
　　分配矩阵Allocation：顾名思义，就是用于表示已经分配给各个进程的各种资源的数目。也是一个nxm的矩阵。
　　需求矩阵Need：用于表示进程仍然需要的资源数目，用一个nxm的矩阵表示。系统可能没法一下就满足了某个进程的最大需求（通常进程对资源的最大需求也是只它在整个运行周期中需要的资源数目，并不是每一个时刻都需要这么多），于是，为了进程的执行能够向前推进，通常，系统会先分配个进程一部分资源保证进程能够执行起来。那么，进程的最大需求减去已经分配给进程的数目，就得到了进程仍然需要的资源数目了。

银行家算法通过对进程需求、占有和系统拥有资源的实时统计，确保系统在分配给进程资源不会造成死锁才会给与分配。
死锁避免的优点：不需要死锁预防中的抢占和重新运行进程，并且比死锁预防的限制要少。
死锁避免的限制：
必须事先声明每个进程请求的最大资源量
考虑的进程必须无关的，也就是说，它们执行的顺序必须没有任何同步要求的限制
分配的资源数目必须是固定的。
在占有资源时，进程不能退出

4、死锁实现代码：

/** 
* 一个简单的死锁类 
* 当DeadLock类的对象flag==1时（td1），先锁定o1,睡眠500毫秒 
* 而td1在睡眠的时候另一个flag==0的对象（td2）线程启动，先锁定o2,睡眠500毫秒 
* td1睡眠结束后需要锁定o2才能继续执行，而此时o2已被td2锁定； 
* td2睡眠结束后需要锁定o1才能继续执行，而此时o1已被td1锁定； 
* td1、td2相互等待，都需要得到对方锁定的资源才能继续执行，从而死锁。 
*/  
public class DeadLock implements Runnable {  
    public int flag = 1;  
    //静态对象是类的所有对象共享的  
    private static Object o1 = new Object(), o2 = new Object();  
    @Override  
    public void run() {  
        System.out.println("flag=" + flag);  
        if (flag == 1) {  
            synchronized (o1) {  
                try {  
                    Thread.sleep(500);  
                } catch (Exception e) {  
                    e.printStackTrace();  
                }  
                synchronized (o2) {  
                    System.out.println("1");  
                }  
            }  
        }  
        if (flag == 0) {  
            synchronized (o2) {  
                try {  
                    Thread.sleep(500);  
                } catch (Exception e) {  
                    e.printStackTrace();  
                }  
                synchronized (o1) {  
                    System.out.println("0");  
                }  
            }  
        }  
    }  
  
    public static void main(String[] args) {  
          
        DeadLock td1 = new DeadLock();  
        DeadLock td2 = new DeadLock();  
        td1.flag = 1;  
        td2.flag = 0;  
        //td1,td2都处于可执行状态，但JVM线程调度先执行哪个线程是不确定的。  
        //td2的run()可能在td1的run()之前运行  
        new Thread(td1).start();  
        new Thread(td2).start();  
  
    }  
}

多线程死锁、活锁、饥饿

一、死锁

推荐阅读