人教部编第四章 处理机调度学习指导材料.docx

《人教部编第四章 处理机调度学习指导材料.docx》由会员分享，可在线阅读，更多相关《人教部编第四章 处理机调度学习指导材料.docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章 处置机调理 与逝世 锁4.1 常识 点汇总1、处置机调理 级不 调理 ：选出待分配 的功课 或过程 处置机调理 ：调配 处置机 三级调理 ：初级调理 功课 调理 、中级调理 内存对调 、初级 调理 过程 调理 2、功课 形态 功课 形态分为四种：提交、后备、履行 跟 实现 。 功课 形态变迁图： 图4-1 功课 形态及变迁3、功课 调理 跟 调理 的功用 . 功课 调理 的义务 后备形态 履行 形态 履行 形态 实现 形态 功课 调理 的功用 记载零碎中各个功课 的状况 依照某种调理 算法从后备功课 行列 中抉择 功课 为选中的功课 调配 内存跟 外设等资本 为选中的功课 树破 响应

2、的过程 功课 终了落后 展善后处置任务 4、过程 调理 跟 调理 的功用 1. 过程 调理 ：后备形态 履行 形态 2. 过程 调理 机遇：义务实现 后、等候资本 时、运转到时了、发觉 重调标记 3. 过程 调理 的功用：保管现场、抉择 过程 、规复 现场5、两级调理 模子 功课 调理 跟 过程 调理 的区不功课 调理 微不雅 调理 为过程 运动 做预备 ，即有取得处置机的资历 调理 次数有的零碎不设功课 调理 过程 调理 微不雅 调理 使过程 运动 起来，即调配 失掉了处置机 调理 频率高过程 调理 必弗成 少 6、评估 调理 算法的目标 调理 功用评估 准那么：CPU应用率、吞吐量、周转时

3、辰 、停当 等候时辰 跟 呼应时辰 1吞吐量：单元 时辰 内CPU实现 功课 的数目 2周转时辰 ： 1) 周转时辰 =实现 时辰提交时辰 2) 均匀周转时辰 =周转时辰 n 3) 带权周转时辰 =周转时辰 实践运转时辰 4) 均匀带权周转时辰 =带权周转时辰 n7、功课 与过程 调理 算法 1 先来先效劳FCFS调理 算法的实现 思维 ：按功课 过程 到来的先后次第进展调理 ，即先来的先失掉运转。 用于功课 调理 ：从功课 对列定时 辰 先后为序中抉择 队头的一个或多少 个功课 运转。 用于过程 调理 ：从停当 行列 中抉择 一个最进步 入该行列 的过程 投入运转。 比方 设有三个功课 ，编

4、号为1，2，3。各功课 分不对应一个过程 。各功课 顺次抵达，相差一个时辰 单元 。 图示出采纳FCFS方法 调理 时这三个功课 的履行 次序 算出各功课 的周转时辰 跟 带权周转时辰 功课 抵达时辰 运转时辰 开场时辰 实现 时辰 周转时辰 带权周转时辰 10240242412132427268.673232730289.33均匀周转时辰 T=26 均匀带权周转时辰 W=6.332时辰 片轮转RR调理 算法的实现 思维 ：零碎把一切停当 过程 按进步 先出的原那么排成一个行列 。新来的过程 加到停当 行列 末端 。每当履行 过程 调理 时，过程 调理 次序 老是 选出停当 行列 的队首过程

5、，让它在CPU上运转一个时辰 片的时辰 。事先辰 片到，发生时钟中缀，调理 次序 便停顿该过程 的运转，并把它放入停当 行列 末端 ，而后 ，把CPU分给停当 行列 的队首过程 。时辰 片：是一个小的时辰 单元 ,平日 10100ms数目 级。 比方 设四个过程 A、B、C跟 D顺次进入停当 行列 同时抵达，四个过程 分不需要 运转12、5、3跟 6个时辰 单元 。 图示RR法时辰 片q=1跟 q=4示过程 运转状况 算出各过程 的周转时辰 跟 带权周转时辰 3 优先级调理 算法的实现 思维 ： 从停当 行列 当选 出优先级最高的过程 到CPU上运转。 给每个过程 给予 一个优先级，带有最高优

6、先级的过程 开始 履行 。又分为静态优先级跟 静态优先级。静态优先级在不时地落低着处于运转态的过程 的优先级，以避免优先级高的过程 不时地履行 。1) 两种差别 的处置方法 ：非抢占式优先级法、抢占式优先级法2) 两种断定 优先级的方法 ：静态优先级、静态优先级 比方 假设 在单CPU前提 下有以下要履行 的功课 ：功课 运转时辰 优先级 1103211323414552 用履行 时辰 图描绘非侵占优先级调理 算法履行 这些功课 的状况 算出各功课 的周转时辰 跟 带权周转时辰 功课 抵达时辰 运转时辰 开场时辰 实现 时辰 周转时辰 带权周转时辰 1010010101021128191818

7、.03221113115.5435101188.054513181428均匀周转时辰 T=122 均匀带权周转时辰 W=706 4短功课 优先SJF占用CPU时辰 最短的过程 先运转。事前要估量 次序 运转的时辰 5最短残余 时辰 优先残余 运转时辰 最短的过程 开始 运转。也要事前估量 次序 运转的时辰 6最高呼应比优先HRN呼应比最高的过程 开始 履行 。呼应比=1+等候时辰 /估量 运转时辰 。该算法联合 了FCFS跟 SJF算法。7多级反应法多重行列 法差别 过程 的时辰 片差别 ；过程 采纳静态优先级；优先级与时辰 片联合 在一同，优先级越高，时辰 片越短。8战略驱动法为了保障 用户

8、间的公道9最晚时辰 限调理 该算法保障 在每个过程 必需实现 的最外时辰 限前运转完该过程 。8、逝世 锁1逝世 锁不雅 点 多个过程 轮回 等候它方占领 的资本 而有限日 地对峙 下去的场面。2发生逝世 锁的全然 缘故：资本 有限且操纵 不当。3发生逝世 锁的须要 前提 发生逝世 锁的须要 前提 ：互斥前提 、弗成 侵占前提 、占领 且请求前提 、轮回 等候前提 。假如在盘算 机零碎中同时存在 下面四个须要 前提 时，那么会发作逝世 锁。即四个前提 中有一个不存在 ，零碎就不会发作逝世 锁。4处置逝世 锁的普通办法 处置逝世 锁的三种办法：逝世 锁的防备 、避免、检测与规复 。 5逝世 锁防

9、备 的全然 思维 跟 可行的处置办法 1 逝世 锁防备 的全然 思维 ：攻破 发生逝世 锁的四个须要 前提 的一个或多少 个。2防备 逝世 锁的战略：资本 事后调配 战略、资本 有序调配 战略。 资本 事后调配 战略：攻破 占领 且请求前提 ，过程 在运转前一次性地向零碎请求它所需要 的全体 资本 ，假如所序文的全体 资本 得不到满意 ，那么不调配 任何资本 ，此过程 暂不运转。 资本 有序调配 战略：攻破 轮回 等候前提 ，把资本 事前分类编号，顺次 调配 ，使过程 在请求、占用资本 时不会形成 环路。6什么是过程 的平安序列，逝世 锁与平安序列的关联 1平安序列的界说 ：所谓零碎是平安的，

10、是指零碎中的一切过程 能够 依照某一种次第调配 资本 ，同时顺次地运转终了，这种进次序 列P1，P2，Pn确实是平安序列。2平安序列P1，P2，Pn是如此 构成 的：假设 对于 每一个过程 Pi(1in)，它需要 的附加资本 能够 被零碎中以后可用资本 加上一切过程 Pj(j0并且 一切最年夜 需要 量之跟 小于m+n,那么该零碎是逝世 锁有关的。解 此题的考察 要点是资本 共享零碎。令每个过程 恳求共享资本 的最少量相称 ，且为x，0n号资本 。零碎也能够 规则由年夜 到小的恳求次第。(2) 顺次 调配 能够 毁坏环路等候前提 。因为 在过程 发作逝世 锁时，必定存在一个“过程 -资本 的环

11、形链。令Pi表现 第i个过程 ，Ri表现 第i个资本 ，那么，n个跟 n个资本 的过程 -资本 形链如下列图： 图4.4 过程 资本 调配 图在有环路存在，必定存在一个过程 Pi，该过程 曾经占领 了一个较年夜 编号的资本 ，并再恳求一个较小编号的资本 ，否那么轮回 无奈 存在。要扫除轮回 的发生，让Pi先恳求较小编号的资本 ，假如不克不及 满意 就禁绝 恳求较年夜 编号的。如此 一来，较小编号的资本 如用于其余 过程 ，Pi过程 请求不到，也就不克不及 请求高号资本 ，因而形成 不了轮回 ，也 就不会发生逝世 锁。例4.2.14 什么叫功课 调理 跟 过程 调理 ？下面给出的算法中，哪些合适

12、于前者，哪些合适于后者？1FCFS2LJFLongest Job First3SJF4RR5Priority解(1) 功课 调理 是处置机调理 中的初级调理 ，该调理 将依照某种算法从后备功课 中抉择 一个功课 ，将其装入内存创破 为过程 。(2) 过程 调理 是处置机调理 中的初级 调理 ，该调理 将依照某种算法从停当 行列 中中抉择 一个过程 ，让该过程 运用CPU运转次序 。(3) 合适于功课 调理 的算法有：1、2、3跟 5。(4) 合适于CPU调理 的算法有：1、4跟 5。例4.2.15 单处置机分时零碎收到了3个功课 ，功课 提交状况见下表： Job功课 提交时辰 运转长度此中 I

13、/O时辰 CPU时辰 A10.00.36小时0.18小时0.18小时B10.20.32小时0.16小时0.16小时C10.40.36小时0.18小时0.18小时现假设 ：(1) 单CPU上分时运转两道功课 ，假设 每道功课 的I /O等候时辰 皆占各自总运转时辰 的50%，那么CPU将有20%的时辰 闲暇；(2) 零碎有相称 充分 的可用资本 CPU除外供用户运用。请写出各个功课 的终了时辰 。解 在分时零碎中，过程 轮番运用CPU。每个过程 运用完一个时辰 片后就将处置机转给另一个过程 。曾经明白，每个过程 单道运转时的I /O等候时辰 皆占各自总运转时辰 的50%，假设 两个过程 分时运转

14、时那么CPU将有20%的时辰 闲暇，即，CPU为各过程 分不运转40%。如此 一来，可列出下表所示的运转状况。时辰 事情道数CPU等候各占CPU通过期 辰 功课 进度还需10.0-10.2A提交150%50%0.2A0.10.0810.2-10.4B提交220%40%0.2AB0.080.0800.0810.4-10.6C提交220%40%0.2BC0.080.0800.110.6-10.8150%50%0.2C0.10因而，3个功课 的实现 时辰 为：(1) A：10.4小时；(2) B：10.6小时；(3) C：10.8小时；例4.2.6 一个盘算 机零碎中领有 6台打印机，现有N个过程 竞争运用，每个过程 请求 两台，试咨询 ，N的值怎样 拔取 时零碎中相对不会呈现逝世 锁？ 解 此题的考察 要点是资本 竞争与逝世 锁咨询 题。曾经明白零碎中的每个过程 需要 两台打印机，那么在最坏的状况下，各过程 都占用了此中 的一台，并且 都在恳求本人所需的另一台。假如如今零碎另有 过剩 的一台，那么就能够 满意 此中 一个过程 运转终了。因而说，假如让6-1台打印机分给N个过程 ，满意 它们每人一台的话，过程 数目 N必定小于即是 5。当该过程 运转终了开释 出它所占领 的打印机后，又能够 进一步满意 其余 过程 。零碎就不会呈现逝世 锁。