线程死锁及其解决

一、什么是死锁
死锁：（摘自百度百科）
两个或两个以上的进程在执行过程中，因争夺共享资源而造成的一种互相等待的现象，若无外力作用，它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁，这些永远在互相等待的进程称为死锁进程。 由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊现象死锁。
二、死锁的原因及形成思索的条件
死锁形成的原因：
1、系统资源不足。
2、进程（线程）推进的顺序不当。
3、资源分配不当。

死锁形成的条件：
1、互斥条件：
所谓互斥就是进程在某一时间内独占资源。
2、请求与保持条件：
一个进程因请求资源而阻塞时，对方已获得资源并保持不放。
3、不剥夺条件：
进程已获得资源，未使用完之前不能强行剥夺。
4、循环等待条件：
若干进程之间形成一种头尾相接的循环等待方式。

三、死锁形成的场景
我们知道引入死锁是为了解决多进程多线程之间同步与互斥的问题，但是又引入了新的问题那就是死锁。下面我们来看看多线程典型的死锁的情景：
1、线程自己将自己锁住：
如果一个线程先后两次调用lock，在第二次调用的时候由于锁已经被占用，那么线程就会被挂起等待线程会挂起等待占用锁的线程释放锁。然而锁正是被自己占用着的，该线程又被挂起而没有机会释放锁，因此 就永远处于挂起等待状态了，于是就形成了死锁(Deadlock)。
2、多线程 抢占锁资源：
线程A有一个锁1，线程B有一个锁2。线程A试图调用lock来获取锁2就得挂起等待线程B释放，线程B也调用lock试图获得锁1。那么这就很尴尬，都在等对方释放，然后获得对方的锁。这时也就是死锁。
其中一个解决方法就是加大锁定的粒度，也就是尽量锁大的对象，不要锁得太小，还有尽量不要同时锁2个或2个以上的对象，但是还有待于进一步研究。

死锁形成的几种场景：
1、忘记释放锁

void data_process()
{
    EnterCriticalSection();

    if(/* error happens, forget LeaveCriticalSection */)
        return;

    LeaveCriticalSection();
}

2、单线程重复申请锁

void sub_func()
{
    EnterCriticalSection();
    do_something();
    LeaveCriticalSection();
}

void data_process()
{
    EnterCriticalSection();
    sub_func();
    LeaveCriticalSection();
}

3、多线程多锁申请

void data_process1()
{
    EnterCriticalSection(&cs1);　　// 申请锁的顺序有依赖
    EnterCriticalSection(&cs2);
    do_something1();
    LeaveCriticalSection(&cs2);
    LeaveCriticalSection(&cs1);
}

void data_process2()
{
    EnterCriticalSection(&cs2);　　// 申请锁的顺序有依赖
    EnterCriticalSection(&cs1);
    do_something2();
    LeaveCriticalSection(&cs1);
    LeaveCriticalSection(&cs2);
}

四、死锁的避免及其解决方案
处理死锁的方法：
1、预防死锁：
破坏死锁产生的必要条件中的一个或多个，互斥条件不能被破坏否则会造成结果的不可再现性。
2、避免死锁：
在资源分匹配过程中，防止系统进入不安全区域
3、检测死锁：
通过检测机构检测死锁的发生，然后采取适当措施解除死锁
4、解除死锁：
在检测机构检测死锁发生后，采取适当措施解除死锁

五、利用银行家算法来解决死锁问题
1、银行家算法
设Request( i)是进程Pi的请求向量，如果Request(i) [j] = K,表示进程Pi需要K个Rj类型的资源。
（1）如果Request(i) [j] <= Need[i][j],转向步骤（2）。
（2）如果Request(i) [j] <= Available[j] ,转向步骤（3）。
（3）系统尝试着把资源分给进程Pi。
Available[j] = Available[j] - Request(i) [j];
Allocation[i][j] = Allocation[i][j] + Request(i) [j];
Need[i][j] = Need[i][j] - Request(i) [j];
（4）系统执行安全性算法，检查此次资源分配后系统是否处于安全状态。
2、银行家算法中的数据结构
（1）可利用资源向量Available[m]。m为系统中的资源种类数，如果向量Available[j] = K,则表示系统中Rj类资源由K个。
（2）最大需求矩阵Max[n][m]。m为系统中的资源种类数，n为系统中正在运行的进程（线程）数，如果Max[i][j] = K,则表示进程i需要Rj类资源的最大数目为K个。
（3）分配矩阵Allocation[n][m]。m为系统中的资源种类数，n为系统中正在运行的进程（线程）数，如果Allocation[i][j] = K,则表示进程i当前已分得Rj类资源的数目为K个。
（4）需求矩阵Need[n][m]。m为系统中的资源种类数，n为系统中正在运行的进程（线程）数，如果Need[i][j] = K,则表示进程i还需要Rj类资源K个。
以上三个矩阵间的关系：
Need[i][j] = Max[i][j] - Allocation[i][j]
3、安全性算法
（1）设置两个向量：
1、工作向量Work[m],它表示系统可提供给进程继续运行所需要的各类资源数目,初始值Work = Available。
2、Finish:它表示系统是否有足够的资源分配给进程，使其运行完成。开始时Finish[i] = false，当有足够的资源分配给进程时Finish[i] = true。
（2）从进程（线程）集合中找到一个能满足下述条件的进程（线程）。
1、Finish[i] = false
2、Need[i][j] <= Work[j]，如果找到转到步骤3，没找到转到步骤4。
3、Work[j] = Work[j] + Allocation[i][j] ;
Finish[i] = true;
go to step 2;
4、如果所有进程（线程）的Finish[i] = true都满足，表示系统处于安全状态，反之系统处于不安全状态。