笔法较为粗糙，渐行渐改正，有错误望指出，有新的理解方法欢迎讨论。

离散分配方式

连续分配容易造成很多碎片，虽然可以通过紧凑的算法来将碎片拼接成可用的大块空间，但必须付出很大的开销。如果允许一个进程直接分散的装入很多不相邻的分区，则无需紧凑，即离散分配方式。如果离散分配的基本单位是页，称为分页储存管理方式；如果离散分配及基本单位是段，称为分段存储管理方式。本文主要讨论分页存储。

分页储存管理方式

分页存储管理是解决存储碎片的一种方法。
动态重定位是解决存储碎片问题的一种途径，但要移动大量信息从而浪费处理机时间,代价比较高,这是因为这种分配要求把作业必须安置在一连续存储区内的缘故,而分页存储管理正是要避开这种连续性要求。

页面与页表

页面

相对物理块来说，页是逻辑地址空间（虚拟内存空间）的划分，是逻辑地址空间顺序等分而成的一段逻辑空间，并依次连续编号。页的大小一般为 512B~8KB。

例如：一个 32 位的操作系统，页的大小设为 $$2^{12}=4Kb$$ ，那么就有页号从 0 编到$2^{20}$的那么多页逻辑空间。

物理块

物理块则是相对于虚拟内存对物理内存按顺序等大小的划分。物理块的大小需要与页的大小一致。

例如：$2^{31}$=2Gb 的物理内存，按照 4Kb/页的大小划分，可以划分成物理块号从 0 到 $2^{19}$ 的那么多块的物理内存空间。

逻辑地址结构

页式存储管理中，逻辑地址可以解读成页号+地址偏移量（页内地址）。如下图所示：

这是一个 32 位的逻辑地址，页大小设为 $2^{12}$=4Kb。高 20 位则是页号，低 12 位则是页内地址。逻辑地址为 A，页面大小为 L，则页号 P 和页内地址 d 计算公式如下：

页表

页表是记录逻辑空间（虚拟内存）中每一页在内存中对应的物理块号。但并非每一页逻辑空间都会实际对应着一个物理块，只有实际驻留在物理内存空间中的页才会对应着物理块。
页表是需要一直驻留在物理内存中的（多级页表除外），另外页表的起址和长度存放在 PCB（Process Control Block）进程控制结构体中。

逻辑地址到物理地址的变换过程

1. 进程访问某个逻辑地址时，分页地址机构自动将逻辑地址分为页号和页内地址

2. 页号大于页表长度，越界错误

3. 页表项的地址 p = 页表起始地址 F + 页号 P * 表项大小 S，从而得到对应的物理块号 B

4. 页和物理块的大小是一致的，所以 页内地址=块内地址

5. 然后 物理地址 = 物理块号 B * 页大小 L + 页内地址

6. 根据物理地址读取数据

例：某系统采用分页式存储管理，页大小为 2KB。已知进程 A 的逻辑地址空间为 4 个页，内存分配如下页表所示，求逻辑地址 4832 的物理地址。（所有数据都是十进制）

解：

2KB=2048B

页号 P=逻辑地址/页大小=4832/2048=2

页内地址 F=逻辑地址%页大小=4832%2048=736

根据页表查得 2 号页对应着 25 号物理块

物理地址 A=物理块号页大小 + 页内地址=252048+736=51936

快表(TLB，Translation Look aside Buffer)

快表是为了加快虚拟地址到物理地址这个转换过程而存在的。页式存储管理的快表一般存放在 CPU 内部的高速缓冲存储器 Cache。快表与页表的功能类似，其实就是将一部分页表存到 CPU 内部的高速缓冲存储器 Cache。CPU 寻址时先到快表查询相应的页表项形成物理地址，如果查询不到，则到内存中查询，并将对应页表项调入到快表中。但，如果快表的存储空间已满，则需要通过算法找到一个暂时不再需要的页表项，将它换出内存。因为高速缓冲存储器的访问速度要比内存的访问速度快很多，因此使用可以大大加快虚拟地址转换成物理地址。根据统计，快表的命中率可以达到 90%以上。

一级页表的缺陷

由于页表必须连续存放，并且需要常驻物理内存，当逻辑地址空间很大时，导致页表占用内存空间很大。
例如，地址长度 32 位，可以得到最大空间为 4GB，页大小 4KB，最多包含 4G/4K=1M 个页。若每个页表项占用 4 个字节，则页表最大长度为 4MB，即要求内存划分出连续 4MB 的空间来装载页表；若地址程度为 64 位时，就需要恐怖的 4*$2^{52}$Byte 空间来存储页表了。而且页表采用的是连续分配，不是分页分配。
采用离散分配方式的管理页表，将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。

两级

现代的大多数计算机系统，都支持非常大的逻辑地址空间($2^{32}$～$2^{64}$)。在这样的环境下，页表就变得非常大，要占用相当大的内存空间。例如，对于一个具有32位逻辑地址空间的分页系统，规定页面大小为4 KB，则在每个进程页表中的页表项可达1兆个之多。又因为每个页表项占用四个字节，故每个进程仅仅其页表就要占用4 MB的内存空间，而且还要求是连续的。显然这是不现实的，我们可以采用下述两个方法来解决这一问题：

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

两级页表(Two-Level Page Table)
对于要求连续的内存空间来存放页表的问题，可利用将页表进行分页，并离散地将各个页面分别存放在不同的物理块中的办法来加以解决，同样也要为离散分配的页表再建立一张页表，称为外层页表(Outer Page Table)，在每个页表项中记录了页表页面的物理块号。下面我们仍以前面的32位逻辑地址空间为例来说明。当页面大小为 4 KB时(12位)，若采用一级页表结构，应具有20位的页号，即页表项应有1兆个；在采用两级页表结构时，再对页表进行分页，使每页中包含2^10 (即1024)个页表项，最多允许有2^10个页表分页；或者说，外层页表中的外层页内地址P2为10位，外层页号P1也为10位。此时的逻辑地址结构可描述如下：

由下图可以看出，在页表的每个表项中存放的是进程的某页在内存中的物理块号，如第0#页存放在1#物理块中；1#页存放在4#物理块中。而在外层页表的每个页表项中，所存放的是某页表分页的首址，如第0#页表是存放在第1011#物理块中。我们可以利用外层页表和页表这两级页表，来实现从进程的逻辑地址到内存中物理地址间的变换。

为了地址变换实现上的方便起见，在地址变换机构中同样需要增设一个外层页表寄存器，用于存放外层页表的始址，并利用逻辑地址中的外层页号，作为外层页表的索引，从中找到指定页表分页的始址，再利用
P2作为指定页表分页的索引，找到指定的页表项，其中即含有该页在内存的物理块号，用该块号和页内地址d即可构成访问的内存物理地址。右图示出了两级页表时的地址变换机构。

多级页表

对于32位的机器，采用两级页表结构是合适的；但对于64位的机器，采用两级页表是否仍可适用的问题，须做以下简单分析。如果页面大小仍采用4 KB即$2^{12}$B，那么还剩下52位，假定仍按物理块的大小($2^{12}$位)来划分页表，则将余下的42位用于外层页号。此时在外层页表中可能有4096 G个页表项，要占用16 384 GB的连续内存空间。这样的结果显然是不能令人接受的，因此必须采用多级页表，将外层页表再进行分页，也就是将各分页离散地装入到不相邻接的物理块中，再利用第2级的外层页表来映射它们之间的关系。
对于64位的计算机，如果要求它能支持$2^{64}$B(= 1 844 744 TB)规模的物理存储空间，则即使是采用三级页表结构也是难以办到的；而在当前的实际应用中也无此必要。故在近两年推出的64位OS中，把可直接寻址的存储器空间减少为45位长度(即$2^{45}$)左右，这样便可利用三级页表结构来实现分页存储管理。
多级页表和二级页表是为了节省物理内存空间。使得页表可以在内存中离散存储。（单级页表为了随机访问必须连续存储，如果虚拟内存空间很大，就需要很多页表项，就需要很大的连续内存空间，但是多级页表不需要。）

反置页表

反置页表的提出

之所以叫做 反置 页表，大概是因为它颠倒我们常规理解的寻址：

根据地址拿到数据，在MMU意义上就是根据虚拟地址拿到物理地址。

而反置页表将上述问题转换成了：

给出一个虚拟地址，试问有没有哪个物理页面映射了它，如果有，找出来。

基于反置页表的地址转换过程

注：反置页表全OS只有一个，外部页表每个进程一个。

根据进程标识符和页号检索反置页表，若能找到匹配项，就根据该项的编号找到对应物理块，再根据页内偏移生成物理地址，最后将地址送入地址寄存器；若找不到匹配项，表示该页不在内存，提示出错（无请求调页功能的系统）或调入该页（有请求调页功能的系统从外部页表）。
参考：https://www.tomorrow.wiki/archives/334
https://baike.baidu.com/item/%E5%9F%BA%E6%9C%AC%E5%88%86%E9%A1%B5%E5%AD%98%E5%82%A8%E7%AE%A1%E7%90%86%E6%96%B9%E5%BC%8F

相关例题：

1，某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为$2^{10}$B，页表项大小为2B，逻辑地址结构为：

页目录号	页号	页内偏移量

逻辑地址空间大小为$2^{16}$页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是（）。
A，64　　　　　　　　　　　　　　　　B，128
C，256　　　　　　　　　　　　　　　D，512
answer：　页大小为$2^{10}$B，页表项大小为2B，故一页可以存放$2^9$个页表项，逻辑地址空间大小为$2^{16}$页，即共需$2^{16}$个页表项，则需$2^{16}$/$2^9$=$2^7$=128个页面保存页表项，即页目录表中包含表项的个数至少是128。
2、考虑一个由8个页面，每页1K字节组成的逻辑空间，把它映射到由32个物理块组成的存储器。问:
1.有效的逻辑地址有多少位?
2.有效的物理地址有多少位?
解此题的关键是要知道在分页管理中，页”和“块”是一样大小的，这样才知道物理存储器是32K。

(1)逻辑地址有13位(2)物理地址有15位

3、考虑一个分页存储器，其页表存放在内存。
(1)若内存的存取周期为0.6us，则CPU从内存取条指令(或一个操作数)需多少时间?
(2)若使用快表且快表的命中率为75%， 则内存的平均存取周期为多少?
假定访问快表的时间可以忽略不计
(1)因为页表放在内存，故取一条指令(或一个操作数)须访问两次内存，所以需0.6usX2 = 1 .2us的时间。
(2)这里假定访问快表的时间可以忽略不计，命中快表时取数只要一次访存，故此时的平均存取周期为.0.6usX 0.75+1.2usX (1-0.75)=0.75us
关键:要知道访问快表的时间可以忽略不计和平均存.取周期的概念。

4.在分页存储管理系统中，逻辑地址的结构长度为18位，其中11 ~ 17位表示顽号，0~ 10位表示顽内偏移量。
若有一个作业的各页依次放入2、3、7号物理块中，试问: .
(1)进程逻辑地址空间最大可为多少KB?分为多少页?每页有多大?
(2) 逻辑地址1500应在几号页内?对应的物理地址是多少?
解:在该页表中，有3个页表项,分别为(0,2)、 (1,3)、 (2,7)。
(1)由于逻辑地址共有18位, 所以最大的逻辑地址空间为$2^{18}$B=256KB。 采用0 ~ 10位表示页内偏移量，所以页面大小L=$2^{11}$B，每块大小=页面大小=$2^{11}$B,则页面总数=$2^{18}$/$2^{11}$=128页。
(2)逻辑地址A=1500,对应页号=(int)(1500/$2^{11}$)=0, 页内偏移量W=1500。查找页表可知对应的物理块号为2,所以，对应的物理地址E=2x$2^{11}$+ 1500=5596。

5, 某系统采用分页存储管理方式，设计如下:页面大小为4KB,允许用户虚地址空间最大为16页，允许系统物理内存最多为512个内存块。试问该系统虚地址寄存器和物理地址寄存器的长度各是多少位?
解:页面大小L =4KB=$2^{12}$字节，即页内偏移量占12位。由于物理块大小等于页面大小，所以物理块大小为$2^{12}$字节,物理块位数占12位。
允许用户虚地址空间最大为16页=24页，即页号占4位。
允许系统物理内存最多为512个内存块=$2^9$个内存块，即内存块位数占9位。

虚地址寄存器位数=页号位数+页内偏移量位数=4+12= 16位。
物理地址寄存器位数=物理块位数+内存块位数=12+9=21位。