死锁
死锁
死锁的原因
- 系统资源的竞争
- 进程推进顺序的非法
死锁的必要条件
- 互斥(mutual exclusion):至少存在一个资源使得两个进程需要互斥使用，即一个进程在使用时，另一个进程必须等待。
- 占有并等待(hold and wait):一个进程占有了某个资源后等待另一个资源，但是另一个资源被另外一个进程所占有。
- 非抢占(no preemption):资源不能被抢占，只能被占有的资源资源释放。
- 循环等待(circular wait):一组资源，A等待B抢占的资源，B等待C抢占的资源…….最后N等待A抢占的资源，从而形成环。
四个条件同时成立便会出现死锁，且四个条件并不完全独立(如循环等待可能需要占有并等待的条件才能满足)。
资源分配图
如图所示即资源分配图，其中圆形表示进程，矩形表示资源，P->R表示一条申请边，R->P表示分配边。
可以证明如果分配图中没有环，则系统中没有死锁进程，如果有环则可能存在死锁。而刚好每种资源只有一个时候，存在环则说明有死锁情况发生。
死锁处理方法
- 死锁预防：限制死锁的四个条件，破坏其中一个或几个条件。
- 死锁避免：资源分配过程中，防止系统进入不安全状态。
- 死锁检测及解除：不采取任何措施，但是在系统运行中及时检测死锁的存在，然后解除他们。
死锁预防
互斥
互斥条件必须成立。
持有且等待
在申请一个资源时候不能占有其他资源(即申请资源的系统调用在其他系统调用之前进行，或者申请时候释放已分配的资源，或者在进程运行前一次性分配所有的资源)，这样做缺点就是资源利用率低，且可能发生饥饿。
非抢占
在申请资源时候，现有的资源都可被抢占或者释放。会增加系统的开销，降低系统的吞吐率，适合于CPU寄存器和内存。
循环等待
对所有资源进行排序，资源申请必须按照给定的顺序进行申请。需要程序员自觉遵守顺序，且如果增加了新类型的设备，会改变既定的分配顺序，则编程代码都需要改变。
死锁避免
避免死锁需要额外的信息，即如何申请资源，获知每个进程的资源请求和释放顺序之后，系统可以决定在进程请求资源时候避免未来可能的死锁。而保持系统一直处于安全状态即可避免死锁。但是并非所有的不安全状态都是死锁状态，但当系统进入不安全状态之后，便可能进入死锁状态。
资源分配图算法
在前述资源分配图中增加需求边。这种边与申请边(P->R)一样，但是是虚线。
当进程申请资源时候则把其变为P->R的申请边，当申请到资源之后则变成R->P的分配边，资源释放之后R->的分配边变为P->R的虚线需求边。
资源分配图算法要求，在进程申请资源时，只有将其申请边变为分配边时，不会导致资源分配图形成环。如图所示图一如果变成图二，则会形成环，于是图二被认为是不安全状态，不予分配资源。
银行家算法
一句话来说就是假设分配给一个进程资源之后，系统是否处于不安全状态，如果是不安全状态则不给该次分配。
具体过程就是根据这句话，然后把三个矩阵变来变去，懒得讲了，直接看书比较实在(书上balabala讲了一堆估计也懒得看，反正记住这句话就行了)
死锁检测
死锁定理及资源分配图简化算法
还是这张图，简化算法如下：
- 在资源分配图中找到既不阻塞，也不孤点的进程P
i，并消除其所有请求边和分配边。即找到一条有向申请边，其尾部对应该进程Pi，其边箭头所指的资源申请数量小于等于系统中空闲资源数量。(如图中资源R2资源有两个，其中分配出去给P2一个，所以空闲的是一个，而P1进程申请边请求一个，满足小于等于，也就说明P1可以正常申请且运行，然后将其所有的分配边和申请边全删除，表明进程运行完成资源释放。) - 不断删去所有这样的进程，最后能够删除所有的边，则表明此资源分配图可简化。
死锁定理表明，S为死锁的条件是当且仅当S状态的资源分配图是不可完全简化的。
等待图
如果所有资源只有单个实例，则可以使用等待图的方式。等待图即从资源分配图中删除所有资源类型的节点，并合并适当的边即可。即如果资源分配图中存在Pi ->Rq和Rq->Pj的两条边，则等待图中存在一条Pi->Pj的一条边。如图a为资源分配图，b为对应的等待图。
当等待图中有一个环则系统死锁。
死锁恢复/解除
当检测算法确定当前系统状态存在死锁，于是需要采取一定措施来解除死锁。
- 中止部分/全部死锁进程：可以一次性中止所有进程，又或者一次中止一个进程，直到消除死锁循环。
- 资源抢占：挂起死锁进程，并抢占其所有资源给其他进程使用，且被强占资源的进程需要回滚，同时要确保进程不能发生饥饿情况。
- 进程回退：让一个/多个进程回退到某个状态，使得系统状态到达没有死锁的状态。需要保存历史信息，并设置还原点。