操作系统之调度算法和死锁中的银行家算法习题答案

1 有三个批处理作业 第一个作业 10 00 到达 需要执行 2 小时 第二个作业在 10 10 到 达 需要执行 1 小时 第三个作业在 10 25 到达 需要执行 25 分钟 分别采用先来先服 务 短作业优先和最高响应比优先三种调度算法 各自的平均周转时间是多少 解 先来先服务 结束时间 上一个作业的结束时间 执行时间 周转时间 结束时间 到达时间 等待时间 执行时间 按到达先后 执行顺序 1 2 3 作业到达时间结束时间等待时间执行时间周转时间平均周转时间 110 0012 000m120m120m 210 1013 00110m60m170m 310 2513 25155m25m180m 156 7m 短作业优先 1 初始只有作业 1 所以先执行作业 1 结束时间是 12 00 此时有作业 2 和 3 2 作业 3 需要时间短 所以先执行 3 最后执行作业 2 作业到达时间结束时间等待时间执行时间周转时间平均周转时间 110 0012 000m120m120m 310 2512 2595m25m120m 210 1013 25135m60m195m 145m 最高响应比优先 高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间 综合了先来先服务 和最短作业优先两种算法的特点 1 10 00 只有作业 1 到达 所以先执行作业 1 2 12 00 时有作业 2 和 3 作业 2 等待时间 12 00 10 10 110m 响应比 1 110 60 2 8 作业 3 等待时间 12 00 10 25 95m 响应比 1 95 25 4 8 所以先执行作业 3 3 执行作业 2 作业到达时间结束时间等待时间执行时间周转时间平均周转时间 110 0012 000m120m120m 310 2512 2595m25m120m 210 1013 25135m60m195m 145m 2 在一单道批处理系统中 一组作业的提交时刻和运行时间如下表所示 试计算一下三种 作业调度算法的平均周转时间 T 和平均带权周转时间 W 1 先来先服务 2 短作业优先 3 高响应比优先 解 先来先服务 作业顺序 1 2 3 4 作业到达时间结束时间等待时间执行时间周转时间带权周转时间平均周转时间平均带权周转时 18 009 000m60m60m1 28 309 3030m30m60m2 39 009 4230m12m42m3 5 49 069 4836m6m42m7 51m3 375 短作业优先 作业顺序 1 8 00 只有作业 1 所以执行作业 1 2 9 00 有作业 2 和 3 作业 3 短 所以先执行 3 3 9 12 有作业 2 和 4 作业 4 短 所以先执行 4 4 执行作业 2 作业到达时间结束时间等待时间执行时间周转时间带权周转时间平均周转时间平均带权周转时 18 009 000m60m60m1 39 009 120m12m12m1 49 069 186m6m12m2 28 309 4848m30m78m2 6 40 5m1 65 高响应比优先 作业顺序 1 8 00 只有作业 1 所以执行作业 1 2 9 00 有作业 2 和 3 作业 2 等待时间 9 00 8 30 30m 响应比 1 30 30 2 作业 3 等待时间 9 00 9 00 0m 响应比 1 0 12 1 所以执行作业 2 3 9 30 有作业 3 和 4 作业 3 等待时间 9 30 9 00 30m 响应比 1 30 12 3 5 作业 4 等待时间 9 30 9 06 24m 响应比 1 24 6 5 所以执行作业 4 4 执行作业 3 作业到达时间结束时间等待时间执行时间周转时间带权周转时间平均周转时间平均带权周转时 18 009 000m60m60m1 28 309 3030m30m60m2 49 069 3624m6m30m5 39 009 4836m12m48m4 49 5m3 3 设系统中有 3 种类型的资源 A B C 和 5 个进程 P1 P2 P3 P4 P5 A 资源的数量为 17 B 资源的数量为 5 C 资源的数量为 20 在 T0 时刻系统状态表 如下表所示 系统采用银行家算法试试死锁避免策略 1 T0 时刻是否为安全状态 若是 请给出安全序列 2 在 T0 时刻若进程 P2 请求资源 0 3 4 是否能实施资源分配 为什么 3 在 2 的基础上 若进程 P4 请求资源 2 0 1 是否能实施资源分配 为什 么 4 在 3 的基础上 若进程 P1 请求资源 0 2 0 是否能实施资源分配 为什 么 解 现有资源 E 17 5 20 可用资源 A 2 3 3 所需资源进程 ABC P1347 P2134 P3006 P4221 P5110 1 A 满足 P4 P4 结束 A 4 3 7 A 满足 P5 P5 结束 A 7 4 11 A 满足 P2 P2 结束 A 11 4 13 A 满足 P3 P3 结束 A 15 4 18 A 满足 P1 P1 结束 A 17 5 20 T0 时刻是安全状态 存在安全序列 P4 P5 P2 P3 P1 2 可用资源 A 2 3 3 2 0 1 假设分配给 P4 A 0 3 2 所需资源进程 ABC P1347 P2134 P3006 P4020 P5110 存在安全序列 P4 P2 P3 P5 P1 所以可以分配资源 4 可用资源 A 0 3 2 0 2 0 能满足 P1 需求 假设分配 A 0 1 2 所需资源 进程 ABC P1327 P2134 P3006 P4020 P5110 剩余资源不能满足任意进程需求 进程将会死锁 4 某系统有 R1 R2 R3 共 3 类资源 在 T0 时刻 P1 P2 P3 和 P4 这 4 个进程对资源的占用 和需求情况见下表 此刻系统可用资源向量为 2 1 2 问题 1 将系统中各种资源总量和此刻各进程对各资源的需求数目用向量或矩阵表示出来 2 如果此时 P1 P2 均发出资源请求向量 Request 1 0 1 为了保持系统的安全性应该如 何分配资源 说明你所采用策略的原因 3 如果 2 中两个请求立刻得到满足后 系统此刻是否处于死锁状态 解 1 可用资源 A 2 1 2 资源总量 E 9 3 6 需求资源 R 024 301 202 222 2 假设资源分配给 P1 则 A 2 1 2 1 0 1 1 1 1 需求资源 R 024 301 202 121 A 不能满足任何进程的需求 所以进程死锁 所以拒绝 P1 的请求 假设资源分配给 P2 则 A 2 1 2 1 0 1 1 1 1 需求资源 R 024 301 101 222 A 满足 P2 要求 P2 完成 A 6 2 3 存在安全序列 P2 P1 P3 P4 所以答应 P2 的请求 3 假设资源分配给 P1 则 A 2 1 2 1 0 1 1 0 1 0 1 0 需求资源 R 024 301 101 121 系统此刻并没有立即进入死锁状态 因为这时所有进程没有提出新的资源申请 全部 进程均没有因资源请求没得到满足而进入阻塞状态 只有当进程提出资源申请且全部 进程都进入阻塞状态时 系统才处于死锁状态 5 设有 3 个进程 P Q R 它们共享 10 个同类资源 P Q R 进程的资源最 大需求量依次为 4 7 和 8 现假定它们对资源的请示序列如下表所示 为了避免死锁 系统分配资源时采用银行家算法 如果申请资源得不到满足 进 程就转入阻塞态 根据上述信息 试描述各步骤结束时 申请资源的进程是得到满足 还是转入阻塞状态 为什么 起始状态 各进程均不拥有资源 无进程处于阻塞态 如果剩余资源即可用资源大于当前状态任何进程的需求 则进程不会死锁 且安全 序列任意 因为一旦满足某个进程的需求使其结束后 进程返还占用资源 剩余资源 不变 返还资源为 0 或增多 以此类推即可 需求资源 R 4 7 8 资源总数 E 10 也是可用资源 步骤 1 满足 P 剩余资源可使各进程运行结束 所以 P 得到 2 个资源 E 8 R 2 7 8 步骤 2 满足 Q 剩余资源可使各进程运行结束 所以 Q 得到 4 个资源 E 4 R 2 3 8 步骤 3 满足 R 剩余资源可使各进程运行结束 所以 R 得到 2 个资源 E 2 R 2 3 6 步骤 4 阻塞 Q 若答应请求