第3章-存储管理-习题答案.doc

第3章 存储管理习题
1.1 选择题
1、需要将整个进程放在连续内存空间的存储管理方式是（ A ）。
A．分区存储管理 B．页式存储管理
C．段式存储管理 D．段页式存储管理
2、解决内存碎片问题较好的存储器管理方式是（ B ）。
A．可变分区 B．分页管理
C．分段管理 D．单一连续分配
3、采用（ B ）不会产生内部碎片（即“内零头”）。
A．分页式存储管理 B．分段式存储管理
C．固定分区式存储管理 D．段页式存储管理
4、操作系统采用分页式存储管理方式，要求（ B ）。
A．每个进程拥有一张页表，且进程的页表驻留在内存中。
B．每个进程拥有一张页表，但只要执行进程的页表驻留在内存中，其他进程的页表不必驻留在内存中。
C．所有进程共享一张页表，以节约有限的内存空间，但页表必须驻留在内存中。
D．所有进程共享一张页表，只有页表中当前使用的页面必须驻留在内存中，以最大限度地节约有限的内存空间。
5、在分页式存储管理系统中，每个页表的表项实际上是用于实现（ C ）。
A．访问辅存单元 B．静态重定位
C．动态重定位 D．装载程序
6、设有8页的逻辑空间，每页有1024B，它们被映射到32块的物理存储区中。那么，逻辑地址的有效位是（ C ），物理地址至少是（ C ）位。
A．10、11 B．12、14
C．13、15 D．14、16
7、一个分页存储管理系统中，地址长度为32位，其中页号占8位，则页表长度是（ A ）。
A．2的8次方字节 B．2的16次方字节
C．2的24次方字节 D．2的32次方字节
8、某页式管理系统中，地址寄存器的低9位表示页内地址，则页面大小为（B）。
A．1024字节 B．512字节
C．1024K字节 D．512K字节
9、分段式存储管理系统中，若地址用24位表示，其中8位表示段号，则允许每段的最大长度是（ B ）。
A．2的24次方字节 B．2的16次方字节
C．2的8次方字节 D．2的32次方字节
10、虚拟存储管理机制的理论基础是程序的（ A ）原理。
A．局部性 B．全局性
C．动态性 D．虚拟性
11、虚拟存储系统能够提供容量很大的虚拟空间，但大小有一定范围，受到（ C ）限制。
A．内存容量不足 B．交换信息的大小
C．CPU地址表示范围 D．CPU时钟频率
12、虚拟存储器最基本的特征是（ A ）。
A．从逻辑上扩充内存容量 B．提高内存利用率
C．驻留性 D．固定性
13、一般来说，分配的内存页框数越多，缺页中断率越低，但是以下（ D ）页面置换算法存在异常现象：对于某些进程分配的内存越多缺页中断率反而越高。
A．LRU B．OPT
C．LFU D．FIFO

1.2 填空题
1、影响缺页中断率的因素有（ 页框大小 ）、（ 分配的页框数 ）、页面置换算法和程序本身特性。
2、为了缩短地址转换时间，操作系统将访问频繁的少量页表项存放到称为（ 相联存储器 ）的高速寄存器组中，构成一张（ 快表 ）。
3、在页式存储管理系统中，页面大小为4KB，某进程的0、1、2、3页分别存放在3、5、4、2号页框中，则其逻辑地址1A3F（H）所在页框号为（ 5 ），转换所得物理地址为（ 5A3F ）（H）。
4、分页式存储管理系统中，地址寄存器长度为24位，其中页号占14位，则内存的分块大小应该是（ 210 ）字节。
5、在没有快表的情况下，在分页存储管理系统中，每访问一次数据，至少要访问（ 2 ）次内存。
6、分段式存储管理系统为每个进程建立一张段映射表，即段表。每一段在表中占有一个表项，其中记录该段在内存中的（ 起始地址 ）和段的长度。
7、程序局部性原理可总结为以下三点：（ 时间局部性 ）、（ 空间局部性 ）和顺序局部性。
8、在作业装入内存时进行地址变换的方式称为（ 静态 ）地址重定位，而在作业执行期间，当访问到指令或数据时才进行地址变换的方式称为（ 动态 ）地址重定位。
9、在虚拟段式存储管理中, 若逻辑地址的段内地址大于段表中该段的段长, 则发生（ 地址越界 ）中断。

1.3 简答题
1、给定段表如下：

段 号
段 首 址
段 长
0
200
400
1
2300
300
2
800
100
3
1300
580
4

给定地址为段号和位移：1）[1，10] 、2）[2，150] 、 3）[4，40]，试求出对应的内存物理地址。
答：
1）[1，10] 　对应的内存物理地址是2310
2）[2，150]　对应的内存物理地址是越界
3）[4，40] 　缺段中断

2、在一个分页虚拟存储管理系统中，用户编程空间32个页，页长1KB，内存为16KB。如果用户程序有10页长，若己知虚页0、1、2、3，已分到页框8、7、4、10 ，请将虚地址0AC5H和1AC5H转换成对应的物理地址。
答：
虚地址0AC5H = 0000 1010 1100 0101
映射到物理页框第4页。
对应的物理地址为 0001 0010 1100 0101=12C5H
虚地址1AC5H=0001 1010 1100 0101
页表中尚未有分配的页框，此时引发缺页中断，由系统另行分配页框。

3、请描述存储保护和地址越界中断机制。
答：
l 存储保护：为多个程序共享内存提供保障，使在内存中的各道程序，只能访问它自己的区域，避免各道程序间相互干扰，特别是当一道程序发生错误时，不致于影响其他程序的运行，通常由硬件完成保护功能，由软件辅助实现。
l 地址越界中断：每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界。即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断，由操作系统进行相应处理

3、什么是覆盖？什么是交换？覆盖和交换的区别是什么？
答：
l 覆盖：将程序划分成若干个功能上相对独立的程序段，按照程序的逻辑结构让那些不会同时执行的程序段共享同一个内存区的内存扩充技术。
l 交换：先将内存某部分的程序或数据写入外存交换区，再从外存交换区中调入指定的程序或数据到内存中来，并让其执行的一种内存扩充技术。
l 与覆盖技术相比，交换不要求程序员给出程序段之间的覆盖结构，而且，交换主要在进程或作业之间进行，而覆盖则主要在同一个作业或同一个进程内进行。

4、在分页式存储管理系统中，为什么常既有页表，又有快表？
答：
l 在分页式存储管理中，当CPU执行到某条指令、要对内存中的某一地址访问时，首先要根据相对地址去查页表（访问一次内存），然后获取绝对地址去真正执行指令（第二次访问内存）。
l 为了提高相对地址到绝对地址的变换速度，用存储于高速相联存储器的块表来代替部分页表。这时地址转换是以并行的方式进行，这样做无疑比仅查内存中的页表要快得多。但是，相联存储器的成本较高，由它来存储整个页表是不可取的。考虑到程序局部性原理，实际系统中总是一方面采用内存页表、另一方面用快表来共同完成地址的变换工作。

5、请简述引入快表后的分页式存储管理系统的地址变换过程。
答：
l 地址变换机构自动将页号与快表中的所有页号进行并行比较，若其中有与此匹配的页号，则取出该页对应的页框号，与页内地址拼接形成物理地址。
l 若页号不在快表中，则再到内存页表中取出物理块号，与页内地址拼接形成物理地址。
l 同时还应将这次查到的页表项存入快表中，若快表已满，则必须按某种原则淘汰一个表项以腾出位置。

6、分别简述虚拟内存和虚拟设备技术。
答：
l 虚拟内存：把有限的内存容量变得无限大，用户在运行远大于实际内存容量的程序时，不会发生内存不够的错误。也就是说，用户所运行的程序大小与实际内存容量无关。
l 虚拟设备：通过虚拟技术把一台物理I/O设备虚拟为多台逻辑上的I/O设备供多个用户使用，每个用户可以占用一台逻辑上的I/O设备，实现I/O设备的共享。

7、动态分区管理中查找空闲区的算法有哪些？
答：
l 首次适应算法（first fit）。首次适应算法又称最先适应算法，该算法要求空闲区按地址大小递增的次序排列。在进行内存分配时，从未分配区表（或空闲区链）开始位置顺序查找，直到找到第一个能满足其大小要求的空闲区为止。
l 循环首次适应算法（next fit）。循环首次适应算法又称下次适应算法，它是首次适应算法的变形。该算法是从上次找到的空闲区的下一个空闲区开始查找，直到找到第一个能满足其大小要求的空闲区为止。
l 最佳适应算法（best fit）。最佳适应算法要求空闲区按容量大小递增的次序排列。在进行内存分配时，从未分配区表（或空闲区链）开始位置顺序查找，直到找到第一个能满足其大小要求的空闲区为止。
l 最坏适应算法（worst fit）。最坏适应算法要求空闲区按容量大小递减的次序排列。在进行内存分配时，先检查未分配区表（或空闲区链）中的第一个空闲区，若第一个空闲区小于作业所要求的大小，则分配失败；否则从该空闲区中划出与作业大小相等的一块内存空间分配给请求者，余下的空闲区仍然留在未分配区表（或空闲区链）中。

1.4 解答题
1、分页存储管理系统中，假设某进程的页表内容如下表所示。
页面号
页框号
中断位
0
101H
1
1
—
0
2
254H
1
页面大小为4KB，一次内存的访问时间是100ns，一次快表的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新快表和页表的时间），分配给该进程的物理块数固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设①快表初始为空；②地址转换时先访问快表，若快表未命中，再访问页表（忽略访问页表之后的快表更新时间）；③中断位为0表示页面不在内存，产生缺页中断，缺页中断处理后可以直接读取内存中的数据，而不需再次查询快表或页表。设有虚地址访问序列2362H、1565H、25A5H。
（1） 依次访问上述三个虚地址，各需多少时间？
（2） 基于上述访问序列，虚地址1565H的物理地址是多少？
答：
（1）分别是210 ns，108 ns，110 ns。
（2）形成的物理地址是101565H。

2、请求分页系统中，设某进程共有9个页，分配给该进程的内存块数为5，进程运行时，实际访问页面的次序是0，1，2，3，4，5，0，2，1，8，5，2，7，6，0，1，2。
（1）采用FIFO页面置换算法，列出其页面置换次序和缺页中断次数，以及最后留驻内存的页号顺序。
（2）采用LRU页面置换算法，列出其页面置换次序和缺页中断次数，以及最后留驻内存的页号顺序。
答：
（1）采用FIFO页面置换算法
访问序列
0
1
2
3
4
5
0
2
1
8
5
2
7
6
0
1
2
内存块1
0
0
0
0
0
5
5
5
5
5
5
5
7
7
7
7
7
内存块2

1
1
1
1
1
0
0
0
0
0
0
0
6
6
6
6
内存块3

2
2
2
2
2
2
1
1
1
1
1
1
0
0
0
内存块4

3
3
3
3
3
3
8
8
8
8
8
8
1
1
内存块5

4
4
4
4
4
4
4
2
2
2
2
2
2
淘汰的页
√
√
√
√
√
0
1

2
3

4
5
0
1
8

因此，页面淘汰顺序为0、1、2、3、4、5、0、1、8，缺页中断次数为14次。最后留驻内存的页号顺序为7、6、0、1、2。

（2）采用LRU页面置换算法
访问序列
0
1
2
3
4
5
0
2
1
8
5
2
7
6
0
1
2
内存块1
0
0
0
0
0
5
5
5
5
5
5
5
5
5
5
1
1
内存块2

1
1
1
1
1
0
0
0
0
0
0
7
7
7
7
7
内存块3

2
2
2
2
2
2
2
2
2
2
2
2
2
2
2
内存块4

3
3
3
3
3
1
1
1
1
1
6
6
6
6
内存块5

4
4
4
4
4
8
8
8
8
8
0
0
0
淘汰的页
√
√
√
√
√
0
1

3
4

0
1
8
5

因此，页面淘汰顺序为0、1、3、4、0、1、8、5，缺页中断次数为13次。最后留驻内存的页号顺序为1、7、2、6、0。

3、设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。某进程最多需要6页数据存储空间，页的大小为1KB，操作系统为此进程固定分配了4个页框（页框号分别为7、4、2、9），页面的当前分配情况如下所示：

页面号
页框号
装入时间
访问位
0
7
130
1
1
4
230
1
2
2
200
1
3
9
160
1

当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。
（1）该逻辑地址对应的逻辑页号是多少?
（2） 若采用先进先出(FIFO)页面置换算法，求发生页面置换后，该逻辑地址对应的物理地址？要求给出计算过程。
（3）若采用时钟(Clock)页面置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程。（设搜索下一页的指针按顺时针方向移动，且当前指向当前2号页框，示意图如下所示）

3号页面
9号页框
2号页面
2号页框

0号页面
7号页框

1号页面
4号页框

答：
（1）17CAH 转换为二进制为：0001 0111 1100 1010, 页的大小为1KB，所以页内偏移为10位，于是前6位是页号，所以其页号为0001 01，转换为10进制为5，所以，17CAH对应的逻辑页号为5。
（2）若采用先进先出置换算法，则被置换出的页号对应的页框号是7，因此对应的二进制物理地址为： 0001 1111 1100 1010，转换为16进制位的物理地址为1FCAH。
（3）若采用时钟算法，且当前指针指向2号页框，则第一次循环时，访问位都被置为0，在第二次循环时，将选择置换2号页框对应的页，因此对应的二进制物理地址为：
0000 1011 1100 1010，转换为16进制物理地址为0BCAH。