连续分配方式要求为一个进程分配连续的内存空间，会形成许多“碎片”（外部碎片）， 尽管采用“紧凑”技术可以解决这个问题，但要为移动大量信息花去不少的处理机时间， 代价较高。

非连续分配管理方式根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。

 

1.基本分页存储管理方式

固定分区会产生内部碎片，动态分区会产生外部碎片，这两种技术对内存的利用率都比较低。我们希望内存的使用能尽量避免产生碎片，这就引入了分页的思想：被主存空间划分为大小相等且固定的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请内存中的块空间。

（1）分页存储的几个基本概念

①页面和页面大小：进程中的块称为页，内存中的块称为页框。外存也以同样的单位进行划分，直接称为块。进程在执行时需要申请主存空间，就是要为每一个页面分配主存中的可用页框，这就产生了页和页框一一对应。在为进程分配内存时，以块为单位，将进程中的若干个页分别装入到多个可以不相邻接的物理块中。由于进程的最后一页经常装不满一块，而形成了不可利用的碎片，称之为“页内碎片”。

为了方便地址转换，页面大小应该是2的幂，通常为1KB~8KB。同时页面大小应该适中，如果页面太小，会使进程的页面数过多，这样页表就过长，占用大量内存，而且也会增加硬件地址转换的开销，降低页面换入/换出的效率；页面过大又会使页内碎片增大，降低内存的利用率。所以页面的大小应该适中，考虑到空间效率和时间效率的权衡。

②地址结构：

分页存储管理系统中的逻辑地址

包含两部分，前一部分为页号P，后一部分为页内偏移量W。地址长度为32位，其中0~11位为页内地址，即每页大小为4KB；12-31位为页号，地址空间最多允许有1M=2²⁰页。要注意到 地址结构决定了虚拟内存空间有多大。

③页表：为了将逻辑地址上连续的页号映射到物理内存中后成为离散分布的多个物理块，系统为每个进程建立一张页表，记录页面在内存中对应的物理块号，页表通常存放在内存中。页表是由页表项组成的，页表中每个页表项都由页号和块号组成，根据页表项就可以找到每个页号所对应物理内存中物理块的块号。页表的作用是实现从页号到物理块号的地址映射。

（2）基本地址变换机构

地址变换机构的任务是为了将用户地址空间中的逻辑地址转换为内存中的物理地址，地址变换是借助于页表实现的。整个地址变换过程均是由硬件自动完成的。

页表寄存器(PTR)：用来存放页表在内存中的起始地址和页表的长度。进程未执行时，页表的始址和长度存放在进程控制块中，当进程执行时，才将页表始址和长度存入页表寄存器。

分页存储管理系统的地址变换结构

①计算页号P=（int）（A/L）；页内位移W=A％L。

②比较页号P 和页表长度M ，若P≥M，则产生越界中断，否则转到③接着执行

③页表起始地址F与页号P和页表项长度的乘积相加，用得到的地址值到内存中取出该内存单元存放的数b , 这个b就是物理块号。

④物理块号b和物理块大小的乘积与页内位移W 组合成物理地址E。

⑤用得到的物理地址E去访问内存。

（3）具有快表的地址变换机构

由于页表是存放在内存中的，...

课后习题

 

1.【2009统考真题】分区分配内存管理方式的主要保护措施是（ ）。

A .界地址保护            B .程序代码保护

C .数据保护              D .栈保护

【答案】A

【解析】每个进程都拥有自己独立的进程空间，若一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界，因此需要进行界地址保护，即当程序要访问某个内存单元时，由硬件检查是否允许，若允许则执行，否则产生地址越界中断。

 

2. 【2010统考真题】某基于动态分区存储管理的计算机，其主存容量为55MB（初始为空）,采用最佳适配（Best Fit）算法，分配和释放的顺序为：分配 15MB，分配 30MB，释放 15MB，分配8MB，分配6MB，此时主存中最大空闲分区的大小是（ ）。

A. 7MB                    B. 9MB

C. 10MB                   D. 15MB

【答案】B

【解析】最佳适配算法是指每次为作业分配内存空间时，总是找到能满足空间大小需要的最小空闲分区给作业，可以产生最小的内存空闲分区。下图显示了这个过程的主存空间变化。

图中，灰色部分为分配出去的空间，白色部分为空闲区。这样，容易发现，此时主存中最大空闲分区的大小为9MB。

 

3.动态重定位是在作业的（ ）中进行的。

A. 编译过程                    B. 装入过程

C. 链接过程                     D. 执行过程

【答案】D

【解析】静态装入是指在编程阶段就把物理地址计算好。

可重定位是指在装入时把逻辑地址转换成物理地址，但装入后不能改变。

动态重定位是指在执行时再决定装入的地址并装入，装入后有可能会换出，所以同一个模块在内存中的物理地址是可能改变的。

动态重定位是指在作业运行过程中执行到一条访存指令时，再把逻辑地址转换为主存中的物理地址，实际中是通过硬件地址转换机制实现的。

 

4.在一页式存储管理系统中，页表内容见右表。若页的大小为4KB，则地址转换机构将逻辑地址0转换成的物理地址为（块号从0开始计算）（  ）。

A. 8192                    B. 4096

C. 2048                    D. 1024

【答案】A

【解析】按页表内容可知，逻辑地址0对应块号2 ，页大小为4KB，因此转换成的物理地址为2×4K =8K=8192。

 

5. 页式存储管理中，页表的始地址存放在（ ）中。

A.内存                           B .存储页表

C .快表                           D .寄存器

【答案】D

【解析】页表的功能由一组专门的存储器实现，其始址放在页表基址寄存器（PTBR） 中。这样才能满足在地址变换时能够较快地完成逻辑地址和物理地址之间的转换。

 

6. 可重入程序是通过（ ）方法来改善系统性能的。

A .改变时间片长度              B .改变用户数

C .提高对换速度                D .减少对换数量

【答案】D

【解析】可重入程序主要是通过共享来使用同一块存储空间的，或通过动态链接的方式将所需的程序段映射到相关进程中去，其最大的优点是减少了对程序段的调入/调出，因此减少了对换数量。

 

7. 操作系统实现（ ）存储管理的代价最小。

A .分区                               B .分页

C .分段                               D .段页式

【答案】A

【解析】实现分页、分段和段页式存储管理需要特定的数据结构支持，如页表、段表等。为了提高性能，还需要硬件提供快存和地址加法器等，代价高。分区存储管理是满足多道程序设计的最简单的存储管理方案，特别适合嵌入式等微型设备。

 

8. 对主存储器的访问，（ ）。

A .以块（即页）或段为单位

B.以字节或字为单位

C.随存储器的管理方案不同而异

D.以用户的逻辑记录为单位

【答案】B

【解析】这里是指主存的访问，不是主存的分配。对主存的访问是以字节或字为单位的。例如，在页式管理中，不仅要知道块号，而且要知道页内偏移。

 

9. 【2009统考真题】一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）。

A. 2⁸B                      B. 2¹⁶B

C. 2²⁴B                     D. 2³²B

【答案】C

【解析】分段存储管理的逻辑地址分为段号和位移量两部分，段内位移的最大值就是最大段长。地址长度为32位，段号占8 位，因此位移量占32-8 = 24位，因此最大段长为2²⁴B。

 

10. 【2010统考真题】某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为2¹⁰B ,页表项大小为2 B ,逻辑地址结构为

逻辑地址空间大小为2¹⁶页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（ ）。

A. 64                       B.128

C.256                       D.512

【答案】B

【解析】页大小为2¹⁰B ，页表项大小为2 B ,因此一页可以存放2⁹个页表项，逻辑地址空间大小为2¹⁶页，即共需2¹⁶个页表项，因此需要2¹⁶/2⁹ = 2⁷= 128个页面保存页表项，即页目录表中包含表项的个数至少是128。

 

11. 【2014统考真题】现有一个容量为10GB的磁盘分区，磁盘空间以簇为单位进行分配，簇的大小为4KB，若采用位图法管理该分区的空闲空间，即用一位标识一个簇是否被分配，则存放该位图所需的簇为（ ）个。

A. 80

B. 320

C. 80K

D. 320K

【答案】A

【解析】簇的总数为10GB/4KB = 2.5M，用一位标识一簇是否被分配，整个磁盘共需要2.5M b，即需要2.5M/8 = 320KB，因此共需要 320KB/4KB = 80 簇，选 A

 

12. 【2014统考真题】下列选项中，属于多级页表优点的是（ ）。

A. 加快地址变换速度

B. 减少缺页中断次数

C. 减少页表项所占字节数

D. 减少页表所占的连续内存空间

【答案】B

【解析】多级页表不仅不会加快地址的变换速度，还会因为增加更多的查表过程，使地址变换速度减慢；也不会减少缺页中断的次数，反而如果访问过程中多级的页表都不在内存中，会大大增加缺页的次数，并不会减少页表项所占的字节数，而多级页表能够减少页表所占的连续内存空间，即当页表太大时，将页表再分级，把每张页表控制在一页之内，减少页表所占的连续内存空间，因此选D。

 

13. 【2016统考真题】某进程的段表内容如下所示。

访问段号为2、段内地址为400的逻辑地址时，进行地址转换的结果是（ ）。

A .段缺失异常             B .得到内存地址4400

G 越权异常               D .越界异常

【答案】D

【解析】分段系统的逻辑地址A 到物理地址E 之间的地址变换过程如下：

① 从逻辑地址A中取出前几位为段号S ,后几位为段内偏移量W , 注意段式存储管理的题目中，逻辑地址一般以二进制数给出，而在页式存储管理中，逻辑地址一般以十进制数给出，读者要具体问题具体分析。

② 比较段号S和段表长度M，若 S>=M , 则产生越界异常，否则继续执行。

③ 段表中段号S对应的段表项地址= 段表始址F + 段号S×段表项长度取出该段表项的前几位得到段长C。若段内偏移量> =C ,则产生越界异常，否则继续执行。从这句话可以看出，段表项实际上只有两部分，前几位是段长，后几位是始址。

④ 取出段表项中该段的基址b，计算E=b+W,用得到的物理地 E去访问内存。

题目中段号为2的段长为300,小于段内地址400，因此发生越界异常，D 正确。

 

14. 【2019统考真题】在分段存储管理系统中，用共享段表描述所有被共享的段。若进程和共享段S，则下列叙述中，错误的是（ ）。

A .在物理内存中仅保存一份段S的内容

B.段S在和中应该具有相同的段号

C. 和共享段S在共享段表中的段表项

D. 和已都不再使用段 S时才回收段 S所占的内存空间

【答案】B

【解析】段的共享是通过两个作业的段表中相应表项指向被共享的段的同一个物理副本来实现的，因此在内存中仅保存一份段S 的内容，A 正确。段S对于进程和来说，使用位置可能不同，所以在不同进程中的逻辑段号可不同，B错误。段表项存放的是段的物理地址（包括段始址和段长度），对于共享段S来说物理地址唯一，C正确。为了保证进程可以顺利使用段S ，段S必须确保在没有任何进程使用它（可在段表项中设置共享进程计数）后才能被删除，D 正确。

 

15. 【2019统考真题】某计算机主存按字节编址，采用二级分页存储管理，地址结构如下

虚拟地址2050 1225H对应的页目录号、页号分别是（ ）。

A. 081H, 101H     B. 081H, 401H      C. 201H, 101H      D. 201H, 401H

【答案】A

【解析】题中给出的是十六进制地址，首先将它转化为二进制地址，然后用二进制地址去匹配题中对应的地址结构。转换为二进制地址和地址结构的对应关系如下图所示。

前10位、11~20位、21~32位分别对应页目录号、页号和页内偏移。把页目录号、页号单独拿出，转换为十六进制时缺少的位数在高位补零，0000 1000 0001, 0001 0000 0001分别对应

081H, 101H，选项A正确。

 

16. 【2019统考真题】在下列动态分区分配算法中，最容易产生内存碎片的是（ ）。

A.首次适应算法           B .最坏适应算法

C.最佳适应算法           D.循环首次适应算法

【答案】C

【解析】最佳适应算法总是匹配与当前大小要求最接近的空闲分区，但是大多数情况下空闲分区的大小不可能完全和当前要求的大小相等，几乎每次分配内存都会产生很小的难以利用的内存块，所以最佳适应算法最容易产生最多的内存碎片，C 正确。

 

17. 【2013统考真题】某计算机主存按字节编址，逻辑地址和物理地址都是32位，页表项大小为4B。请回答下列问题：

1） 若使用一级页表的分页存储管理方式，逻辑地址结构为

则页的大小是多少字节？页表最大占用多少字节？

2） 若使用二级页表的分页存储管理方式，逻辑地址结构为

设逻辑地址为L A ,请分别给出其对应的页目录号和页表索引的表达式。

3） 采用1）中的分页存储管理方式，一个代码段的起始逻辑地址为0000 8000H，其长度为8 KB；被装载到从物理地址0090 0000H开始的连续主存空间中。页表从主存0020 0000H开始的物理地址处连续存放，如下图所示（地址大小自下向上递增）。请计算出该代码段对应的两个页表项的物理地址、这两个页表项中的页框号，以及代码页面2的起始物理地址。

【解析】

1) 因为主存按字节编址，页内偏移量是12位，所以页大小为2¹²B = 4KB。 页表项数为2²⁰， 因此该一级页表最大为2²⁰×4B = 4MB。

2) 页目录号可表示为(((unsigned int)(LA))>>22) & 0x3FF。

页表索引可表示为(((unsigned int)(LA))>>12) & 0x3FF。

3 ) 代码页面1的逻辑地址为0000 8000H,表明其位于第8个页处，对应页表中的第8个页表项，所以第8 个页表项的物理地址= 页表始址+ 8×页表项的字节数= 0020 0000H + 8x4 = 0020 0020H。由此可得如下图所示的答案。