1、计算机操作系统典型例题解析 2007-11-13 21:29:43| 分类： 学习材料 |字号 订阅 【例 1】可变分区存储管理系统中，若采用最佳适应分配算法，“空闲区表”中的空闲区可按（ A ）顺序排列。 A、长度递增 B、长度递减 C、地址递增 D、地址递减 分析： 最佳适应算法要求每次都分配给用户进程能够满足其要求的空闲区中最小的空闲区，所以为了提高算法效率，我们把 所有的空闲区，按其大小以递增的顺序形成一空闲分区链。这样，第一个找到的满足要求的空闲区，必然是符合要求中最小的。所以本题的答案是 A。 【例 2】虚拟存储技术是（ B ）。 A、扩充主存物理空间技术 B、扩充主存逻辑地址空间
2、技术 C、扩充外存空间的技术 D、扩充输入 /输出缓冲区技术 分析： 所谓虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统。具体地说，所谓虚拟存储器是指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。实际上，用户所看到的大容量只是一种感觉，是虚的，故称之为虚拟存储器。虚拟存储技术是一种性能非常优越的存储器管理技术、故被广泛地应用于大、中、小型机器和微型机中。所以本题的答案是 B。 【例 3】很好地解决了“零头”问题的存储管理方法是（ A ）。 A、分页存储管理方式 B、分段存储管理方式 C、多重分区管理 D、可变式分区管理 分析： “零头”也就是内存碎
3、片，是指内存中无法被利用的小空闲区。在有些内存管理方式下，系统运行一段时间后，内存的碎片会占据相当的数量的空间。分段存储管理方式、多重分区管理、可变式分区管理都会因为内存分配回收产生“零头”，而分页存储管理方式，按事先划分好的内存块为单位分配回收内存，所以不会产生“零头”。所以本题的答案是 A。 【例 4】系统“抖动”现象的发生是由（ B ）引起的。 A、交换的信息量过大 B、置换算法选择不当 C、内存容量不足 D、请求分页管理方案 分析： “抖动”现象是指刚被换出的页很快又要被访问，为此，又要换出其他页，而该页又很快被访问，如此频繁地置换页面，以致大部分时间都花在页面置换上。交换的信息量过大
4、，内存容量不足都不是引起系统“抖动”现象的原因，而选择的置换算法不当才是引起“抖动”现象的根本原因，例如，先进先出算法就可能产生“抖动”现象。所以本题的答案是 B。 【例 5】虚拟存储管理系统的基础是程序的（ C）理论。 A、全局性 B、虚拟性 C、局部性 D、动态性 分析： 虚拟存储技术是基于程序的局部性原理的，程序的局部性原理体现在两个方面：时间局部性和空间局部性。时间局部性是指一条指令被执行后，那么它可能很快会再次被执行，空间局部性是指若某一存储单元被访问，那么与该存储单元相邻的单元可能也会很快被访问。所以本题的答案是 C。 【例 6】简述页和段的区别。 答：分页和分段有许多相似之处，但
5、是在概念上两者完全不通，主要表现在： 页是信息的物理单位，分页是为了系统管理内存的方便而进行的，故对用户而言，分页是不可见的，是透明的；段是信息的逻辑单位，分段是作业逻辑上的要求，对用户而言，分段是可见的。页的大小是固定的，由系统决定；段的大小是不固定的，由用户作业本身决定。从用户角度看，分页的地址空间是一维的，而段的地址空间是二维的。 【例 7】内存保护是否可以完全由软件来实现？为什么？ 答：内存保护的主要任务是确保每道程序都只在自己的内存内运行。这就要求系统能对每条指令所访问的地址进行越界检查。若发生越界，系统应能立即发现，并发出越界中断请求，以终止该指令。若每次检查完全用软件来实现，则每
6、执行一条指令，都要增加若干条指令去执行越界的检查功能，这无疑将降低程序的执行速度，因此，越界检查通常由硬件实现，并使指令的执行与越界检查功能并行执行，从而不使程序的运行速度降低。当然，对发现有越界后的处理需要与软件配合来完成。因此说内存保护功能是由硬件和软件共同完成的。 【例 8】用可变分区方式管理主存时，假定主存中按地址顺序依次有五个空闲区，空闲区的大小为 32K， 10K， 5K， 228K， 100K。现有五个作业 J1， J2， J3， J4 和 J5。它们各需主存 11K， 10K， 108K， 28K， 115K。若采用首次适应分配算法能把这五个作业按 J1 J5 的次序全部装入主
7、存吗？你认为按怎样的次序装入这五个作业可时主存空间的利用率最高？ 答：最先适应分配算法能把这五个作业按 J1 J5 的次序全部装入主存时， J1、 J2 分割第一个空闲区，剩 11K； J3、 J4 分割第四个空闲区，剩 92K； J5 无法装入，所以用最先适应分配算法不能把这五个作业按 J1 J5 的次序全部装入主存。 如果先装入 J3，装入第四个空闲区，剩余空间 120K；再装入 J5，装入第四个空闲区，剩余空间 5K；再装入 J4，装入第一个空闲区，剩余 4K；再装入 J1， J1 装入第五个空闲区，剩余空间 104K；再装入 J2，装入第二个空闲区，这样效率最好。 【例 9】简述什么是
8、覆盖？什么是交换？覆盖和交换的区别是什么？ 答：所谓覆盖，是指同一主存区可以被不同的程序段重复使用。通常一个作业由若干个功能上相互独立的程序段组成，作业在一次运行时，也只用到其中的几段，利用这样一个事实，我们就可以让那些不会同时执行的程序段共用同一个主存区。 所谓交换，就是系统根据需要把主存中暂时不运行的某个 (或某些 )作业部分或全部移到外存，而把外存中的某个 (或某些 )作业移到相应的主存区，并使其投入运行。 覆盖技术要求程序员必须把一个程序划分成不同的程序段，并规定好它们的执行和覆盖顺序，操作系统根据程序员提供的覆盖结构来完成程序之间的覆盖。覆盖主要在同一个作业或同一个进程内进行；而交换
9、主要是在进程或作业之间进行。另外，覆盖只能覆盖那些与覆盖程序段无关的程序段。 【例 10】对一个将页表放在内存中的分页系统： （ 1）如果访问内存需要 0.2 s，有效访问时间为多少？ （ 2）如果增加一个快表，且假定在快表中找到页表项的几率高达 90，则有效访问时间又是多少（假定查找快报需花的时间为 0）？ 分析： 每次访问数据时，若不使用快表，则需要两次访问内存，即先从内存的页表中读出页对应的块号，然后再根据形成的物理地址去存取数据；使用快表时，若能从快表中直接找到对应的页表项，则可立即形成物理地址去访问相应的数据，否则，仍需两次访问内存。 答： （ 1）有效访问时间为： 2 0.2=0.
10、4 s （ 2）有效访问时间为： 0.9 0.2+（ 1 0.9） 2 0.2=0.22 s 【例 11】某系统采用分页存储管理方式，拥有逻辑空间 32 页，每页 2K，拥有物理空间 1M。 （ 1）写出逻辑地址的格式。（ 2）若不考虑访问权限等，进程的页表项有多少项？每项至少有多少位？（ 3）如果物理空间减少一半，页表结构应相应作怎样的改变？ 答：该系统拥有逻辑空间 32 页，故逻辑地址中页号必须用 5 位来描述；而每页为 2k，因此，页内地址必须用 11 位来描述，这样可得到它的逻辑地址格式如下： 15 11 10 0 （ 2）每个进程最多有 32 个页面，因此，进程的页表项最多为 32
11、项；若不考虑访问权限等，则页表项中只需给出页所对应的物理块号， 1M的物理空间可分成 29个物理块，故每个页表项至少有 9 位。（ 3）如果物理空间减少一半，则页表中页表项数仍不变，但每项的长度可减少 1 位。 【例 12】在分页存储管理系统中，逻辑地址的长度为 16 位，页面大小为 4096字节，现有一逻辑地址为 2F6AH，且第 0、 1、 2 页依次存放在物理块 5、 10、 11 中，问相应的物理地址是多少？ 分析： 在分页存储管理系统中进行地址转换时，地址变换机构将自动把逻辑地址转化为页号和页内地址，如果页号不小于页表长度，则产生越界中断；否则便以页号为索引去检索页表，从中得到对应的
12、块号，并把块号和页内位移分别送入物理地址寄存器的块号和块内位移字段中，形成物理地址。 答： 由题目所给条件可知，分页存储管理系统的逻辑地址结构为： 15 12 11 0 页号 页内位移 逻辑地址 2F6AH的二进制表示如下： 0010 111101101010 页号 页内位移 由此可知逻辑地址 2F6AH的页号为 2，小于页表长度 3，没有越界，该页存放在第 11 个物理块中，用十六进制表示块号为 B，所以物理地址为 BF6AH。 【例 13】什么是虚拟存储器？如何实现分页虚拟存储管理系统？ 答：所谓虚拟存储器，是指仅把作业的一部分装入内存便可运行作业的存储器系统。具体地说，所谓虚拟存储器是指
13、具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储器系统。 要实现分页虚拟存储管理系统，首先要扩充页表，扩充后的页表是在原来页表的基础上发展起来的，包括以下内容：页号、物理块号、状态位、访问位、修改位、外存地址。其中状态位表示该页是否已经调入内存；访问位表示该页在内存期间是否被访问过；修改位表示该页在内存中是否被修改过，若未被修改，则在置换该页时就不需将该页写回到外存，以减少系统的开 销和启动磁盘的次数；若已被修改，则在置换该页时必须把该页写回到外存，以保证外存中所保留的始终是最新副本；外存地址用于指出该页在外存上的地址，通常是物理块号，供调入该页时使用。另外，还要使用两项关键
14、技术：请求调页技术和页面置换技术。 【例 14】在分页虚拟存储管理系统中，为什么说一条指令执行期间可能产生多次缺页中断？ 答：因分页虚拟管理方式中，只要作业的部分页在内存，该作业就能执行，而在执行过程中发现所要访问的指令或者数据不在内存时，则产生缺页中断，将所需的页面调入内存。在分页虚拟存储管理系统中，一条指令（如 Copy A to B ）可能跨了两个页，而其中要访问的操作数可能也跨了两个页。当要执行这类指令，而相应的页都不在内存时，就将产生多次缺页中断（如 Copy A to B 可能产生 6 次缺页中断）。 【例 15】在分页虚拟存储管理系统中，假定系统为某进程分配了四个主存块（将开始
15、4页先装入主存），页的引用顺序为： 7， 1， 2， 0， 3， 0， 4， 2， 3， 0， 3， 2， 7， 0， 1，若采用 FIFO 调度算法、 LRU 调度算法时分别产生多少次缺页中断？依次淘汰的页分是什么？ 答：按照先进先出算法的原则：当发生缺页中断时，将淘汰最先调入 主存的页面： 页号 7 1 2 0 3 0 4 2 3 0 3 2 7 0 主存块的情况 7 7 7 7 3 3 3 3 3 3 3 3 3 3 1 1 1 1 1 1 4 4 4 4 4 4 4 4 2 2 2 2 2 2 2 2 2 2 2 2 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 淘汰
16、页 7 1 2 共发生了 3 次缺页中断，依次淘汰的页位 7、 1、 2。按照最近最少用算法的原则：当发生缺页中断时，后者则淘汰最近一段时面内最久没有被访问的页面。 页号 7 1 2 0 3 0 4 2 3 0 3 2 7 0 主存块的情况 7 1 2 0 3 0 4 2 3 0 3 2 7 0 1 7 1 2 0 3 0 4 2 3 0 3 2 7 2 2 7 1 2 2 3 0 4 2 2 0 3 2 0 0 0 7 1 1 2 3 0 4 4 4 0 3 淘汰页 7 1 4 发生了 3 次缺页中断，依次淘汰的页位 7、 1、 4。 【例 16】现有一分页虚拟存取管理系统，其页表保存在寄存
17、器中。若有一个可用的空页或被替换的页未被修改，则它处理一个缺页中断需要 8ms。如果被替换的页已被修改，则处理一个缺页中断需要 20ms。内存存取时间为 1 s。假定 70被替换的页被修改过，为保证有效存取时间不超过 2 s，可接受的最大缺页率是多少？ 分析： 因为页表放在寄存器里，所以访问页表的时间可以忽略不计。则存取时间就包括内存存取时间和处理缺页中断的时间。 答：如果用 P 表示缺页率，则有效访问时间不超过 2 s 可表示为： (1-p) 1 s p (0.7 20ms 0.3 8ms 1 s) 2 s 因此可计算出： p 1/16400 0.00006 练习题及参考答案 一、单项选择题
18、 1位示图法可用于（ C ）。 A、页式虚拟存储管理中页面置换 B、可变式分区存储管理中空闲区的分配和回收 C、分页式存储管理中主存空闲块的分配和回收 D、文件目录的查找 2下列（ A ）存储方式不能实现虚拟存储器。 A、分区 B、页式 C、段式 D、段页式 3操作系统处理缺页中断时，选择一种好的调度算法对主存和辅存中的信息进行高效调度尽可能地避免（ D ）。 A、碎片 B、 CPU空闲 C、多重中断 D、抖动 4分页式存储管理的主要特点是（ C ）。 A、要求处理缺页中断 B、要求扩充主存容量 C、不要求作业装入到主存的连续区域 D、不要求作业全部同时装人主存 5 LRU页面调度算法淘汰（
19、B ）的页。 A、最近最少使用 B、最近最久未使用 C、最先进入主存 D、将来最久使用 6虚拟存储器实际容量受（ B ）限制。 A、物理主存的大小 B、计算机的地址结构 C、磁盘容量 D、数据存放的绝对地址 7分区管理要求对每一个作业都分配（ A）的主存单元。 A、地址连续 B、若干地址不连续的 C、若干连续的页 D、若干不连续的帧 8页面置换算法中（ A ）不是基于程序执行的局部性理论。 A、 先进先出调度算法 B、 LRU C、 LFU D、最近最不常用调度算法 9在存储管理中，采用覆盖与交换技术的目的是（ A）。 A、节省主存空间 B、物理上扩充主存容量 C、提高 CPU的效率 D、实现
20、主存共享 10分页虚拟存储管理中，缺页中断时，欲调度一页进入主存中，内存己无空闲块，如何决定淘汰已在主存的块时，（ B ）的选择是很重要的。 A、地址变换 B、页面调度算法 C、对换方式 D、覆盖技术 11动态重定位技术依赖于（ B ）。 A、重定位装入程序 B、重定位寄存器 C、地址结构 D、目标程序 12（ D）存储管理兼顾了段式在逻辑上清晰和页式在存储管理上方便的优点。 A、分段 B、分页 C、可变分区方式 D、段页式 13在可变分区存储管理中，某作业完成后要收回其主存空间，该空间可能与相邻空闲区合并，修改空闲区表使空闲区始址改变但空闲区数不变的是（ C ）情况。 A、有上邻空闲区也有下
21、邻空闲区 B、有上邻空闲区但无下邻空闲区 C、无上邻空闲区但有下邻空闲区 D、无上邻空闲区且也无下邻空闲区 14可变分区管理中，首次适应分配算法可将空闲区表中的空闲区栏目按（ A ）顺序排列。 A、地址递增 B、长度递增 C、地址递减 D、长度递减 15在固定分区分配中，每个分区的大小是（ C ）。 A、随作业长度变化 B、相同 C、可以不同但预先固定 D、可以不同但根据作业长度固定 16存储管理主要管理的是（ C ）。 A、外存存储器用户区 B、外存存储器系统区 C、主存储器用户区 D、主存储器系统区 17下述（ B ）页面置换算法会产生 Belady 现象。 A、最佳置换算法 B、先进先出
22、算法 C、 LRU 算法 D、Clock 算法 18作业执行中发生了缺页中断，经操作系统处理后，应让其执行（ C ）指令。 A、被中断的前一条 B、被中断的后一条 C、被中断的 D、启动时的第一条 19 可变分区方式常用的主存分配算法中，（ A）总是找到能满足作业要求的最小空闲区分配。 A、最佳适应算法 B、首次适应算法 C、最坏适应算法 D、循环首次适应算法 20 可变分区方式常用的主存分配算法中，（ C）总是找到能满足作业要求的最大空闲区分配。 A、最佳适应算法 B、首次适应算法 C、最坏适应算法 D、循环首次适应算 法 二、多项选择题 1不需硬件地址转换机构支撑的存储管理方式是（ AD
23、）。 A、单用户连续方式 B、 可变分区方式 C、页式和段式 D、固定分区方式 E、段页式 2可用上下界限寄存器实现存储保护的是（ ACE ）存储管理。 A、分段 B、段页式 C、可变分区 D、分页 E、固定分区 3在下列存储器管理方案中，能实现虚拟存储的是（ CD ） A、分区管理 B、分页存储管理 C、请求分页存储管理 D、请求分段存储管理 E、段页式存储管理 4在下列算法中，可用于页面置换算法的是（ ABE ）。 A、先进先出算法 B、 LRU算法 C、优先级高者优先算法 D、时间片轮转法 E、 Clock 算法 三、填空题 1在存储器管理中，页是信息的 物理 单位，段是信息的 逻辑 单
24、位。页面大小由 系统 确定，段的大小由 _用户作业本身 确定。 2将作业地址空间中的逻辑地址转换为主存中的物理地址的过程称为 地址转换 。 3为了解决碎片问题，可采用一种方法，将内存中的所有作业进行移动，使原来分散的多个小分区拼接成一个大分区，这种方法称为 紧凑 。 4覆盖技术的关键是提供正确的 覆盖结构 。 5页表的作用是 实现从页号到物理块号的映射 。 6程序执行的局部性原理体现在 时间 局部性和 空间 局部性两个方面。 7在分页虚拟存储管理方式中，常采用的页面置换算法有： 最佳置换算法 ，淘汰不再使用或最远的将来才使用的页； 先进先出算法 ，选择淘汰在主存驻留时间最长的页； 最近最少使用
25、算法 ，选择淘汰离当前时刻最近的一段时间内使用得最少的页。 8所谓虚拟存储器是指具有 请求调入 功能和 置换 功能，能从 逻辑 上对内存容量进行扩充的一种存储器系统。 9、可变分区中为提高主存利用率，采用 紧凑 技术，但这样做花费处理器时间，增加系统开销。 10可变分区存储管理中主存预先 不 分区，作业装入主存时，在主存用户空闲区内划分出一块与 作业大小相同 大小适合的连续区域装入 。 11段页式存储管理兼顾了 段式 在逻辑上清晰和 页式 存储管理上方便的优点。 12页面调度算法的选择是很重要的，如果选用了一个 不合适 调度算法就会出现这样的现象，刚被淘汰的页面又立即要用，把它调入，不久又被调出，调出不久又再次调入，如此反复，使调度时间非常频繁，以致大部分时间都花费在来回调度上，这种现象叫做 抖动 ，又称 颠簸 。 13页式存储管理中，进行存储分配时，以 块 为单位进行分配，采用不连续的分配办法，作业信息可以按 页 分散在主存不连续的 主存块 中。
