一. 基础概念
死锁的定义
在多道程序系统中,由于进程的并发执行,提升了系统效率,但是多个进程并发执行带来新的问题——死锁。
- 死锁:由于多个进程因竞争资源而造成的一种僵局(互相等待对方手里的资源),使得各个进程都被阻塞。若无外力干涉,这些进程都无法向前推进。
- 例如:某计算机系统只有一台打印机和一台输入设备,进程 P1 正在占用打印机,进程 P2 正在占用输入设备。两个进都提出请求需要使用对方手中的资源,则这两个进程将无休止等待,陷入死锁状态。
死锁与饥饿
- 死锁原因:一组进程内每个进程都在等待一个事件,该事件只可能由组内另一个进程产生。
- 饥饿原因:进程在信号量内无穷等待。
- 当系统中有多个进程同时申。请某类资源,由分配策略确定资源分配次序,有的分配策略不能保证等待时间的上界存在。这种情况即使未发生死锁,某些进程需要长时间等待。当等待时间给进程带来明显影响时候,就发生“饥饿”现象,甚至最终“饿死”。
- 饥饿不表示一定死锁,但至少有一个进程的执行被无限期推迟。
- 相同点:都是进程无法顺利向前推进的现象。
- 差别
- 发生饥饿的进程可能只有一个;而发生死锁现象的进程 ≥2 个。
- 发生饥饿的进程可以处于阻塞态或就绪态(长期得不到 CPU,如 SJF 算法的问题)。
- 发生死锁的进程必定处于阻塞态。
- 死锁,饥饿与死循环
死锁产生原因
- 系统资源的竞争
- 由于不可剥夺资源(如磁带机,打印机等)数量有限,不能满足多个进程的需要。
- 对于可剥夺资源(如 CPU 和主存)的竞争不会引起死锁。
- 进程推进顺序非法
- 请求和释放资源的顺序不当。
某计算机系统只有一台打印机和一台输入设备,进程 P1 正在占用打印机,进程 P2 正在占用输入设备。两个进都提出请求需要使用对方手中的资源,此时就会造成死锁。
- 信号量使用不当:进程彼此相互等待对方发来的消息,使得进程都无法向前推进。
如:进程 A 等待进程 B 发来的消息,进程 B 又在等待进程 A 发来的消息。可以看出,进程 A 和 B 不是因为竞争同一资源,而是在等待对方的资源导致死锁。
死锁产生的必要条件
- 互斥条件
- 进程对分配的资源进行排他性使用,一段时间内仅允许一个进程占有。
- 此时请求资源使用的进程必须等待。
- 不可剥夺条件
- 进程获得 的资源未使用完之前,不能被其他进程夺走,只能由该进程自己主动释放。
- 请求并保持条件
- 进程已经持有一个资源,但是又提出了新的资源请求,而该资源被其他进程占有。
- 此时请求进程被阻塞,但是不放弃自己已经持有的资源。
- 循环等待条件
- 存在一种进程资源的循环等待链,链中每个进程已获得的资源同时被链中下一个进程请求。如下图:
资源分配圈:循环等待 VS 死锁
参考上图所示资源分配圈
- 循环等待:资源分配圈中 Pn 进程需要的资源不必须只能由 P(n+1) 进程来提供,也可以获得圈外其他同类资源。【即系统中同类资源数量>1】
- 死锁:资源分配圈中 Pn 进程需要的资源必须只能由 P(n+1) 进程来提供,要求更严格。【系统中同类资源数量=1】
死锁处理策略
- 死锁预防:设置某些限制条件,破坏产生死锁的四个必要条件中一个或多个。
- 避免死锁:资源动态分配过程中,使用某种方法防止系统进入不安全状态。
- 死锁的检测及解除:不采取限制措施,允许死锁的发生。通过检测机构检测出死锁发生,然后采取某种措施解除死锁。
- 对比:
二. 死锁预防
预防死锁,只需要破坏产生死锁的四个必要条件之一即可。
破坏互斥条件
- 原理:将只能互斥访问的资源改造为允许共享使用,这样就可以避免系统进入死锁。
如:操作系统可以使用 SPOOLing 技术将独立设备改造为共享设备。
- 弊端:有些资源(如打印机等临界资源)只能互斥使用,因此该方法不太可行;而且,为了 系统安全,很多时候必须保护互斥性。
破坏不可剥夺条件
- 原理:当进程占有某些资源,但是请求某些新的资源不能得到满足时候,必须放弃已占有资源,待以后重新申请。
- 弊端:
- 实现起来比较复杂。
- 释放已获得资源可能造成前一段工作失效。
因此 常用于 状态易于保存和恢复的资源,如:CPU 的寄存器及内存资源。
一般不能用于打印机之类的资源:反复申请和释放资源既影响进程推进速度,又增加系统开销,进而降低系统吞吐量。
破坏请求并保持条件
- 采用预先静态分配法:进程运行前一次申请完它所需要的全部资源。资源未被满足之前,不让它投入运行,进程运行期间,不提出资源分配请求。【从而破坏”请求“条件;等待期间不占用任何资源,破坏”保持“条件。】优点:实现简单。
- 优点:实现简单。
- 缺点:系统资源被严重浪费,有些资源可能仅在运行初期或快结束才使用,而且还会导致“饥饿”现象:个别资源长期被其他进程占用,导致等待该资源的进程长时间得不到运行。
- 允许进程只获得运行初期所需资源后,即可开始运行。运行过程中逐步释放分配给自己且已使用完毕的全部资源后,才能请求新的资源。
- 特点:改进了方法一缺点。
破坏循环等待条件
- 方法:顺序资源分配法:给系统中各类资源编号,规定每个进程必须按编号递增顺序请求资源,同类资源(编号相同)一次申请完。
一个进程只有在已经占有小编号的资源时,才有资格申请更大编号的资源。已有大编号资源,不能逆向请求小编号资源,避免了循环等待。
- 缺点:
- 编号必须相对稳定,不便于增加新类型设备。
- 进程实际使用资源的顺序可能与编号次序不一样,造成资源浪费。
- 必须按规定次序申请资源,给用户编程带来麻烦。
三. 死锁的避免
避免死锁属于事先预防策略,允许进程动态申请资源,在每次分配资源前,分析此次资源分配结果是否会带来死锁风险;只有在不产生死锁的前提下,系统才会分配资源。否则让进程等待。
限制条件较弱,有利于获得较好的系统性能。
系统安全状态
- 安全状态:是指系统能按照某种进程推进顺序(P1,P2…Pn)为每个进程 Pi 分配所需资源,直至满足每个进程对资源的最大需求,使得每个进程都可顺利完成。此时称 P1,P2,P3…Pn 为安全序列(可能有多个)。若系统无法找到一个安全序列,则称系统处于不安全状态。
- 如果系统处于安全状态,则一定不会发生死锁;反之有可能发生死锁。
银行家算法
- 核心思想:在每次分配资源前,分析此次资源分配结果是否会带来死锁风险,由此决定是否分配资源**。**
四. 死锁检测和解除
死锁避免 VS 死锁检测
- 死锁避免:需要保证进程运行过程一直不出现死锁;需要知道进程从开始到结束的所有资源请求。
- 死锁检测:检测某个时刻是否发生死锁,不需要知道进程整个生命周期的资源请求,只需要知道对应时刻的资源请求。
死锁检测
死锁解除
- 资源剥夺法
- 挂起某些死锁进程,并抢占它的资源,将这些资源分配给其他死锁进程。
- 应防止挂起时间过长导致长时间处于资源匮乏状态。
资源分配图中,用死锁定理简化后,还有边相连的进程就是死锁进程。
撤销进程法
- 强制撤销部分、甚至全部死锁进程并剥夺进程的资源。
- 撤销原则
- 按进程优先级
- 按撤销进程代价高低
- 实现简单,付出的代价可能很大。【有些进程可能已经接近结束,一旦终止,以后需要从头再来】
- 进程回退法:让一个或多个死锁进程回退到足以避免死锁的地步。
- 回退时自愿释放资源 而并非剥夺。
- 要求系统保持进程的历史信息,设置还原点。