精华内容
下载资源
问答
  • 操作系统死锁和饥饿
    2021-08-31 14:16:35

    操作系统——死锁和饥饿

    转自:https://blog.csdn.net/qq_42192693/article/details/103054682

    1、概念

    • 死锁:如果一组进程中的每一个进程都在等待由该进程中的其它进程才能引发的事件,那么该组进程是死锁的。
    • 饥饿:指系统不能保证某个进程的等待时间上界,从而使该进程长时间等待,当等待时间给进程推进和响应带来明显影响时,称发生了进程饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被饿死

    2、产生原因

    • 死锁:源于多个程序对资源的争夺,不仅对不可抢占资源进行争夺时会引起死锁,而且对可消耗资源进行争夺时,也会引起死锁。
    • 饥饿:如果一个线程因为处理器时间全部被其它线程抢走而得不到处理器运行时间,这种状态被称之为饥饿,一般是由高优先级线程吞噬所有的低优先级线程的处理器时间引起的。

    3、必要条件

    • 死锁:互斥、不可剥夺、请求与保持、循环等待
    • 饥饿:没有其产生的必要条件,随机性很强。并且饥饿可以被消除,因此也将忙等待时发生的饥饿称为活锁

    4、异同点

    • 相同:二者都是由于竞争资源而引起的
    • 不同:
      • 从进程状态考虑,死锁进程都处于等待状态,忙等待(处于运行或就绪状态)的进程并非处于等待状态,但却可能被饿死。
      • 死锁进程等待永远不会被释放资源,饿死进程等待会被释放但却不会分配给自己资源,表现为等待时限没有上界(排队等待或忙等待)。
      • 死锁一定发生了循环等待,而饿死不一定。
      • 死锁一定涉及多个进程,而饥饿或被饿死的进程可能只有一个。
      • 在饥饿的情形下,系统中至少有一个进程能正常运行,只是饥饿进程得不到执行机会。而死锁则可能会最终使整个系统陷入死锁并崩溃。

    5、举例

    • 死锁:砍树你需要一个斧子,但是斧子需要木头来做,这就发生了死锁。
    • 饥饿:排队过程中,总有人插队到你的前面,导致你一直处于排队状态,这就发生了饥饿。
    更多相关内容
  • 了解死锁饥饿产生的条件 了解死锁的解决方法 掌握利用银行家算法进行死锁避免
  • 操作系统:线程死锁饥饿、活锁

    1. 死锁

    可以认为是两个线程或进程在请求对方占有的资源。
    在这里插入图片描述

    出现以下四种情况会产生死锁:

    • 情况一:相互排斥。一个线程或进程永远占有共享资源,比如,独占该资源。
    • 情况二:循环等待。例如,进程A在等待进程B,进程B在等待进程C,而进程C又在等待进程A。
    • 情况三:部分分配。资源被部分分配,例如,进程A和B都需要访问一个文件,同时需要用到打印机,进程A得到了这个文件资源,进程B得到了打印机资源,但两个进程都不能获得全部的资源了。
    • 情况四:缺少优先权。一个进程获得了该资源但是一直不释放该资源,即使该进程处于阻塞状态。

    2. 活锁

    活锁和死锁很像似。 只是活锁的状态可以发生改变。不过虽然状态可以改变,却没有实质的进展。

    比如两个人在一个很宅的胡同里。 一次只能并排过两个人。 两人比较礼貌,都要给对方让路。 结果一起要么让到左边,要么让到右边,结果仍然是谁也过不去。 类似于原地踏步或者震荡状态。

    活锁一般是由于对死锁的不正确处理引起的。由于处于死锁中的多个线程同时采取了行动。 而避免的方法也是只让一个线程释放资源。


    3. 饿死

    一个线程在无限地等待多个线程相互传递使用并且用不会释放的资源。

    饿死(starvation) 是一个线程长时间得不到需要的资源而不能执行的现象。 有人饿死并不代表着出现了死锁。很有可能系统还能很好的进行。所以,没有出现死锁并不能就认为系统是完好的。还要保证没有出现饿死的现象。

    避免饿死就应该是采用队列的方式,保证每个人都有机会获得请求的资源。 当然实现方式可以很多个变化,比如优先级,时间片,等,都是“队列”的特殊形式



    展开全文
  • 设计一个程序,能够显示当前各哲学家的状态桌上餐具的使用情况,并能无死锁的推算出下一状态各哲学家的状态桌上餐具的使用情况。即设计一个能安排哲学家正常生活的程序。 3.2 问题描述 可能出现死锁问题,因为...
  • 高清无水印原文件下载: 链接:https://pan.baidu.com/s/1xrJgW0IeEyuyjifjCgwFHQ 提取码:3el5 注意该文件需要使用MindMaster软件打开

    在这里插入图片描述

    高清无水印原文件下载:
    链接:https://pan.baidu.com/s/1xrJgW0IeEyuyjifjCgwFHQ
    提取码:3el5
    注意该文件需要使用MindMaster软件打开

    展开全文
  • 第五章 死锁饥饿;[学习目标] 1.掌握死锁的定义,死锁的条件死锁的处理以及处理死锁的算法银行家算法 2.理解资源分配图 [学习要点] 本章的重点在于掌握死锁的处理方法会用银行家算法计算是否发生死锁;第五章 死锁与...
  • 并发处理中需要解决两个问题,死锁和饥饿。处理死锁问题又三种常用方法:预防、检测、避免。

    一、概述

    并发处理中需要解决两个问题,死锁和饥饿。
    处理死锁问题又三种常用方法:预防、检测、避免

    二、死锁原理

    死锁:一组相互竞争系统资源或进行通信的进程间的 “永久” 阻塞。

    所有死锁都涉及 两个 / 多个 进程之间对资源需求的冲突。
    生活中的死锁
    我们使用 联合进程图(joint progress diagram) 来表示两个进程竞争两个资源的进展情况。

    在下图中,X轴表示P的进展,Y轴表示Q的执行进展,因此两个进程的共同进展由从原点开始,到东北方向的前进路径表示。

    图中显示了 P 和 Q 都请求 资源A、资源B、资源A和B 的区域,假定每个进程需要对资源进行互斥访问控制,有如下六条路径:

    1. Q 获得 B,然后获得 A;再后释放 B 和 A;当 P 恢复执行时,它可获得全部资源。
    2. Q 获得 B,然后获得 A;P 执行 并阻塞在对 A 的请求上;Q 释放 B 和 A;当 P 恢复执行时,它可以获得全部资源
    3. Q 获得 B,P 获得 A;继续执行时,Q 阻塞在 A 上、P 阻塞在 B 上,死锁不可避免
    4. P 获得 A,Q 获得 B;继续执行时,Q 阻塞在 A 上、P 阻塞在 B 上,死锁不可避免
    5. P 获得 A,然后获得 B;Q 执行 并阻塞在对 B 的请求上;P 释放 A 和 B;当 Q 恢复执行时,它可以获得全部资源
    6. P 获得 A,然后获得 B;再后释放 A 和 B;当 Q 恢复执行时,它可获得全部资源。

    图中灰色阴影区域称为 敏感区域(fatal region),执行路径进入敏感区域,死锁将不可避免。

    联合进程图 — 死锁

    1. 资源分类

    资源通常分为两类:可重用资源、可消耗资源。

    ① 可重用资源

    可重用资源:一次进攻一个进程安全使用且不因使用而耗尽的资源。进程得到并使用后,释放资源供其他进程再次使用。

    举例:处理器、I/O通道、内存&外存 等硬件资源,设备、文件、数据库、信号量等数据结构。

    ② 可消耗资源

    可消耗资源:可被创建(生产)、销毁(消耗)的资源。某种类型可消耗资源的数量通常没有限制,无阻塞生产进程可以创建任意数量的这类资源,为一次性使用资源。

    举例:中断、信号、消息、I/O缓存区信息。

    2. 资源分配图

    表征进程资源分配的 有效工具 是 资源分配图(resource allocation graph),它是有向图,说明了系统资源、进程状态,其中每个资源、进程用节点表示,圆点表示资源的一个示例,一个资源可拥有多个实例。(I/O设备有多个资源实例,它由操作系统中的资源分配模块分配。)
    资源分配图
    下图是一个死锁的例子(对应开头的小汽车):
    死锁实例

    3. 条件

    必要条件(死锁可能性):

    • 互斥
      一次只有一个进程可以使用资一个资源
    • 占有且等待
      一个进程等待其他进程时,继续占有已分配资源
    • 不可抢占
      不能强行抢占进程已占有资源

    充分条件(死锁存在性):

    • 循环等待
      存在闭合的进程链,每个进程至少占有此链中下一个进程所需资源。

    三、死锁预防

    死锁预防(deadlock prevention)策略是试图设计一种系统来排除发生死锁的可能性。

    死锁预防两类方法:

    • 间接预防:防止三个必要条件发生(互斥、占有且等待、不可抢占)
    • 直接预防:防止一个充分条件发生(循环等待)

    互斥:
    若要对资源进行互斥访问,操作系统需支持互斥。如某些文件支持多个读访问,但允许互斥的写访问,有可能会在请求写权限时发生死锁。

    占有且等待:
    可以要求进程一次性请求所有资源,并阻塞这个进程直至所有请求满足。该方法存在三个方面的低效性:

    • 不利己: 一个进程可能被阻塞很长时间,以等待满足其所有的资源请求,实际上只要有部分资源,就可先继续执行一部分。
    • 不利他: 分配给一个进程的资源可能会在相当一段时间内不会被进程使用,而其他进程也无法使用。
    • 未知性: 进程可能实现并不知道它需要的所有资源。

    不可抢占:

    • 占有某资源的一个进程进一步申请资源时,若被拒绝则必须释放最初占有资源,必要时才可再次申请。
    • 一个进程请求被另一个进程占有的资源时,操作系统可以抢占并要求另一个进程释放资源,这取决于进程优先级是否不同。

    循环等待:
    循环等待条件可通过定义资源的线性顺序预防:若进程已分配了R类型的资源,则其接下来请求的资源只能是哪些排在R类型之后的资源,但该方法可能较为低效。(证明:假设进程A、B死锁,原因:A 获得 资源Ri 并请求 资源Rj,而 B 获得 资源Rj 并请求 资源Ri,则需 i < j 且 j < i,无法成立)

    四、死锁避免

    死锁避免(deadlock avoidance)与死锁预防差距很小,它允许三个必要条件,而通过明智地选择保证永远不会到达死锁点。

    死锁避免的两种方法:

    • 若一个进程的请求会导致死锁,则不启动进程
    • 若一个进程增加的资源请求会导致死锁,则不允许这一资源分配

    1. 进程启动拒绝

    考虑一个有 n 个进程和 m 种不同类型资源的系统,定义以下向量、矩阵:
    资源请求、分配的向量、矩阵
    从中可以看出以下关系成立:

    1. R j = V j + ∑ i = 1 N A j R_j = V_j + \sum_{\mathclap{i=1}}^{N} A_j Rj=Vj+i=1NAj
      对所有j,所有资源要么可用,要么已被分配

    2. C i j ≤ R i C_{ij} ≤ R_i CijRi
      对所有i,j,任何一个进程对任何一种资源都不会超过这个进程最初声明这种资源的总量

    3. A i j ≤ C i j A_{ij} ≤ C_{ij} AijCij
      对所有i,j,分配给任何一个进程的任何一个资源都不会超过这个进程最初声明的此资源的最大请求量

    所以,死锁避免策略如下:
    若一个新进程的资源需求会导致死锁,则拒绝启动这个新进程,即只有
    R j ≥ C ( n + 1 ) j + ∑ C i j R_j ≥ C_{(n+1)j} + \sum C_{ij} RjC(n+1)j+Cij
    (满足所有进程的 最大请求量 + 新的进程请求 时)才会启动一个新进程 Pn+1,该策略并非最优,它包含最坏情况:所有进程同时发出最大请求。

    2. 资源分配拒绝

    资源分配拒绝策略,又称为 银行家算法(banker algorithm),它需要定义状态、安全状态的概念。

    考虑一个系统,它有固定数量的进程和固定数量的资源,任何时候一个进程可能分配到 0个/多个资源,因此状态包含上一小节定义的两个向量 Resource、Available 及两个矩阵 Claim、Allocation。

    • 安全状态(safe state) :至少有一个资源分配序列不会导致死锁(所有进程都能运行直至结束)
    • 不安全状态(unsafe state) :非安全的一个状态,不安全状态不一定导致死锁

    在当前资源情况下,可用资源应满足当前的分配情况和任何一个请求的最大需求,即:
    C i j − A i j ≤ V j C_{ij}-A_{ij}≤V_{j} CijAijVj
    即系统在进行资源分配之前,应先计算此次分配资源的安全性,若此次分配不会导致系统进入不安全状态,则将资源分配给线程,否则进程等待。死锁避免策略能保证系统中的进程、资源总处于安全状态。

    安全状态确定:
    在下图中,针对P1,我们无法分配任何资源,但我们可以给P2分配一个R3单元,这样P2就拥有了所需的最大资源,从而可以运行到结束。此后,其持有的所有资源回到可用资源池。依次为P1、P3、P4分配资源,所有进程运行结束,此时定义状态为安全状态。
    安全状态

    不安全状态确定:
    在下图中,假设P1请求另外一个R1和R3单元,若同意该请求,则到达第②步,该状态不安全(每个进程至少需要一个额外的R1单元,但现在没有一个可用的R1单元),因此P1将阻塞等待。此时,并不处于死锁状态,它仅有死锁的可能,若P1运行后先行释放一个R1和一个R3单元,后来再次需要,系统将到达安全状态。

    因此死锁避免策略,不准确地预测死锁,而是保证其永远不会出现。
    不安全状态


    死锁避免:

    优点:

    • 无需抢占、回滚,限制较少

    限制:

    • 必须事先声明每个进程请求最大资源
    • 所讨论的进程必须无关,即执行顺序无同步要求限制
    • 分配的资源数量必须固定
    • 占有资源,进程不能退出

    五、死锁检测

    死锁检测(deadlock detection):通过限制访问资源在进程上加以约束来解决死锁问题。只要有可能,就给进程分配所请求的资源,操作系统周期性的执行算法检测循环等待条件。

    1. 死锁检测算法

    死锁检测算法使用了上节定义的 Allocation矩阵、Available 向量,此外还定义了一个请求矩阵Q,其中 Qij 表示 进程i 请求的 j类资源 的数量,它主要是标记为死锁进程的过程。最初,所有进程都是未标记的,执行以下步骤:

    1. 标记 Allocation 矩阵种 一行全为0的进程
    2. 初始化一个临时向量W,令其等于 Available 向量
    3. 查找下标i,对所有的1 ≤ k≤ m, Qik ≤ Wk,若找不到这样的行,终止算法
    4. 若找到这样的行,标记进程i,并把 Allocation 矩阵中相应行加到 W 中,即对所有的 1 ≤ k≤ m, 令Wk = Wk + Aik

    我们举例描述该算法:

    • 由于 P4 没有已分配资源,标记 P4
    • 令 W = (0 0 0 0 1)
    • 进程 P3 的请求小于等于W,因此标记 P3,并令 W = W + (0 0 0 0 1) = (0 0 0 1 0)
    • 不存在其他未标记进程在 Q 中的行小于等于 W,因此终止算法。
      算法结果 P1 和 P2 未标记,表明这两个进程是死锁的。
      死锁按测

    2. 恢复

    检测到死锁,需要某种策略进行恢复(按复杂度递增):

    1. 取消所有的死锁进程。
    2. 把每个死锁进程回滚到前面定义的某些检查点,并重新启动所有进程。
      此时要求构建回滚、重启机制,再次死锁风险仍旧存在,但因并发的不确定性,一般不会出现。
    3. 连续取消死锁进程直至不在存在死锁。
      所取消进程的顺序应基于某种最小代价原则,在每次取消后,再次调用检测算法,测试是否仍存在死锁。
    4. 连续抢占资源直至不在出现死锁。
      类似第3种策略,每次抢占后重新调用检测算法,被抢占资源的进程需回滚到获得资源前的状态。

    策略3/4 可选择原则如下:

    • 目前为止消耗的处理器时间最少
    • 目前为止产生的输出最小
    • 预计剩下的时间最长
    • 目前为止分配的资源总量最小
    • 优先级最低

    六、综合的死锁策略

    解决死锁各种策略都有优缺点,所以我们在不同的情况下使用不同的策略:

    • 把资源分成几组不同的资源类
    • 为预防在资源类之间由于循环等待产生死锁,可使用前面定义的线性排序策略
    • 在一个资源类中使用最合适的算法

    常见资源类:

    • 可交换空间:进程交换所用外存中的存储块
    • 进程资源:可分配设备(如磁带设备、文件)
    • 内存:可按 页/段 分配给进程
    • 内部资源:诸如 I/O 通道

    可采用的策略:

    • 可交换空间:若知道最大存储需求,可要求一次性分配所有请求资源来预防死锁
    • 进程资源:死锁避免策略通常很有效
    • 内存:基于抢占的与方式最适合的策略,当被抢占被换至外存以解决死锁
    • 内部资源:可使用基于资源排序的预防策略
    展开全文
  • 操作系统课件:05第五章 死锁饥饿.ppt
  • 6.4.2 破坏占有等待条件 另一种破坏占有等待条件的略有不同的方案是要求当一个进程请求资源时先暂时释放其当前占用的所有资源然后再尝试一次获得所需的全部资源 6.4.3 破坏不可抢占条件 破坏关于死锁的第三个...
  • 1.死锁 1.1死锁原理
  • 操作系统-并发:死锁和饥饿

    千次阅读 2019-05-26 13:32:22
    本章介绍并发处理中需要解决的两个问题:死锁和饥饿。本章首先讨论死锁的基本原理和饥饿的相关问题;接着分析处理死锁的三种常用方法:预防、检测避免;然后考虑用于说明同步和死锁的一个经典问题;哲学家就餐问题...
  • 操作系统死锁和饥饿

    千次阅读 多人点赞 2019-11-13 18:17:47
    饥饿:指系统不能保证某个进程的等待时间上界,从而使该进程长时间等待,当等待时间给进程推进响应带来明显影响时,称发生了进程饥饿。当饥饿到一定程度的进程所赋予的任务即使完成也不再具有实际意义时称该进程被...
  • 操作系统:05第五章 死锁饥饿.ppt
  • 1、什么是死锁 死锁,是指两个或两个以上的进程(或线程)执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用干预,他们都死等下去,也都将无法往下推进。 产生死锁的必要条件: 1、互斥条件:所谓...
  • 操作系统死锁

    2022-04-28 22:13:10
    死锁资源可抢占资源不可抢占资源资源获取死锁资源死锁的条件死锁模型鸵鸟算法死锁检测恢复每一种类型一个资源的死锁检测方式某种类型多个资源的死锁检测方式从死锁中恢复通过强占进行恢复通过回滚进行恢复杀死...
  • 1.为了解决哲学家就餐中的死锁问题,可以按顺时针方向给...2.某计算机系统中有K台打印机,由4个进程竞争使用,每个进程需要3台打印机,则系统不会产生死锁的最小K值是(     )。 编号 选项 A 8
  • 区别 死锁 饥饿 死循环 概念 各进程相互等待对方手里的资源。导致各进程都阻塞,无法向前推进的现象。...由于长期得不到想要的资源,某进程无法向前推进的现象。...操作系统分配资源的策略不合理导致5.是管理者(操...
  • 3.可看做一个软件模块,将共享的变量对于这些共享变量的操作封装起来,形成一个具有一定接口的功能模块,进程可以调用管程来实现进程级别的并发 4.管程的组成(封装):共享数据结构、对数据结构初始化的语句、一...
  • 可以把死锁定义为一组相互竞争系统资源或进行通信的进程间的永久阻塞。 死锁由三个必要条件: 互斥 占有且等待 不可抢占 循环等待 死锁预防 本质是试图设计一种系统来排除发生死锁的可能性。 互斥 这个条件不可能...
  • 死锁 ​ 一组进程中的每个进程均等待此组进程其他所占有的、因而无法得到的资源,这种现象称为死锁 死锁类型 竞争资源引起的死锁 进程间通信引起的死锁 其他条件引发的死锁 死锁产生的必要条件 资源独占条件 一个...
  • 我来说说操作系统死锁饥饿的区别辨析

    万次阅读 多人点赞 2015-04-25 22:04:42
    我觉得可以这么理解死锁和饥饿的区别,首先死锁是同步的,饥饿时异步的。也就是说,死锁可以认为是两个线程或进程同时在请求对方占有的资源,饥饿可以认为是一个线程或是进程在无限的等待另外两个或多个线程或进程...
  • 资源分配图:刻画进程请求占有资源的一个有效工具。(圆圈:进程节点;方框:资源节点;方框中的圆点:资源实例;圆圈到方框的边:资源请求边) 产生死锁的原因: 竞争资源(系统提供的资源数目<并发进程所...
  • 操作系统实验源代码(创建进程、信号量、死锁和饥饿
  • 计算机操作系统 死锁

    千次阅读 2022-04-26 00:04:37
    计算机系统中产生死锁,可能会由于竞争不可抢占资源而陷入僵局。每个人都要接入这个文件。当两个进程都尝试接入这个资源有可能导致状态出错,大家都打不开。 1.2 死锁 产生死锁有几个必要条件 1)互斥条件:进程分配...
  • 操作系统——死锁

    2021-08-31 13:55:18
    死锁产生的原因大致有两个:资源竞争程序执行顺序不当 死锁产生的必要条件 资源死锁可能出现的情况主要有 互斥条件:每个资源都被分配给了一个进程或者资源是可用的 保持等待条件:已经获取资源的...
  • 操作系统——死锁

    2021-02-02 16:43:39
    文章目录一、死锁概述二、预防死锁三、避免死锁四、死锁的检测与解除 一、死锁概述 二、预防死锁 三、避免死锁 四、死锁的检测与解除
  • 请求保持条件:进程已经保持了一个资源,但又提出新的资源请求。 不可抢占条件:进程已获得的资源在未使用之前不能被抢占。 循环等待条件:在发生死锁时,必然存在一个进程-资源循环链。即P0等待P1, P1等待P2, ......
  • 操作系统-死锁.pptx

    2022-06-22 15:50:36
    SPOOLing系统死锁示例 操作系统-死锁全文共26页,当前为第4页。 一 什么是死锁? 死锁的定义 2022/6/20 5 一组进程中,每个进程都无限等待被该组进程中另一进程所占有的资源,因而永远无法得到该资
  • 管程的目的是为了实现进程的同步互斥 管程作为一种特殊的软件模块, 有以下部分组成 局部于管程的共享数据结构说明; 对该数据结构进行操作的一组函数; 对局部于管程的共享数据设置初始值的语句; 管程需要有一个...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 13,881
精华内容 5,552
关键字:

操作系统死锁和饥饿