什么会限制虚拟内存（内存保护都是啥）

内存是计算机五大组分里的存储器，指令和数据，都要先加载到内存，才能被CPU读取执行。

Linux下，程序并不能直接访问物理内存。

内存需被分成固定大小页（Page），再通过虚拟内存地址（Virtual Address）到物理内存地址（Physical Address）的地址转换（Address Translation），才能到达实际存放数据的物理内存位置。我们的程序看到的内存地址，都是虚拟内存地址。

那这些虚拟内存地址究竟是怎么转换成物理内存地址的呢？

简单页表

很直观啊，建张映射表，完成虚拟内存里面的页 =》物理内存页的一一映射，这就是页表（Page Table）。

页表把一个内存地址分成：

• 页号（Directory）
• 偏移量（Offset）

如32位内存地址：

• 前面高位，内存地址的页号
• 后面低位，内存地址里的偏移量

做地址转换的页表，只需保留虚拟内存地址的页号 => 物理内存地址的页号之间的映射关系

同一页里的内存，物理层面连续。比如页大小4K比特（4KiB），需20位高位，12位低位。

一个内存地址转换，就是如下步骤：

• 把虚拟内存地址，分为页号、偏移量
• 从页表里，查询出虚拟页号，对应的物理页号
• 直接拿物理页号，加上前面的偏移量，即得物理内存地址

那这样一个页表需多大空间呢？

如32位内存地址空间，页表共需记录 2^20 个到物理页号的映射关系。该存储关系就像一个2^20大小数组。一个页号是完整的32位4字节，这一个页表就要4MB

但这空间可不是只占用一份。每个进程都有独立的虚拟内存地址空间。这意味着，每个进程都要这样一个页表。不管这进程需几KB or 几GB内存空间，都要这样一个页表。这还只是32位内存地址空间，更多的64位os，用这数组的数据结构保存页面，内存占用更大。

有啥更好的解决办法呢？

多级页表

没必要存2^20个物理页表，大部分进程所占内存有限，需要的页自然很有限。只需存那些用到的页之间的映射关系即可。是不是应该用哈希表？No！实际采用的多级页表（Multi-Level Page Table），为什么不用哈希表呢？

一个进程的内存地址空间是怎么分配的

整个进程的内存地址空间，通常“两头实、中间空”。程序运行时，内存地址从顶部往下，不断分配占用的栈的空间。而堆的空间，内存地址则是从底部往上，不断分配占用。

所以，实际程序进程里，虚拟内存占用的地址空间，通常是两段连续空间。而非完全随机的内存地址。而多级页表，就特别适合这样的内存地址分布。

示例

4级的多级页表，同样一个虚拟内存地址，偏移量的部分和上面简单页表一样，但页号部分拆成四段，从高到低，分成4级到1级，4个页表索引。

• 对应一个进程会有个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级页表。找到最终物理页号，就好像通过一个特定访问路径，走到树最底层的叶节点。

以分成4级的多级页表为例，每级若都用5比特表示。则每张某1级的页表，只需2^5=3225=32个条目。若每个条目还4字节，则共需128字节。一个1级索引表对应32个4KiB，即16KB。一个填满的2级索引表，对应32个1级索引表，即512KB。

若某进程占用1MB内存空间，分成了2个512KB连续空间。则它共需2个独立、填满的2级索引表，即64个1级索引表，2个独立3级索引表，1个4级索引表。共69个索引表，每个128字节，约9KB空间。比起4MB，差不多1/500了。

虽多级页表节约存储空间，却带来时间开销，是个“时间换空间”策略。 原进行一次地址转换，只需访问一次内存就能找到物理页号，算出物理内存地址。但用了4级页表，就得访问4次内存才能找到物理页号。内存访问比Cache慢很多，本只是做个简单的地址转换，反而要多访问了好多次内存。对这时间性能损失，如何更好解决呢？

总结

从最简单的进行虚拟页号一一映射的简单页表说起，仔细讲解了现在实际应用的多级页表。多级页表就像是一颗树。因为一个进程的内存地址相对集中和连续，所以采用这种页表树的方式，可以大大节省页表所需要的空间。而因为每个进程都需要一个独立的页表，这个空间的节省是非常可观的。

在优化页表的过程中，我们可以观察到，数组这样的紧凑的数据结构，以及树这样稀疏的数据结构，在时间复杂度和空间复杂度的差异。另外，纯粹理论软件的数据结构和硬件的设计也是高度相关的。

参考

《计算机组成与设计：硬件/软件接口》的第5.7章节

《What Every Programmer Should Know About Memory》的第4部分，Virtual Memory

,