内存分页机制

引言

• 一个问题：随着应用程序越来越多，导致程序无法全部加载入内存，如何解决？
• 解决办法：内存分页机制

内存为什么要分页

• 我们先来回顾一下一直以来所学习的保护模式下的内存分段机制
• 通过段描述符的方式，硬件可对段式内存进行直接管理
• 思考：按段加载（局部性原理）是否可以解决引言中所说的问题？

• 只将当前程序运行所需要的段加载进内存
• 当某个段不再使用时，从内存中移除

• 答案：可以起到一定的作用，但依旧很大缺陷
• 原因：

• 段的大小不确定，可能大于实际物理内存
• 段加载时需要具体的长度信息，不同的段长度不同，要是遇到段很大，那就需要加载很长时间，等加载结束再运行程序，从程序运行效率上讲这么设计也不合理

段式内存管理原理

• CPU 允许在描述符表中已注册的段不在内存中存在，如果该描述符中的 P 位为 1，表示该段在内存中存在，可以执行。如果 P 位为 0，说明内存中并不存在该段，这时候 CPU 将会抛出个 NP（段不存在）异常，转而去执行中断描述符表中 NP 异常对应的中断处理程序，此中断处理程序是操作系统负责提供的，该程序的工作是将相应的段从外存（比如硬盘）中载入到内存，并将段描述符的 P 位置 1，中断处理函数结束后返回，继续执行。
• 以上是 CPU 加载内存段的过程，内存段是何时移出到外存上的呢？
• 当 CPU 访问一个段时，该段的段描述符的 A 位由 CPU 置 1，但清 0 工作可是由操作系统来完成的。此位干干嘛用的呢？如果仅仅用来表示该段被访问过，这也意义不大啊。其实这正是软件和硬件相互配合的体现，操作系统每发现该位为 1 后就将该位清 0，这样一来，在一定周期内统计该位为 1 的次数就知道该段的使用频率了，从而可以找出使用频率最低的段。当物理内存不足时，可以将使用频率最低的段换出到硬盘，以腾出内存空间给新的进程

什么是内存分页

• 内存分页机制不是完全抛弃内存分段机制，而是在分段的基础上再进行分页
• 将整个段内存按照固定的大小划分成很多个页，一页的大小为 4K（也可以是别的大小）
• 每个段可由一个或多个内存页组成
• 页是进行内存管理的基本单元

初识虚拟地址映射

• 页的出现解决了物理内存不足的问题
  
• 之前保护模式下使用的都是线性地址，只不过没有特别的说明那是线性地址
  
• 线性地址的概念：保护模式下地址空间虽然到达了前所未有的 4GB，但其依然是受限制的，此进程要和其他进程包括操作系统共享这 4GB 内存空间，我们把段基址+段内偏移地址称为线性地址，线性地址是唯一的，只能属于某一个进程。
  
• 线性地址与物理地址一一对应，怎么去打破这种对应关系，使得逻辑上连续的线性地址其对应的物理地址可以不连续
  
• 于是，虚拟地址和虚拟地址映射被创造出来了
  
• 线性地址空间（逻辑地址）：程序执行时内部所使用的内存空间（独立于其它程序）
  
• 逻辑地址需要进行转换才能得到对应的物理地址
  
• 页式内存管理中的地址

• 地址 = 页号 + 页内偏移
• 逻辑地址 = 逻辑页号 + 页内偏移
• 物理地址 = 物理页号 + 页内偏移
• 地址转换时只变更页号即可，页内偏移不变

• 逻辑地址到物理地址的映射（重定位）

• 由于软件映射执行效率太慢，于是 CPU 提供了硬件映射支持
• 在 CPU 实现中，这种映射关系是通过一张表来实现的，该表就是我们所说的页表，查找页表的工作也是由硬件完成的
• 逻辑地址 -> 查表（硬件行为） -> 物理地址

• 对比看一下分段机制和分页机制的区别
  
  
• 以图形的方式来直观体会分页机制的思想是：通过映射，可以使连续的线性地址与任意物理内存地址相关联，逻辑上连续的线性地址其对应的物理地址可以不连续
  
  
• 在开启了分页机制后，线性地址已经不再是原先我们学习的 CS:EIP 地址，该地址被认为是虚拟地址。下面我们如果说线性地址的话就统一当成虚拟地址处理好了，即可以理解为开启了分页机制后线性地址=虚拟地址
  

一级页表

• 页表其实就是一个一维数组，其存储着线性地址到物理地址的映射关系。这个数组中的每一个元素都我们又称之为页表项（Page Table Entry，PTE）。页表项的作用是存储内存物理地址，大小为 4 字节，当访问一个线性地址时，实际上就是在访问页表项中所记录的物理内存地址
• 一页大小为 4KB，4GB 地址空间最多可以被划分成 4GB/4KB=1M(1048576) 个页
• 下图是页表与物理内存关系示意图

一级页表线性地址与物理地址之间的转换

• 有了页表的整体概念，那么继续深入思考：一个 32 位的线性地址如何具体映射到实际物理内存上的呢？
  
• 我们将 32 的线性地址分成两个部分，高地址（bit12-bit31）表示内存块（页表）数量，低地址（bit0-bit11）表示内存块（页表）尺寸大小
  
  
• 内存块（页）数量为 2 的 20 次方，即 1MB；内存块（页）尺寸大小为 2 的 12 次方，即 4KB。同样这 20 位也用来索引一个页（索引范围 0～0xfffff）
  
• bit0-bit11 位用来表示页的大小，也就是这 12 位可以作为页内寻址（页内偏移）
  
• 先用高 20 位定位哪一页，再用低 12 位定位该页中的偏移地址，于是，真正的物理地址就找到了。哈哈哈，是不是感觉设计的很巧妙？
  
• 咱们还是通过例子来理解线性地址到物理地址转换过程吧，假设程序中使用了线性地址 0x1234，那么该地址对应的实际物理地址是多少呢？
  
  
• 0x1234 的高 20 位值为 1，将该值作为数组索引（将上图一级页表看成一个数组，由下向上），于是从一级页表中我们可以找到对应的地址是 0x9000，低 12 位值位 0x234，它作为物理页的页内偏移地址与物理页地址 0x9000 相加，和为 0x9234，这就是线性地址 0x1234 最终转换成的物理地址
  

二级页表

• 有了一级页表，为啥还需要二级页表呢？

• 一级页表中最多可容纳 1M（1048576）个页表项，每个页表项是 4 字节，如果页表项全满的话，便是 4MB 大小
• 一级页表中所有页表项必须要提前建好，原因是操作系统要占用 4GB 虚拟地址空间的高 1GB，用户进程要占用低 3GB
• 页表并不是只有一个，而是每个进程都有自己的页表，进程一多，光是页表占用的空间就很大了

• 归根结底，我们要解决的是：不要一次性地将全部页表项建好，需要时动态创建页表项
  
• 二级页表就能很好的解决这些问题
  
• 无论是几级页表，标准页的尺寸都是 4KB，这一点是不变的。所以 4GB 线性地址空间最多有 1M 个标准页。一级页表是将这 1M 个标准页放置到一张页表中，二级页表是将这 1M 个标准页平均放置 1K 个页表中。每个页表中包含有 1K 个页表项。页表项是 4 字节大小，页表包含 1K 个页表项，故页表大小为 4KB，这恰恰是一个标准页的大小
  
• 拆分出了这么多个页表，如何使用它们呢？为此，专门有个页目录表来存储这些页表。每个页表的物理地址在页目录表中都以页目录项（Page Directory Entry， PDE）的形式存储，页目录项大小同页表项一样，都用来描述一个物理页的物理地址，其大小都是 4 字节，而且最多有 1024 个页表，所以页目录表也是 4KB 大小，同样也是标准页的大小
  
• 无论是页表还是页目录表，其本身也要占用内存
  
  
• 如上图所示，页目录表中共 1024 个页表，也就是有 1024 个页目录项。一个页目录项中记录一个页表物理页地址，物理页地址是指页的物理地址，在页目录项及页表项中记录的都是页的物理地址，页大小都是 0x1000，即 4096，因此页地址是以 000 为结尾的十六进制数字。每个页表中有 1024 个页表项，每个页表项中是一个物理页地址，最终数据写在这页表项中指定的物理页中。页表项中分配的物理页地址在真正物理内存中离散分布，毫无规律可言，操作系统负责这些物理页的分配与释放
  
• 由于页目录表和页表本身都要占用内存，且为 4KB 大小，故它们也会由操作系统在物理内存中分配一物理页存放。图中最粗的线存放页目录表物理页，稍细一点的线指向的是用来存放页表的物理页，其他最细的线是页表项中分配的物理页
  
• 页表结构本身与其他数据混布渗透在物理内存中，页表所占用的物理页在外在形式上与其他数据占用的物理页没有什么不同，只有 CPU 知道它们的作用不同
  
• 页目录表中的页目录项也可以为空，一个页目录项为空意味着可以少分配一个页表自身的（4K）的内存空间，即不需要一次性将所有页表都创建好（浪费内存）。如果一个页表已经被创建，当该页表中的页表项全部为空时我们就可以将该页表自身所处的 4K 内存空间释放。
  

二级页表线性地址与物理地址之间的转换

• 前面所说的一级页表转换方法，是将 32 位线性地址拆分成两部分，高 20 位用于定位一个物理页，低 12 位用于物理页内的偏移量。在二级页表转换中，依然用 32 位线性地址的不同部分来定位物理页
  
• 页目录中有 1024 个页目录项，页表中也有 1024 个页表项，只需要 10 位二进制就能够表示了，于是，线性地址的高 10 位（第 31～22 位）用来在页目录中定位一个页表，线性地址的中间 10 位（第 21～12 位）用来在页表中定位具体的物理页，余下的低 12 位依旧用于页内偏移量
  
• 举个例子：假设程序中使用了线性地址 0x1234567，那么该地址对应的实际物理地址是多少呢？
  
  
• 首先，我们把 0x1234567 转成二级制 00000001001000110100010101100111，将其分成高 10 位（0000000100，0x4），中 10 位（1000110100，0x234），低 12 位（0101 0110 0111， 0x567）
  
• 我们把页目录和页表都看成一维数组， 高 10 位和低 10 位的值我们可以把它看成数组的下标，而该数组每个元素占 4 个字节，数组首地址 + 数组下标*每个元素占的字节就可以找到某个数组元素所处的地址
  
• 页目录物理首地址存储在 cr3 寄存器中
  
• 根据高 10 位 0x4 在页目录中找到第 4 个元素，其内值为 0x1000
  
• 拿到 0x1000 这个地址后我们再跳到物理内存 0x1000 处，以 0x1000 当作数组首地址，找到下标为 0x234 的数组元素，发现其内值为 0xfa000，于是我们再跳转到物理内存 0xfa000 地址处，加上低 12 位 0x567，最终得到地址 0xfa000，这个地址就是实际的物理地址
  

进程与页表

• 每个进程都有自己的页表，每个进程都以为自己独占整个 4G 内存空间
  
  
• 进程切换时，页表也跟着切换，这个后面再细说
  

页交换

• 思考一个问题：物理内存空间是有限的，随着任务进程越来越多，越来越复杂，物理内存被用完了怎么办？
• 答案就是页交换，什么是页交换呢？
• 既然物理内存不够了，那我们就将一个页内存块中的数据写到外部存储设备中，然后将该页释放出来以供新的申请使用，当需要使用到该页的原内容时，再从外部存储设备读取出来放到新申请的内存页中以供使用
• 问题又来了：页交换时如何选择需要交换的内存页呢？
• 原则：挑选不再使用的内存页
• 方法有很多种，这里我们说一下 LRU 算法，即统计一定周期内页使用的次数，将使用次数最少的页交换出来
• 当然，你或许会说之前使用少不代表之后使用不频繁啊，那也没办法，操作系统不可能知道未来所发生的事情，只能用统计过去的方式来预测未来

页目录项与页表项结构

• 一直都说它们是 4 字节大小，用来存储物理页地址，但一直 未曾见过它们的真实面目。下面给大家呈上它们的结构
  
  
• 确实如之前所述，4 字节大小，但其内容并不全是物理地址，只有第 12～31 位才是物理地址，这才 20 位
  
• 按理说 32 位地址应该用 32 位来表示啊，为什么只用 20 位就够了？
  
• 原因：标准页大小是 4KB，于是我们要求物理页的起始地址必须 4K 字节对其，故地址都是 4K 的倍数，也就是地址的低 12 位都是 0，所以只需要记录物理地址高 20 位就可以啦。这样省出来的 12 位（第 0～11 位）可以用来添加其他属性啦
  
• 下面就对这些属性位一一进行介绍

• P，Present，意为存在位。若为 1 表示该页存在于物理内存中，若为 0 表示该表不在物理内存中。操作系统的页式虚拟内存管理便是通过 P 位和相应的 pagefault 异常来实现的
• RW，Read/Write，意为读写位。若为 1 表示可读可写，若为 0 表示可读不可写
• US，User/Supervisor，意为普通用户/超级用户位。若为 1 时，表示处于 User 级，任意级别（0、1、2、3）特权的程序都可以访问该页。若为 0，表示处于 Supervisor 级，特权级别为 3 的程序不允许访问该页，该页只允许特权级别为 0、1、2 的程序可以访问
• PWT，Page-level Write-Through，意为页级通写位，也称页级写透位。若为 1 表示此项采用通写方式，表示该页不仅是普通内存，还是高速缓存。此项和高速缓存有关，“通写”是高速缓存的一种工作方式，本位用来间接决定是否用此方式改善该页的访问效率。这里咱们直接置为 0 就可以啦
• PCD，Page-level Cache Disable，意为页级高速缓存禁止位。若为 1 表示该页启用高速缓存，为 0 表示禁止将该页缓存。这里咱们将其置为 0
• A，Accessed，意为访问位。若为 1 表示该页被 CPU 访问过啦，所以该位是由 CPU 设置的。还记得段描述符中的 A 位和 P 位吗？这两位在一起可以实现段式虚拟内存管理。和它们一样，这里页目录项和页表项中的 A 位也可以用来记录某一内存页的使用频率（操作系统定期将该位清 0，统计一段时间内变成 1 的次数），从而当内存不足时，可以将使用频率较低的页面换出到外存（如硬盘），同时将页目录项或页表项的 P 位置 0，下次访问该页引起 pagefault 异常时，中断处理程序将硬盘上的页再次换入，同时将 P 位置 1
• D，Dirty，意为脏页位。当 CPU 对一个页面执行写操作时，就会设置对应页表项的 D 位为 1。此项仅针对页表项有效，并不会修改页目录项中的 D 位
• PAT，Page Attribute Table，意为页属性表位，能够在页面一级的粒度上设置内存属性。比较复杂，将 此位置 0 即可
• G，Global，意为全局位。由于内存地址转换也是颇费周折，先得拆分虚拟地址，然后又要查页目录，又要查页表的，所以为了提高获取物理地址的速度，将虚拟地址与物理地址转换结果存储在 TLB（Translation Lookaside Buffer）中，TLB 以后咱们会细说。在此先知道 TLB 是用来缓存地址转换结果的高速缓存就 ok 啦。此 G 位用来指定该页是否为全局页，为 1 表示是全局页，为 0 表示不是全局页。若为全局页，该页将在高速缓存 TLB 中一直保存，给出虚拟地址直接就出物理地址啦，无需那三步骤转换。由于 TLB 容量比较小（一般速度较快的存储设备容量都比较小），所以这里面就存放使用频率较高的页面。顺便说一句，清空 TLB 有两种方式，一是用 invlpg 指令针对单独虚拟地址条目清理，或者是重新加载 cr3 寄存器，这将直接清空 TLB
• AVL，意为 Available 位，表示可用，谁可以用？当然是软件，操作系统可用该位，CPU 不理会该位的值，那咱们暂时也别研究这一位了