9.24 ｜讲讲操作系统的多级页表，为什么多级页表会省空间？

多级页表本质上是一个时间换空间的策略，通过增加一定的地址访问时间来减少对空间的占用。

多级页表作用：通过只为进程实际使用的那些虚拟地址内存区请求页表来减少内存使用量（出自《深入理解Linux内核》第三版51页）

想要把虚拟内存地址，映射到物理内存地址，最直观的方法，就是来建立一张映射表。这个映射表，能够实现虚拟内存里面的页，到物理内存里面的页的一一映射。这个映射表，在计算机里面，就叫做页表

在一个实际的程序地址里面，虚拟内存占用的地址空间，通常是两端连续的空间，而不是完全随机的内存地址。

如果我们只有一个页表，那就需要在这一个页表里将所有的地址都映射出来，而在其中的大部分地址，其实都是没有利用到的（比如租了100个库房，只用了10个，剩下的就一直空着浪费钱），绝大部分空间其实都是被浪费掉的。

那么如何进行优化呢？核心思想就在于 按需分配 ，也就是说：有多少合法的虚拟页号，我们就维护一个多大的映射，并为此使用多大的内存用来保存映射。这是因为，每个应用的地址空间最开始都是空的，或者说所有的虚拟页号均不合法，那么这样的页表自然不需要占用任何内存。

优化例子

设想我们要维护一个字符串的多重集，集合中所有的字符串的字符集均为 α={a,b,c} ，长度均为一个给定的常数 n 。该字符串集合一开始为空集。我们要支持两种操作，第一种是将一个字符串插入集合，第二种是查询一个字符串在当前的集合中出现了多少次。

简单起见，假设 n=3 。那么我们可能会建立这样一颗 字典树 (Trie) ：

../_images/trie.png

对于题目要求的两种操作，我们只需根据输入的字符串中的每个字符在字典树上自上而下对应走出一步，最终就能够找到字典树中维护的它的计数。之后我们可以将其直接返回或者加一。

这样的优点是举例了所有情况，缺点是维护了一些可能不存在的节点，但这些节点确实占用了空间。

可以这样优化：

../_images/trie-1.png

一开始仅存在一个根节点。在我们插入字符串 acb 的过程中，我们只需要分配 a 和 ac 两个节点。

如果后续再插入一个字符串，那么 至多分配两个新节点 ，因为如果走的路径上有节点已经存在，就无需重复分配了，只需增加计数。字典树中节点的数目（或者说字典树消耗的内存）是随着插入字符串的数目逐渐线性增加的。

==多级页表也是类似的思想，如果这种情况没有出现，就不分配给具体的地址。==

普通页表

对于一个内存地址转换，其实就是这样三个步骤：

把虚拟内存地址，切分成页号和偏移量的组合；
从页表里面，查询出虚拟页号，对应的物理页号；
直接拿物理页号，加上前面的偏移量，就得到了物理内存地址。

多级页表

偏移量的部分和上面简单页表一样不变，但是原先的页号部分，我们把它拆成四段，从高到低，分成 4 级到 1 级这样 4 个页表索引。

我们先通过 4 级页表索引，找到 4 级页表里面对应的条目（Entry）。这个条目里存放的是一张 3 级页表所在的位置。4 级页面里面的每一个条目，都对应着一张 3 级页表，所以我们可能有多张 3 级页表。

找到对应这张 3 级页表之后，我们用 3 级索引去找到对应的 3 级索引的条目。3 级索引的条目再会指向一个 2 级页表。同样的，2 级页表里我们可以用 2 级索引指向一个 1 级页表。

而最后一层的 1 级页表里面的条目，对应的数据内容就是物理页号了。在拿到了物理页号之后，我们同样可以用“页号 + 偏移量”的方式，来获取最终的物理内存地址。

我们可能有很多张 1 级页表、2 级页表，乃至 3 级页表。但是，因为实际的虚拟内存空间通常是连续的，我们很可能只需要很少的 2 级页表，甚至只需要 1 张 3 级页表就够了。

多级页表就像一个多叉树的数据结构，所以我们常常称它为页表树（Page Table Tree）。因为虚拟内存地址分布的连续性，树的第一层节点的指针，很多就是空的，也就不需要有对应的子树了。所谓不需要子树，其实就是不需要对应的 2 级、3 级的页表。找到最终的物理页号，就好像通过一个特定的访问路径，走到树最底层的叶子节点。

多层分页表就好像把完整的电话号码分成区号。我们把同一地区的电话号码以及对应的人名记录同通一个小本子上。再用一个上级本子记录区号和各个小本子的对应关系。如果某个区号没有使用，那么我们只需要在上级本子上把该区号标记为空。同样，一级分页表中0x01记录为空，说明了以0x01开头的虚拟地址段没有使用，相应的二级表就不需要存在。正是通过这一手段，多层分页表占据的空间要比单层分页表少了很多。

多层分页表还有另一个优势。单层分页表必须存在于连续的内存空间。而多层分页表的二级表，可以散步于内存的不同位置。这样的话，操作系统就可以利用零碎空间来存储分页表。

总结

单页表相当于一个缓存了所有情况的集合，优点是访问速度快，缺点是占用空间大

多级页表相当于只缓存已经存在的情况，优点是占用空间较少，缺点是访问时间相对较长。

背诵版

多级页表本质上是一个时间换空间的策略，通过增加一定的访问地址时间来减少对空间的占用。

操作系统需要将虚拟内存地址翻译为物理内存地址，而记录对应关系最简单的办法，就是把对应关系记录在一张表中。为了加快翻译速度，这个表必须加载在内存中。这个表就是页表。

如果页表直接把所有的对应关系记录到同一个表中，会有很多位置都是浪费了的，对于任何一个应用进程，其进程空间真正用到的地址都相当有限的。

而对于每一个进程，都有属于自己独立的虚拟内存地址空间。这也就意味着，每一个进程都需要这样一个页表。当进程多了之后，页表占用的空间也会随之增大。

多层分页表就好像把完整的电话号码分成区号。我们把同一地区的电话号码以及对应的人名记录同通一个小本子上。再用一个上级本子记录区号和各个小本子的对应关系。如果某个区号没有使用，那么我们只需要在上级本子上把该区号标记为空。同样，一级分页表中记录为空，说明了以这个一级页表开头的虚拟地址段没有使用，相应的二级表就不需要存在。正是通过这一手段，多层分页表占据的空间要比单层分页表少了很多。

单层分页表必须存在于连续的内存空间。而多层分页表的二级表，可以散步于内存的不同位置。这样的话，操作系统就可以利用零碎空间来存储分页表。