3.1.4.1 基本分页存储管理方式

非连续分配允许一个程序分散地装入到不相邻的内存分区中，根据分区的大小是否固定分为分页存储管理方式和分段存储管理方式。

分页存储管理方式中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。

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

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

分页的方法从形式上看卖相分区相等的固定分区技术，分区管理不会产生外部碎片。但它又有本质的区别：块的大小相对分区要小很多，而且进程也按照块进行划分，进程运行时按块申请主存可用空间并执行。这样，进程只会在为最后一个不完整的块申请一个主存块空间时，才产生主存碎片，所以尽管会产生内部碎片，但是这种碎片相对进程来说也是很小的，每个进程平均产生半个块大小的内部碎片（也称页内碎片）

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

①页面和页面大小

进程中的块称为页（Page），内存中的块称为页框（Page Frame，或页帧）。外存也以同样的单位进行划分，直接称为块（Block）。进程在执行时需要申请主存空间，就是要为每个页面分配主存中的可用页框，这就产生了页和页框的一一对应。

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

②地址结构。分页存储管理的逻辑地址结构：

地址结构包含两部分：前一部分为页号P，后一部分为页内偏移量W。地址长度为32位，其中0-11位为页内地址，即每页大小为4KB；12-31位为页号，地址空间最多允许有2^20页。

③页表。为了便于在内存中找到进程的每个页面所对应的物理块，系统为每个进程建立一张页表，记录页面在内存中对应的物理号，页表 一般存放在内存中。

在配置了页表后，进程执行时通过查找该表，即可找到每页在内存中的物理块号。可见，页表的作用是实现页号到物理块号的地址映射。

（2）基本地址的变换机构

地址变换机构的任务是将逻辑地址转换为内存中物理地址，地址变换是借助于页表实现的。

在系统中通常设置一个页表寄存器（PTR），存放页表在内存的始址F和页表长度M,进程未执行时，页表的始址和长度存放在进程控制块中，当进程执行时，才将页表始址和长度存入页表寄存器。设页面大小为L，逻辑地址A到物理地址E的变换过程如下：

①计算页号P(P=A/L)和页内偏移量W(w=A%L)

②比较页号P和页表长度M，若P>=M,则产生越界中断，否则继续执行。

③页表中P对应的页表项地址=页表起始地址F+页号*页表项长度，取出该页表项内容b,即为物理块号。

④计算E=b*L+W

以上整个地址变换过程均是由硬件自动完成的。

假如，页面大小L为1K字节，页号2对应的物理块为b=8，计算逻辑地址A=2500的物理地址 E的过程如下

p=2500/1K=2;

w=2500%1K=452;

查找得到页号2对应的物理块的块号为8，E=8*1024+452=8644.

下面讨论分页管理方式存在的两个主要问题：

①每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速度会降低。

②每个进程引入了页表，用于存储映射机制，页表不能太大，否则内存利用率会降低。

(3)具有快表的地址变换机构 

由上面介绍的地址变换过程可知。若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存

第一次是访问页表，确定所存取的数据或指令的物理地址

第二次才根据该地址存取数据或指令。

显然，这种方法比通常执行指令的速度慢了一半。

为此，在地址变换机构中增设了一个具有并行查找能力的高速缓存存储器——块表，又称为联想寄存器（TLB），用来存放当前访问的若干页表项，以加速地址变换的过程。于此对应，主存中的页表也常称为慢表。

在具有快表的分页机制中，地址的变换过程：

①CPU给出逻辑地址后，由硬件地址进行地址转换并将页号送入高速地址缓冲寄存器，并将此页号与快表中的所有页号进行比较。

②如果找到匹配的页号， 说明所要访问的页表项在块表中，则直接从中取出该页所对应的页框号，与页内偏移量拼接成物理地址。这样存取数据仅一次访存便可实现。

③如果没有找到，则需要访问主存中的页表，在读出页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表进行替换。

注意：有些处理机设计为块表和慢表同时查找，如果在块表中查找成功则终止慢表的查找。

一般块表的命中率可以达到90%以上，这样，分页带来的速度损失降低到10%以下。快表的有效性是基于局部性原理。这在后面的虚拟内存中将具体讨论。

（4）两级页表

第二个问题：由于引入了分页管理，进程在执行时不需要将所有页调入内存页框中，而只要将保存有映射关系的页表调入内存即可。但是我们仍然需要考虑页表的大小。以32位逻辑空间，页面大小4KB，页表项大小4B为例，若要实现进程对全部逻辑空间的映射，则每个进程需要（2^32/4KB）2^20,约100万个页表项。也就是说，每个进程仅页表这一项就需要4MB主存空间，这显然是不切合实际的。

而即便不考虑对全部逻辑地址空间进行映射的情况，一个逻辑地址空间稍大的进程，其页表大小也可能是过大的。

①进程举例(全部放入内存)

以一个40MB的进程为例，页表项共40KB(40MB/4KB*4B)，如果将所有页表项内容保存在内存中，那么需要（40KB/4KB）10个内存页框来把保存整个页表。整个进程大小约为（40MB/4KB）1万个页面，而实际执行时只需要几十个页面进入内存页框就可以运行，但如果要求10个页面大小的页表必须全部进入内存，这相对实际执行的几十个进程页面的大小来说，肯定是降低了内存利用率的；从另一方面来讲，这10页的页表项也并不需要同时保存在内存中，因为大多数情况下，映射所需要的页表项都在页表的同一页面中。

解决方案：

为了压缩页表，我们将页表映射的思想进一步延伸，就可以得到二级分页，即使用层次结构的页表：将页表的10页空间也进行地址映射，建立上一级页表，用于存储页表的映射关系。这里对页表的10个页面进行映射只需要10个页表项，所以上一级页表只需要1页就足够（可以存储2^10=1024个页表项）。在进程执行时，只需要将1页的上一级页表调入内存即可，进程的页表和进程本身的页面，可以在后面的执行中再调入内存。

②系统举例（页表理论占用最大内存）

以上面提到的条件：32位逻辑地址空间、页面大小4kB、页表项大小4B，以字节为编址单位，我们就这个条件来构造一个合适这个条件的页表结构。页面大小为4KB,则页内偏移址为log2 4K=12位，页号部分为20位，若不采用分级页表，那么光页表就要占用2^20*4B/4KB=1024页（页框），而这大大超过了许多进程自身需要的页面，对于内存来说是非常浪费资源的，而且查询页表工作也变得十分不便，试想若把这些页表放在连续的空间中，查询对应的物理页号的时候可以通过页表首页地址+页号*4B的形式得到，而这种方法查询起来虽然相对方便，但是连续的1024页对于内存的要求实在太高，并且上面说到了其中大多数页面都是不会用到的，所以这种方法并不具有可行性。

解决方案：

如果不把这些页表放在连续的空间中，我们就需要一张索引表来告诉我们第几张应该去哪找，这就能解决页表的查询问题，并且不用把所有的页表都调入内存，只有需要它的时候才调入（虚拟存储器思想），这就能解决占用内存空间过大的问题。

你也许会发现了这个方案和当初引进页表机制的方式一模一样，实际上就是构建一个页表的页表，也就是二级页表。为了查询的方便，顶级页表大小设立一个页面，那么顶级页表共可以容纳4KB/4B=1K个页表项，则它占用的地址位数为log2 1K=10位，而之前计算过页内偏移地址占用了12位，那么32位的逻辑地址空间就剩下10位，正好使得二级页表的大小在一页之内，这样我们就得到了路基地址空间的格式：

二级页表实际上就是在原有页表结构上再加了一层页表

建立多级页表的目的在于建立索引，这样不用浪费主存空间去存储无用的页表项，也不用盲目地顺序式查找页表项，而建立索引的要求是最高一级页表项不超过一页的大小。