【操作系统】③死锁
2022秋招大厂-Java后端开发-面试题目汇总① 2022秋招-研究所/银行-软件开发-面试题目汇总 【总结】海量数据处理的方法总结 【总结】面试中常见的智力题 【秋招总结】无实习无框架项目经历的Java后端开发上岸之路
一、死锁基本知识点
1.死锁的概念
在两个或者多个并发进程中,如果每个进程持有某种资源而又等待其它进程释放它或它们现在保持着的资源,在未改变这种状态之前都不能向前推进,称这一组进程产生了死锁。通俗的讲,就是两个或多个进程无限期的阻塞、相互等待的一种状态。
死锁是指两个或两个以上的进程在执行过程中,由于竞争资源或者由于彼此通信而造成的一种阻塞的现象,若无外力作用,它们都将无法推进下去。此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程。
2.死锁产生的原因
- 竞争资源;
- 进程推进顺序不当(比如 a,b 互相等待对方发信息);
3.死锁的必要条件
● 互斥条件:指进程对所分配到的资源进行排它性使用,即在一段时间内某资源只由一个进程占用。如果此时还有其它进程请求资源,则请求者只能等待,直至占有资源的进程用毕释放。
● 请求与保持条件:进程已经保持了至少一个资源,但又提出了新的资源请求,而该资源已被其他进程占有,此时请求进程被阻塞,但对自己已获得的资源保持不放。
● 不可剥夺条件:进程所获得的资源在未使用完毕之前,不能被其他进程强行夺走,即只能 由获得该资源的进程自己来释放(只能是主动释放)。
● 循环等待条件:指在发生死锁时,必然存在一个进程——资源的环形链,即进程集合{P0,P1,P2,···,Pn}中的P0正在等待一个P1占用的资源;P1正在等待P2占用的资源,……,Pn正在等待已被P0占用的资源。若干个进程间形成了首尾相接循环等待资源的情况
二、死锁处理方法
主要有以下四种方法:
- 鸵鸟策略
- 死锁检测与死锁恢复
- 死锁预防
- 死锁避免
1.鸵鸟策略
把头埋在沙子里,假装根本没发生问题。
因为解决死锁问题的代价很高,因此鸵鸟策略这种不采取任务措施的方案会获得更高的性能。
当发生死锁时不会对用户造成多大影响,或发生死锁的概率很低,可以采用鸵鸟策略。
大多数操作系统,包括 Unix,Linux 和 Windows,处理死锁问题的办法仅仅是忽略它。
2.死锁的检测和解除
在死锁产生前不采取任何措施,只检测当前系统有没有发生死锁,若有,则采取一些措施解除死锁。
死锁的检测:
根据死锁定理:S 为死锁的条件是当且仅当 S 状态的资源分配图是不可完全简化的,该条件称为死锁定理。
死锁的解除:
1、资源剥夺:挂起某些死锁进程,并抢占它的资源,将这些资源分配给其他死锁进程。(但应该防止被挂起的进程长时间得不到资源);
2、撤销进程:强制撤销部分、甚至全部死锁进程并剥夺这些进程的资源。(撤销的原则可以按进程优先级和撤销进程代价的高低进行);
3、进程回退:让一个或多个进程回退到足以避免死锁的地步。【进程回退时自愿释放资源而不是被剥夺。要求系统保持进程的历史信息,设置还原点。】
- 利用抢占恢复
- 利用回滚恢复
- 通过杀死进程恢复
3.死锁预防
破坏四个必要条件之一
3.1. 破坏互斥条件:
改造独占性资源为虚拟资源,大部分资源已无法改造。
即允许进程同时访问某些资源。但是,有的资源是不允许被同时访问的,像打印机等等。所以,这种办法并无实用价值。
3.2. 破坏不可剥夺条件:
当一进程占有一独占性资源后又申请一独占性资源而无法满足,则退出原占有的资源。
当一个进程已占有了某些资源,它又申请新的资源,但不能立即被满足时,它必须释放所占有的全部资源,以后再重新申请。这就相当于该进程占有的资源被隐蔽地强占了。这种预防死锁的方法实现起来困难,会降低系统性能。
3.3. 破坏请求与保持条件:
采用资源预先分配策略,即进程运行前申请全部资源,满足则运行,不然就等待,这样就不会占有且申请。
可以实行资源预先分配策略。即进程在运行前,一次性地向系统申请它所需要的全部资源。
如果某个进程所需的全部资源得不到满足,则不分配任何资源,此进程暂不运行。只有当系统能够满足当前进程的全部资源需求时,才一次性地将所申请的资源全部分配给该进程。由于运行的进程已占有了它所需的全部资源,所以不会发生占有资源又申请资源的现象,因此不会发生死锁。
3.4.破坏循环等待条件:实行顺序资源分配法
实现资源有序分配策略,对所有设备实现分类编号,所有进程只能采用按序号递增的形式申请资源。
首先给系统中的资源编号,规定每个进程,必须按编号递增的顺序请求资源,同类资源一次申请完。也就是说,只要进程提出申请分配资源Ri,则该进程在以后的资源申请中,只能申请编号大于Ri的资源。
4.避免死锁
银行家算法【在动态分配资源的过程中,银行家算法防止系统进入不安全状态,从而避免死锁】
银行家算法:
当进程首次申请资源时,要测试该进程对资源的最大需求量,如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源,否则就推迟分配。
当进程在执行中继续申请资源时,先测试该进程已占用的资源数与本次申请资源数之和是否超过了该进程对资源的最大需求量。若超过则拒绝分配资源。若没超过则再测试系统现存的资源能否满足该进程尚需的最大资源量,若满足则按当前的申请量分配资源,否则也要推迟分配。
安全序列:
是指系统能按某种进程推进顺序(P1, P2, P3, …, Pn),为每个进程 Pi 分配其所需要的资源,直至满足每个进程对资源的最大需求,使每个进程都可以顺序地完成。这种推进顺序就叫安全序列【银行家算法的核心就是找到一个安全序列】。
系统安全状态 :
如果系统能找到一个安全序列,就称系统处于安全状态,否则,就称系统处于不安全状态
#高频知识点汇总##Java##学习路径#