操作系统 第5章教学课件.pptx

《操作系统 第5章教学课件.pptx》由会员分享，可在线阅读，更多相关《操作系统 第5章教学课件.pptx（43页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、操作系统 第5 章教学课件第5章 死锁目录C O N T E N T S5.35.45.55.6处理死锁的策略死锁的预防死锁的避免死锁的检测和解除5.15.2死锁的概念死锁的产生5.7 饥饿死锁的概念5.15.1 死锁的概念由于临界资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而导致无法继续运行。这就产生了两个或两个以上的进程长期处于等待状态的一种特殊现象，这种现象称为死锁。死锁现象不仅出现在计算机系统中，在日常生活中也广泛存在。例如，在一条河上有一座桥，桥面很窄，只能容纳一辆汽车通行，无法让两辆汽车并行。在计算机系统中也存在类似的情况。例如，某

2、计算机系统中只有一台打印机和一台输入设备，进程P1正占用输入设备，同时又提出使用打印机的请求，但此时打印机正被进程P2占用，而P2在未释放打印机之前，又提出请求使用正被P1占用着的输入设备。死锁的产生5.25.2.1 资源分类操作系统是一个资源管理者，负责分配不同类型的资源给进程使用。现代操作系统所管理的资源类型十分丰富，并且可以从不同的角度出发对其进行分类。例如，可以把资源分为可剥夺资源和不可剥夺资源。按资源使用期限，可将资源分为可再次使用的永久资源和消耗性的临时资源。一般来说，所有的硬件资源都属于可再次使用的永久资源，它们可以被进程反复使用。不可剥夺资源是指除占用资源的进程不再需要使用该资

3、源而主动释放资源外，其他进程不得在占用进程使用资源过程中强行剥夺。在进程同步和通信中出现的消息、信号和数据也可以看做资源，它们属于消耗性的临时资源，因为类似消息这类资源，在接收进程对其处理后，消息就被撤销了，不再存在了。对永久资源和临时资源的使用都有可能导致死锁。5.2.2 死锁产生的原因死锁产生的原因之一是资源竞争。如 果 系 统 中 只 有 一 个进 程 在 运 行，所 有 资 源 为 一 个 进 程 独 享，则 不 会 出 现 死 锁现 象。当 系 统 中 有 多 个 进 程 并 发 执 行 时，若 系 统 中 的 资 源不 足 以 同 时 满 足 所 有 进 程 的 需 要，则 引 起

4、 进 程 对 资 源 的 竞争，从 而 可 能 导 致 死 锁 的 产 生。图 5-1给 出 了 两 个 进 程 竞争资源的情况。在 图 5-1中，假 定 进 程 P1和 P2分 别 申 请 到 了 资 源 A和 资 源B，现 在 进 程 P1又 提 出 使 用 资 源 B的 申 请，由 于 资 源 B已 被进 程 P2占 用，所 以 进 程 P1阻 塞；而 进 程 P2可 以 继 续 运 行，进 程 P2在 运 行 中 又 提 出 使 用 资 源 A的 申 请，由 于 资 源 A已 被进 程 P1占 用，所 以 进 程 P2阻 塞。于 是 进 程 P1、P2都 因 资 源得不到满足而进入阻塞

5、状态，两个进程发生死锁。1)操作系统的地位5.2.2 死锁产生的原因死锁产生的原因之二是进程的推进顺序不当。竞争 资 源 虽 然 可 能 导 致 死 锁，但 资 源 竞 争 并 不 等 于 死锁，只 有 在 进 程 运 行 过 程 中 请 求 和 释 放 资 源 的 顺 序不 当 时（即 进 程 的 推 进 顺 序 不 当 时），才 会 导 致 死锁。在 图 5-1中，若 进 程 P1和 P2按 照 下 列 顺 序 执 行：P1申 请 A，P1申 请 B，P1释 放 A，P1释 放 B；P2申 请 B，P2申 请 A，P2释 放 B，P2释 放 A，则 两 个 进 程 均 可 以 顺利 运 行

6、 完 成，不 会 发 生 死 锁。图 5-2中 的 路 径 给 出了 进 程 的 上 述 执 行 顺 序。类 似 的，若 两 个 进 程 按 照路 径 和 路 径 所 示 的 顺 序 推 进 也 不 会 产 生 死 锁，但按照路径所示的顺序推进则会产生死锁。1)操作系统的地位5.2.3 产生死锁的必要条件互斥条件。进程要求对所分配的资源进行排他性控制，即在一段时间内某资源仅为一个进程所占有。请求和保持条件。在等待分配新资源的同时，进程继续占有已分配到的资源。请求和保持条件又称占有且等待条件、部分分配条件。不剥夺条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行夺走，即只能由获得该资源的

7、进程自己释放。循环等待条件。存在一种进程资源的循环等待链，链中的每一个进程已获得的资源同时被链中的下一个进程所请求。3)系统调用与过程（函数）调用的区别处理死锁的策略5.35.3 处理死锁的策略目前用于处理死锁的策略主要有以下几种。忽略死锁这 种 处 理 方 式 又 称 鸵 鸟 算法，是 指 像 鸵 鸟 一 样 对 死锁 视 而 不 见。不 同 的 人 对死锁现象有不同的反应。预防死锁通 过 设 置 某 些 限 制 条 件 来破 坏 产 生 死 锁 的 4个 必 要 条件 中 的 一 个 或 几 个 来 防 止发生死锁。避免死锁在 资 源 的 动 态 分 配 过 程 中，用 某 种 方 法 防

8、 止 系 统 进 入 不安全状态，从而避免死锁。检测及解除死锁通 过 系 统 的 检 测 机 构 及 时 地 检测 出 死 锁，然 后 采 取 某 种 措 施解除死锁。死锁的预防5.45.4 死锁的预防要想防止死锁的发生，只破坏死锁产生的4个必要条件之一即可。为 了 否 定 互 斥 条 件，就 要 允 许 多 个 进 程 同 时 访 问 资源。但 是 这 会 受 到 资 源 本 身 固 有 特 性 的 限 制，有 些 资源 根 本 不 能 同 时 访 问，只 能 互 斥 访 问。由 此 看 来，企图 通 过 否 定 互 斥 条 件 防 止 死 锁 的 发 生 是 不 可 能 的。对于 临 界

9、资 源 的 访 问，不 但 不 能 否 定 互 斥，相 反 还 要 设法保证互斥，因此只能破坏死锁的另外3个必要条件。5.4.1 破坏不剥夺条件为了破坏不剥夺条件，可以制定这样的策略：一个已获得了某些资源的进程，若新的资源请求不能立即得到满足，则它必须释放所有已获得的资源，以后需要资源时再重新申请。这意味着，一个进程已获得的资源在运行过程中可以被剥夺，从而破坏了不剥夺条件。该策略实现起来比较复杂，释 放 已 获 得 资 源 可 能 造成 前 一 段 工 作 的 失 效，重 复 申 请 和 释 放 资 源 会 增 加 系统 开 销，降 低 系 统 吞 吐 量。这 种 方 法 常 用 于 状 态

10、易 于保 存 和 恢 复 的 资 源，如 CPU的 寄 存 器 及 内 存 资 源，一 般不能用于打印机之类的资源。为了破坏请求和保持条件，可以采用静态资源分配法。静态资源分配法要求进程在其运行之前一次申请它所需要的全部资源，在它的资源未满足前，不把它投入运行。一旦投入运行后，这些资源就一直归它所有，也不再提出其他资源要求，这样就可以保证系统不会发生死锁。这种方法既简单又安全，但降低了资源利用率。采用这种方法必须事先知道作业（或进程）需要的全部资源，即使有的资源只在运行后期使用，甚至有的资源在正常运行中根本不用，也不得不预先统一申请，结果使得系统资源不能充分利用。以打印机为例，一个作业可能只在

11、最后完成时才需要打印计算结果，如果在作业运行前就把打印机分配给了它，那么在作业整个执行过程中打印机基本处于闲置状态。破坏请求保持条件 发生死锁5.4.2 破坏请求和保持条件5.4.3 破坏循环等待条件为 了 破 坏 循 环 等 待 条 件，可 以 采 用 有 序 资 源 分 配 法。有 序 资 源 分 配 法 的 实 现 思 想是 将 系 统 中 的 所 有 资 源 都 按类 型 赋 予 一 个 编 号（如 打 印机 为 1，磁 带 机 为 2，等 等），要 求 每 一 个 进 程 均 严 格 按 照编 号 递 增 的 次 序 来 申 请 资 源，同类资源一次性申请完。只 要 进 程 提 出

12、申 请 分 配 资源 Ri，则 该 进 程 在 以 后 的 资源 申 请 中，只 能 申 请 资 源 编号 排 在 Ri后 面 的 资 源（i为 资源 编 号），不 能 再 申 请 资 源编 号 低 于 Ri的 资 源。对 资 源申 请 作 了 这 样 的 限 制 后，系统 中 不 会 再 出 现 几 个 进 程 对资源的请求形成环路的情况。这 种 方 法 存 在 的 主 要 问 题是 各 种 资 源 编 号 确 定 后 不 宜修 改，从 而 限 制 了 新 设 备 的增 加；尽 管 在 为 资 源 编 号 时已 考 虑 到 大 多 数 作 业 实 际 使用 这 些 资 源 的 顺 序，但 也

13、 经常 会 发 生 作 业 使 用 资 源 的 顺序 与 系 统 规 定 顺 序 不 同 的 情况，造成资源的浪费。死锁的避免5.55.5 死锁的避免预防死锁方法中所采取的几种策略，总的来说都对资源的使用施加了较强的限制条件，虽然实现起来较为简单，但严重地损害了系统的性能。在避免死锁的方法中，不对进程申请资源施加限制条件，而是检查进程的资源申请是否会导致系统进入不安全状态，只要能使系统始终处于安全状态，便可避免死锁的发生。由于该方法对进程使用资源所施加的限制条件较弱，从而可能获得较好的系统性能。5.5.1 安全状态与不安全状态在 避 免 死 锁 的 方 法 中，允 许 进 程 动 态 地 申

14、请 资 源，系 统 在 进 行 资 源 分 配 之 前，先 计 算 资 源 分 配 的安全性。若此次分配不会导致系统进入不安全状态，便将资源分配给进程，否则进程需要等待。如 果 在 某 一 时 刻，系 统 能 按 某 种 顺 序 如 来 为 每 个 进 程 分 配 其 所 需 的 资 源，直 至 最大 需 求，使 每 个 进 程 都 可 以 顺 利 运 行 完 成，则 称 此 时 的 系 统 状 态 为 安 全 状 态，称 序 列 为安全序列。若某一时刻系统中不存在一个安全序列，则称此时的系统状态为不安全状态。虽 然 并 非 所 有 不 安 全 状 态 都 是 死 锁 状 态，但 是，当 系

15、统 处 于 不 安 全 状 态 时，便 可 能 进 而 进 入 死 锁状态；反之，只要系统处于安全状态，便可避免进入死锁状态。5.5.2 银行家算法可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类资源的空闲资源数目，其初始值是系统中所配置的该类资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Available(j)=k，就表示系统中现有k个空闲的Rj类资源。分配矩阵Allocation。这是一个nm的矩阵，它定义了系统中当前已分配给每一个进程的各类资源数目。最大需求矩阵Max。这是一个nm的矩阵，它定义了系统中每一个进程对各类资源的最大需求数目。

16、如果Max(i，j)=k，表示进程Pi需要Rj类资源的最大数目为k。需求矩阵Need。这是一个nm的矩阵，它定义了系统中每一个进程还需要的各类资源数目。如果Need(i，j)=k，就表示进程Pi还需要k个Rj类资源才能完成其任务。1）银行家算法的数据结构5.5.2 银行家算法如果RequestiNeedi，则转向步骤（2）；否则出错，因为进程所需要的资源数目已超过它所宣布的最大值。系统试着把申请的资源分配给进程Pi，并修改下面数据结构中的数值。Available=Available-Requesti；Allocationi=Allocationi+Requesti；Needi=Needi-Re

17、questi;如果RequestiAvailable，则转向步骤（3）；否则，表示系统中尚无足够的资源满足进程Pi的申请，Pi必须等待。系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将视分配作废，恢复原来的资源分配状态，让进程Pi等待。2）银行家算法的实现5.5.1 安全状态与不安全状态设置两个向量。Work：表 示 系 统 可 提 供 给 进 程 继 续 运 行 的 各 类 资 源 的 空 闲 资 源 数 目。它 含 有 m个 元 素，执 行 安 全性算法开始时，Work=Available。Finish：表 示 系

18、统 是 否 有 足 够 的 资 源 分 配 给 进 程，使 之 运 行 完 成。开 始 时，Finish(i)=false；当有足够资源分配给进程Pi时，令Finish(i)=true。从进程集合中找到一个能满足下述条件的进程。Finish(i)=false;NeediWork;如找到，则执行步骤（3），否则执行步骤（4）。当进程Pi获得资源后，可顺利执行直到完成，并释放出分配给它的资源，故应执行：Work=Work+Allocationi;Finish(i)=true；然后转向步骤（2）。若所有进程的Finish(i)都为true，则表示系统处于安全状态；否则，系统处于不安全状态。系统所执行

19、的安全性算法描述如下。5.5.1 安全状态与不安全状态假 定 系 统 中 有 4个 进 程 P1、P2、P3、P4，3种 类 型 的 资 源 R1、R2、R3，数 量 分 别 为 9、3、6，在 T0时刻的资源分配情况如表5-1所示。3)银行家算法示例5.5.1 安全状态与不安全状态试问：（1）T0时刻是否安全？（2）T0时 刻 以 后，若 进 程 P2发 出 资 源 请 求 Request2(1，0，1)，系统能否将资源分配给它？（3）在 进 程 P2申 请 资 源 后，若 P1发 出 资 源 请 求 Request1(1，0，1)，系统能否将资源分配给它？（4）在 进 程 P1申 请 资

20、源 后，若 P3发 出 资 源 请 求 Request3(0，0，1)，系统能否将资源分配给它？3)银行家算法示例5.5.1 安全状态与不安全状态解：（1）T0时刻的安全性。利 用 安 全 性 算 法 对 T0时 刻 的 资 源 分 配 情 况 进 行 分 析，可 得 表 5-2所 示 的 T0时 刻 的 安 全 性 分 析，从 中得知，T0时刻存在一个安全序列P2，P1，P3，P4，故系统是安全的。3)银行家算法示例5.5.1 安全状态与不安全状态解：（2）P2请求资源。P2发出请求向量Request2(1，0，1)，系统按银行家算法进行检查。Request2(1，0，1)Need2(1，0

21、，2)。Request2(1，0，1)Available(1，1，2)。系 统 先 假 定 可 为 P2分 配 资 源，并 修 改 Available、Allocation2、Need2，由 此 形 成 的 资 源 分 配 情况如表5-3所示。3)银行家算法示例5.5.1 安全状态与不安全状态解：（2）P2请求资源。利用安全性算法检查此时系统是否安全，可得表5-4所示的安全性分析。3)银行家算法示例5.5.1 安全状态与不安全状态解：（3）P1请求资源。P1发出请求向量Request1(1，0，1)，系统按银行家算法进行检查。Request1(1，0，1)Need1(2，2，2)。Reques

22、t1(1，0，1)Available(0，1，1)，让P1等待。（4）P3请求资源。P3发出请求向量Request3(0，0，1)，系统按银行家算法进行检查。Request3(0，0，1)Need3(1，0，3)。Request3(0，0，1)Available(0，1，1)。系统先假定可为P3分配资源，并修改有关数据，得到如表5-5所示的资源分配表。3)银行家算法示例5.5.1 安全状态与不安全状态解：（3）P1请求资源。再 利 用 安 全 性 算 法 检 查 此 时 系 统 是 否 安 全。从 表 5-5中 可 以 看 出，可 用 资 源 Available(0，1，0)已不能满足任何进程

23、的需要，故系统处于不安全状态，此时系统不能分配资源。3)银行家算法示例死锁的检测和解除5.65.6.1 资源分配图检测死锁的基本思想 是 在 操 作 系 统 中保 存 资 源 的 请 求 和 分 配 信 息，利 用 某 种算 法 对 这 些 信 息 加 以 检 查，以 判 断 是 否存 在 死 锁。为 此，我 们 将 进 程 和 资 源 间的 申 请 和 分 配 关 系 描 述 成 一 个 有 向 图 资源分配图。（1）N被分成两个互斥的子集，一个是进程节点子集P=p1，p2，pn，另一个是资源节点子集R=r1，r2，rm，N=PR。在图5-3所示的例子中，P=p1，p2，R=r1，r2，N=

24、p1，p2r1，r2。（2）凡属于E中的一条边eE，都连接着P中的一个节点pi和R中的一个节点rj。e=pi，rj是资源请求边。由进程节点pi指向资源节点rj，表示进程pi请求一个单位的rj资源；e=rj，pi是资源分配边，由资源节点rj指向进程节点pi，表示把一个单位的rj资源分配给进程pi。在图5-3中有两条资源请求边和4条资源分配边。资源分配分配信息 分配关系5.6.1 资源分配图资源分配图又称进程资源图，该图由一组节点N和一组边E所构成，具有下述形式的定义和限制。在资源分配图中，找出一个既不阻塞又非孤立的进程节点pi（即从进程集合中找到一个有边与它相连，且资源申请数量小于系统中已有空闲

25、资源数量的进程）。因进程pi获得了它所需要的全部资源，它能继续运行直至完成，然后释放它所占用的所有资源。这相当于消去pi的所有请求边和分配边，使之成为孤立的节点。在图5-3中，进程p1是一个既不阻塞又非孤立的进程节点，将p1的两条分配边和一条请求边消去，便形成了图5-4（a）所示的情况。进程pi释放资源后，可以唤醒因等待这些资源而阻塞的进程，原来阻塞的进程可能变为非阻塞进程。图5-3中的进程p2原为阻塞进程，但在图5-4（a）中变成了非阻塞进程。根据步骤（1）中的简化方法，消去两条分配边和一条请求边，就形成了图5-4（b）所示的情况。重复上述过程对资源分配图进行简化，直到找不出一个既不阻塞又非

26、孤立的进程节点为止。若能消去图中所有的边，使所有进程节点都成为孤立节点，则称该图是可完全简化的，否则称该图是不可完全简化的。5.6.2 死锁的检测和解除1)死锁定理5.6.2 死锁的检测和解除死锁检测的思想是考查某一时刻系统状态是否合理，即 是 否存 在 一 组 可 以 实 现 的 系 统 状 态，能 使 所 有 进 程 都 得 到 它 们 所 申请 的 资 源 而 运 行 结 束，其 实 现 算 法 思 想 为：获 得 某 时 刻 t系 统 中各 类 可 用 资 源 的 数 目 w(t)，对 于 系 统 中 的 一 组 进 程 P1，P2，Pn，找 出 那 些 对 各 类 资 源 请 求 数

27、 目 均 小 于 系 统 现 有 的 各 类 可用 资 源 数 目 的 进 程，这 样 的 进 程 可 以 获 得 它 们 所 需 要 的 全 部 资源并运行结束。从死锁检测算法的实现思想中可以看出，死 锁 检 测 算 法 比 较复 杂，因 而 需 要 确 定 何 时 进 行 死 锁 检 测。一 种 实 现 方 法 是 每 次分 配 资 源 后 进 行 死 锁 检 测，这 样 能 尽 早 发 现 死 锁，但 会 花 费 大量 CPU时 间。另 一 种 实 现 方 法 是 定 期 检 查，如 每 隔 一 段 时 间 检查一次，或者当CPU使用率下降到某个下限值时进行检查。1)死锁定理5.6.2

28、死锁的检测和解除1)死锁定理一旦检测出系统中出现了死锁，就应将陷入死锁的进程从死锁状态中解脱出来，常用的解除死锁的方法有以下两种。资源剥夺法。当发现死锁后，从其他进程那里剥夺足够数量的资源给死锁进程，以解除死锁状态。撤销进程法。最简单的方法是撤销全部死锁进程，使系统恢复到正常状态，但这种做法付出的代价太大。另一种方法是按照某种顺序逐个撤销死锁进程，直到有足够的资源供其他未被撤销的进程使用，消除死锁状态为止。解除死锁死锁进程 消除死锁5.6.2 死锁的检测和解除3)死锁的解除饥 饿5.7和死锁类似的一种现象是饥饿。饥 饿 是 指系 统 不 能 保 证 某 个 进 程 的 等 待 时 间 上 界，

29、从而 使 该 进 程 长 时 间 等 待，当 等 待 时 间 给 进 程推 进 和 响 应 带 来 明 显 影 响 时，便 称 发 生 了 进程 饥 饿。当 饥 饿 到 一 定 程 度 的 进 程 所 赋 予 的任 务 即 使 完 成 也 不 再 具 有 实 际 意 义 时，则 称该进程被饿死。5.7 饥饿饥饿产生饥饿的主要原因是：在一个动态系统中，对于每类系统资源，操作系统需要确定一个分配策略，当多个进程同时申请某类资源时，由分配策略确定资源分配给进程的次序。有时资源分配策略可能是不公平的，即不能保证等待时间上界的存在。在这种情况下，即使系统没有发生死锁，某些进程也可能会长时间等待。饥饿的产

30、生没有必要条件，随机性很强，并且饥饿可以消除，因此也将“忙式等待”（在就绪队列中等待）时发生的饥饿称为活锁。由于饥饿和饿死与资源分配策略有关，因而解决饥饿与饿死问题可从资源分配策略的公平性考虑，确保所有进程不被忽视。操作系统资源利用 最大化5.7 饥饿1)产生饥饿的原因死锁与饿死有一些相同点，两者都是由于竞争资源而引起的，但又有明显差别。从进程状态考虑，死锁进程一直处于等待状态，忙式等待的进程并非处于等待状态，但却可能被饿死。死锁进程等待永远不会被释放的资源，饿死进程等待会被释放但却不会分配给自己的资源，表现为等待时间没有上界。死锁一定发生了循环等待，而饿死则不然。这也表明通过资源分配图可以检测死锁是否存在，但不能检测是否有进程饿死。死锁一定涉及两个及两个以上的进程，而饥饿或被饿死的进程可能只有一个。在饥饿的情形下，系统中有至少一个进程能正常运行，只是饥饿进程得不到执行机会。而死锁则可能会最终使整个系统陷入死锁而崩溃。操作系统资源利用 最大化5.7 饥饿2）死锁与饥饿的区别习题1）选择题 2）填空题3）判断题 4）解答题感 谢 观 看