通用操作系统原理之虚拟内存

发表于 更新于 分类于 ，

理论驱动实践，实践驱动理论。

虚拟内存问题概述

如果你了解过一点虚拟内存的知识，这篇笔记可能会让你更深入的理解。

  • 三个内存相关的问题
    • 没有足够的内存
    • 地址空间碎片化
    • 地址冲突
  • 什么是虚拟内存
    • 中间件
    • 如何解决三个内存问题
    • 页表和转换
  • 如何实现虚拟内存
    • 怎么让转换变得更快
  • 虚拟内存和高速缓存 Cache

三个内存相关的问题

  • 没有足够的内存怎么办

MIPS 提供给每个应用程序 32 位的地址空间，每个应用程序可以访问这 32 个地址空间中的任意一个字节。最早的 MIPS 架构是 32 位，最新的版本已经变成 64 位。也就是说你可以使用 2^32bytes 也就是 4GB，这只是理论上，实际可能会缩小到 2GB 可用空间。

如果你的物理内存（内存条）是 1GB 该怎么办呢？就像下面这个图，可寻址空间大于实际物理内存大小。

  • 程序如何分配内存（对于碎片内存）

就像下面这张图，首先内存加载程序 p1 和 p2，开始 3G 空间被占用，剩余 1G 空间剩余，这时候 p1 退出，p3 想使用内存，虽然还有 2G 剩余空间，但空间是碎片化的，这也是一个问题。这被称作 Memory fragmentation内存碎片化。

  • 如何保证进程安全（进程之间地址不相互访问）

就像下面这张图，两个程序同时访问 1024 这个地址的空间，内存中的信息会不会相互覆盖？

总结一下，如果所有程序都有相同的 32 位的寻址空间，那么可能导致以下问题：

  • 如果实际物理能存大小小于 4GB 电脑可能会崩溃
  • 如果运行多个程序可能会用光所有内存，这不是真正的用光而是碎片化的内存无法真正利用，这种碎片化依赖于我们不同程序的运行次序
  • 不同的进程之间的数据可能会相互覆盖破坏，因为有相同的寻址地址

那么如何解决？

问题的关键在于所有的程序有相同的寻址空间，那么我们可不可以有属于自己的虚拟内存？如果可以的话，我们可以

  • 将程序的内存空间和物理内存之间做一个映射（这使得我们使用物理内存 RAM 变的更加灵活）
  • 当程序用光的时候，我们甚至可以将程序移动到硬盘

什么是虚拟内存

中间件

虚拟内存是一层 “中间组件”，虚拟内存的想法来自于一句话：

Any problem in computer science can be solved by adding indirection.
任何计算机问题都可以通过添加一个中间件来解决。

如果没有虚拟内存这一层中间件，程序寻址空间将和实际物理内存相同。例如寻址空间大小大于实际 RAM 大小，如果你访问地址 2024，得到的结果可能和访问地址 24 相同（因为地址越界最高位失效）。

虚拟内存的作用就是将程序地址空间做一层映射映射到实际 RAM 地址。

如下图所示：

如何解决三个内存问题

  • 没有足够的内存
    将一部分程序地址空间映射到硬盘，我们需要他的时候只需要将这一部分加载到内存中即可。内存中的暂时不使用的程序（比如 Program0）可以将其放到硬盘中，这个过程叫做 Page Out，即内存页换出，并更新映射，然后当新程序（P3）来了就可以映射到内存中原来旧程序（P0）部分。

  • 碎片内存使用

这就是前面提到过的问题，如何充分利用程序退出后碎片化的内存？
有了前面提及的映射，这个就比较容易解决了，我们可以将地址空间按照任意方式映射到实际物理内存 RAM

  • 进程安全（进程之间不相互访问）

进程之间的内存如何能够独立、隔离（isolate）出来呢？例如同时访问 1024 的地址，两个程序如何能保证不是访问的实际物理内存中的同一个区域呢？

通过映射方式我们可以想出来，只需要保证不同程序的相同虚拟地址映射到不同的物理地址就可以了。

这样一来，因为每个程序都有自己的地址空间，那么他们不可能访问其他程序的数据，这非常的安全和可靠！

这也是有缺点的，当两个程序合作的时候，如何共享内存呢？只需要将两个程序各自的虚拟地址空间拿出一部分映射到相同的物理地址空间。

页表和转换

前面一直提到的映射就是页表的部分，页表所做的功能就是转换，从VA（Virtual Address）虚拟地址转换为PA（Physical Address）物理地址。页表映射的单位是一个页。

那程序是如何访问内存的呢？

  • CPU 执行使用虚拟地址。
  • MMU 将虚拟地址转换成物理地址
  • （可选）如果转换过程中发现映射表中没有物理内存，那么操作系统就将它从硬盘加载到内存并修改映射表

  • 通过物理地址读取 RAM 并将数据返还给程序。

页表

页表保存着 VA 虚拟地址到 PA 物理地址的映射方式。

下面一步一步说明页表的构建过程，从有问题的页表到一个臻于完美的页表，这可能是现代计算机操作系统所利用的机制。

既然页表保存着虚拟地址到物理地址的映射，那么页表就需要保存每一个虚拟地址到每一个物理地址的映射，我们称每一条记录为页表入口 Page Table Entry (PTE)。如果是这样的话，那需要多大的页表？结合下图：如果是 32 位地址空间，每个字就需要 1 个 PTE，这里一个字是 32 位，也就是 4 个字节，所以每 4 个大小也就是 2 位的地址空间就需要 1 个 PTE，所以总共需要 2^30 个 PTE。又因为每个 PTE 存储的是一个映射，由于虚拟地址是连续的可以只用偏移地址来表示，只需要存 32 位的物理地址，所以总共需要 2^30x32b=4GB 个大小。这说明 1 个 4GB 大小的 RAM 我们就需要拿出全部容量来存储页表，而且这没有考虑每个程序都需要一个页表。如果你没有明白这个计算公式，你仅需要知道如果这样构造页表所需容量太大，需要改造！

那么如何改造呢？以上情况的映射是 1 个字对应一个 PTE 页表入口，我们称这种情况为细粒度映射，那我们可不可以使用粗粒度映射呢？就像这个图一样：

这个图中，我们将每 4Kb 大小的地址空间做一个 PTE，我们称之为 4KB Pages，因为每个 RAM 按字节计量，或者你可以看为 1K 个字大小的页。这样我们就减少了映射也就是 PTE 的个数。这 4KB 大小的页映射的内部是连续的，如下图：

有了以上改进，我们有了更少的 PTE 映射个数，但是我们页降低了使用 RAM 的灵活性，因为我们每次需要移动一个页（4KB）。

现代计算机系统中，比较典型的就是 4KB Pages（1024 words per page，每一页 1024 个字）。

地址转换

我们需要将虚拟地址转换为物理地址。

假设我们使用的是 4KB Pages，我们有 32 位虚拟地址，28 位物理地址，如下图

那我们 4KB 大小的页内部没有做映射，这一部分如何映射呢？解决办法就是使用偏移量offset，如下图

我们将一个虚拟地址转换为物理地址，虚拟地址的 pagenumber 部分通过页表转换为实际物理地址的 pagenumber 部分，虚拟地址的 offset 部分直接作为物理地址的 offset 部分。

下面这个例子，32 位虚拟地址，28 位物理地址，4KB 大小的页，所以需要 12 位 offset。当虚拟地址为 0x00003204 的时候，将虚拟地址分为虚拟页编号（0x00003）、偏移量（0x204），offset 直接使用，所以物理页内偏移量为 0x204，虚拟页编号通过查页表，得到物理页编号为 0x0006。所以得到的物理地址为 0x0006204

当然，如果查页表的时候可能会产生 page fault，即所需要的内容没有在 RAM 中，如图中的 0x00000，这就需要发生中断，加载内容到 RAM，然后修改页表，返回到内存上次执行的位置，这时候就会找到所对应的物理页编号了。

详细说一下当所需要的页不在内存中时会发生什么：

  • 页表入口 PTE 告诉你所需要的页在硬盘中
  • 硬件（CPU）生成一个 Page Fault 页错误
  • 硬件跳到 Page Fault Handler 页错误处理程序来处理
    • 操作系统选择 RAM 中的一个页剔除写到硬盘中
    • 如果是需要读取的页是脏页，就需要先将其写回到硬盘再读取
    • 操作系统读取所需要的页到 RAM
    • 操作系统修改页表的映射
  • 操作系统跳转到发生页错误的地方开始执行（这一次就不会产生页错误了）

脏页是指页中的数据被改变了，如果没有改变，那就没必要写回到硬盘了。

脏页－linux 内核中的概念，因为硬盘的读写速度远赶不上内存的速度，系统就把读写比较频繁的数据事先放到内存中，以提高读写速度，这就叫高速缓存，linux 是以页作为高速缓存的单位，当进程修改了高速缓存里的数据时，该页就被内核标记为脏页，内核将会在合适的时间把脏页的数据写到磁盘中去，以保持高速缓存中的数据和磁盘中的数据是一致的。（来自百度百科）

那么页不在内存中时，这个过程需要多长时间呢？大约需要 80 million 周期，这是采样自现代 CPU，其中硬盘的读取占了大多数时间。页错误可能是计算机中最慢的操作了。

既然这么慢，那为什么还要用它呢？

优点：

  • 你用光了内存计算机不会发生崩溃
    缺点：
  • 如果发生页错误会很慢

但是现代计算机还是使用内存页机制。如果你有非常大、足够大的 RAM 就不会发生页置换，这就是我们为什么认为内存越大计算机就变的越快的原因。

足够大的内存这是不可能的，不过一些现代操作系统不会发生页置换：

  • IOS：如果你用了过多的内存，系统会杀死你的进程
  • OS X 10.9：系统会先压缩你的程序，只有不得不置换的时候才会发生

这可能就是为什么在国内 Apple 比较受欢迎的原因吧，o (￣︶￣)o

每个程序都有自己的页表，我们可以把每个程序的虚拟地址映射到独一无二的内存中，这是为了程序之间不会没有预测的访问数据。

这说明每一个程序都有自己的 32 位虚拟地址空间，下面是 Linux 虚拟内存空间的使用情况。

1GB 预留给 linux 内核作为内核区，栈区可以向下扩展到一个固定的最大值，Libraries 区用于一些共享库的放置，堆区用于存储动态申请的内存向上扩展，接下来是 data 数据区用于存储静态变量，代码区用于放置程序编译之后的二进制代码。这之间有一些随机的偏移，这提高了安全性因为你不知道数据和代码区具体在哪儿。

这是一个具体的例子。

每个程序都有自己的虚拟地址空间，都有自己的页表映射方式保证了程序之间的隔离，因为不会随意相互访问内存，映射到内存的相同区域保证了程序之间的可合作性。

看一看实际如何使用独立的页表映射方式。这儿有两个程序，CPU 都要执行这段指令 ld R2,2(R0)，就是将内存地址 2 的数据加载到 R2 寄存器中，这里的内存地址是虚拟地址，因此需要通过查页表的方式来查询实际物理内存地址，然后取出数据。因为两个程序有不同的页表，执行指令时取得的虚拟地址 2 对应的物理地址一般不同或者相同（共享，这只需要将不同地址的虚拟地址映射到相同的 RAM 物理地址即可），因此最终访问的 RAM 地址也是不同的。CPU 执行上下文切换切换进程时会将进程资源一起切换，这个切换就包含页表的切换。就像下面这张图。

如何实现虚拟内存

如何让虚拟内存有作用呢？因为虚拟内存使得内存使用更加灵活，但也有可能降低计算机系统的效率，我们只需要让虚拟内存机制达到尽可能大的效率即可。

虚拟内存的使用过程中需要做什么事情？

  • 访问内存中的页表
  • 通过查询页表将虚拟地址转换为物理地址
  • 访问 RAM 相应物理内存中的数据

这个过程中访问了内存 2 次，访问内存有很多的工作要做，要了解到我们平均每条指令就需要访问 1.33 次内存（4/3，每三条指令访问 4 次内存），这部分显得很低效，这是优化的部分之一！

使用虚拟内存有优点，因为有 “无限制” 的程序和内存（每个程序都有地址空间，内存页可以换入换出），可以保护程序内存实现隔离，使用内存变得很灵活；但使用虚拟内存也会带来很昂贵的资源消耗，每个内存操作都需要查询页表，而且需要访问两次内存（1 次页表访问、1 次内存物理地址（访问 RAM 数据）访问）

如何更快地完成虚拟地址到物理地址的转换

  • TLB
    因为页表的访问是必须的，所以不可能减少这一部分工作。那我们可不可以通过软件来实现？我们知道这又增加了指令条数，也就增加了内存访问次数。那可不可以通过硬件来实现？添加一个缓存 Cache。我们称这个 Page Table Cache 为 Translation Lookaside Buffer(TLB)。他的工作机制如下图

最初，通过访问 RAM 中的页表来将虚拟地址转换为物理地址，这是非常慢的操作。

我们通过访问 TLB 缓存来获取虚拟地址对应的物理地址这是十分迅速的，因为访问速度比 RAM 快，这非常像一个 Cache。如果想让 TLB 非常迅速，TLB 就必须尽可能小。我们通常将 TLB 分离成指令页缓存（iTLB）和数据页缓存（dTLB），比如现代 intel 所生产的，每一页 4KB，一共有 64 个页表入口 PTE，或者是每一页 2MB，32 个 PTE，都是 4 路关联（4 路组关联，区别于全关联）

全部页表有 1M 个 PTE，但是 TLB 里只有 64 个，这个差别很多大，这样访问页的时候如果在 TLB 里那就会变得很快。

  • 页在 RAM 中
    • PTE 在 TLB
      • 最快
      • 1 个周期用于地址转换，然后访问 RAM 或 cache 中的数据
    • PTE 不在 TLB
      • 较慢
      • 20-1000 个周期从 RAM 中加载 PTE 到 TLB，然后访问 RAM 数据
  • 页不在 RAM
    • PTE 在 TLB（几乎不可能，因为最近不经常使用的内存页被置换到硬盘，所以 TLB 在这段时间内也被置换了）
      • 很慢
      • 大约 80M 周期从硬盘加载到内存
    • PTE 不在 TLB
      • 比很慢还慢一点（o (￣︶￣)o）
      • 20-1000 个周期地址转换，这时知道内存页在硬盘
      • 大约 80M 周期从硬盘加载到内存

TLB 非常的小，怎么让 TLB 看着大一点，换句话说如何充分利用这么小的一个空间？

  • 让每一页变的大一点。例如从 64 个 4KB 大小的页（共 256KB 数据）换为 32 个 2MB 大小的页（共 64MB 数据）
  • 添加一个二级 TLB，可能比一级 TLB 大一点，但是有一点慢。大多数二级 TLB 是一级 TLB 大小的八倍，当一级 TLB 的 PTE 没有命中的话就去二级 TLB 去查找加载到一级 TLB

  • 让硬件自动填充 TLB（因为不会经过操作系统的处理）。这被称为 Hardware Page Table Walk，由 MMU 来完成。

下面是如何通过 TLB 将虚拟地址转化为物理地址的例子。

CPU 执行指令的时候，使用到了虚拟内存地址 0x00003204，需要将虚拟地址转化为物理地址，首先去 TLB 查找缓存页表，这个例子中发现 TLB 中没有所要查找的页表入口 PTE，然后就需要通过查找 RAM 中的页表中的 PTE，找到了之后就需要将该 PTE 加载到 TLB，然后将虚拟页编号映射到物理页编号（0x00003->0x0006），页内偏移直接使用，最终获取物理地址 0x0006204。

下面再看一个 PTE 在 TLB 中的例子。

这个例子中 CPU 中使用虚拟地址 0x00003208，首先通过虚拟页编号到 TLB 中去找，虚拟页编号 0x00003，发现该页在 TLB 中，那就直接转化为物理地址。

下面又是一种情况，当所查找的页不在 TLB 中且 TLB 中满时需要做什么，需要将 TLB 中选取一个 PTE 剔除以释放空间

当所需要的页不在 RAM 中时会发生什么？CPU 使用虚拟地址 0x00000860，发现页编号 0x0000 不在 TLB 中，然后去 RAM 页表中查找，发现所需物理页在 DISK 中，然后就需要将 DISK 中数据加载到 RAM 中并更新 RAM 中的页表，然后将页表中对应的 PTE 加载到 TLB 中，将虚拟页号转换为物理页号获取物理地址。

  • 多级页表

多级页表是使优化地址转换的另一方法。首先我们考虑一下页表的大小，虽然我们使用了 4KB 大小的页来减少页表中 PTE 中的数量，但对于 32 位大小的虚拟地址空间来说还是会有 1M 个 PTE，每个 PTE 大约占 4B（20 位物理地址，还有其他的权限标志位等）。总共 4MB。但是我们每个程序都需要一个页表，假设我们有 100 个程序在运行，那内存中就需要有 400MB 来维护各个程序的页表！还有一点，我们无法将页表换出到 DISK 硬盘中，因为我们需要通过页表来获取实际 RAM 物理地址，如果页表不在 RAM 中那我们就没有办法找到页表了（因为我们需要页表进行地址转换，其他设备的数据都是通过页表加载到内存并更新页表）。

那怎么解决这个问题呢？

我们虚拟内存的实现是通过添加一个中间件的思想实现的，那我们可不可以再添加更过的中间件来处理这个问题，答案是肯定的，使用多级页表。

下图是一个例子。

这个例子中使用了二级页表，一级页表中存了 1024 个 4KB 的页的 PTE，每个 PTE 中物理页编号指向的是一个二级页表，这个页表对应存储的才是真正数据对应的物理页。对于每个程序，每个二级页表有 1024 个 PTE，一共有 1024 个二级页表，那么有 1024x1024 个 PTE，刚好就是 1M 个 PTE，和未使用多级页表中的情况是一样的。

所以有了多级页表机制，我们可以把一级以下的页表换出到 DISK 硬盘中，因为我们可以通过一级页表来获取它，这也说明了一点我们必须要把一级页表存储在 RAM 中，就像下面这张图。

我们来思考一下，使用了多级页表，对于一个 32 位应用程序我们至少需要多大的内存空间来保存页表呢？4KB+4KB，因为使用了多级页表，一级页表必须存储在 RAM 中，因为一级页表只告诉我们二级页表的物理地址，所以我们还需要一个二级页表来获取实际的程序数据所在物理地址。一级页表有 1024 个 PTE，每个 PTE 大约 4B，所以一级页表是 4KB，二级页表同样如此，所以总共为 4KB+4KB，这比 4MB 好多了！

下面是一个二级页表使用的一个例子。

CPU 使用到了虚拟地址 0x00402204，那就需要将其转换为物理地址，转换过程中将虚拟地址分为两个部分：虚拟页号和页内偏移，虚拟页号又分为一级页表编号和二级页表编号。两级页表分别使用虚拟页号的一半（10 位），对于虚拟地址 0x00402204，一级页表编号 N1 是 0000 0000 01，二级页表编号 N2 是 00 0000 0010，首先使用 N1 查询 RAM 中的一级页表得到二级页表的物理页地址（一个页刚好是 4KB，二级页表的大小），如果页不在 RAM 中就需要将它加载到 RAM 中并更新一级页表，然后使用 N2 查询二级表获取实际数据的物理页地址，如果实际数据的内存页不在 RAM 中就需要加载到 RAM 中并更新二级页表，最终通过物理页地址和虚拟地址的页内偏移得到了最终的物理地址。

小结一下：

  • 每个运行的程序需要一个一级页表存储在 RAM 中，这样可以获取低级的页表以获取实际数据的物理页。
  • 需要一个二级页表存储在 RAM 中，这样我们可以翻译程序的某些地址，随时切换。
  • 使用两级页表共同完成地址 VA->PA 的转换
  • 高 10 位地址用于索引一级页表的 PTE
  • 接下来的 10 位用于索引二级页表的 PTE
  • 我们可以置换页表中的一部分到 DISK 硬盘中

虚拟内存和高速缓存 Cache

这一部分讨论有关 TLB 转译后备缓冲区和高速缓存 Cache 的交互问题。

我们通常有两种方式来将 TLB 和 Cache 来交互：

  • 物理缓存（Physical Cache），Cache 使用物理地址（比较慢，访问 cache 之前必须做一次 TLB 地址转换，假设 TLB 转换需要 1 个周期、物理地址读取 Cache 需要 1 个周期）

  • 虚拟缓存（Virtual Cache），Cache 使用虚拟地址直接获取缓存数据（很快，1 个周期），不必进行地址转换，如果 Cache 没有命中才会发生地址转换。

对于虚拟缓存来说，两个程序不能共享虚拟缓存，因为虚拟缓存使用的是虚拟地址，虚拟内存的程序隔离机制无法起作用（因为地址没有转换），这也是虚拟缓存的一个问题。我们也可以简单地解决这个问题，方法就是不仅仅使用虚拟地址，再添加一个标志位用于区分是哪一个应用程序（比如 PID）。

有没有两全其美的方法，访问 Cache 的同时访问 TLB，仍然可以使用虚拟内存的隔离机制。

  • 还是使用虚拟地址 VA 访问 Cache，cache 数据记录中有一个物理标志 PTag，同时通过 TLB 将虚拟地址 VA 转换为物理地址 PA
  • 通过物理标志 PTag（缓存数据所在的 RAM 物理地址）和 TLB 获取的物理地址 PA 比较是不是命中

这只是想法，具体实现还是有些差别，下面一步步说明。

这种访问我们称之为虚索引实标签缓存（Virtually Indexed,Physically Tagged），这是当今处理器中最常用的一级缓存。

这种缓存利用了页面技术的一个特征，即虚拟地址和物理地址享有相同的页内偏移值（page offset）。(Wikipedia)

  • Cache 通过页内偏移（虚拟和物理是相通的）索引
  • 用物理页面号做标志

这样我们既实现了使用虚拟地址访问 Cache（快速，不用地址转换），又实现了虚拟内存隔离保护机制（物理地址做标志）。

这种技术的一个缺点是，在使用直接匹配缓存的前提下，缓存大小不能超过页面大小，否则页面偏移范围就不足以覆盖缓存索引范围。这个弊端可以通过提高组相联路数来改善。(Wikipedia)（待完善）

总结一下：

  • TLB 地址转换和查询 Cache 同时进行
    • 使用虚拟页号进行地址 TLB 转换
    • 使用虚拟地址偏移量进行 cache 索引
    • 通过 TLB 获取了物理页号
    • 通过 Cache 获取了物理标志（物理页号）
  • TLB 转换得到的物理页号和物理标志 PA Tag 相等说明缓存命中。

这种方式快速的原因是地址转换和 cache 索引同时进行，安全的原因是 Cache 只有在物理地址匹配的情况下才会命中。

总结

以上便是对虚拟内存的学习和总结，可能还有一些地方会有错误或者知识点漏洞，希望读者可以热情的提出 issue。如果还有不理解的地方可以查阅文章末尾我所参考的一些资料，谢谢阅读！

参考资料

引用作品

引用文献

参阅书目