操 作 系 统 习 题 课 习 题 一 : 多 道 程 序 1
习 题 一 : 多 道 程 序 第 (1) 问 :Turn around 时 间 作 业 从 投 入 到 完 成 所 需 时 间 J1:110ms J2:90ms J3:110ms 第 (2)(3) 问 : 计 算 CPU 和 I/O 设 备 的 利 用 率 CPU 的 利 用 率 为 :(110-30)/110=72.7% 的 利 用 率 为 :(110-30)/110=72.7% 的 利 用 率 为 :(110-20)/110=81.8% 习 题 一 : 课 堂 练 习 (2013 阿 里 招 聘 试 题 ) 假 设 在 内 存 中 有 P1 P2 P3 三 道 程 序, 并 按 照 P1 P2 P3 的 优 先 次 序 运 行, 其 内 部 计 算 和 I/O 操 作 时 间 由 下 给 出 : P1: 计 算 60ms I/O 操 作 80ms 计 算 20ms P2: 计 算 120ms I/O 操 作 40ms 计 算 40ms P3: 计 算 40ms I/O 操 作 80ms 计 算 40ms 调 度 程 序 的 时 间 忽 略 不 计, 完 成 者 三 道 程 序 比 单 道 运 行 节 省 的 时 间 是 ( ) A 80ms B 120ms C 160ms D 200ms 2
习 题 一 : 课 堂 练 习 单 道 所 需 时 间 :520ms 多 道 所 需 时 间 :60+120+20+40+80+40=360ms 故 节 省 的 时 间 为 160ms 答 案 为 C 习 题 二 :CPU 调 度 3
习 题 二 :CPU 调 度 第 一 问 : 采 用 优 先 级 调 度 算 法, 其 执 行 顺 序 为 B E A C D 如 下 表 : 作 业 运 行 时 间 等 待 时 间 周 转 时 间 带 权 周 转 时 间 B 6 0 6 6/6=1 E 8 6 14 14/8=1.75 A 10 14 24 24/10=2.4 C 2 24 26 26/2=13 D 4 26 30 30/4=7.5 作 业 平 均 周 转 时 间 T=(6+14+24+26+30)/5=20 作 业 平 均 带 权 周 转 时 间 W=(1+1.75+2.4+13+7.5)/5=5.13 习 题 二 :CPU 调 度 第 二 问 : 采 用 先 来 先 服 务, 其 执 行 顺 序 为 A B C D E 如 下 表 : 作 业 运 行 时 间 等 待 时 间 周 转 时 间 带 权 周 转 时 间 A 10 0 10 10/10=1 B 6 10 16 16/6=2.66 C 2 16 18 18/2=9 D 4 18 22 22/4=5.5 E 8 22 30 30/8=3.75 作 业 平 均 周 转 时 间 T=(10+16+18+22+30)/5=19.2 作 业 平 均 带 全 周 转 时 间 W=(1+2.66+9+5.5+3.75)/5=4.38 4
习 题 二 :CPU 调 度 第 三 问 : 采 用 短 作 业 优 先 调 度 算 法, 其 执 行 顺 序 为 C D B E A 如 下 表 : 作 业 运 行 时 间 等 待 时 间 周 转 时 间 带 权 周 转 时 间 C 2 0 2 2/2=1 D 4 2 6 6/4=1.5 B 6 6 12 12/6=2 E 8 12 20 20/8=2.5 A 10 20 30 30/10=3 作 业 平 均 周 转 时 间 T=(2+6+12+20+30)/5=14 作 业 平 均 带 权 周 转 时 间 W=(1+1.5+2+2.5+3)/5=2 习 题 二 :CPU 调 度 思 考 : 通 过 计 算 时 间 片 轮 转 (t=2) 算 法 的 平 均 等 待 时 间, 周 转 时 间, 比 较 其 与 前 三 种 算 法 的 区 别 5
习 题 三 : 哲 学 家 就 餐 习 题 三 : 课 堂 练 习 京 东 掌 门 和 奶 茶 妹 妹 近 日 京 东 掌 门 证 实 了 和 奶 茶 妹 妹 的 恋 情, 京 东 依 靠 着 财 大 气 粗, 可 以 源 源 不 断 的 生 产 奶 茶, 这 样 奶 茶 妹 妹 就 可 以 尽 情 享 用 女 神 最 爱 的 奶 茶 了 可 是 京 东 的 库 存 不 给 力, 只 能 储 存 N 杯 奶 茶, 当 库 存 满 时 京 东 就 不 再 生 产 奶 茶 了, 当 没 有 库 存 时, 奶 茶 妹 妹 就 没 奶 茶 喝 了, 只 能 呵 呵 了 请 用 信 号 量 P,V(wait,signed) 操 作 实 现 京 东 掌 门 和 奶 茶 妹 妹 的 互 斥 和 同 步, 要 求 写 出 完 整 的 过 程 ; 并 指 出 所 用 信 号 量 的 含 义 和 初 值 6
习 题 三 : 课 堂 练 习 京 东 掌 门 和 奶 茶 妹 妹 信 号 量 : Semaphore empty=n; // 表 示 库 存 空 余 Semaphore full=0; // 表 示 库 存 已 满 Semaphore mutex=1; // 库 存 互 斥 信 号 京 东 奶 茶 妹 妹 generant(){ consumer(){ P(mutex); (1) P(mutex); (1) P(empty); P(full); P(mutex); (2) P(mutex); (2) generate();// 生 产 奶 茶 consume();// 喝 奶 茶 V(mutex); (2) V(mutex); (2) V(full); V(empty); V(mutex); (1) V(mutex); (1) 问 题 : 1. 如 果 库 存 是 一 个 互 斥 资 源, 京 东 掌 门 和 奶 茶 妹 妹 不 能 同 时 访 问 库 存, 该 如 何 实 现? 2. 互 斥 信 号 量 应 该 放 哪 儿? 先 同 步, 后 互 斥 习 题 三 : 课 堂 练 习 2009 年 计 算 机 考 研 题 三 个 进 程 P1 P2 P3 互 斥 使 用 一 个 包 含 N(N>0) 个 单 元 的 缓 冲 区 P1 每 次 用 produce() 生 成 一 个 正 整 数 并 用 put() 送 入 缓 冲 区 某 一 空 单 元 中 ;P2 每 次 用 getodd() 从 该 缓 冲 区 中 取 出 一 个 奇 数 并 用 countodd() 统 计 奇 数 个 数 ;P3 每 次 用 geteven() 从 该 缓 冲 区 中 取 出 一 个 偶 数 并 用 counteven() 统 计 偶 数 个 数 请 用 信 号 量 机 制 实 现 这 三 个 进 程 的 同 步 与 互 斥 活 动, 并 说 明 所 定 义 的 信 号 量 的 含 义 要 求 用 伪 代 码 描 述 7
习 题 三 : 课 堂 练 习 2009 年 计 算 机 考 研 题 同 学 们 课 下 思 考 :( 几 点 提 示 ) 1. 有 几 种 关 系?(P1 和 P2 的 奇 数 同 步 关 系,P1 和 P3 的 偶 数 同 步 关 系,P1 和 (P2,P3) 的 生 产 者 - 消 费 者 同 步 关 系,(P1,P2,P3) 的 缓 冲 区 互 斥 关 系 ) 2. 需 要 几 个 信 号 量?( 每 个 关 系 一 个 信 号 量 ) 3. 信 号 量 的 初 值 分 别 怎 么 赋 值? 习 题 三 : 课 堂 练 习 一 个 司 机 与 售 票 员 在 公 共 汽 车 上, 为 保 证 乘 客 的 安 全, 司 机 和 售 票 员 应 协 调 工 作 : 停 车 后 才 能 开 门, 关 车 门 后 才 能 行 车 用 PV 操 作 来 实 现 他 们 之 间 的 协 调 8
习 题 三 : 课 堂 练 习 一 个 司 机 与 售 票 员 信 号 量 : Semaphore s1=0;// 是 否 允 许 启 动 汽 车 Semaphore s2=0;// 是 否 允 许 开 门 司 机 driver(){ P(s1);// 请 求 启 动 汽 车 start(); drive(); stop(); V(s2);// 允 许 打 开 车 门 售 票 员 busman(){ shutdown();// 关 车 门 V(s1);// 允 许 开 车 selling();// 售 票 P(s2);// 请 求 开 门 open();// 开 车 门 discharge_or_takein();// 上 下 乘 客 习 题 三 : 课 堂 练 习 水 果 盘 当 水 果 盘 空 时, 父 亲 可 以 放 香 蕉 或 者 母 亲 可 以 放 苹 果, 但 盘 中 已 有 水 果 时, 就 不 能 放, 父 母 等 待 当 盘 中 有 香 蕉 时, 女 儿 可 吃 香 蕉, 否 则, 女 儿 等 待 ; 当 盘 中 有 苹 果 时, 儿 子 可 吃, 否 则, 儿 子 等 待 9
习 题 三 : 课 堂 练 习 水 果 盘 信 号 量 : Semaphore empty=1;// 空 盘 子 Semaphore apple=0;// 放 了 苹 果 的 盘 子 Semaphore banana=0;// 放 了 香 蕉 的 盘 子 父 亲 father(){ peelingb();// 剥 香 蕉 P(empty); set();// 放 香 蕉 V(banana);// 允 许 吃 母 亲 mother(){ peelinga();// 剥 苹 果 P(empty); set();// 放 苹 果 V(apple);// 允 许 吃 儿 子 son(){ P(apple); geta();// 拿 苹 果 V(empty); eat();// 吃 女 儿 daughter(){ P(banana); getb();// 拿 香 蕉 V(empty); eat();// 吃 习 题 三 : 课 堂 练 习 生 产 者 消 费 者 扩 展 多 缓 冲 区 一 个 从 键 盘 输 入 到 打 印 机 输 出 的 数 据 处 理 流 程 图 如 图 所 示 其 中 键 盘 输 入 进 程 通 过 缓 冲 区 bufa 把 数 绝 传 送 给 计 算 进 程, 计 算 进 程 把 处 理 结 果 通 过 bufb 传 送 给 打 印 进 程 假 设 上 述 两 个 缓 冲 区 的 大 小 分 别 为 a 和 b, 试 写 出 键 盘 输 入 进 程 计 算 进 程 及 打 印 进 程 间 的 同 步 算 法 Input Buffer A Calculate Buffer B Print out 10
习 题 三 : 课 堂 练 习 生 产 者 消 费 者 扩 展 多 缓 冲 区 信 号 量 : Semaphore emptya=a;//buffer a 的 缓 冲 区 大 小 Semaphore emptyb=b;//buffer b 的 缓 冲 区 大 小 Semaphore fulla=0;//a 缓 冲 区 已 用 数 量 Semaphore fullb=0;//b 缓 冲 区 已 用 数 量 Semaphore mutexa=1;// 访 问 buffer a 时 互 斥 Semaphore mutexb=1;// 访 问 buffer b 时 互 斥 input(){ inputdata(); 输 入 数 据 P(emptya); P(mutexa); puta();// 向 A 中 输 入 V(mutexa); V(emptya); print(){ P(fullb); P(mutexb); getb();// 从 B 中 读 入 V(mutexb); V(emptyb); printdata();// 输 出 caculate(){ P(fulla); P(mutexa); geta();// 从 A 中 读 入 V(mutexa); V(fulla); caculate();// 计 算 P(emptyb); P(mutexb); putb();// 向 B 中 输 入 V(mutextb); V(fullb); Input Buffer A Calculate Buffer B Print out 习 题 三 : 哲 学 家 吃 面 0 0 1 4 1 4 2 伪 代 码 : semaphore chopstick[5]={1;// 筷 子 信 号 量 int i;// 表 示 位 置 philosopher(int i){ think();// 思 考 p(chopstick[i]);// 申 请 右 边 的 筷 子 p(chopstick[(i+1)mod5]);// 申 请 左 边 的 筷 子 eat();// 吃 面 v(chopstick[i]);// 释 放 右 边 的 筷 子 v(chopstick[(i+1)mod5]);// 释 放 左 边 的 筷 子 3 3 2 思 考 : 五 个 哲 学 家 同 时 拿 起 右 边 的 筷 子, 会 出 现 什 么 情 况? 死 锁 11
4 习 题 三 : 哲 学 家 吃 面 0 0 1 1 4 2 3 3 2 伪 代 码 : semaphore chopstick[5]={1;// 筷 子 信 号 量 semaphore room=4;// 同 时 最 多 允 许 4 人 int i;// 表 示 位 置 philosopher(int i){ think();// 思 考 p(room); p(chopstick[i]);// 申 请 右 边 的 筷 子 p(chopstick[(i+1)mod5]);// 申 请 左 边 的 筷 子 eat();// 吃 面 v(chopstick[i]);// 释 放 右 边 的 筷 子 v(chopstick[(i+1)mod5]);// 释 放 左 边 的 筷 子 v(room);// 释 放 空 间 习 题 三 : 哲 学 家 吃 面 其 他 解 决 方 案 : 1. 仅 当 哲 学 家 的 左 右 两 支 筷 子 都 可 用 时, 才 允 许 他 拿 起 筷 子 进 餐 (AND 型 信 号 量 ) 2. 规 定 奇 数 号 的 哲 学 家 先 拿 起 他 左 边 的 筷 子, 然 后 再 去 拿 他 右 边 的 筷 子 ; 而 偶 数 号 的 哲 学 家 则 相 反 12
习 题 四 : 死 锁 问 题 习 题 四 : 死 锁 问 题 (1) 计 算 得 到 时 刻 的 资 源 分 配 表 如 下, 剩 余 单 元 数 为 150-(25+40+45)=40 此 时 40 不 小 于 进 程 请 求 的 单 元 数 25 进 程 Max Allocation Need Available 70 25 45 40 60 40 20 60 45 15 60 13
习 题 四 : 死 锁 问 题 (1) 计 算 得 到 时 刻 的 资 源 分 配 表 如 下, 剩 余 单 元 数 为 150-(25+40+45)=40 此 时 40 不 小 于 进 程 请 求 的 单 元 数 25 进 程 Max Allocation Need Available 70 25 45 15 60 40 20 60 45 15 60 25 35 习 题 四 : 死 锁 问 题 将 25 分 配 给 进 程, 还 剩 余 15 个 单 元, 将 其 分 配 给 进 程, 此 时 结 果 如 下 表, 得 到 安 全 序 列 {,,, 进 程 Max Work Need Allocation Work+Allocation Finish 60 15 15 45 60 True 60 60 20 40 100 True 70 100 45 25 125 True 60 125 35 25 150 True 14
习 题 四 : 死 锁 问 题 (2) 此 时 的 剩 余 单 元 数 150-(25+40+45)=40 此 时 40 不 小 于 进 程 请 求 的 单 元 数 35, 将 其 35 个 单 元 分 配 给 进 程, 余 下 5 个 单 元, 其 资 源 分 配 如 下,4 个 进 程 都 不 够 分 配, 找 不 到 安 全 序 列, 故 为 不 安 全 状 态 进 程 Max Allocation Need Available 70 25 45 5 60 40 20 60 45 15 50 35 15 Thanks! 15