操作系统---死锁相关

简介: 操作系统---死锁相关

一. 基础概念

死锁的定义

在多道程序系统中,由于进程的并发执行,提升了系统效率,但是多个进程并发执行带来新的问题——死锁。

  • 死锁:由于多个进程因竞争资源而造成的一种僵局(互相等待对方手里的资源),使得各个进程都被阻塞。若无外力干涉,这些进程都无法向前推进。
  • 例如:某计算机系统只有一台打印机和一台输入设备,进程 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 死锁检测

  • 死锁避免:需要保证进程运行过程一直不出现死锁;需要知道进程从开始到结束的所有资源请求。
  • 死锁检测:检测某个时刻是否发生死锁,不需要知道进程整个生命周期的资源请求,只需要知道对应时刻的资源请求。

死锁检测

死锁解除

  • 资源剥夺法
  • 挂起某些死锁进程,并抢占它的资源,将这些资源分配给其他死锁进程。
  • 应防止挂起时间过长导致长时间处于资源匮乏状态。

资源分配图中,用死锁定理简化后,还有边相连的进程就是死锁进程。

撤销进程法

  • 强制撤销部分、甚至全部死锁进程并剥夺进程的资源。
  • 撤销原则
  • 按进程优先级
  • 按撤销进程代价高低
  • 实现简单,付出的代价可能很大。【有些进程可能已经接近结束,一旦终止,以后需要从头再来】
  • 进程回退法:让一个或多个死锁进程回退到足以避免死锁的地步。
  • 回退时自愿释放资源 而并非剥夺。
  • 要求系统保持进程的历史信息,设置还原点

目录
相关文章
|
6月前
|
算法 安全
【操作系统】死锁处理-银行家算法
【操作系统】死锁处理-银行家算法
196 0
操作系统(3.5)--死锁概述
系统中所拥有的不可抢占性资源其数量不足以满足多个进程运行的需要,使得进程在运行过程中,会因争夺资源而陷入僵局。
89 0
操作系统:死锁资源的计算
操作系统:死锁资源的计算
1223 0
|
3月前
|
算法 安全
操作系统中的死锁
【8月更文挑战第23天】
45 0
|
3月前
|
程序员 数据库
深入剖析操作系统死锁:不可不知的四大条件!
大家好,我是小米。今天探讨操作系统中的死锁问题——两个或更多进程因争夺资源陷入相互等待的状态。死锁有四个必要条件:互斥、请求与保持、非剥夺及循环等待。解决策略包括:使用乐观锁破坏互斥条件;资源一次性分配避免请求与保持;允许资源剥夺;以及采用资源有序分配法消除循环等待。通过这些方法,可以有效预防和解决死锁,提升系统稳定性和效率。希望本文能帮助你更好地理解并处理死锁问题!
129 4
|
3月前
|
算法 安全 调度
操作系统中的死锁、饥饿和优先级反转
【8月更文挑战第23天】
102 0
|
6月前
|
安全 算法 程序员
操作系统(9)----死锁
操作系统(9)----死锁
39 1
|
6月前
|
存储 算法 安全
操作系统基础:死锁
操作系统基础:死锁
|
6月前
|
算法 安全 调度
[操作系统] 面试宝典之~死锁连环系列
[操作系统] 面试宝典之~死锁连环系列
|
6月前
能列举一个操作系统发生死锁的例子吗
能列举一个操作系统发生死锁的例子吗