操作系统之死锁

死锁其实在信号量时已经提到过，当一个进程想要申请资源A，拥有资源B，而另一个进程想申请资源B，但是拥有资源A，那么就会产生死锁。
信号量本身就是个资源，有一定数量。资源分为很多很多，如内存空间，CPU周期，I/O设备等，每个资源有一定数量的资源实例。
资源和信号量一样，有等待队列，当一个进程想要申请资源，但需要其他进程释放此资源，则进入该资源的等待队列。

死锁的必要条件：
1.互斥。即资源不能被多个进程所占有。这点其实除了只读文件，其他基本都满足。
2.占有并等待：A进程占有一些资源，还需要的一些资源被其他进程占有，所以处在等待状态。
3.非抢占：资源不能被中途抢占。
4.循环等待：｛P0，P1,P2....｝进程队列，P0等待P1占用的资源，类似。

只要4个条件满足，则说明必定死锁。

资源分配图：为了清晰的看是否有死锁。P->R实线 申请；R->P实线 分配；P->R虚线 需求。
当每个资源类型只有一个实例，则有环等价于死锁。
当存在资源类型有多个实例，则死锁必有环，有环不一定死锁。

死锁处理：
1.1.死锁预防。通过不满足四个必要条件之一。
（1）互斥：很难不满足。
（2）占有并等待：第一，可要求进程创建就要申请好全部的资源；或第二，进程申请资源时要释放占有的资源。
但是第一种情况会发生饥饿。因为如果一个进程需要很多很多进程，这些资源几乎不会同时有，则这个进程永远不会执行。
（3）非抢占：如果A进程想要申请资源a，但是a被B进程占有，且B进程在等待资源b，则A进程可以抢占B进程的资源a执行。等到B进程得到原本

拥有的资源a和申请的b，则执行。 抢占和被抢占
（4）循环等待：规定资源被申请的顺序，每个进程申请资源的顺序被规定了。如果需要Rj（j<i）则需要先释放Ri。
1.2.死锁避免。前面讨论的预防死锁的解决方案中包括限制资源的申请，但是这对资源的利用率来说下降太多了。
所以引出了死锁避免：要求事先得到进程申请资源和拥有的资源的信息 来判定是否值得等待。(想起了管程的条件变量选择重启进程的解决方

法就是得知进程的最大需求)
最简单的方法是事先告诉每个进程对于每个资源类型的最大需求。从而使得循环等待不成立。
（1）安全状态:能确定一个进程序列<p1,p2...>，按照这种顺序执行进程就不会死锁（一个结束一个开始）。使得当Pi申请资源时，申请的资

源一定要小于剩余可用资源+pi队列前面的进程所占有的资源，则称为安全的。因为你想，Pi最多就等的长一点时间，但是最终还是能行的。
安全则不会死锁。不安全不一定会死锁。
只有资源分配后能安全状态，才允许申请。
（2）资源分配图算法：适用于每个资源类型只有一个实例。
分配边释放就变成需求边。

2.允许进入死锁，但可以检测并恢复。
3.忽略死锁。
银行家算法： 银行有一些资源，一个客户一会要一点资源，一会要一点资源，银行耐着性子分配。 预先知道Max，Allocation，Available
在新进程进入时，必须说明需要资源类型的种类和数量，但是不能超过系统总资源。
n为进程个数，m为资源类型种类，available为长度为m的向量，表示每种资源拥有多少的资源。
Max是n*m的矩阵，Max[i]表示特定进程需要的每个资源的最大需求。
Allocation是n*m的矩阵，Allocation[i]表示特定进程已经分配的每个资源的数量。
Need是n*m的矩阵，Need[i]是特定进程需要的剩余资源。
两个向量比较，只有每个分量都大，才大。
安全性算法：
设work是长度m的向量，finish是长度n的向量，
work=available;
for(int i=0;i<n;i++)
finish[i]=false;
for(int i=0;i<n;i++)O(n)
{
if(finish[i]==false&&Need[i]<work) O(m) //如果进程i的最大剩余需求小于系统剩余的资源量
{
work=work+allocation[i]; O(m) //执行完后释放，则系统剩余资源变多
finish[i]=true; //进程i执行结束
}
else break;
}
for(int i=0;i<n;i++)
{
if(finish[i]==false) return false;
}
return true;
资源请求算法：
Request[i]是进程i的请求向量。
if Request[i]<Need[i] 说明能申请
if Request[i]<Available 说明能分配
if能分配
｛
Available-=Request[i]; //系统剩余减少
Allocation[i]+=Request[i]; //已分配增多
Need[i]-=Request[i]; //剩余需求减少
｝
分配完执行安全性算法，即看看是不是安全。

系统不采用预防或避免提前去除死锁时，可以
1.有一个算法可以检索死锁的发生。
2.有一个算法可以让死锁恢复。
当资源类型只有一个资源实例时，可以用等待图（只有进程）解决。当有环时，则死锁。
当资源类型可以有多个实例时，则可以用银行家算法解决。

有一个好办法解决死锁，就是当CPU使用率低于多少多少时，才调用死锁检测，再去除死锁。

恢复死锁可以：
1.随便终止一个进程打破循环等待。
当选择进程的终止时，需要考虑很多方面，就像CPU调度里的优先队列法，可以以不同方面考虑优先。可以以进程执行时间、进程还需资源多少

、进程是交互的还是批处理的。
2.抢占死锁进程资源。
抢占要抢占谁的又是个问题。自己选呗~而被抢占资源的进程必须回滚到不会发生死锁的时刻。而且不能一直欺负一个进程，这样该进程会发生

饥饿。