首先,从操作系统的角度整理死锁和操作系统的死锁处理策略。
死锁概念
什么现象会导致并发死锁,使每个进程都在争用资源,等待彼此手中的资源,导致每个进程被阻塞,无法前进?
死锁发生后,如果没有外力的干扰,这些过程就无法前进。
死锁、饥饿、死循环差异死锁:
各进程相互等待对方手中的资源,导致各进程堵塞,无法前进的现象
饿了:
由于长期得不到想要的资源,某些过程无法前进;
死循环
进程正在运行时,循环无法跳过。 有时是因为程序逻辑中的错误,有时是程序员故意设计的。
发生死锁的四个必要条件互斥条件不剥夺条件要求和条件循环等待条件;
互斥条件:
只有争夺必须排他地使用的资源才会导致死锁
不剥夺条件:
流程获得的资源在未使用之前,其他流程不能强制夺走,只能自主释放;
要求和保留条件:
进程至少保存一个资源,但是提出新的资源要求,该资源被其他进程占有时,要求进程被屏蔽,但对自己现有的资源却置之不理;
循环等待条件:
存在进程资源循环等待链,链中的每个进程同时请求下一个进程获取的资源。
何时会发生死锁,发生不可剥夺资源的不合理分配,可能会导致死锁。
与系统资源的冲突:
各进程对不可剥夺的资源的竞争可能会引起死锁
进程的进度顺序不正确:
请求和释放资源的顺序不正确可能会导致死锁
如果信号量使用错误,就会发生死锁。
死锁的处理策略;
预防死锁:
破坏死锁所产生的四个必要条件中的一个或多个;
避免死锁:
通过某种方式防止系统进入不安全状态,避免死锁;
检测和解除死锁:
虽然可以接受死锁的发生,但是操作系统的责任是检测死锁并采取措施消除死锁。
死锁的预防
破坏排他条件:将只能排他使用的资源改造为允许共享使用SPOOLing技术等时,系统不会出现死锁状态。
缺点:并不是所有的资源都可以改造成共享资源,为了系统的安全,很多地方都要保护这种互斥性。
不剥夺条件:方案1 :
如果某个进程请求新资源无法满足,它必须立即释放所有保留的资源,并在以后需要时重新申请。 这意味着,即使一些资源尚未使用,也需要积极释放,破坏不可剥夺的条件。
方案2 :
当某个进程所需资源被其他进程占用时,操作系统可以协同工作,强制剥夺所需资源;
这种方式一般需要考虑各进程的优先级,剥夺调度方式是将CPU强制剥夺给优先级更高的进程使用;
坏处:
实现很复杂;
由于释放获取的资源可能会导致前一阶段的工作无效,因此此方法一般仅适用于易于保存和恢复的资源,如PCB。
重复的申请和资源释放会增加系统开销,降低系统吞吐量
根据方案1,如果在一个进程中得不到资源,则会释放所有资源,如果继续这样进行,可能会发生进程饥饿。
破坏要求和保持条件采用静态分配方法:
也就是说,进程请求上次执行所需的所有资源,在该资源未得到满足之前不开始执行。 在执行之后,这些资源总是其所有者,且该过程不再要求其它资源。
坏处:
一些资源可能会在短时间内使用,但该进程保留了所有资源,资源利用率较低
另一个进程可能会陷入饥饿。
破坏循环等待条件的顺序资源分配法:
对系统中的资源进行编号,规定每个进程必须按照编号的递增顺序请求资源,一次性申请完同类资源(相同编号的资源)。
只有当一个进程占用了小号码的资源时,才有资格申请更大号码的资源。 已经拥有大号码资源的进程,反而不能申请小号码资源。 因此,不会发生循环等待。
坏处:
添加新设备很不方便,因为可能会重新分配所有号码。
进程实际使用资源的顺序可能与编号的增加顺序不一致,从而导致资源浪费。
必须按规定的程序申请资源,用户编程很麻烦
避免死锁银行家算法。
安全序列:
如果系统按此顺序分配资源,则意味着每个进程都将成功完成。
如果能找到安全的序列,系统就处于安全状态。
在分配资源之前,必须确保分配后的安全性。
在分配资源后,如果系统找不到安全序列,系统可能会变得不安,之后所有进程都可能无法正常运行。 当然,如果有提前返还部分资源的过程,系统也有可能再次回到安全状态。
如果系统处于安全状态,则不会发生死锁; 如果系统进入不安全状态,可能会发生死锁。 发生死锁时,系统一定会处于不安全的状态。
银行家算法的核心思想:
当进程踢出资源申请时,会提前判断此次分配是否会使系统陷入不安全状态,如果可能,会不按时响应此次请求,让其先阻塞等待;
银行家算法步骤:
> 检查此次申请是否超过了之前声明的最大需求数;检查此时系统剩余的可用资源是否还能满足这次请求;
试探着分配,更改各数据结构;
用安全性算法检查此次分配是否会导致系统进入不安全状态;
安全性算法步骤:
检查当前剩余可用资源是否能满足某个进程的最大需求,如果可以,就把该进程加入安全序列,并把该进程持有的资源全部回收;
不断重复上述过程,看系统是否能让所有进程都加入安全序列。
死锁检测算法:用于检测系统状态,以确定系统中是否发生了死锁;
死锁接触算法:当认定系统中已经发生了死锁,利用该算法可将系统从死锁状态中解脱出来;
资源分配图:
用资源分配图这种图数据结构来表达资源的请求和分配信息。
资源分配图数据结构:
进程结点:对应一个进程;
资源结点:对应一类资源,一类资源可能有多个;
进程结点 -> 资源结点:请求边,表示进程想申请几个资源;
资源结点 -> 进程结点:分配边,表示已经为进程分配了几个资源;
不阻塞进程:
是指其申请的资源数还是足够的 的进程;
可完全简化的:
在资源分配图中,找不既不阻塞又不是孤点的进程P1,消除他的所有请求边和分配变,使之成为孤点;
进程P1梭释放的资源,唤醒其它的进程,按照上述步骤再次排除是否是孤点。
经过一系列简化后,若能消除图中所有的边,则称该图是可完全简化的。
死锁检测算法:
依次消除与不阻塞进程相连的边,直到无边可消;
死锁定理:
如果某时刻系统的资源分配图是不可完全简化的,那么此时系统死锁。
死锁的进程:
在资源分配图简化后,还连着边的进程就是死锁进程。
可完全简化的图,则一定没有发生死锁;如果最终不能消除所有边,就一定发生了死锁;
死锁的解除一旦检测出死锁,就应该立即解除。
解除死锁的主要方法有:
资源剥夺法:挂起某些死锁的进程,并抢占它的资源,将这些资源分配给其他死锁的进程;但应防止被挂起的进程长时间得不到资源而饥饿;撤销进程法(终止进程法):
强制撤销部分、甚至全部进程,并剥夺这些进程的资源;实现简单,但付出的代价可能会很大,因为有些进程可能已经快运行完了,结果被终止了,还得重头再来;进程回退法:
让一个或多个死锁进程回退到足以避免死锁的地步;这就要求操作系统要记录进程的历史信息,设置还原点;
如何决定对哪个进程动手呢:
进程优先级;
进程已经执行了多长时间;
进程还有多久能完成;
进程已经使用了多少资源;
进程是交互式的还是批处理式的;