死锁-操作系统-程序员面试

时间:2022-10-05 14:25:18

操作系统-死锁

3 死锁

在多道程序中,由于多个并发进程共享系统的资源,如果使用不当,可能会造成一种僵局,即当某个进程提出资源使用请求后,使得系统中一些进程处于无休止的阻塞状态,在无外力作用下,这些进程将无法继续进行下去,称为死锁。

3.1 死锁产生的环境和条件

死锁产生的环境

1) 多道程序设计

2) 多个进程并发

3) 资源共享和独占

4) 没有外力可以借助

死锁产生的必要条件

1) 资源互斥使用(资源独占)

2) 非剥夺控制(不可强占)

3) 请求与保持

4) 循环等待

如果死锁发生,则四个条件必然同时满足

死锁的危害

轻则系统资源利用率下降,重则系统瘫痪

3.2 死锁的解决策略

置之不理--鸵鸟政策

优点:简单、简化系统设计,节约成本
缺点:安全性欠佳,适合于低可靠性和低安全性系统

事后处理法--让死锁发生,事后处理

思路:可以容忍死锁的发生,事后处理
优点:灵活,但不是所有情况都可以容忍死锁的发生

积极预防法--不让死锁发生

思路:以积极的抑制为出发点
手段:

1) 死锁的预防:破坏死锁产生的条件,使其不具备发生的可能

2) 死锁的避免:允许存在发生死锁的可能性,但是在每一步进行资源分配时灵活处理,使得永远不到达死锁的状态。

3.2 死锁的预防

破坏互斥条件

局限性:“互斥”条件破坏往往困难,而且对很多资源行不通,因此不是一种好的方案。

破坏不可剥夺条件

思路:允许一个进程还未执行完成时释放已经占有的资源(被剥夺使用权)
局限:实现困难,为了恢复现场需要耗费很多时间和空间。因此只适合类似CPU、存储器这样的资源。

破坏请求与保持条件(零散请求)

思路:进程创建时就由系统分配了所有需要的资源,然后执行,并且以后没有资源申请要求,进程执行完后,释放资源。
局限:系统效率低,资源浪费严重,并发性下降。

破坏循环等待条件

思路:给资源进行编号,进程必须按序进行申请。
局限:资源编号困难,资源编号很难和进程申请资源的顺序一致。

结论:死锁预防是一破坏死锁产生的必要条件为基本方法,从而防止死锁的发生,对资源加上了诸多的限制,因此这种策略虽然具有一定的效果,但其资源的利用率和效率较低,很难令人满意。

3.3 死锁的避免

思路:允许死锁产生的条件存在,但是通过动态的明智的选择--在分配资源之前,系统判断,假若满足进程的要求是否会产生死锁,如果会,资源不予分配,从而确保永远不会到达死锁,避免死锁的发生。
优点:比预防更为灵活实用,允许更多的并发,其资源利用率和效率也更高。

系统的状态

安全状态:指在某个时刻,当多个进程动态的申请资源时,如果存在一种顺序,使得系统按照这种顺序逐次地为每个进程分配所需要的资源后,每个进程都可以在最终得到最大需求量后,依次顺序的完成。
不安全状态:死锁状态
避免死锁的关键就是:让系统在动态分配资源的过程中,不要进入到不安全状态。

银行家算法

单银行家算法

例:假设一个银行拥有资金数量为 10 现有 4 个客户 a,b,c,d 。要求贷款所需最大资金需求量为 8,5,6,7

 死锁-操作系统-程序员面试

多项资源银行家避免算法

适用于一个进程申请多个资源的情况
例:系统中有5台打印机,7个写字板,8台扫描仪,9个读卡器,共有5个进程T1、T2、T3、T4、T5共享这些资源,各进程Max和Allocation矩阵如下:
问:如果T2此时希望得到1台打印机,1个手写板,2个读卡器是否可以满足?

死锁-操作系统-程序员面试

3.4 死锁的检测与解除

检测工具 -- 资源分配图

资源分配图:是描述进程申请资源和资源分配的关系模型图,表示系统中某个时刻进程对资源的申请和占有情况。

死锁-操作系统-程序员面试 规则:
1) 圆表示一个进程
2)方块表示资源类,其中的圆点表示该类型资源中的某个单个资源。
3)从资源指向进程的箭头表示资源分配给了这个进程
4)从进程指向资源的箭头表示进程请求这个资源

检测方法 -- 化简

方法:
1) 从那些没有阻塞的进程入手,删除那些没有阻塞进程的请求边,并使得资源数减1
2)重复
a) 途中所有请求边都删除了,则不会死锁。
b) 图中仍然有请求边但无法化简,系统死锁。

死锁的解除

a) 重新启动(简单、浪费)
b) 撤销进程
1) 撤销造成死锁的进程
2) 一次性撤销所有死锁进程(损失较大)
3)逐个撤销,分别回收资源(可Ian撤销那些优先级低的、已占有资源少或已运行时间短、还需运行时间较长的进程,尽量减少系统的损失)。
c) 剥夺资源
d) 进程回退