连续存储会产生许多的“碎片”，虽然“紧凑”方法可以将许多碎片拼接可以的大块空间，但开销大。

如果允许将一个进程直接分散的装入到许多不相邻的分区中，便可以充分利用内存空间。基于这一思想，产生了离散分配方法。根据在离散分配时所分配的地址空间的基本单位不同，将离散分配方法分为以下三种：

• 分页存储管理方式:该方法中，将用户程序的地址空间分为若干个固定大小的区域，成为“页”或者“页面”，典型的页面大小为1KB.相应的，也将内存空间分为若干个物理块或者叶框，页和块的大小相同，这样可将用户程序的任一页放入任一物理块中，实现离散分配。
• 分段存储管理方式：这种方法时为了满足用户的要求而形成的一种存储管理方式，它把用户程序的地址空间分为若干个大小不相同的段，每段可以定义一组相对完整的信息，在存储器分配时，以段为单位。这些段不相邻，同样也实现了离散分配。
• 段页式存储管理方式：这是分段和分页结合的产物。它具有两者的优点，是目前应用教广泛的一种存储管理方式。

分页存储管理的基本方法

1.页面和物理块

• 页面
  分页存储管理将进程的逻辑地址分为若干页。病对每个页进行编号，从0开始，如：第0页，第1页。相应的，把内存中的物理地址分为若干块，同时对他们进行编号，如0#，1#等。在内存分配时，以块为单位，将若干页面分别装入多个不相邻的物理块中。由于进程的最后一页经常装不满，就形成了不可利用的碎片，称为“页面碎片”

• 页面大小
  在分页系统中，页面过小，一方面可以减小内存碎片，有利于内存利用率提高。另一方面，会造成单个进程占有多个页面，从而导致进程的页面过长，占用大量内存，还会降低页面换进换出的效率。页面过大，可以减小页表长度，提高页面换进换出的速度，但使页面碎片过大。因此，页面的大小应该适中，且页面大小应该为2的幂。通常为1kb—8kb.
  2.地址结构
  分页地址中地址结构如下：
  
  两部分：前一部分为页号P，后一部分为位（偏）移量，即页内地址。0~11位页内地址，12 ~ 31位位页号，地址空间做多。
  

3.页表
在分页系统中，为了保证进程可以在内存中找到每个页面对应的物理块，系统为每一个进程建立了一张页面映像表，简称页表。在进程地址空间内的所有页，依次在页表中有一页表项，其中记录了相应页在内存对应的物理块号。如下图：

在分页系统中，常常会在页表的表项中设置一各存取控制字段，用于表示该存储块中的内容是允许读/写还是只读，以此来对该存储块中的内容加以保护。

地址变换机构

地址变化机构的任务是将逻辑地址中的页号转换为内存中的物理块号。
1.基本的地址变换机构
进程在运行期间，需要将用户地址空间中的逻辑地址变换为内存空间中的物理地址，由于它执行的频率非常高，每条指令的地址都需要进行变换，因此需要采用硬件来实现。页表功能是由一组专门的寄存器来实现的。但由于寄存器成本高，且大多计算机的页表又可能很大，不可能用一个寄存器完成。

因此，页表大多驻留在内存中，在系统中只设置一个页表寄存器，在其中存放页表在内存中的的始址和页表的长度。在进程未执行时，这两个数据存在进程的PCB中，当操作系统调度该进程时，再讲这两个数据装入页表寄存器中。因此。单处理机环境中，虽然系统可以允许多个进程，但只需要一个页表寄存器。

转换过程
当进程要访问某个逻辑地址中的数据时，分页地址变化机构会自动将有效地址分为页号和页内地址两部分，再以页号为索引去检索页表。查找操作由硬件执行。执行前，将页号和页表长度进行比较，查看是否出现越界错误，如果出现则产生地址越界中断，若未出现，则将表页始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可以得到该块的物理块号，将之装入物理地址寄存器中，与此同时，再将有有效地址寄存器中页内地址送入物理地址寄存器的块内字段中，这样就完成了从逻辑地址到物理地址的转变。

2.具有快表的地址变换机构
述方法需要访问两次内存，一次是访问页表，确定所存取数据或指令的物理地址，一次是根据该物理地址存取数据或者指令。显然这样的方法较慢。

为此我们可以在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器——快表，又称联想寄存器，用来存放当前访问的若干页表项，加速地址变换过程，命中率达到90%以上

• 由地址变换机构自动地将页号直接送入高速缓存寄存器，并将此页号与高速缓存中的所有页号进行比较，
• 若其中有此页号，便表示所要访问的页表项在快表找那个，可直接读取该也对应的物理块号，并送到物理地址寄存器
• 如在块表中为找到对应的页表项，则还需再访问内存中的页表，找到后把从页表项读出的物理块号送往地址寄存器，同时将此页表项存入快表的一个寄存器单元中。
• 如果联想寄存器已满，则OS必须找到一个老的且已被认为是不在需要的页表项，将它换出。
  
  块表不可能做很大，通常存放16~ 512个页表项。

访问内存的有效时间

内存的有效访问时间(Effective Access Time，EAT):从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所需要花费的总时间

假设访问一次内存的时间为t，在基本分页存储管理方式中，有效访问时间为:EAT = t + t = 2t

在引入快表的分页存储管理方式中，有效访问时间的计算公式即为;
$EAT=а×λ+(t+λ)(1—а)+t=2t+λ-t×а$EAT=а×λ+(t+λ)(1—а)+t=2t+λ−t×а
λ表示查找快表所需要的时间，а表示命中率，t表示访问一次内存所需要的时间。

两级和多级页表

现代系统大多都支持非常大的逻辑空间，在这种情况下，页表就变得非常大，要占用相当大的内存空间。为了解决这一问题，我们采用了两种方法来改进这个问题

• 对于页表所需要的内存空间，采用离散分配的算法。来解决难以找到一块连续的大内存问题
• 只将当前需要的部分页表项调入到内存，其余页表项仍驻留在磁盘上，需要时在调入。

1.两级页表
对难于找到大的连续的内存空间来存放页表的问题：

• 可利用将页表进行分页的方法，使每个页面的大小与内存物理块的大小相同,并为它们进行编号,即依次为0#页、1#页,.，n#页，然后离散地将各个页面分别存放在不同的物理块中。
• 也要为离散分配的页表再建立一张页表， 称为外层页表(Outer Page Table),在每个页表项中记录了页表页面的物理块号。
• 

虽然解决了对于大页表无需大片连续存储空间的问题，但并未解决用较少的内存空间去存放大页表的问题。
只用离散分配空间的办法并未减少页表所占用的内存空间。能够用较少的内存空间存放页表的唯一方法是， 仅把当前需要的一批页表项调入内存，以后再根据需要陆续调入。

2.多级页表
对于32位的机器，采用两级页表结构是合适的，但对于64位的机器，即使是采用三级页表结构也是很难办到的的，而当前的实际应用中也无此必要。故在进两年退出的64OS中，把可直接寻址的存储器空间减少为45位长度，便可以利用三级页表结构实现分页存储管理。

反置页表

1.反置页表的引入
1.反置页表的引入
为了减少页表占用内存的大小，引入了反置页表。

一般的页表的页表项是按照页号进行排序的。页表项中的内容是物理块号。而反置页表是为每一个物理块建立一个页表项，并将他们按照物理块的编号进行排序，其中内容是页号和其所隶属进程的标识符。

2.地址变换

在利用反置页表进行地址变换时，是根据进程标识符和页号，去检索反置页表。如果检索到与之匹配的页表项，则该页表项(中)的序号i便是该页所在的物理块号，可用该块号与页内地址一起构成物理地址送内存地址寄存器。若检索了整个反置页表仍未找到匹配的页表项，则表明此页尚未装入内存。对于不具有请求调页功能的存储器管理系统，此时则表示地址出错。对于具有请求调页功能的存储器管理系统，此时应产生请求调页中断，系统将把此页调入内存。

反置页表仅包含以调入内存的页面，并未包含未调入内存的页面，所以还应该为每个进程建立一个外部页表。