操作系统课后习题1-9答案

练习 1 1 1 1 10 题解见书 1 11 有一台输入设备和一台输出设备的计算机系统上 运行有两道程序 两 道程序投入运行情况如下 程序 1 先开始运行 其运行轨迹为 计算 50ms 输出 100ms 计算 50ms 输出 100ms 结束 程序 2 后开始运行 其运行轨迹为 计算 50ms 输入 100ms 计算 100ms 结束 1 忽略调度时间 指出两道程序运行时 CPU 是否有空闲 在哪部分空 闲 指出程序 1 和程序 2 有无等待 CPU 的情况 如果有 发生在哪部分 题解 由题画出 CPU 利用图如下 由图可知 1 CPU 有空闲 在 100ms 150ms 时间段是空闲的 2 程序 1 无等待时间 而程序 2 在一开始的 0ms 50ms 时间段会等待 1 12 在计算机系统上运行三道程序 运行次序为程序 1 程序 2 程序 3 程序 1 的运行轨迹为 计算 20ms 输入 40ms 计算 10ms 程序 2 的运行轨迹为 计算 40ms 输入 30ms 计算 10ms 程序 3 的运行轨迹为 计算 60ms 输入 30ms 计算 20ms 忽略调度时间 画出三道程序运行的时间关系图 完成三道程序共花多少时间 与单道程序比较 节省了多少时间 解答 三道程序运行 完成三道程序共花 170ms 与单道程序 260ms 比较 节省了 90ms 始终按照 1 2 3 的次序 即程序 1 程序 2 程序 3 程序 1 程序 2 在 程序 3 运行前会停 10ms 等待输入完成 程序 3 如果不是按照程序 1 2 3 的次序完成则会有多种情况 1 13 在计算机系统上有两台输入 输出设备 运行两道程序 程序 1 的运行轨迹为 计算 10ms 输入 5ms 计算 5ms 输出 10ms 计算 10ms 程序 2 的运行轨迹为 输入 10ms 计算 10ms 输出 5ms 计算 5ms 输出 10ms 在顺序环境下 先执行程序 1 再执行程序 2 求总的 CPU 利用率为 多少 题解 由题画出 CPU 利用图如下 由图可知 在总共 80ms 的时间里 CPU 空闲时间为 40ms 即 CPU 利用率 40ms 80ms 100 50 1 14 一个计算机系统有足够的内存空间存放 3 道程序 这些程序有一半的时 间在空闲等待 I O 操作 问多大比例的 CPU 时间被浪费掉了 题解 由题画图如下 因为每个程序有一半的时间在等待 I O 操作 所以在并发状态下 程序 1 程 序 2 程序 3 所占时间比依次减半 如上图 所以浪费的时间比例为 1 8 练习 2 2 18 某系统中进程状态变化如图 2 22 所示 当对系统中的进程进行观察时 发现某一进程产生的一次状态变化会引起另一进程发生状态变化 1 在什么情况下 一个进程的状态变化 3 能够立即引起另一进程的状态变化 1 2 在什么情况下 一个进程的状态变化 2 能够立即引起另一进程的状态变化 1 3 进程的状态变化 3 是否可能引起另一进程的状态变化 2 进程的状态变化 3 是否可能引起另一进程的状态变化 1 解答 1 当就绪队列中还存在其它进程的情况下 一个进程的状态变化 3 能够立即 引起另一进程的状态变化 2 2 当就绪队列中还存在其它进程的情况下 一个进程从运行状态变化到就绪 状态后 另一个就绪进程能够从就绪状态变为运行状态 3 不可能 可能 2 19 分别写出相应的程序来描述图 2 23 中的前趋图 解答 S1 S2 S3 S4 S5 S6 S7 程序 S1 a x 1 S2 b a 2 S3 c a 3 S4 d b 4 S5 e b c S6 f e 5 S7 g e 6 S1 S2 S3 S4 S5 S6 S7 程序 S1 a x 1 S2 b a 2 S3 c a 3 S4 d b 4 S5 e b c S6 f d e S7 g c e 2 20 假设在一个系统中 新进程以每分钟 8 个进程的速率到达 每个进程请 求服务的平均时间为 6s 估计在一个单处理器系统中 CPU 忙的时间比率 如果新进程以每分钟 10 个进程的速率到达 每个进程请求服务的平均时间 也为 6s 估计在一个单处理器系统中 CPU 忙的时间比率 如果新进程创建以每分钟超过 10 个进程的速率到达 每个进程请求服务 的平均时间为 6s 估计在一个单处理器系统中 CPU 忙得时间比率 并解释此时 的情况 解答 因为新进程每分钟 8 个进程的速率到达 每个进程之间达到的时间间隔为 7 5s 由于每个进程占用 6s 的 CPU 时间 所以 1 分钟之内 CPU 的空间时间为 8 1 5s 12s CPU 的利用率为 48 60 0 8 即 80 因为新进程每分钟 10 个进程的速率到达 每个进程之间达到的时间间隔为 6s 由于每个进程占用 6s 的 CPU 时间 所以 1 分钟之内 CPU 的空间时间为 0s CPU 的利用率为 100 如果新进程创建以每分钟超过 10 个进程的速率到达 每个进程请求服务的 平均时间为 6s 则请求服务时间会大于 1 分钟 CPU 一直会处于繁忙 所以 CPU 忙的时间比率同样为 100 2 21 一个系统中有 4 个进程 进程 P1 要求 20s 后运行 经过 40s 后再次运 行 进程 P2 要求 25s 后运行 进程 P3 要求 35s 后运行 经过 35s 后再次运行 进程 P4 要求 60s 后运行 进程在阻塞队列等待被唤醒后运行 试创建进程的唤 醒队列 解答 进程的唤醒队列为 P1 P2 P3 P4 P1 P3 注意 经过 40s 后再次运行 表示第 1 次运行完成后再过 40s 2 22 如果线程是在用户空间线程库中实现 解释为什么当进程中的一个线程 阻塞时 进程内的所有其它线程都会阻塞 如果线程是在内核空间中实现 而进 程内的一个线程阻塞不会引起进程内的其他线程被阻塞 为什么 解答 用户级线程由用户空间运行的用户级线程库实现 当一个应用程序提交给 操作系统后 操作系统首先为该应用程序建立一个内核管理进程 然后用户级 线程库为该进程创建一个或多个用户级线程 但内核并不知道用户空间线程的 活动 内核只是以进程为单位 实现进程状态的转换 因此当进程中的一个线 程阻塞时 进程内的所有其它线程都会阻塞 如果线程是在内核空间中实现的 这些内核级线程都由内核创建和控制管 理 内核为整个进程及进程中的所有线程维护现场信息 内核的调度是在线程 的基础上进行的 因而进程的一个线程阻塞不会引起进程内的其他线程被阻塞 练习 3 3 13 证明作业调度算法中短作业优先调度算法具有最小平均等待时间 证明 假设在作业队列中等待运行的作业有 N 道 分别为 N0 N1 N2 Nn 1 它们的运行时间分别为 t0 t1 tn 1 且满足 t0 t1 0 说明任何一种作业调度顺序的作业的平均等待时间都大于按照短作业优先的作 业的平均等待时间 3 14 假设在一个处理器上执行 5 个作业 作业到达的次序和需要执行的时间分 别为 J0 75ms J1 15ms J2 5ms J3 15ms J4 45ms 假定系统中使用 FCFS 调度算法 作业 J3 的周转时间是多少 作业的平均等 待时间是多少 答 周转时间 ms 等待时间 ms J0750 J19075 J29590 J311095 J4155110 平均等待时间 ms 74 3 15 在单道批处理系统中 三个作业的提交时间分别为 10 00 10 10 10 20 需要执行时间分别为 2 小时 1 小时 0 5 小时 分别按照短作业优先调度算法和高响应比优先调度算法进行调度 比较哪一种 调度算法更好 解 1 不抢占 执行顺序为 A C B 平均周转时间 120 130 200 3 150 min 平均带劝周转时间 120 120 130 30 200 60 3 26 9 抢占 A 10 10 B 10 20 C 10 50 B 11 40 A 13 30 平均周转时间 210 90 30 3 110 min 平均带劝周转时间 210 120 90 60 30 30 3 510 360 17 12 2 响应比高者优先调度算法不会抢占 因此 只存在这样一种情况 执行顺序为 A C B 平均周转时间 120 130 200 3 150 min 平均带劝周转时间 120 120 130 30 200 60 3 26 9 所以 如果要比较哪一种算法好自然针对不抢占的情况 根据比较结果 它们的平均周转时间和平均带权周转相同 这主要是该应用正好发生了这样凑 巧的情况 3 16 假设在具有一个处理器的系统上执行下面的作业 假如采用抢占式短作业 优先调度算法 作业需要处理时间 T 和到达时间 A 分别如下 那么 IT 到达时间 A 0500 13510 22010 32555 44095 作业 1 的周转时间是多少 作业的平均等待时间是多少 答 1 执行顺序为 0 10 2 30 1 65 3 90 0 130 4 170 作业 0 的周转时间为 130 作业作业 1 1 的周转时间为 的周转时间为 5555 作业 2 的周转时间为 20 作业 3 的周转时间为 35 作业 4 的周转时间为 65 平均周转时间 305 5 61 作业 0 的等待时间为 130 50 80 作业 1 的等待时间为 55 35 20 作业 2 的等待时间为 10 10 0 作业 3 的等待时间为 35 25 10 作业 4 的等待时间为 65 40 25 3 17 假如在具有一个处理器系统中 采用优先级高者优先的进程调度算法 优 先数小代表优先级高 进程达到顺序 I 和需要处理时间 T 优先数分别如下 IT 优先级 0753 1151 254 3155 4452 1 没有优先级抢占情况下 写出进程的执行先后序列 进程 2 的周转时间是 多少 进程的平均等待时间是多少 3 有优先级抢占情况下 写出进程的执行先后序列 进程 2 的周转时间是多 少 进程的平均等待时间是多少 答 1 无抢占 执行顺序为 1 15 4 60 0 135 2 140 3 155 进程 0 的周转时间为 135 进程 1 的周转时间为 15 进程进程 2 2 的周转时间为 的周转时间为 140140 进程 3 的周转时间为 155 进程 4 的周转时间为 60 进程的平均等待时间 135 75 15 15 140 5 155 15 60 45 5 70 2 有抢占 优先级抢占同上一样 3 18 假如在具有一个处理器的系统中 采用时间片轮转调度算法 时间片大 小为 10 进程需要处理时间 T 和到达时间 A 分别如下 IT 到达时间 A 0500 13510 22010 31580 44085 写出进程的执行序列 进程 3 的周转时间是多少 进程的平均等待时间是多 少 答 进程的执行序列为 0 1 2 0 1 2 0 1 3 4 0 1 3 4 0 4 进程 0 的周转时间 T0 140 进程 1 的周转时间 T1 105 进程 2 的周转时间 T1 50 进程进程 3 3 的周转时间的周转时间 T1 T1 4040 进程 4 的周转时间 T1 75 进程的平均等待时间为 140 50 105 35 50 20 40 15 75 40 5 50 3 18 在时间片轮转调度算法中 有 n 个进程共享 CPU 1 如果进程切换的时间不可忽略 每次进程切换用去时间为 s 秒 在保 证每个进程至少每 t 秒内能够在 CPU 上轮回一次的前提下 确定时间片大 小 q 使得进程切换所造成的负载最小 2 如果 n 100 t 1 s 0 001 那么 q 的大小应该是多少 答 1 时间片大小 q t ns n 2 q 1 100 0 001 100 0 009 3 19 有一个四道作业的操作系统 若在一段时间内先后到达 6 个作业 它们的 提交时间和估计运行时间由下表给出 作业 提交时间 估计运行时间 分钟 1 8 00 60 2 8 20 35 3 8 25 20 4 8 30 25 5 8 35 5 6 8 40 10 系统采用短作业优先调度算法 作业被调度进入系统后中途不得退出 但作 业运行时可被更短的作业抢占 分别给出 6 个作业的执行时间序列 作业的 周转时间 平均周转时间 答 作业的执行顺序为 1 8 20 2 8 25 3 8 45 5 8 50 6 9 00 4 9 25 2 9 55 1 10 35 作业 1 的周转时间 155 min 作业 2 的周转时间 95 min 作业 3 的周转时间 20 min 作业 4 的周转时间 55 min 作业 5 的周转时间 15 min 作业 6 的周转时间 20 min 作业的平均周转时间为 作业的平均周转时间为 360 6 60360 6 60 3 20 在一个实时系统中有 4 个周期性事件 周期分别为 50 100 150 200ms 假设其处理时间分别需要 30 25 20 和 xms 则该系 统可调度允许的 x 值最大为多少 解 30 50 25 100 150 20 200 x 1 X 10 3 3 21 某系统的进程状态变化如图 3 23 所示 该系统的进程调度为非抢占方式 根据该状态图叙述系统的调度策略 调度效果 图 3 23 状态变化图 阻塞 运行低优先级就绪 首先选择 100ms 高优先级就绪 其次选择 100ms y 答 首先采用优先权高者优先调度算法 然后采用时间片为 100ms 的调度算 法 该调度算法如果调度效果考虑更周到的话 应该让阻塞队列上的进程唤醒 后进入低优先级就绪队列 这样能够保证优先级高的进程及时调度 优先级低 的进程能够合理的得到调度 第 4 章 4 13 如果有n个进程共享一个互斥段 1 如果每次只允许一个进程进入互斥段 2 如果每次最多允许m个进程同时进入互斥段 m10 2 V s 5 x 3 y x 2 6 else P s x 分别说明 1 2 3 4 5 6 语句之后的 x y 值为多少 答 1 x 11 y 2 2 x 11 y 2 3 x 11 y 9 4 x 11 y 9 5 x 10 y 9 6 x 10 y 8 4 18 三个进程 输入 计算 输出 它们通过两个缓冲区传递数据 如图 4 11 所示 每个缓冲区一次只能放入一条数据 写出用信号量进行同步 解 var empty1 full1 empty2 full2 semaphore 1 0 1 0 begin parbegin I begin repeat wait empty1 put to buffer1 signal full1 until false end P begin repeat wait full1 get from buffer1 signal empty1 wait empty2 put to buffer2 signal full2 until false end O begin repeat wait full2 get from buffer2 signal empty2 until false end parend end 第 5 章 5 1 什么是死锁 引起死锁的原因和必要条件是什么 死锁是指多个进程因为竞争资源造成的一种僵局 原因 并发进程对临界资源的竞争和并发进程推进顺序不当 必要条件 互斥条件 占有并请求条件 不剥夺条件 环路等待条件 5 2 比较解决死锁的方法中 那种方法最容易实现 那种方法使得资源的利用 率最高 解决死锁的方法 预防死锁 避免死锁 检测死锁 解除死锁 预防死锁是通过设计协同资源管理程序 在进程运行期间 柏怀死锁产生 的四个条件之中的任何一个 是指不成立 是最容易实现的方法 解除死锁是在发现死锁后 解除死锁 释放资源 是资源利用率最高的方 法 5 3 预防死锁的方法有哪些 破坏互斥条件 破坏占有并请求 阻止环路等待 允许剥夺 5 8 系统中有 3 个进程共享 4 个资源 每个进程每次只能申请或释放一个资源 每个进程最多需要 2 个资源 给进程是否会发生死锁 为什么 解 不会发生死锁 3 个进程共享 4 个资源 每个进程最多需要 2 个资源 总有一 个进程的请求会满足 运行并释放资源 不会形成环路等待 5 9 系统中有 20 个进程 每个进程最多使用 3 个资源 每个进程逐个申请并竞 争使用 60 个同类资源 一旦某进程获得所需要的资源 完成后立即释放全部资 源 系统是否会发生死锁 为什么 系统不会发生死锁 以最坏的情况来考虑 20 个进程都需要使用 3 个资 源 当前 每个进程都持有 2 个资源 20 2 40 都在申请第 3 个资源 60 40 20 对于剩余的 20 个资源 每个进程多会得到一个资源 不会形成环路等 待 5 10 一台计算机有 8 台打印机 被N个进程竞争使用 每个进程最多需 要 3 台 请问N为多少时 系统没有死锁的危险 说明原因 解 N 3 时 没有死锁的危险 对于 N 个进程 都持有 2 台打印机时 申请第 3 台打印机 只要有一 台的多余的打印机能被申请到 则系统就没有死锁的危险 即 N 2 1 8 得 N 3 5 115 11 考虑图考虑图 5 95 9 所示的资源分配图 哪个进程会发生死锁 所示的资源分配图 哪个进程会发生死锁 进程 P3 P4 会发生死锁 对于进程 P1 P2 进程的推进不需要等待其他进程的完成 进程 P3 P4 P3 要等 P4 完成并释放资源后方能推进 而 P4 要等到 P3 完成后 才能 结果是 P3 P4 都不能完成 形成死锁 5 125 12 假定有假定有 3 3 个人排队等候上电梯 当电梯门打开的时候 个人排队等候上电梯 当电梯门打开的时候 3 3 个人都朝门口个人都朝门口 冲去 但是门不够大 他们冲去 但是门不够大 他们 3 3 人不能同时进门 描述解决这种死锁的方法 可人不能同时进门 描述解决这种死锁的方法 可 以让以让 3 3 个人都上电梯 说明你的解决方案清除了哪个死锁的必要条件 个人都上电梯 说明你的解决方案清除了哪个死锁的必要条件 答 让 3 个人轮流进电梯 破坏了死锁发生的 4 个必要条件中的 不剥夺条件 5 13 假定一个系统具有四种资源类型 分别为 R 3 7 2 3 最大资源 需求数表如图 5 10 所示 资源分配器根据图 5 11 中的表来分配资源 这个状 态安全吗 为什么 图5 10图5 11 答 这个状态安全 存在安全执行序列 P4 P0 P1 P3 P2 6 9 如果一个分页系统能够向用户提供的逻辑地址最大为 16 页 页面大 小为 2K 内存总共有 8 个存储块 请问逻辑地址应该为多少位 内 存空间为多大 解 逻辑地址应该为 4 11 15 位 内存空间为 8 2K 16K 6 10 如果一个分页系统的页表存放在内存 1 若对内存的一次存取需要 1 2 s 请问一次页面访问的存取需 要花多少时间 2 若系统配置了联想寄存器 对快表的命中率为 70 假如查询 联想寄存器的时间忽略不计 请问实现一次页面访问的存取 时间是多少 解 1 访问一次页面的存取需要花费的时间为 2 1 2 s 2 4 s 2 实现一次页面访问的存取时间 0 3 1 2 s 1 2 s 1 56 s 6 11 如果一个分页系统逻辑地址长度为 16 位 页面大小为 4KB 第 0 1 2 页对应 10 12 14 号物理块 请问逻辑地址为 2F6AH 对应的物理地 址为多少 解 逻辑地址为 2F6AH 对应的二进制码为 0010 1111 0110 1010 页号为 2 页内偏移为 F6AH 查询页表 2 号页面对应 14 号块 所以 物理地址为 1110 1111 0110 1010 最终物理地址为 EF6AH 6 12 如果内存中有 4 个空闲块 每个空闲块的大小为 10MB 有 10 个请求 每次请求 1MB 的内存大小 对于下面列出的内存分配方法中的每一种 确定所 有 10 个请求都被满足之后剩余空闲块的大小 a 首次适应算法 b 循环首次适应算法 c 最佳适应算法 d 最坏适应算法 解 a 首次适应算法 块 1 用完 块 2 3 4 剩余 10MB b 循环首次适应算法 块 1 2 余 7MB 块 3 4 余 8MB c 最佳适应算法 块 1 用完 块 2 3 4 余 10MB d 最坏适应算法 块 1 2 余 7MB 块 3 4 余 8MB 6 13 如果一个系统的段表为 段 号始 址段 长 0200510 190030 210080 31200500 4180080 求下列逻辑地址相应的物理地址 如果越界请指明 0 380 1 20 1 24 2 200 3 500 4 120 解 0 380 表示为 0 段 段内偏移为 380 物理地址为 580 1 20 表示为 1 段 段内偏移为 20 物理地址为 920 1 24 表示为 1 段 段内偏移为 24 物理地址为 924 2 200 表示为 2 段 段内偏移为 200 已经越界 3 500 表示为 3 段 段内偏移为 500 物理地址为 1700 4 120 表示为 4 段 段内偏移为 120 已经越界 7 5 在分页虚拟存储器管理中 如果已知时间利用率为 CPU20 分页 磁盘 92 外设 50 请问采取哪些措施可以改善 CPU 的利用率 解 增大分页磁盘空间 7 6 一个 32 位地址的计算机系统使用二级页表 虚拟地址为 9 位顶级页 表 11 位二级页表和偏移 请问 页面长度为多少 虚拟地址空间 有多少个页面 解 页面占用的位数 32 9 11 12 位 页面长度为 4K 虚拟地址空间有 1M 个 页面 7 7 如果分页虚拟存储系统向用户提供的逻辑地址空间最大为 16 页 每 页 2KB 内存总共有 8 个存储块 请问逻辑地址至少应为多少位 内 存空间多大 解 解 逻辑地址应该为 4 11 15 位 内存空间为 8 2K 16K 7 8 在一个请求分页的虚拟存储器管理中 一个程序的运行页面走向为 1 2 3 4 2 3 5 6 3 1 4 6 7 5 2 4 1 3 2 如果为程序分配页框为 3 个 4 个 请分别用 FIFO OPT 和 LRU 算法求 出缺页中断次数和缺页率 解 页框为 3 FIFO 缺页中断次数为 14 缺页率为 14 19 OPT 缺页中断次数为 8 缺页率为 8 19 LRU 缺页中断次数为 13 缺页率为 13 19 页框为 4 FIFO 缺页中断次数为 7 缺页率为 7 19 OPT 缺页中断次数为 5 缺页率为 5 19 LRU 缺页中断次数为 10 缺页率为 10 19 9 99 9 若采用字长为若采用字长为 1616 位的位示图管理磁盘空间 某操作系统的磁盘文件空间位的位示图管理磁盘空间 某操作系统的磁盘文件空间 共有共有 500500 块 问位示图需要多少个字 第块 问位示图需要多少个字 第i i列第列第j j行对应的块号为多少 行对应的块号为多少 答 答 32 i j32 i j 按照书上公式按照书上公式 9 109 10 一个链接文件由一个链接文件由 5 5 个逻辑记录组成 每个逻辑记录的大小与磁盘块大小个逻辑记录组成 每个逻辑记录的大小与磁盘块大小 都为都为 512512 字节 一次存放在字节 一次存放在 2525 7070 9898 8383 6060 号磁盘上 若要存取文件的第号磁盘上 若要存取文件的第 1 1 769769 逻辑字节处的信息 问需要访问哪个磁盘块 逻辑字节处的信息 问需要访问哪个磁盘块 答 答 8383 9 119 11 在在 UNIXUNIX 操作系统中 如果一个盘块的大小为操作系统中 如果一个