OS-2.4 死锁

2.4 死锁

==死锁公式：m个资源>n个进程（每个进程所需资源数k-1）【不会发生死锁】==

按照安全家算法，只要保证进程申请的最大资源数≤m，就一定存在一个安全队列。考虑极端的情况，n-1个进程申请了1个资源，剩下的一个进程申请了m个资源，则==各个进程最大需求之和为m+（n-1），此时一定不会发生死锁==

死锁的概念

基本概念

死锁：互相拥有对方的资源，且互相等待对方的资源，所有人都因此而阻塞。

饥饿：长期得不到资源。

死循环：进程跳不出某个循环。（死循环的进程可以上CPU）

死锁和饥饿是OS要解决的问题。死循环是coder要解决的问题。

死锁产生的四个必要条件（需同时满足）

互斥条件：对互斥使用的资源的争抢。

不剥夺条件：进程所获得的资源在未使用完之前，不能被其他进程强行夺走，只能主动释放。

请求并保持条件：已有（一个）资源，同时发出新的资源请求，若无法获得，则阻塞但不会释放已占有的资源。

循环等待条件：存在一种进程资源的循环等待链。

注：发生死锁一定有循环等待，但是发生循环等待未必是死锁。（if 同类资源大于1，可以由别人提供）

什么时候（有可能）发生死锁

① 对系统资源的竞争

② 进程推进顺序非法

③ 信号量使用不当

In total：对不可剥夺资源的不合理分配，可能造成死锁。

死锁的处理策略

回顾

死锁的处理策略① – 预防策略

A：破坏–互斥条件

比如SPOOLing技术，把互斥的资源改成可共享的资源，让各个进程看起来自己的响应被即刻接收处理了（实际上多加了一层类似cache的层）

缺点：很多资源无法改成可共享的资源。本质上不可行。

B：破坏–不剥夺条件

①进程请求资源得不到满足时，主动释放自己保持的资源。（以后需要再重新申请）

②进程需要的资源被其他进程占有时，OS帮助强行去剥夺资源。

缺点：

①实现复杂

②释放已获得的资源可能造成前一阶段的工作失效。

③申请和释放资源会增加系统开销。

④方案一可能会有进程一直无法完整地申请到资源，造成进程饥饿。

C：破坏–请求和保持条件

进程在运行前，申请完它所需要的全部资源！（就不会出现已有一个资源，继续申请资源，同时保留已有的资源不放手的情况。）

缺点：有的资源用的时间短，用完在进程中闲着，造成资源浪费。

D：破坏–循环等待条件

顺序资源分配法：给系统的资源编号，每个进程必须按编号递增的顺序请求资源。

这样子总有一个进程拥有的资源编号是最大的，这个进程申请后面的资源必然畅行无阻，不会造成all堵塞的死锁现象。

缺点：

①不方便增加新的设备。

②进程实际使用资源的顺序可能和编号递增的顺序不一致（导致前面的资源浪费）

③编程麻烦。

EG：①哲学家问题奇数号拿左边筷子，偶数右边。②限制允许拿起筷子的哲学家数量。（即不被限制的可以拿两双，破坏了环）

回顾

死锁的处理策略② – 避免死锁

安全序列，不安全状态，死锁

不安全状态不一定发生死锁，死锁一定是不安全状态。安全状态一定不发生死锁。

安全系列不是固定的，不是唯一的，不是必须遵循的法则，只是一种可能的分配方案。

==银行家算法==

在进程提出资源申请的时候，先预算一下此次分配是否会导致系统进入不安全状态。

如果会进入不安全状态，就暂时不答应这次请求，让进程先阻塞等待。

==安全性算法==

检查当前的剩余可用资源，是否能满足某一个进程（从编号小的进程开始）的当前最大需求，如果可以，就把该进程加入安全队列，

之后把该进程的资源全部回收，更新剩余可用资源值，

重复第一步，直到最终所有进程都加入安全队列（或否）。

注意区分三个矩阵：“最大需求矩阵”，“已分配矩阵”，“还需资源”

例子：能找到安全序列

例子：找不到安全序列

实现

回顾

死锁的处理策略③ – 检测和解除

死锁的检测

==死锁 == 形成环路 + 每种资源只有一个==

①用某种数据结构保存资源的请求和分配信息

请求边：从进程节点指向资源节点

分配边：从资源节点指向进程节点

②提供一种算法，利用上述信息来检测（当前）系统是否进入死锁状态

算法简单来说就是，把 没发生阻塞的 进程，所有相连的边都消去，

如果最终消除所有边，就是可完全简化的，一定没有发生死锁。（死锁定理）

（没发生阻塞：进程能申请到资源）

死锁的解除

①资源剥夺

②进程撤销

③进程回退

回顾