操作系统复习题集及答案.doc

1、操 作 系 统 复 习 题 集三、简答题1. 分 页 存 储 管 理 存 在 的 局 限 性 是 什 么 ?逻辑地址空间：页是物理单位，共享困难、不便对代码进行分类管理，不能进行动态连接。2. 多 道 程 序 系 统 为 什 么 能 提 高 CPU 的 利 用 率 ？利用了原来 CPU 空 闲 等 待 时 间3. 文 件 的 逻 辑 结 构 有 哪 些 ？一种是无 结 构 的 流 式 文 件 ， 是 指 对 文件内信息不再划分单位，它是依次的一串字符流构成的文件；一种是有结构的记录式文件, 是用户把文件内的信息按逻辑上独立的含义划分信息单位，每个单位称为一个逻辑记录（简称记录） 。所有记录通常

2、都是描述一个实体集的，有着相同或不同数目的数据项，记录的长度可分为定长和不定长记录两类。4. 什 么 是 设 备 独 立 性 ？应用程序独立于具体使用的物理设备。设备独立性又称为数据无关性。它指的是应用程序在使用设备进行 I/O 时，使用的是逻辑设备，而系统在实 际 执行 时 使 用 的 是 物 理 设 备 ， 由 操 作 系 统 负 责 逻 辑 设 备 与 物 理 设 备 的 映 射 。5. 为什么要引入线程，解释一下线程与进程之间的相互关系。因为虽然进程可以提高 CPU 的利用率，但 是 进 程 之 间 的 切 换 是 非 常 耗 费 资源 和 时 间 的 ,为了能更进一步的提高操作系统的

3、并发进,引 进 了 线 程 .这样,进 程 是分 配 资 源 的 基 本 单位,而 线 程 则 是 系 统 调 度 的 基 本 单 位 .一 个 进 程 内 部 的 线程 可 以 共 享 该 进 程 的 所分配到的资源.线程的创建与撤消,线 程 之 间 的 切 换 所 占用 的 资 源 比 进 程 要 少 很多.总 的 来 说 就 是 为 了 更 进 一 步 提 高 系 统 的 并 发 性 ,提高 CPU 的 利 用 率 . 线 程 是 进 程 的 基 础 ， 进 程 包 含 多 个 线 程 ， 是 线 程 的 载 体 。6. 死 锁 的 必 要 条 件 是 什 么 ？死 锁 ： 当 某 进

4、程 提 出 资 源 申 请 后 ， 使 得 系 统 中 一 些 进 程 处 于 无 休 止 的 阻塞 状 态 ， 在 无 外 力 作 用 下 ， 永 远 不 能 再 继 续 前 进 。 产 生 死 锁 的 必 要 条 件 ： 互斥 条 件 ： 某 段 时 间 内 某 资 源 只 能 由 一 个 进 程 使 用 。 不 剥 夺 条 件 ： 资 源 在 未 使用 完 前 ， 不 能 被 剥 夺 ， 由 使 用 进 程 释 放 。 部 分 分 配 （ 请 求 和 保 持 ） ： 进 程 因请 求 资 源 而 阻 塞 时 ， 对 已 分 配 给 它 的 资 源 保 持 不 放 。 环 路 条 件 ：

5、发 生 死 锁 时 ，有 向 图 必 构 成 一 环 路 。7. 什 么 是 虚 拟 内 存 ？虚 拟 内 存 是 计 算 机 系 统 内 存 管 理 的 一 种 技 术 。 它 使 得 应 用 程 序 认 为 它 拥有 连 续 的 可 用 的 内 存 （ 一 个 连 续 完 整 的 地 址 空 间 ） ， 而 实 际 上 ， 它 通 常 是 被分 隔 成 多 个 物 理 内 存 碎 片 ， 还 有 部 分 暂 时 存 储 在 外 部 磁 盘 存 储 器 上 ， 在 需 要时 进 行 数 据 交 换 。8. 假 脱 机 技 术 是 什 么 ？通 过 共 享 设 备 来 模 拟 独 享 设 备

6、所 采 用 的 操 作 是 假 脱 机 操 作 ， 即 在 联 机 情况 下 外 部 设 备 设 备 同 时 操 作 。 所 使 用 的 假 脱 机 技 术 称 之 为 假 脱 机 技 术 。9. 为 银 行 取 款 机 系 统 配 备 的 操 作 系 统 应 归 类 于 什 么 类 型 的 操 作 系 统 ？10. 多 道 程 序 设 计 的 主 要 优 点 是 什 么 ？解 ： 多 道 程 序 设 计 是 指 在 主 存 中 同 时 存 放 多 道 用 户 作 业 ， 使 它 们 都 处 于 执 行的 开 始 点 和 结 束 点 之 间 ， 这 些 程 序 共 享 计 算 机 系 统 资

7、源 。 多 道 程 序 设 计 的 主要 优 点 有 ： (1) 提 高 CPU 的 利 用 率 。 在 多 道 程 序 环 境 下 ， 多 个 程 序 共 享 计 算机 资 源 ， 当 某 个 程 序 等 待 I/O 操 作 时 ， CPU 可 以 执 行 其 他 程 序 ， 大 大 提 高 了CPU 的 利 用 率 。 (2) 提 高 设 备 的 利 用 率 。 在 多 道 程 序 环 境 下 ， 多 个 程 序 共 享系 统 的 设 备 ， 大 大 提 高 系 统 设 备 的 利 用 率 。 (3)提 高 系 统 的 吞 吐 量 。 在 多 道 程序 环 境 下 ， 减 少 了 程 序

8、的 等 待 时 间 ， 提 高 了 系 统 的 吞 吐 量 。11. 请 为 的 下 面 应 用 环 境 的 计 算 机 选 择 适 合 的 操 作 系 统 。(1） 飞 机 的 导 航 （ 2） 办 公 室 自 动 化 系 统 （ 3） 航 空 订 票 系 统 （ 4） 复 杂的 科 学 计 算 （ 5） 图 书 检 索 系 统12. 什 么 是 并 发 、 并 行 ？并 发 和 并 行 是 即 相 似 又 有 区 别 的 两 个 概 念 ， 并 行 是 指 两 个 或 者 多 个 事件 在 同 一 时 刻 发 生 ； 而 并 发 是 指 两 个 或 多 个 事 件 在 同 一 时 间 间

9、隔 内 发 生 。 在多 道 程 序 环 境 下 ， 并 发 性 是 指 在 一 段 时 间 内 宏 观 上 有 多 个 程 序 在 同 时 运 行 ，但 在 单 处 理 机 系 统 中 ， 每 一 时 刻 却 仅 能 有 一 道 程 序 执 行 ， 故 微 观 上 这 些 程 序只 能 是 分 时 地 交 替 执 行 。 倘 若 在 计 算 机 系 统 中 有 多 个 处 理 机 ， 则 这 些 可 以 并发 执 行 的 程 序 便 可 被 分 配 到 多 个 处 理 机 上 ， 实 现 并 行 执 行 ， 即 利 用 每 个 处 理机 来 处 理 一 个 可 并 发 执 行 的 程 序 ，

10、 这 样 ， 多 个 程 序 便 可 以 同 时 执 行13 什 么 是 临 界 区 ？一 次 仅 允 许 一 个 进 程 使 用 的 资 源 称 为 临 界 资 源 ， 在 进 程 中 对 于 临 界 资 源 访问 的 程 序 段 称 为 临 界 区 。14. 引 入 缓 冲 的 目 的 是 什 么 ？答 ： （ 1） 缓 和 外 部 设 备 和 CPU 的 速 度 差 异 ； （ 2） 减 少 CPU 被 中 断的 次 数 ； （ 3） 实 现 CPU 和 设 备 、 设 备 和 设 备 之 间 的 并 行 操 作 。15. 设 备 驱 动 程 序 的 主 要 任 务 是 什 么 ？设 备

11、 驱 动 程 序 是 请 求 I/O 的 进 程 与 设 备 控 制 器 之 间 的 一 个 通 信 程 序 ， 主要 功 能 有 ： 将 用 户 的 要 求 转 换 为 具 体 要 求 。 检 查 用 户 的 合 法 性 ， 了 解 设 备 状 态 ， 根 据 要 求 传 递 参 数 ， 设 置 设 备 的 工 作方 式 。 向 设 备 控 制 器 发 I/O 命 令 启 动 设 备 ， 完 成 具 体 的 I/O 操 作 。 及 时 响 应 外 设 的 中 断 请 求 ， 根 据 中 断 类 型 调 用 相 应 的 中 断 处 理 程 序 。 具 有 通 道 的 控 制 系 统 ， 还 要

12、 构 造 通 道 程 序 。四、综合题1. 信号量的 PV 操作解决进程的同步问题。2. 银行家算法判断系统状态是否安全。3. 分页系统中逻辑地址和物理地址的转换。4. 页面置换算法，主要掌握先进先出、LRU、最佳置换。5. 磁盘调度算法，包括 FCFS、短寻道优先、电梯算法、LOOK 算法等。6. 进程调度算法，包括 FCFS、短任务优先、最短剩余时间优先、时间片轮转等。综合题案例：1.考虑下列进程集，进程占用的 CPU 区间长度以毫秒来计算：假设在时刻 0 以进程 P1，P 2，P 3，P 4，P 5 的顺序到达。a.画出 4 个 Gantt 图分别演示用 FCFS、SJF、非抢占优先级（

13、数字小代表优先级高）和 RR（时间片1）算法调度时进程的执行过程。b.在 a 里每个进程在每种调度算法下的周转时间是多少？c.在 a 里每个进程在每种调度算法下的等待时间是多少？d.在 a 里哪一种调度算法的平均等待时间对所有进程而言最小？答：a.甘特图（看教材 138 页）FCFS:P1 P2 P3 P4 P50 10 11 13 14 19SJF:P2 P4 P3 P4 P50 1 2 4 9 19非抢占优先级:进程 区间时间 优先级P1 10 3P2 1 1P3 2 3P4 1 4P5 5 2P2 P5 P1 P3 P40 1 6 16 17 19RR:P1P2 P3 P4 P5 P1

14、P3 P5 P1 P5 P1 P5 P1 P5 P1 P1 P1 P1 P10 19b.周转时间FCFS RR SJF 非抢占优先级P1 10 19 19 16P2 11 2 1 1P3 13 7 4 18P4 14 4 2 19P5 19 14 9 6c.等待时间FCFS RR SJF 非抢占优先级P1 0 9 9 6P2 10 1 0 0P3 11 5 2 16P4 13 3 1 18P5 14 9 4 2d.SJF2.考虑一个运行十个 I/O 限制任务和一个 CPU 限制任务的系统。假设，I/O 限制任务一次分配给一个 I/O 操作 1 毫秒的 CPU 计算，但每个 I/O 操作的完成需

15、要 10 毫秒。同时，假设间接的上下文切换要 0.1 毫秒，所有的进程都是长进程。对一个 RR 调度来说，以下情况时 CPU 的利用率是多少：a.时间片是 1 毫秒b.时间片是 10 毫秒答：a.时间片是 1 毫秒：不论是哪个进程被调度，这个调度都会为每一次的上下文切换花费一个 0.1 毫秒的上下文切换。CPU 的利用率是 1/1.1*100=92%。b.时间片是 10 毫秒：这 I/O 限制任务会在使用完 1 毫秒时间片后进行一次上下文切换。这个时间片要求在所有的进程间都走一遍，因此，10*1.1+10.1(因为每个 I / O 限定任务执行为 1 毫秒，然后承担上下文切换的任务，而 CPU

16、 限制任务的执行 10 毫秒在承担一个上下文切换之前) 。因此，CPU 的利用率是20/21.1*100=94%。3. 考虑下面的一个系统在某一时刻的状态：Allocation Max AvailableA B C D A B C D A B C DP0 0 0 1 2 0 0 1 2 1 5 2 0P1 1 0 0 0 1 7 5 0P2 1 3 5 4 2 3 5 6P3 0 6 3 2 0 6 5 2P4 0 0 1 4 0 6 5 6使用银行家算法回答下面问题：a.Need 矩阵的内容是怎样的？b.系统是否处于安全状态？c.如果从进程 P1 发出一个请求（0 4 2 0） ，这个请求能

17、否被满足？答：a.Need矩阵的内容是P0（0 0 0 0） P1（0 7 5 0） P2（1 0 0 2） P3（0 0 2 0） P4（0 6 4 0） 。b. .系统处于安全状态，因为Available矩阵等于（ 1 5 2 0） ，进程P0和P 3都可以运行，当进程P3运行完时，它释放它的资源，而允许其它进程运行。c.可以被满足，满足以后，Available矩阵等于（1 1 0 0） ，当以次序P 0，P2, P3, P1 ,P4运行时候，可以完成运行。4. 按顺序给出 5 个部分的内存，分别是 100KB,500KB,200KB,300KB 和600KB，用 first-fit,be

18、st-fit 和 worst-fit 算法，能够怎样按顺序分配进程212KB,417KB,112KB,426KB 和 426KB？哪个算法充分利用了内存空间？答：a. First-fit:b. 212K is put in 500K partitionc. 417K is put in 600K partitiond. 112K is put in 288K partition (new partition 288K = 500K 212K)e. 426K must waitf. Best-fit:g. 212K is put in 300K partitionh. 417K is put i

19、n 500K partitioni. 112K is put in 200K partitionj. 426K is put in 600K partitionk. Worst-fit:l. 212K is put in 600K partitionm. 417K is put in 500K partitionn. 112K is put in 388K partitiono. 426K must waitBest-fit: 算法充分利用了内存空间。5. 考虑一个分页系统在内存中存储着一张页表。a.如果内存的查询需要 200 毫秒，那么一个分页内存的查询需要多长时间？b.如果我们加上相关联的

20、寄存器，75%的页表查询可以在相关联的寄存器中找到，那么有效的查询时间是多少？（假设如果入口存在的话，在相关的寄存器中找到页表入口不花费时间）答：a.400 毫秒：200 毫秒进入页表，200 毫秒进入内存中的字b.有效进入时间=0.75*200 毫秒+0.25*400 毫秒=250 毫秒6. 假设有一个请求调页存储器，页表放在寄存器中：处理一个页错误，当有空的帧或被置换的页设有被修改过时要用 8ms，当被置换的页被修改过明用20ms，存储器访问时间为 100ns。假设被置换的页中有 70被修改过，有效访问时间不超过 200ns 时最大可接受的页错误率是多少？答：0.2 sec = (1 P)

21、 0.1 sec + (0.3P) 8 millisec + (0.7P) 20 millisec0.1 = 0.1P + 2400 P + 14000 P0.1= 16,400 PP = 0.0000067. 假设一个请求调页系统具有一个平均访问和传输时间为 20ms 的分页磁盘。地址转换是通过在主存中的页表来进行的，每次内存访问时间为 1s。这样，每个通过页表进行的内存引用都要访问内存两次。为了提高性能，加入一个相关内存，当页表项在相关内存中时，可以减少内存引用的访问次数。假设 80%的访问发生在相关内存中，而且剩下中的 10%（总量的 2%）会导致页错误。内存的有效访问时间是多少？答:

22、有效访问时间= (0.8) (1 sec)+ (0.1) (2 sec) + (0.1) (5002 sec)= 501.2 sec 0.5 millisec8. 某虚拟存储器的用户空间共有 32 个页面，每页 1KB，主存 16KB。试问：（1）逻辑地址的有效位是多少？（2）物理地址需要多少位？（3）假定某时刻系统用户的第 0，1，2，3 页分别分配的物理块号为5，10，4，7，试将虚地址 0A5C 和 093C 变换为物理地址。解 （1）程序空间的大小为 32KB，因此逻辑地址的有效位数是 15 位。（2）内存空间的大小是 16KB，因此物理地址至少需要 14 位。（3）当页面为 1KB

23、时，虚地址 0A5C 表示页号为 00010，页内地址是1001011100。该页在内存的第 4 块，即块号为 0100，因此 0A5C 的物理地址是01001001011100，即 125CH。（4）用同样的方法可以求得，093C 的物理地址是 113CH。9. 若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024 字节，试将逻辑地址 1011，2148，3000，5012 转化为相应的物理地址（注：此处块号即为页面号） 。页号 块号01232316解 本题中，为了描述方便，设页号为 P，页内位移为 W，逻辑地址为 A，内存地址为 M，页面大小为 L，则P=int(A/L)

24、W=A mod L对于逻辑地址 1011P=int(1011/1024)=0W=1011 mod 1024=1011A=1101=(0,1101)查页表第 0 页在第 2 块，所以物理地址为 M=1024*2+1101= 3059。对于逻辑地址为 2148P=2148/1024=2W=2148 mod 1024=100A=2148=(2,100)查页表第 2 页在第 1 块，所以物理地址为 M=1024*1+100=1124。对于逻辑地址为 3000P=3000/1024=2W=3000 mod 1024=952A=3000=(2,952)查页表第 2 页在第 1 块，所以物理地址为 M=10

25、24*1+952=1976对于逻辑地址 5012P=5012/1024=4W=5012 mod 1024=916因页号超过页表长度，该逻辑地址非法。10. 某段式存储管理系统中，有一作业的段表（SMT）如下表所示，求逻辑地址0 ，65，1，55， 2，90，3，20对应的主存地址（按十进制） 。 （其中方括号中的第一个元素为段号，第二个元素为段内地址）段号 段长（容量） 主存起始地址 状态01232005010015060085010001110解 逻辑地址0，65 ：对应的主存地址为 60065665。逻辑地址1 ，55 ：因段内地址超过段长，所以产生段地址越界中断。逻辑地址2 ，90 ：对

26、应的主存地址为 1000901090。逻辑地址3 ，20 ：因为状态位为 0，即该段在辅存中，所以产生缺段中断。11对页面访问串：1，2，3，4，1，2，5，1，2，3，4，5，指出在驻留集大为 3 时，使用 FIFO、OPT 和 LRU 替换算法的缺页次数。(OPT 和 LRU 如果出现多选项时使用 FIFO)答： FIFO: 缺页 11 次页面号1234125 123451 1 1 4 4 4 4 4 2 2 2 52 2 2 1 1 1 1 1 3 3 33 3 3 2 5 5 5 5 4 4OPT: 缺页 7 次页面号1234 1 25 1 234 51 1 1 1 1 1 1 1 1

27、 3 3 32 2 2 2 2 2 2 2 2 4 43 4 4 4 5 5 5 5 5 5LRU: 缺页 10 次页面号1234125 1 23451 1 1 4 4 4 5 5 5 3 3 32 2 2 1 1 1 1 1 1 4 43 3 3 2 2 2 2 2 2 512.假设一个磁盘驱动器有 5000 个柱面，从 0 到 4999，驱动器正在为柱面 143的一个请求提供服务，且前面的一个服务请求是在柱面 125.按 FIFO 顺序，即将到来的请求队列是86，1470，913，1774，948，1509，1022，1750，130从现在磁头位置开始，按照下面的磁盘调度算法，要满足队列中

28、即将到来的请求要求磁头总的移动距离（按柱面数计）是多少？a. FCFSb. SSTFc. SCANd. LOOKe. C-SCAN答：a. FCFS 的调度是 143 ， 86 ， 1470 ， 913 ， 1774 ， 948 ， 1509 ， 1022 ， 1750 ， 130 。总寻求距离是 7081 。b. SSTF 的调度是 143 ， 130 ， 86 ， 913 ， 948 ， 1022， 1470， 1509， 1750， 1774。总寻求距离是 1745。 c. SCAN 的调度是 143 ， 913 ， 948 ， 1022， 1470， 1509， 1750， 1774

29、， 4999 ， 130 ， 86 。总寻求距离是 9769 。d. LOOK 的调度是 143 ， 913 ， 948 ， 1022， 1470， 1509， 1750， 1774， 130 ， 86 。总寻求距离是 3319 。 e. C-SCAN 的调度是 143 ， 913 ， 948 ， 1022 ， 1470 ， 1509 ， 1750 ， 1774 ， 4999 ， 86 ， 130 。总寻求距离是 9813 。f. C-LOOK 的调度是 143 ， 913 ， 948 ， 1022 ， 1470 ， 1509 ， 1750 ， 1774 ， 86 ， 130 。总寻求距离是

30、3363 。13.假设有两个并发进程 P1 和 P2, 程序代码为P1: begin P2: beginA; C;B； D;end end其中，A, B, C 和 D 均为原语。请给出 P1 和 P2 两个进程所有可能的执行过程。答：ABCD，ACBD,ACDB,CDAB,CABD,CADB14. 桌上有一空盘，只允许存放一个水果。爸爸可向盘中放苹果，也可向盘中放桔子。儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘中空时一次只能放一只水果供吃者取用，请用 P、V 原语实现爸爸、儿子、女儿三个并发进程的同步。分析 在本题中，爸爸、儿子、女儿共用一个盘子，且盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是苹果，则允许女儿吃，儿子必须等待；若放入果盘中的是桔子，则允许儿子吃，女儿必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。解 在本题中，应设置三个信号量 S、So 、Sa，信号量 S 表示盘子是否为空，