极客时间已完结课程限时免费阅读

40 | 理解内存（上）：虚拟内存和内存保护是什么？

40 | 理解内存（上）：虚拟内存和内存保护是什么？-极客时间

40 | 理解内存（上）：虚拟内存和内存保护是什么？

2019-07-26 徐文浩 来自北京
《深入浅出计算机组成原理》
课程介绍

讲述：徐文浩

时长09:30大小8.70M

我们在专栏一开始说过，计算机有五大组成部分，分别是：运算器、控制器、存储器、输入设备和输出设备。如果说计算机最重要的组件，是承担了运算器和控制器作用的 CPU，那内存就是我们第二重要的组件了。内存是五大组成部分里面的存储器，我们的指令和数据，都需要先加载到内存里面，才会被 CPU 拿去执行。
专栏第 9 讲，我们讲了程序装载到内存的过程。可以知道，在我们日常使用的 Linux 或者 Windows 操作系统下，程序并不能直接访问物理内存。
我们的内存需要被分成固定大小的页（Page），然后再通过虚拟内存地址（Virtual Address）到物理内存地址（Physical Address）的地址转换（Address Translation），才能到达实际存放数据的物理内存位置。而我们的程序看到的内存地址，都是虚拟内存地址。
既然如此，这些虚拟内存地址究竟是怎么转换成物理内存地址的呢？这一讲里，我们就来看一看。

简单页表

想要把虚拟内存地址，映射到物理内存地址，最直观的办法，就是来建一张映射表。这个映射表，能够实现虚拟内存里面的页，到物理内存里面的页的一一映射。这个映射表，在计算机里面，就叫作页表（Page Table）。
页表这个地址转换的办法，会把一个内存地址分成页号（Directory）和偏移量（Offset）两个部分。这么说太理论了，我以一个 32 位的内存地址为例，帮你理解这个概念。
其实，前面的高位，就是内存地址的页号。后面的低位，就是内存地址里面的偏移量。做地址转换的页表，只需要保留虚拟内存地址的页号和物理内存地址的页号之间的映射关系就可以了。同一个页里面的内存，在物理层面是连续的。以一个页的大小是 4K 字节（4KB）为例，我们需要 20 位的高位，12 位的低位。
总结一下，对于一个内存地址转换，其实就是这样三个步骤：
把虚拟内存地址，切分成页号和偏移量的组合；
从页表里面，查询出虚拟页号，对应的物理页号；
直接拿物理页号，加上前面的偏移量，就得到了物理内存地址。
看起来这个逻辑似乎很简单，很容易理解，不过问题马上就来了。你能算一算，这样一个页表需要多大的空间吗？我们以 32 位的内存地址空间为例，你可以暂停一下，拿出纸笔算一算。
不知道你算出的数字是多少？32 位的内存地址空间，页表一共需要记录 2^20 个到物理页号的映射关系。这个存储关系，就好比一个 2^20 大小的数组。一个页号是完整的 32 位的 4 字节（Byte），这样一个页表就需要 4MB 的空间。听起来 4MB 的空间好像还不大啊，毕竟我们现在的内存至少也有 4GB，服务器上有个几十 GB 的内存和很正常。
不过，这个空间可不是只占用一份哦。我们每一个进程，都有属于自己独立的虚拟内存地址空间。这也就意味着，每一个进程都需要这样一个页表。不管我们这个进程，是个本身只有几 KB 大小的程序，还是需要几 GB 的内存空间，都需要这样一个页表。如果你用的是 Windows，你可以打开你自己电脑上的任务管理器看看，现在你的计算机里同时在跑多少个进程，用这样的方式，页表需要占用多大的内存。
这还只是 32 位的内存地址空间，现在大家用的内存，多半已经超过了 4GB，也已经用上了 64 位的计算机和操作系统。这样的话，用上面这个数组的数据结构来保存页面，内存占用就更大了。那么，我们有没有什么更好的解决办法呢？你可以先仔细思考一下。

多级页表

仔细想一想，我们其实没有必要存下这 2^20 个物理页表啊。大部分进程所占用的内存是有限的，需要的页也自然是很有限的。我们只需要去存那些用到的页之间的映射关系就好了。如果你对数据结构比较熟悉，你可能要说了，那我们是不是应该用哈希表（Hash Map）这样的数据结构呢？
很可惜你猜错了：）。在实践中，我们其实采用的是一种叫作多级页表（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=32 个条目。如果每个条目还是 4 个字节，那么一共需要 128 个字节。而一个 1 级索引表，对应 32 个 4KB 的也就是 128KB 的大小。一个填满的 2 级索引表，对应的就是 32 个 1 级索引表，也就是 4MB 的大小。
我们可以一起来测算一下，一个进程如果占用了 8MB 的内存空间，分成了 2 个 4MB 的连续空间。那么，它一共需要 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。

课后思考

在实际的虚拟内存地址到物理内存地址的地址转换的过程里，我们没有采用哈希表，而是采用了多级页表的解决方案。你能想一想，使用多级页表，对于哈希表有哪些优点，又有哪些缺点吗？
欢迎留言和我分享你的想法，如果觉得有收获，你也可以把这篇文章分享给你的朋友，和他一起学习和进步。
分享给需要的人，Ta购买本课程，你将得20元
生成海报并分享

赞 35

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
39 | MESI协议：如何让多核CPU的高速缓存保持一致？
下一篇
41 | 理解内存（下）：解析TLB和内存保护
unpreview
 写留言

精选留言(49)

  • 鱼向北游
    2019-07-27
    哈希表有哈希冲突 并且顺序乱 不符合局部性原理 所以页表存储更复合计算机运行特点 64位系统的快表应该是对页表快速查询的一个优化吧 是用硬件实现么?期待老师下次讲解
    共 2 条评论
    46
  • 华新
    2020-05-14
    找了半天终于搞明白为啥用多级页表可以节省内存空间了。总觉得加了四级占的空间更大了才对。 有跟我存在一样疑惑的可以参看以下地址，说的很明白： https://www.polarxiong.com/archives/%E5%A4%9A%E7%BA%A7%E9%A1%B5%E8%A1%A8%E5%A6%82%E4%BD%95%E8%8A%82%E7%BA%A6%E5%86%85%E5%AD%98.html
    展开
    共 7 条评论
    33
  • -W.LI-
    2019-07-27
    我们可以一起来测算一下，一个进程如果占用了 1MB 的内存空间，分成了 2 个 512KB 的连续空间。那么，它一共需要 2 个独立的、填满的 2 级索引表，也就意味着 64 个 1 级索引表，2 个独立的 3 级索引表，1 个 4 级索引表。一共需要 69 个索引表，每个 128 字节，大概就是 9KB 的空间。比起 4MB 来说，只有差不多 1/500。 1个3级索引表，不是有32个2级索引表么? 为啥需要2个独立的3级索引表啊?
    展开
    共 16 条评论
    22
  • 业余爱好者
    2020-06-20
    多级页表感觉就是对大量地址的分组，如果组还是太多就接着分组，一直到一个组数规模适中的程度。查找时逐层进行。由于地址空间是个杠铃结构，很多分组就不需要了，这样就大大节省了内存空间。
    8
  • zhe
    2019-08-19
    而一个 1 级索引表，32 个 4KiB 的也就是 16KB 的大小，这个怎么算的

    作者回复: zhe同学， 你好，谢谢纠正。这里写错了，我修正过来，是128KB。写的时候太快把4KiB当成了4K Bit了。

    6
  • 去777
    2020-03-11
    跟调表的思想有点像
    共 2 条评论
    5
  • 王加武
    2019-12-24
    数据结构真的是无处不在啊！ 哈希表是数组 + 链表组成的，充分的结合了数组和链表的优势，互补！但是哈希表存在哈希冲突，并且是无序的！不符合局部性原理！

    作者回复: 👍，其实算法和数据结构在软硬件的开发的方方面面都会涉及到。

    5
  • 美美
    2019-07-30
    一个页号是完整的 32 位的 4 字节（Byte） ------------------------------- 一个页号不是20位吗，为什么是32位呢
    共 5 条评论
    5
  • 许童童
    2019-07-26
    多级页表相对于哈希表，优点我觉得应该是可以用到计算机的局部性原理，而用哈希表的话，顺序是打乱的而且存在哈希冲突。多级页表的缺点就是要一级一级查找，速度相对比较慢。
    3
  • 放下
    2020-07-05
    而一个 1 级索引表，对应 32 个 4KB 的也就是 128KB 的大小，这个4KB是指什么呢？是指1级索引表对于32个页表，一个页表4KB，是这样理解吗，请老师解答下
    共 1 条评论
    2
  • 李
    2019-07-26
    2个独立的二级索引，一个三级索引，一个四级索引吧？ 为什么2个独立索引 还需要两个独立3级索引呢？ 一个三级索引不就可以引用2个独立索引了吗？
    共 3 条评论
    2
  • 李
    2019-07-26
    32 位的内存地址空间，页表一共需要记录 2^20 个到物理的映射关系。这个存储关系，就好比一个 2^20 大小的数组。一个页号是完整的 32 位的 4 字节（Byte），这样一个页表就需要 4MB 的空间 请问这两个是怎么算出来的？
    展开
    共 7 条评论
    2
  • benxiong
    2020-07-28
    希望老师能解答一下二楼 W.LI的问题
    1
  • 时光
    2020-06-01
    老师，为什么需要两个独立的三级索引表，一个不行吗。按照我的想法，从底层往上构建树，倒数第一层64个节点、倒数第二层2个节点、倒数第三层1个节点、倒数第四层1个节点这样就能表示出来了。
    1
  • zaab
    2019-10-12
    我看不懂的地方1.使用32位的内存地址，因为1位只能是0或者1， 所以最多有2的32次方的种不同排列，一个地址对应存1bit数据， 那么1024bit = 1kb , 1024kb=1M 1024M=1G , 所以是 4294967296 /1024/1024/1024= 4GB； 2.以一个页的大小是 4K 字节（4KB）为例，我们需要 20位高位，12位低位； 12位低位做偏移量，2的12次方=4096=4kb..
    共 4 条评论
    1
  • 焰火
    2019-09-19
    如果程序很大，两头实，中间也实，那么多级页表所占用的空间肯定比简单页表大得多吧？ 进程的页表是操作系统进行统一管理的还是每个进程的装载器自我管理呢？

    作者回复: 焰火同学， 你好，不太可能都实的，比如现在64位的计算机，内存空间是 2^64，没有哪个程序会需要那么多空间的。 进程的页表是由操作系统内核来创建管理的，Linux下也就是大家所谓的Kernel在管理。

    1
  • 活的潇洒
    2019-08-21
    为什么我们不用哈希表而用多级页表呢？ 虚拟内存占用的地址空间，通常是两段连续的空间。而不是完全散落的随机的内存地址。而多级页表，就特别适合这样的内存地址分布 day40 笔记：httpshttps://www.cnblogs.com/luoahong/p/11383429.html
    1
  • 免费的人
    2019-07-26
    页大小是4KByte 还是Bit ？
    共 3 条评论
    1
  • 徐凯
    2019-07-26
    哈希表会有哈希冲突，比较不稳定。对于访问内存页的过程影响很大 老师是这样么
    1
  • 啦啦啦
    2019-07-26
    还是你讲的更通俗易懂
    1