5.5　自测练习答案

一、填空题

1.地址重定位、保护、内存空间的扩充

2.逻辑地址、相对地址

3.静态分配、动态分配

4.地址重定位（或地址转换、地址映射）

5.固定分区存储管理

6.可变分区存储管理

7.动态

8.静态重定位

9.动态

10.地址越界、非法操作（或操作越权）

11.基址寄存器、限长（长度）寄存器

12.内存、限长（长度）寄存器、基址寄存器

13.最先适应分配算法、最坏适应分配算法

14.内碎片、外碎片

15.节省主存空间

16.逻辑地址、页面或页、页面、（物理）块或页框

17.物理块、页面或页、物理块

18.页表

19.段、段、段内、段

20.段号、段内地址（段偏移）

21.二、段、段、页

22.页面（或页）、页面（或页）

23.块号

24.段在内存的起始地址、段长度

25.虚拟

26.最佳算法、先进先出算法、最近最少使用算法

27.FIFO

28.1

29.13、14、14、12

30.逻辑地址结构

31.程序（的）局部性、时间、空间

32.逻辑地址、物理地址空间、机器的地址长度、物理内存大小

33.12（解释：分区数目为228/216=212，因此需要12位来存储一个分区。）

34.3、2

35.14、16

二、单项选择题

1.A　2.D　3.B　4.A　5.C

6.A　7.D　8.B　9.D　10.D

11.B　12.A　13.D　14.A　15.A

16.B　17.B　18.D　19.B　20.D

21.A　22.B　23.D　24.B　25.A

26.D　27.B　28.D　29.A　30.A

31.D　32.B　33.C　34.A　35.C

36.B　37.C　38.B　39.C　40.A

三、不定项选择题

1.BCD　2.AB　3.AC　4.A　5.BCD

6.ABCD　7.ABC　8.BCD　9.A　10.CF

11.ABCDE　12.ABC　13.ABC　14.ABCD　15.ABCD

四、是非题

1.正确

2.正确

3.错误：虚地址是作业或程序的逻辑地址，只有经过地址转换机构后得到的物理地址才是程序执行时所要访问的内存地址。

4.错误：紧凑技术使分散的空闲区合并，并不能增加内存容量。

5.正确

6.错误：交换技术与非连续存放技术相结合，才构成虚拟存储器。

7.正确

8.正确

9.错误：页面的调入/调出应在内存和文件区及对换区。

10.正确

11.错误：产生页面中断的次数不仅与页面大小有关系，还与访问页面的踪迹、主存容量，以及淘汰算法都有关。

12.正确

13.正确

14.错误：虚存容量不仅受外存容量的限制，而且还受到CPU地址所能表示范围的限制。

15.错误：首先，最佳置换算法只可作为一种评价标准，目前很少在实际中使用。另外，改进型CLOCK算法能相对避免进程的抖动，因而效率较高。

五、综合题

1.答：常用的内存保护方法有硬件法、软件法和软硬件结合保护法3种。

上、下界保护法是一种常用的硬件保护法。上、下界存储保护技术要求为每个进程设置一对上、下界寄存器。上、下界寄存器中装有被保护程序和数据段的起始地址和终止地址。在程序执行过程中，在对内存进行访问操作时，首先进行访问地址合法性检查，即检查经过重定位之后的内存地址是否在上、下界寄存器所规定的范围之内。若在规定的范围之内，则访问是合法的；否则是非法的，并产生访问越界中断。

保护键法也是一种常用的软件存储保护法。保护键法为每一个被保护存储块分配一个单独的保护键。在程序状态字中设置相应的保护键开关字段，对不同的进程赋予不同的开关代码，以便于与被保护的存储块中的保护键相匹配。保护键可以设置读写同时成对保护的，或者只对读写进行单项保护的。如果开关字段与保护键匹配，或者存储块未受到保护，则访问该存储块是允许的；否则，将产生访问出错中断。

另外一种常用的软、硬件内存保护方式是，界限存储器与CPU的用户态、核心态相结合的保护方式。在这种保护方式下，用户态进程只能访问那些在界限寄存器所规定范围内的内存部分，而核心态进程则可以访问整个内存地址空间。

2.答：内零头（又称内碎片），若存储单元长度为n，该块存储的作业长度为m，当n＞m，则剩下长度为（n-m）的空间，称为该单元的内碎片；若存储单元长度为n，在该系统所采用的调度算法下，较长时间内无法选出一道长度不超过该块的作业，则称该块为外零头（外碎片）。

在固定分区分配中，两种零头均会存在，因为空间划分是固定的，无论作业长短，存储单元均不会随之变化，若作业短而存储块长，则产生内零头；若作业长而存储块短，则产生外零头。

在可变式分区分配中，只有外零头而无内零头，因为空间划分是依作业长度进行的，是要多少给多少，但剩下的部分太短而无法再分，则成为外零头。

在页式虚存中，会存在内零头而无外零头，因为存储空间与作业均分为等长单元，所以不存在无法分配的单元，但作业长度并不刚好为页面大小的整数倍，因此在最后一页会有剩余空间，即为内零头。

在段式虚存中，会存在外零头而无内零头，因为段式的空间划分类似于可变分区分配，根据段长分配，要多少给多少，但会剩余小空间无法分配，则为外零头。

3.答：段式管理就是将程序按照内容或过程（函数）关系分成段，每段拥有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间，也就是一个二维虚拟存储器。段式管理程序以段为单位分配内存，然后通过地址映射机构把段式虚拟地址转换成实际的内存物理地址。与页式管理时一样，段式管理也采用只把那些经常访问的段驻留内存，而把那些在将来一段时间内不被访问的段放入外存，待需要时自动调入相关段的方法，实现二维虚拟存储器。

段式管理和页式管理的主要区别有：

1）页式管理中源程序进行编译链接时，是将主程序、子程序、数据区等按照线性空间的一维地址顺序排列起来。段式管理则是将程序按照内容或过程（函数）关系分成段，每段拥有自己的名字。一个用户作业或进程所包含的段对应于一个二维线性虚拟空间，也就是一个二维虚拟存储器。

2）与动态页式管理一样，段式管理也提供了内外存统一管理的虚存实现。与页式管理不同的是，段式虚存每次交换的是一段有意义的信息，而不是像页式存储管理那样只交换固定大小的页，从而需要多次的缺页中断，才能把所需信息完整地调入内存。

3）在段式管理中，段长可根据需要动态增长。这对那些需要不断增加或改变新数据或子程序的段来说，将是非常有好处的。

4）段式管理便于对具有完整逻辑功能的信息段进行共享。

5）段式管理便于进行动态链接，而页式管理进行动态链接的过程非常复杂。

4.答：可变分区分配的存储管理方案中，基于链表的存储分配算法主要有3种：首次适应分配算法、循环首次适应分配算法和最佳适应分配算法。

（1）首次适应分配算法

在首次适应算法中，每个空白区按其位置的顺序链接在一起，即每个后继的空白区其起始地址总是比前者的大。当系统要分配一个存储块时，就按照空白块链的顺序，依次查询，直到找到第一个满足要求的空白块为止。由这种算法确定的空白块，其大小不一定刚好满足要求。如果找到的这个空白区比要求的大，则把它分成两个分区，一个为已分配分区，其大小刚好等于所要求的，另一个仍然为空白块，且留在链中原来的位置上。如果在空白链中从头到尾找了一遍，找不到满足要求的空白块，则返回“暂不能分配”。系统在回收一个分区时，首先检查该分区是否有邻接的空白块，如果有，则应将这个分区与之合并，并将该空白块保留在链中原来的位置；如果回收的分区不和空白块邻接，则应根据其起始地址大小，把它插在链中的相应位置上。

首次适应分配算法的实质是，尽可能地利用存储器低地址部分的空白块，尽量保存在高地址部分的大空白块。其优点在于：当需要一个较大的分区时，便有希望找到足够大的空白块以满足要求。其缺点是：在回收一个分区时，需要花费较多的时间去查找链表，确定它的位置。

（2）循环首次适应分配算法

循环首次适应分配算法与首次适应分配算法类似，只是在每次分配分区时，系统不是从第一个空白块开始查找，而是从上次分配的空白块处查找。当查找至链尾时，便从链首继续查找，直到查找完整个链表。在系统回收一个分区时，为了减少在插入一个空白区时花在查寻链表的时间，如果这个分区不和空白块邻接，则把它插入到前向指针链的最后一个空白块后；如果和空白块相邻，则根据情况做相应处理。由此可见，这些空白块在链中的位置没有一定的规则。

这种循环首次适应分配算法的实质是，使得小的空白块均匀地分布在可用存储空间内。这样，当回收一个分区时，它和一个较大空白块相邻的可能性比较大，因而合并后可得到更大的空白块。与首次适应算法相比，它产生过小空白块的现象比较小。

（3）最佳适应分配算法

在最佳适应分配算法中，空白块按大小顺序链接在一起。系统在寻找空白块时，总是从最小的一个开始。这样，第一次找到的满足要求的空白块必然是最适合的，因为它最接近于要求的大小。这种算法的优点是：如果存储空间中具有正好是所要求大小的空白块，则必然被选中；如果不存在这样的空白块，也只对比要求稍大的空白块划分，而绝不会去划分一个更大的空白块。此后，遇到大的存储要求时，就比较容易满足了。最佳适应算法的缺点在于：寻找一个较大空白块时花费的时间较长；回收一个分区时，把它插入到空白块链中合适的位置上也较为费时；此外，由于每次都划分一个与要求大小最接近的空白块，使得系统中小的空白块较多。这种算法的实质是，在系统中寻找与要求的空间大小最接近的一个空白块。

5.答：交换技术与覆盖技术共同点包括：进程的程序和数据主要放在外存，当前需要执行的部分放在内存，内外存之间进行信息交换。交换技术与覆盖技术不同点：1）交换技术不要求用户给出程序段之间的逻辑覆盖结构；2）交换发生在进程或作业之间，而覆盖发生在同一进程或作业内；3）覆盖只能覆盖那些与覆盖段无关的程序段。

6.答：用户程序的结构可以是一维空间（一个用户程序就是一个程序，并且程序和数据是不分离的），也可以是二维空间（程序由主程序和若干个子程序或函数组成，并且程序与数据是分离的），还可以是N维空间（一个大型程序，由一个主模块和多个子模块组成，其中的各子模块又由主程序和子程序或函数组成）。

7.答：虚拟存储器通过把主、辅存（内存、外存）统一起来管理，给用户造成一种仿佛系统内有巨大主存（内存）供用户使用的假象。例如页式存储管理，一道作业被划分成若干页，其中较活跃的几页放在内存中，而其余不活跃的页被放在辅存中，当需要访问辅存内的页时，就可通过页面调度将其调入内存运行；但用户感觉不到这种变化，它以为作业的所有部分都存在于主存。这样就可以让更多的作业进入主存，提高系统的效率。

8.答：物理存储器的结构是个一维的线性空间，容量有限。而用户程序的结构可以是任意维数的，而且用户程序的大小可能比内存容量小，也可能比内存容量大，有时候可能要大很多。如何将与物理内存结构不同，且大于物理内存容量的用户程序装入内存并运行？虚拟存储技术，也称为虚拟存储器，它为用户提供一种不受物理存储器结构和容量限制的存储器技术。它是用户编程时所使用的一种用户思维中的存储器，它可以是任何结构（一维线性空间、二维空间，甚至N维空间），并且没有容量的限制。

现代计算机操作系统都采用了这种技术，使得用户编程序时不需要考虑物理内存的结构和容量，极大地方便了用户。但虚拟存储器需要大容量的外存储器的支持。

9.答：虚拟存储技术的核心问题是将程序的访问地址（虚地址）与主存的物理地址（实地址）分离。用户只需要在虚地址空间上编写程序，并在各自的虚拟内存上运行。操作系统负责分配主存空间，并完成地址重定位。

实现虚拟存储技术主要需要3个硬件条件：1）一定容量的主存；2）足够大的辅存；3）地址变换机构。

10.答：这种现象称为抖动或颠簸，主要原因是由高缺页率引起的。

系统规定缺页率的上界和下界。当运行进程的缺页率高于上界时，说明分给它的物理块数量过少，应当增加；当运行进程的缺页率低于下界时，说明分给它的物理块数过多，可以减少。这样，根据缺页率的反馈，动态调整物理块的分配，可以防止抖动的发生。

11.答：页面大小64，页内位移是6位，该进程所需页数为702/64=11页，编号为0，1，…，10；逻辑地址为八进制，因此地址数的右边两位即为页内位移d，其余左边高位为页号p。

（105）八进制：p=1，d=5，得内存页帧号为F1，页内位移为5。

（217）八进制：p=2，d=17，得内存页帧号为F2，页内位移为17。

以上两地址均在联想存储器中可以找到，无需到内存中查找页表。

（567）八进制：p=5，d=67，该页号不在联想存储器中，需到主存页表项寻找页帧号，得内存页帧号为F5，页内位移为67。

（1120）p=11；（2500）p=25；以上两地址均为页号越界，进程代码段所占页号最大为10，不可转换。

12.答：可以采用下述两种方法来解决这一问题。

1）通过多级页表的方式来解决，要求连续内存空间存放页表，即将页表分页，并将各个页面离散地存放在不同的物理块中。以二级页表为例说明具体方法：将一张页表分割成多个大小与物理块相同的页表页，页表页从0顺序编址，允许离散存放在物理块中，每个页表页含有若干个页表表项。系统为每个进程建立页目录表，这是一级页表，其表项用于指出页表页，而页表页是二级页表，其中每个表项给出页号与块号的对应关系。这样就构成了二级页表机制。

2）只将当前需要的部分页表页调入内存，其余仍驻留在磁盘上，需要时动态调入。可以在一级页表中增加“页表页是否在内存”的标志位，地址转换机构检查该标志，如未在内存，产生“缺页表页”中断。

13.答：1）FIFO算法的实质是：总是选择作业中在主存驻留时间最长的一页淘汰，即先进入主存的页，先退出主存。在本例中，给出了页面踪迹，只需要按页面使用的顺序进行页面的替换，记录缺页次数即可。

若在内存中为每一个作业进程分配3页，对于题中的页面访问过程，采用FIFO淘汰算法，其页面调度过程如表5-8所示。

由上可知，采用FIFO算法，缺页次数为9次。

2）LRU算法的基本思想是根据一个作业在执行过程中过去的页面踪迹来推测未来的行为。它认为过去一段时间里不曾被访问过的页，在最近的将来可能也不再会被访问。这种算法的实质是：当需要置换一页时，选择在最近一段时间内最久未用的页予以淘汰。

采用LRU算法，其页面调度过程如表5-9所示。

由上可知，采用LRU淘汰算法，缺页次数为7次。

14.答：假设某作业运行中使用的页号依次为：4、3、2、1、4、3、5、4、3、2、1、5。

若在内存中为每一作业分配3个物理块，对于题中的页面访问过程，其页面调度过程如表5-10所示。

若在内存中为每一作业分配4个物理块，对于题中的页面访问过程，其页面调度过程如表5-11所示。

从上面例子可以看出，若在内存中为每一作业分配3个物理块，对于题中的页面访问过程，将产生9次缺页中断。若在内存中为每一作业分配4个物理块，对于题中的页面访问过程，将产生10次缺页中断。

15.答：首先分析虚地址：3个虚地址均为十六进制，存储系统在接收虚地址后，应先将其转化为二进制数，再存储；然后根据页面大小（1KB=210）算出页内位移及页号p，再到页表里搜寻物理块号，进行物理地址的转换。在页式存储管理中，物理页的大小与逻辑页的大小相等，所以页的大小为1K。

下面分别计算3个虚地址。

0AC5H=（101011000101）₂，得d=（1011000101）₂，p=（10）₂。通过页表得知，对应的物理块号是4。第4块的首址为4K，所以物理地址为（1001011000101）2=12C5H，合成物理地址为12C5H。

1AC5H=（1101011000101）₂，得d=（101000101）₂，p=（110）₂，页表中没有该页号，此时发生缺页中断，将根据当前的页面调度策略选择页表当中的一项调换出内存，假设选择第0页，则第6页获得内存物理块号8，所以物理地址为（10001011000101）₂=22C5H，合成物理地址为22C5H。

3AC5H=（11101011000101）₂，得d=（101000101）₂，p=（111）₂，页表中没有该页号，根据页面调度策略选择页表当中的一项调换出内存，假设选择第1页，则第7页获得内存物理块号7，所以物理地址为（1111011000101）₂=1EC5H，合成物理地址为1EC5H。

16.【分析】

在页式存储管理系统中，系统是通过页表来进行地址转换的。对于本题，系统采用了1024字节为一页的分页方式，即页内相对地址为10位。这样，在进行地址转换时，我们首先从虚地址中分离出页号和页内地址，即2100的页号为2，页内地址为52；3100的页号为3，页内地址为28。然后，通过页表给出物理地址的页号，即2100的物理页号为6，3100的物理页号为8。最后与页内地址组合，即可计算出物理地址。

答：1）J₂的页表如图5-8所示。

图　5-8　页表

2）地址变换如图5-9和图5-10所示。

图　5-9　页式存储管理系统中2100的地址变换示意

图　5-10　页式存储管理系统中3100的地址变换示意

根据地址变换图可得出有效逻辑地址2100所对应的物理地址为6196，3100所对应的物理地址为8220。

17.答：覆盖技术中，覆盖段由用户设计，用户自身对内存的划分要参与操作；虚拟存储技术是由系统提供逻辑空间给用户使用，而用户并不真正了解内存的情况，物理空间的划分和管理由系统完成。

交换技术是将内存中处于就绪队列或等待队列的进程暂时调出内存，放入磁盘空间，以便让更多的作业被选择进入内存，提高系统效率。虚存中使用的调入、调出技术是利用磁盘空间对内存进行扩充，提供一个大于实际内存的逻辑空间给用户使用。它们的相同之处是：它们都将本应处于实际内存的内容调至辅存，提高系统效率；不同之处是：交换技术并未提供大于实际内存空间的逻辑空间以供用户使用，该技术并不是直接面向用户的；而虚存技术则是提供更大的逻辑空间以供用户使用，是直接面向用户的。

18.答：请求页式管理是动态页式内存管理的一种，它在作业或进程开始执行之前，不把作业或进程的程序段和数据段一次性全部装入内存，而只装入被认为是经常反复执行和调用的工作区部分，其他部分则在执行过程中动态装入。请求页式管理的调入方式是：当需要执行某条指令，而又发现它不在内存时，或当执行某条指令需要访问其他数据或指令时，而这些指令和数据又不在内存中，从而发生缺页中断，系统将外存中相应的页面调入内存。请求页式管理系统的工作流程图如图5-11所示。

图　5-11　请求页式管理系统的工作流程图

19.答：页式虚存管理是在页式存储管理的基础上实现了虚拟存储器，作业在执行时并不是所有的页都放在主存，若欲访问的页面不在主存，则必须由操作系统将当前所需页面从外存装入主存。这一过程由中断系统完成，称为缺页中断。

缺页中断由缺页处理和页淘汰组成，过程如下：

1）缺页处理：当硬件执行访存指令，因为要访问页面不在主存时会发生缺页异常，进行如下处理：

·根据发生页故障的虚地址得到页表项。

·申请一个可用页帧，即物理（存储）块（可能需要引起淘汰某页）。

·检查页类型，若为零页，则将刚申请到的页帧清0，将页帧号添入页表项，置合法位为1；否则，调用I/O子系统将页表项中辅存块号所指的页面读到页帧中，将页帧号填入页表项，合法位置1，结束缺页异常的处理，恢复现场，重新执行访存指令。

2）页淘汰：可以发生在申请页帧时，因为已无可用空闲页帧，而需要淘汰部分页面，将其所占的页帧回收，主要有以下工作（假设淘汰页p）：

·查p页表项的修改位，若未修改，将该页回收，并将各特征位重置为默认值。·若已修改，则检查p的类型栏。

·若是零页或回写交换空间页，则申请一块交换空间，将该页修改后的新内容保存下来。

·将该页回收，并将各特征位重置为默认值。

20.答：1）命中率是指页号在快表中被查找到的百分比，是通过快表实现内存访问的比率。60%的命中率意味着有60%的时间，可以在快表中找到所需的页号。接近100%的命中率表示大部分的内存访问都可以通过快表实现，几乎不使用页表。

有效内存访问时间是根据概率，对以下两种情况进行加权得到。

·如果在快表中找到所需的页码，则根据物理块号，进而访问内存中所需的字节，总共需要花费的时间s1为：访问快表时间与访问内存时间之和。

·如果在快表中没有找到所需的页号，则必须先访问内存中的页表得到物理块号，进而访问内存中所需的字节，总共需要花费的时间s2为：访问快表时间、访问页表时间以及访问内存时间三者之和。

假设命中率为h，则有效内存访问时间=s1×h+s2×（1-h）。

2）当有效内存访问时间为140纳秒时，命中率为80%，计算过程如下：

140=（20+100）×h+（20+100+100）×（1-h）

h=0.8

3）当有效访问时间为122纳秒时，命中率为98%，计算过程如下：

122=（20+100）×h+（20+100+100）×（1-h）

h=0.98

4）当命中率为80%时，有效访问时间为140纳秒；当命中率为98%，有效访问时间为122纳秒。这说明，命中率越高，内存访问时间越短，系统性能越好。