#操作系统 连续分配，为用户进程分配的必须是一个连续的内存空间。 非连续分配，为用户进程分配的可以是一些分散的内存空间。连续分配方式已经在上一节部分完成。非连续分配有以下几种方式：
- 基本分页存储管理；
- 基本分段存储管理；
- 段页式存储管理。
操作系统，将内存空间分为一个个大小相等的分区（比如：Linux系统的每个分区4KB），每个分区就是一个页框（page frame，又称页帧、内存块、物理块、物理页面）。每个页框有一个编号，即页框号（page frame number，又称页框号、页帧号、内存块号、物理块号、物理页号），页框号从0开始。 将进程的逻辑地址空间（logical memory）也分为与页框大小相等的一个个部分， 每个部分称为一个页或页面（page）。每个页面也有一个编号， 即页号（page number），页号也是从0开始。 操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中。也就是说，进程的页面与内存的页框有一一对应的关系。 各个页面不必连续存放，可以放到不相邻的各个页框中。
但是，进程的最后一个页面可能没有一个页框那么大，也就是说，分页存储有可能产生内部碎片，因此页框不能太大，否则可能产生过大的内部碎片造成浪费。
为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表。页表，通常存在PCB（进程控制块）中。对于页表这样的数据结构而言：
- 一个进程对应一张页表；
- 进程的每个页面对应一个页表项；
- 每个页表项由“页号”和“块号”组成；
- 页表记录进程页面和实际存放的内存块之间的映射关系；
- 每个页表项的长度是相同的。
- 进程页表的页表项，在内存中时连续存放的。
在进程内存连续存放的时候，操作系统如何实现逻辑地址到物理地址的转换的，关于这一点在之前的部分已经有解释过，使用的是地址重定位技术，将逻辑地址与偏移量相叠加，即可得到真正的存储地址。
当前使用分页存储的时候，由逻辑地址到物理地址的转化，又是一件不一样的事情了。但是，虽然进程的各个页面是离散存放的，页面内部确实是连续存放的。
首先，有一个问题，对于某系统物理内存大小为4GB，页面（page）大小为4KB，则每个页表项至少应该为多少字节？
4GB / 4KB = 2^20. 因此为了给这2^20个页面标识地址，需要20bit的容量，作为标识。那么对于每一个页面内部的某一个地址，则需要2^12个位置，这是用于标识页内部的具体某一个地址位置的信息，这叫做页偏移量。
如果要访问逻辑地址A，则需要：
- 确定逻辑地址A（0x00018004）对应的“页号”P（0x00018）；
- 找到P号页面在物理内存中的起始地址，这里需要查页表，查得0x002000；
- 确定逻辑地址A的“页内偏移量”W（0x004），其中逻辑地址A对应的物理地址（0x0020004）= P号页面在内存中的起始地址（0x0020000）+页内偏移量W（0x004）。
在上图中，偏移量总是相对的，所以在逻辑地址和物理地址的转化过程中，偏移量总是不变的。
基本地址变换机制（paging translation mechanism），之所以叫基本，是针对于下一节中的快表而言。 这一转换依赖一个页表寄存器（paging table register）来实现，可以借助进程的页表将逻辑地址转换为物理地址。
进程在CPU上执行，操作系统中在内存系统区中的PCB中会保存程序运行的一系列信息，CPU中设置了一个页表寄存器（PTR），存放了页表在内存中的起始地址F（其实就是一个指针）和页表长度M（页表长度就是页表中的表项个数，即有多少对逻辑地址和物理地址的映射关系）。进程未执行时，页表的始址和页表长度放在进程控制块（PCB）中，当进程被调度时，操作系统内核会把它们放到页表寄存器中。
- 根据逻辑地址计算出页号、页内偏移量；
- 比较页号和页表长度，判断页号是否越界；
- 不越界，偏移页号可以查询相应页表，找到页号对应的页表项，确定页面存放的内存块号，映射物理内存；
- 用内存块号和页内偏移量得到物理地址；
- 访问目标内存单元。
快表，又称联想寄存器（TLB， translation lookaside buffer），是一种访问速度比内存快很多的高速缓存（cache，TLB不是内存），用来存放最近访问的页表项的副本，可以加速地址变换的速度。与此对应，内存中的页表常称为慢表。
有了快表之后，地址转换过程如下：
- CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
- 如果找到匹配的页号（快表命中），说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。
- 如果没有找到匹配的页号（快表未命中），则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表未命中，则访问某个逻辑地址需要两次访存（注意：在找到页表项后，应同时将其存入快表，以便后面可能的再次访问。但若快表已满，则必须按照一定的算法对旧的页表项进行替换）。
由于查询快表的速度比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。 因为局部性原理，一般来说快表的命中率可以达到 90% 以上。
什么是局部性原理呢？局部性分为事件局部性和空间局部性：
- 时间局部性，指如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问。（因为程序中存在大量的循环）
- 空间局部性，指一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的） 之前提及的基本地址变换机制中，每次要访问一个逻辑地址，都需要查询内存中的页表。由于局部性原理，可能连续很多次查到的都是同一个页表项。因此时间比使用快表会长的多。
- 问题一：页表必须连续存放，因此当页表很大时，需要占用很多个连续的页框。
- 问题二：没有必要让整个页表常驻内存，因为进程在一段时间内可能只需要访问某几个特定的页面。 以下以一个具体场景来说明情况。
【场景说明】某计算机系统按字节寻址，支持 32 位的逻辑地址，采用分页存储管理，页面大小为4KB，页表项长度为4B。
- 4KB = 2^12B，因此页内地址要用12位表示，剩余 20 位表示页号。 因此，该系统中用户进程最多有 2^20 页(极端情况，占满了所有的内存空间)。
- 相应的，一个进程的页表中，最多会有2^20 = 1M = 1,048,576 个页表项，所以一个页表最大需要 2^20 * 4B = 2^22 B，共需要 2^22/2^12 = 2^10个页框存储该页表。
- 根据页号查询页表的方法，K 号页对应的页表项存放位置 = 页表始址 + K * 4 ，要在所有的页表项都连续存放的基础上才能用这种方法找到页表项。
但是，根据局部性原理可知，很多时候，进程在一段时间内只需要访问某几个页面 就可以正常运行了。因此没有必要让整个页表都常驻内存。
如何解决这样的问题呢？这里就是得用到套娃的思想了，类似于“二阶导数”。我们可以把页表再分页并离散存储，然后再建立一张页表记录页表各个部分的存放位置，称为页目录表（或称外层页表、顶层页表、根页表）。
在两级页表的架构下，如何实现从逻辑地址到物理地址的转化呢？
- 按照地址结构将逻辑地址拆分成三部分（一级页号、二级页号、页内偏移）；
- 从PCB中读出页目录表始址，再根据一级页号查页目录表，找到下一级页表在内存中的存放位置；
- 根据二级页号查二级页表，找到最终想访问的内存块号；
- 结合页内偏移量得到物理地址。
可以在需要访问页面时才把页面调入内存（这里，采用的是虚拟存储技术，其实就是借助外存的空间暂存内存页表）。这时可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存。
这时，若想访问的页面不在内存中，则产生缺页中断（内中断/异常），然后将目标页面从外存调入内存。
若分为两级页表后，页表依然很长，则可以采用更多级页表，一般来说各级页表的大小不能超过一个页面（说直白点，就是分拆出来的子页表段，必须得放进一个内存块里面）。
【问题】例如，某系统按字节编址，采用 40 位逻辑地址（这值很大了），页面大小为 4KB，页表项大小为 4B，假设采用纯页式存储，则要采用几级页表，页内偏移量为多少位？
- 页面大小 = 4KB =2^12B，按字节编址，因此页内偏移量为12位;
- 页号 = 40 - 12 = 28 位,
- 页面大小 = 2^12B，页表项大小 = 4B ，则每个页面可存放 2^12 / 4 = 2^10 个页表项，
- 因此各级页表最多包含 2^10 个页表项，需要 10 位二进制位才能映射到 2^10 个页表项，因此每一级的页表对应页号应为10位。
- 结论，总共28位的页号至少要分为三级。
- 第一次访存：访问内存中的页目录表；
- 第二次访存：访问内存中的二级页表；
- 第三次访存：访问目标内存单元。