分页虚拟存储理论
0x00 很久之前
在很久之前，计算机使用单程序存储管理。
在这种管理模式下，每次只能运行一个程序。操作系统每次将相应的程序从磁盘加载到 RAM 中。直至进程运行结束后跳转到操作系统代码，操作系统再根据用户需求将程序装入 RAM 中，覆盖掉旧的程序。存在问题：
- 一次只能运行一个程序
- 进程（程序）的切换很慢
- 程序的大小取决于 RAM 物理内存的大小
事实上，后面又发展了多道程序，交换技术等技术来试图解决上述问题但效果不好，这里就不展开讲了，但为什么会讲一下单道存储管理，因为其与 Linux 虚拟存储空间布局很像，暂时无需知道什么是虚拟存储空间。
0x01 虚拟存储器 Virtual Memory
虚拟存储技术发展的根本原因：
RAM 小且昂贵，无论是上世纪还是当下，RAM 都是小且昂贵的资源，所以我们不得不充分利用，进而发展出虚拟存储技术。假设我们的 RAM 可以无限大且廉价。
虚拟存储的基础及事实：
- 局部性原理：程序在执行时呈现出局部性规律，即在一段时间内，整个程序的执行仅限于程序中的某一部分。这也意味着并不需要完全把程序加载到 RAM 也能保证程序的执行。
- 磁盘空间很大且足够便宜，可以把程序暂时不需要的那一部分放在磁盘上，把需要的那部分放在 RAM 上。
Virtual Memroy[1] 由 Fotheringham 在 1961 年提出[2]，其基本思想是：
- 程序的代码数据和栈的总大小可以超过物理内存（RAM）
- 操作系统将正在运行的程序的需要的那部分保留在内存中，而将当前不使用的部分放置在磁盘上，根据需要调入内存。
根据虚拟存储器实现的技术可以分为：
- 页式：采用 分页 Paging 技术
- 段式：采用 分段 Segmentation 技术
- 分页分段结合：Paged Segmentation
目前大多数虚拟存储管理系统都采用分页 paging 技术，本文也仅讲解分页存储管理。
0x02 分页基本思想
- 将物理内存划分为为许多固定大小（PAGE SIZE）的内存块 ，称为物理页面 页框 page frame,并为每个页框从低地址开始编号称为PFN。
- 将程序（用户程序和OS）中使用的地址称为虚拟地址，并构成虚拟地址空间。将虚拟地址空间划分为大小相同的块，称为虚拟页面 page。
- CPU 访问程序中使用的地址时，并不是放在地址总线上，而是被送往存储管理单元 MMU，其利用映射关系（其实就是页表）将虚拟地址转化为物理地址后再进行访问。
Example
- RAM 大小为 16KB(0x0000 ~ 0x3fff)，虚拟地址空间为 32KB(0x0000 ~ 0x7fff)
- 页框大小为 4KB
- 某一时刻系统中的映射关系如下:
此时 CPU 执行下面指令：
MOVE REG,0x3002
在启用分页虚拟内存后，CPU 看到的地址都是虚拟地址，此时 CPU 并不会直接把 0x3002 放在地址总线上，而是将 0x3002 地址送往 MMU，MMU 根据上述映射关系，找到页框号 PFN，计算出物理地址为 0x0002，进而将 0x0002 处内容放在寄存器中。
MMU 如何工作:
- 根据虚拟地址和映射关系（页表）找到 PFN
- PFN 和 页内偏移计算得到物理地址 物理地址计算公式
Physical Address = PFN * PAGE_SIZE + OFFSET
页内偏移计算：页内偏移通俗来讲就是余数，因为每个 Page 的大小是 4KB ，0x3002 就是 第三个 page，再偏移 0x002 位置。更简单一点就是虚拟地址的低 12 位（PAGE SIZE =4KB）。
PFN 计算：这部分属于页表的内容，目前我们就是用眼看，可以看出来 PFN 是 0
关于虚拟空间中的操作系统：用户程序的执行是依赖操作系统的，比如用户程序打印 Hello World 到屏幕，用户程序是不知道如何操作屏幕（硬件）的，因此需要操作系统来帮助其操作硬件。从用户程序跳转到操作系统也称为陷入内核态。但是陷入内核态时我们的页表还是进程的页表，也就是进程的虚拟地址空间。假设进程的虚拟地址空间中没有内核，那么此时 CPU 也不知道操作系统在何处了。理解这点我们才能理解 Linux 虚拟地址空间映射 map。
0x03 页表
用来保存 虚拟页面->物理页面 之间的映射关系，换而言之，页表保存了虚拟地址->物理地址之间的映射关系。
从数学的角度讲，页表就是一个函数，MMU 利用这个函数，输入虚拟地址，得到页框号 PFN。
这里的关键时输入集合是虚拟地址，因此页框大小不变的情况下，虚拟地址空间越大，所需的页表也会越大，而不是取决于物理内存的大小。
我们还可以得出一个结论，一个页表对应一个虚拟地址空间，一个页表项对应一个页面。
根据前文例子中的映射关系，可以得到如下简易的页表，这个页表以一个数组形式展现，其中的每一项我们称为页表项。页表项的核心是 PFN ，当然也需要存储一些其他信息，比方说虚拟内存对应的页面是否在 RAM 上。
对于页表两个需要关注的问题：
- 页表占据的空间
- 页表的映射速度
关于页表的空间，假设虚拟地址空间大小为 4GB，页框大小为 4KB，所需要的表项达到了 100 万个。而在 Linux 中，每个进程的虚拟地址空间都是独立的，每个进程都它自己的页表（上文每个页表对应一个虚拟地址空间），总的页表体积非常大，因此常需要使用多级页表来解决这个问题。
0x04 多级页表
多级页表的理论基础是，当进程运行时通常不会用到所有的虚拟地址空间。所以页表并不需要所有的页表项。
Example
虚拟地址为 32 位（虚拟地址空间为 4GB），页面大小为 4KB。
如果采用普通页表，虚拟页面号占 20 位，页内偏移地址占 12 位。所需的页表项数目为 2^20 ，这是个非常庞大的数字（4GB/4KB = 2^20，也可以这样计算）。
假设一个进程需要的内存空间仅为 8MB（而我们的虚拟地址空间可达 4GB），最低端的 4MB 程序代码，紧接着4MB 用来存储数据。前文讲过，一个页表项对应一个页面。这里我们只有 8MB 需要映射，也就是只需要 8MB/4KB = 2048 个页表项。
- 建立 1 张页目录表，含有 1024 个页目录项，每项为一个地址或一个空值，该地址为一张页表的位置。
- 建立 2 张页表，每个页表含有 1024 个表项，每个页面为 4KB，因此每个页表即可指向 4MB 的地址空间。
多级页表的 MMU 如何工作？MMU 关键部分是计算出 PFN，计算 PFN 的关键是如何索引到页表项。
0x05 页表项的结构
页表项的核心是存储页框号 PFN，通常还需要存储一些属性来实现某些功能。不同的 CPU 及操作系统对页表项的设计是不同的。如下是一个典型的页表项：
- 保护位：表示允许对这个页面的操作是可读，可写，可读写。
- 修改位：表示页面中的内容是否被修改过。也称为脏位。当一个页面需要被换下存到磁盘时，如果没有修改过就不需要将这部分内容存入磁盘。此时磁盘与内从中的内容是一致的。
- 访问位：表示页面是否被访问过。用于页面置换算法，可优先置换掉没有被访问过的页面。
- 有效位：表示这个页面是否在内存中。如果不在内存中则无效，此时 MMU 会产生一个缺页中断给 CPU，要求 CPU 将相应的页面置换到内存。
- 禁用缓存位：表示页面是否可以被缓存。主要用于某些页面被映射到设备寄存器而不是 RAM。
0x06 关联存储器 TLB Transition Lookaside Buffer
绝大多数进程运行时，倾向于集中访问一小部分页面。一部分页表项会经常使用，这是局部性的一种体现。
根据这个观察，设计出一种硬件，用来存储常用的页表项。 当 MMU 根据虚拟页面号寻找页表项时首先从 TLB 中查找。而不需要在内存中查找页表项，减少了对内存的访问。
如果 TLB 中没有，则在内存中的页表找到对应页表项，并在 TLB 中驱逐一个页表项，把需要访问的那个页表项放在 TLB 中。
0x07 页面置换算法
TODO