Virtua Memory Concepts
地址空间
之前内容把内存理解成一个连续的物理字节数组, 可以通过给出一些称为地址的偏移来访问
所以在使用物理寻址的系统中, 以 CPU 执行一条移动指令为例, 生成了一个有效的物理地址, 这个地址实际上是主存储器中一个字节的偏移量
像下面这样 CPU 在 PA 生成的物理地址为 4 后把地址发送给内存, 然后内存从该地址获取其中保存的字, 然后将其发送回 CPU
虚拟化
实际上, 这是非常简单的微控制器工作的方式, 但这并不是大多数系统的工作方式, 包括手机, 台式机和服务器
这些系统虚拟化这个主存储器, 现在, 虚拟化的概念在计算机科学中是非常重要的, 它扩展了很多, 应用于计算机系统的很多领域
当虚拟化资源时, 会向该资源的用户显示该资源的一些不同类型的视图, 这些视图通常是呈现某种抽象或某种不同的资源视图
可以通过介入对该资源的访问过程来实现这一点: 当有一些资源, 并且想要虚拟化它时, 通过干预或介入对该资源的访问过程来实现这一点
相同的技术可以用来虚拟化资源, 一旦拦截了访问的过程, 就可以用任何想要的方式处理它: 这样就有很多方法改变那个资源对用户的视图
看待磁盘的方式就是一个很好的例子: 磁盘在物理上由柱面、磁道、扇区、盘面组成, 访问这些磁盘上的一个特定扇区时, 必须指定柱面、磁道和盘面
但实际看到磁盘控制器显示的视图实际上不是这样的, 它是磁盘的虚拟化视图, 而磁盘控制器则将磁盘抽象成一系列逻辑块的形式提供给内核
它通过拦截来自内核的读写请求来呈现该视图, 并将内核发送的逻辑块号转换为实际的物理地址
虚拟寻址
磁盘虚拟化是通过让磁盘控制器拦截请求实现的, 对于主存储器资源, 这些请求由一块称为 MMU 的内存管理单元的硬件来处理
当 CPU 执行一条指令时, 比如移动指令, 会产生一个虚拟地址, 接着CPU 将该虚拟地址发送给 MMU。这是一个称为地址转换的过程
在下图中 MMU 将虚拟地址 4100 转换为物理地址 4, 这个物理地址 4 对应于实际想要的数据对象的地址。
在 MMU 将虚拟地址转换为物理地址之后, 内存会将返回存储在该地址中的字
用于所有现代服务器、笔记本电脑和智能手机。计算机科学的伟大思想之一。
地址空间
地址空间是一个地址的集合, 不是数据字节的集合, 而是字节的地址的集合:
- 线性地址空间是连续的非负整数集合, 只有
0,1,2,3,4等等 - 虚拟地址空间是包含
N = 2^n个虚拟地址的集合, 是线性地址空间 - 物理地址空间是包含
M = 2^m个物理地址的集合
| 线性地址空间 | 虚拟地址空间 | 物理地址空间 |
|---|---|---|
| 连续非负整数地址的有序集 | 一组 N = 2n 的虚拟地址 | 一组 M = 2m 的物理地址 |
虚拟地址空间通常比物理地址空间大得多, 物理地址空间对应于系统中实际拥有的 DRAM 容量。对于在该系统上运行的所有进程, 虚拟地址空间是相同的
意义
有效使用主内存: 将 DRAM 用作部分虚拟地址空间的缓存
虚拟内存使用 DRAM 作为存储在磁盘上的实际数据的缓存, 可以将虚拟内存视为存储在磁盘上数据的 DRAM 类缓存
仅仅将虚拟地址空间的一部分实际存储在物理存储器中, 这样只需缓存经常使用的数据, 通过仅使用虚拟地址空间的一部分, 可以更有效地使用内存
简化内存管理: 每个进程都获得相同的统一线性地址空间
地址空间对每个进程来说都是相同的, 代码以及数据总是加载到固定的地址, 栈位于用户可见地址空间的顶部
每个进程都具有相同的虚拟地址空间, 但实际上与虚拟地址相对应的内容分布在整个主存储器里
隔离地址空间: 一个进程不能干扰另一个进程的内存, 用户程序无法访问内核信息和代码
为进程提供了单独的地址空间, 可以防止其他进程访问: 虚拟内存允许创建这些单独的受保护的私有地址空间
作为缓存工具
概念上可以将虚拟内存视为存储在磁盘上的 N 个连续字节序列, 存储在磁盘上的虚拟内存的内容缓存在 DRAM 中, 所以 DRAM 是这些连续字节数组的缓存
像缓存一样, 数据被分解成块, 虚拟内存系统中的那些块称为页面, 且通常比的缓存块大得多, 通常是 4096 个字节而不是 64 字节 (大小为 P = 2p 字节)
虚拟内存可以看作存储在磁盘上的一系列页面, 这就是所谓的虚拟页面。这些页面中的每一个都将标识一个数字, 比如图中的虚拟页面 0, 虚拟页面 1
这些页面中的一部分存储在物理 DRAM 存储器中, 并且会有一些映射表示哪些页面已被缓存
如上图所示, 在 DRAM 中的某个地方缓存了三个虚拟页面, 虚拟页号与它映射到的物理页号之间没有关系
未缓存的页面只存储在磁盘上, 没有分配的页面既不存在于磁盘, 也不存在于内存中
如果操作系统为每个可能的虚拟地址都在磁盘上预留空间，那再大的硬盘也会瞬间被填满, 未分配意味着"不存在"，自然不需要占用任何存储资源。
比如64位系统下有天文数字个页面, 地址空间中的每一个地址都是 48 位的
虚拟内存的核心思想之一是"惰性"或"按需"分配。只有当程序真正需要一块内存时，操作系统才会在物理内存和磁盘上(如果需要换出的话)真正地为其创建实体。
DRAM 缓存结构
虚拟内存 DRAM 缓存结构选择全相联, 并通过记录页表位置查找命中, 其中页表的替换算法由操作系统实现。总是选择写回策略
将 DRAM 想象成缓存, 但它的组织形式与之前的缓存的差异是由于未命中时的巨大代价所致: DRAM 大约比 SRAM 慢 10 倍, Disk 比 DRAM 慢约 10,000 倍
巨大的未命中代价的后果: 假设有一个缓存和 DRAM, 那么在未命中时就要从磁盘中获取数据项, 会消耗很多时间, 直接映射的缓存会受到冲突未命中的影响。
增加缓存的关联性就可以减少冲突未命中的可能性, 但块的大小需要权衡: 既要从磁盘中获取数据块的代价分摊下来小, 又不要让数据块过多占用稀缺的缓存空间
在本例中缓存的块大小是 64 字节: 大多数虚拟内存系统的块大小是 4 KB, 有些系统是 4 MB, 这是 x86 系统的普遍情况
但除非缓存是全相联的, 否则永远不会完全消除冲突未命中的可能性: 于是虚拟内存在 DRAM 中的缓存是全相联的, 只有一个组
每个虚拟页面可能被缓存到缓存中的任何位置, 任何 VP 都可以放置在任何 PP 中, 但这样就 无法通过简单的取模运算 获知 VP 在哪个 PP 里
尽管 CPU 缓存有专用比较器, 可以使用硬件并行搜索查找全相联。但虚拟内存没有并行搜索电路。如果让软件去遍历搜索，代价高到无法接受
所以选择依靠一个专门的登记表(页表), 来记住所有这些被缓存的块在这个巨大的"全相联组"中的具体位置
当选择记录页表时, 又出现新的问题: 当尝试选出牺牲页时, 如果选错并且驱逐了一个即将用到的页面，CPU就会触发缺页异常，然后去读磁盘。
因此虚拟内存缓存具有比 LRU 更复杂的替换算法: 选出一个牺牲块所需的时间远小于错误的选择付出的代价: 获取块的时间, 由于缓存未命中而去访问磁盘的代价
一次磁盘I/O的时间是几毫秒级别(相当于几百万个CPU时钟周期), 但操作系统执行一段复杂的C代码来计算踢哪个页面，可能只花几微秒
这些复杂的替换算法超出了本课程的范围, 你会在操作系统课上学到这些算法
由于虚拟内存系统总是使用写回策略, 尽可能地将写回磁盘的操作推迟:
直写(WT，Write-Through)：只要CPU一写内存，立刻也写到磁盘。这会让程序慢如蜗牛(每次写都要等磁盘)。
写回(WB，Write-Back)：CPU只写DRAM里的缓存页，在页表里标记为"脏页"。直到这个页要被踢出内存时，才真正写到磁盘。
操作系统选择写回的原因：利用软件调度的灵活性，把多次写操作合并成一次磁盘写，极大地减少了磁盘访问次数。
页表
跟踪复杂的缓存和 DRAM, 记录虚拟页面位置的数据结构称为页表。内核维护并位于内存当中, 是每个进程上下文的一部分
所以每个进程都有自己的页表, 它由一系列将虚拟页映射到物理页的页表条目数组 (PTEs) 组成。其中 PTE k 保存的是 DRAM 中物理页面 k 的物理地址
图中右下是存储在磁盘上的虚拟页面, 图中右上是物理的, 物理中的 VP 是存储在 DRAM 中的不同物理页面中的虚拟页面
页表记录这些虚拟页存储的位置: 在上例中, 这个 PTE 1 对应虚拟页面 1, 这里表示虚拟页面 1 被映射到物理页面 0, 虚拟页面 2 被映射到物理页面 1, 依此类推
有些已分配但是不在内存中的页面, 存储在磁盘上, 对于这些页面, 页表条目包含指向该页面在磁盘上的位置的指针, 将其视为逻辑块编号, 可在磁盘上找到该页面
然后还有一些页面是未分配的, 因此这个页表中有一个空条目
页命中
缓存会有命中和未命中: 对虚拟地址空间中字的引用在页表中存在(在物理内存中)称为页命中, 这个字包含在缓存在 DRAM 中的页面中
已知 CPU 在执行指令时会生成一个虚拟地址, 接着 MMU 会在页表中查找: 假设此虚拟地址位于虚拟页面 2 中的某个位置, 那么 MMU 就去查找第 2 个页表条目
然后 MMU 会得到虚拟页面 2 的物理地址。在这种情况下, 页面在内存中, 它被缓存在内存中, 所以这是一次命中, 现在内存可以将该物理地址返回给 MMU
缺页
对虚拟内存中字的引用不在物理内存中, 也就是不在页表上, 说明没有缓存在 DRAM 中
在上面例子中: 虚拟页面 3 没有缓存在 DRAM 中, 它存储在磁盘上
缺页处理
页不命中会导致硬件触发异常: 这使得控制权转移给内核中称为缺页处理程序的代码, 这段代码选择要驱逐的牺牲页, 在这个例子里牺牲是虚拟页面 4
然后内核从磁盘中获取虚拟页面 3 将其加载到内存中然后更新此页表条目, 以反映虚拟页面 4 现在存储在磁盘上的事实
如果虚拟页面 4 曾经被修改过, 那么必须将修改的内容写入磁盘
一旦处理程序将虚拟页面 3 复制到内存中, 就可以重新执行导致缺页的指令: 内核中的缺页处理程序会返回到原来产生错误的指令, 然后重新执行该指令
现在当 MMU 查找到 PTE3 对应的页面时, 会发现它确实缓存在物理内存当中, 所以现在指令可以继续, 无论 DRAM 中的那个虚拟地址里保存的是什么字
页分配
假如调用了 malloc 函数分配一大块虚拟地址空间, 其中一个页面尚未分配, 那么内核或者 malloc 函数必须通过调用一个名为 sbrk 的函数来分配该内存
函数 sbrk 是一个 Unix/Linux 系统调用, 用于来请求增加堆空间: 函数 sbrk 在虚拟地址空间中划出块新区域, 在页表中创建条目, 记录"这个虚拟页面存在了"
调用 sbrk 时, 物理内存(DRAM)里没有任何变化, 没有实际的物理页被分配: 所做的只是分配空间、更改此页表条目
当程序第一次读/写这个新分配的页面时, CPU 去查页表发现"这个虚拟页面存在，但不在物理内存", 触发缺页异常
操作系统这时才真正分配一个物理页框, 把数据放进去, 更新页表，标记为"已缓存"
局部性
我不知道你们是怎么想的, 但在我第一次知道这个机制时, 我非常震惊, 它似乎是最低效的糟糕的想法
对于使用内存的每一条指令, 你怎么能负担得起, 把它们来回复制并查找页表的代价, 这似乎是一个糟糕的主意, 但是局部性再次拯救了我们
虚拟内存的效率似乎非常低, 但它的工作原理是局部性的: 由于时间局部性和空间局部性原理, 往往会重复使用相同的东西或者使用附近的东西
在任何时候程序都倾向于只访问一组称为工作集的活动虚拟页, 时间局部性较好的程序将具有较小的工作集
如果 (工作集大小 < 主存大小) : 内存可以存放下工作集中的所有页面, 对于一个进程来说，强制未命中后的性能良好
但系统运行多个进程, 出现(总和(工作集大小) > 主存大小), 进程就会互相颠簸, 页将不断换进换出, 导致页面来回复制
当我们学习地址转换时, 我们将学到一个称为翻译后备缓冲器的小硬件缓存, 这进一步利用了程序的局部性
内存管理工具
每个进程都拥有一个独立的虚拟地址空间, 它可以将内存视为简单的线性数组: 映射函数通过物理内存分散地址, 精心选择的映射可以提高局部性
虚拟内存极大地简化了内核对于内存管理的各个方面, 每个进程都有自己专属的虚拟地址空间: 内核通过为每个进程提供自己独立的页表来实现这一点
在进程的上下文中, 页表是内核中的数据结构, 是内核为进程所维护的, 每个进程的页表都映射该进程的虚拟地址空间
在虚拟地址空间中这些连续的页面, 可以映射到 DRAM 中的物理地址空间的任何位置, 它们可以分散在各处
不同的虚拟页面和不同的进程可以映射到不同的物理页面: 如图, 进程 1 的虚拟页面 1 映射到物理页面 2, 但在进程 2 中, 虚拟页面 1 被映射到物理页面 8
程序员可以认为每个进程都有一个相似的虚拟地址空间: 有相同大小的地址空间, 代码和数据分别从同一个地址开始, 但其实进程使用的页面实际上可能会分散在内存中
如果我们没有这个机制, 请考虑如何跟踪在这个机器上你如何能跟踪这些进程使用的所有数据的位置
在过去虚拟内存产生之前: 只为每个进程提供物理地址空间的一部分, 只将物理地址空间分区, 然后每个进程都只能在属于它的那一部分地址空间中加载和运行
如果要添加一个进程 D, 但 D 启动前, 进程A、B、C各占一块已经将预留区用完了。就算有预留, 预留太小也无法加载大程序
但如果让每个进程都得到一些小块，还会保留一些地址空间，以防新的进程需要内存: 预留的空间闲着不用，别的进程也用不了
不能提前链接程序, 因为程序必须知道自己真正要加载到物理内存的哪个位置, 它必须在加载时重定位
一个进程, 你不知道它会加载到内存的什么位置, 只知道它会使用内存的某些块
程序编译时不能确定最终地址, 加载进内存时加载器要扫描整个程序代码, 把所有涉及地址的指令，都加上一个"基地址"(程序实际加载的位置)
所以你必须要重定位所有的引用, 在实际加载时, 重定位对全局符号的引用
另一个方案就是程序里不许用绝对地址, 所有地址都写成"相对于程序开头偏移多少": 这大大限制了编程灵活性
或者你必须创建一个所有指令都使用相对地址的系统, 没有绝对地址, 所有地址都表示成相对于程序的开头而言的偏移
每个虚拟页面都可以映射到任何物理页面: 甚至在不同时刻, 相同的虚拟页面也可以存储在不同的物理页面中
一个页面, 有一段时间可能会缓存在一个物理页面中, 然后它被替换出, 并在下次引用时, 如果它没有被映射, 那么它可以重新被缓存到不同的物理页面中
还可以将多个虚拟页面映射到同一物理页面, 让不同进程中的页表条目指向相同的物理页面: 多个进程可以共享某些代码或数据的非常简单直接的方式
上图中虚拟页面 2 指向物理页面 6, 在进程 1 和进程 2 的页表中, 都是这样映射的, 这就是共享库的实现方式
所以 lib.c 对于系统上运行的每个进程来说都是相同的代码, lib.c 只需要加载到物理内存中一次
想要访问 lib.c 中的函数和数据的进程只需要映射, 让虚拟地址空间中的页面指向实际加载 lib.c 的物理页面
好的, 现在系统中只有一个 lib.c 的副本, 但每个过程都可以认为它有自己的副本
简化链接和加载
链接 每个程序都有相似的虚拟地址空间 代码、数据和堆总是从相同的地址开始
Loading execve 为 .text 和 .data 部分分配虚拟内存页，并创建标记为无效的 PTEs 虚拟内存系统根据需要逐页复制 .text 和 .data 部分
链接器假设每个程序都将加载到完全相同的位置: 所以链接器能提前知道这些东西将要加载到哪里, 然后它可以相应地重定位所有这些引用
加载程序, execve 会查看 elf 可执行二进制文件: 它知道该二进制文件中的代码和数据段有多大, 它从固定的地址开始为 .text 和 .data 部分分配虚拟内存页
加载器 execve 为代码和数据段创建 PTE, 并把每一个 PTE 都标记为无效的
虽然每个已分配的虚拟页面在页表中都有一个对应的页表条目，但这个条目的物理页号字段此时可能并没有指向实际的物理内存
操作系统通过将有效位设为0，表示这个页面虽然在虚拟地址空间中存在，但目前并不在物理内存中
- 节省物理内存：程序分配了 1GB 虚拟内存，但只用 100MB，物理内存只给那 100MB
- 按需加载：第一次访问时，有效位=0 触发缺页异常，操作系统才从磁盘加载
- 支持换出：内存紧张时，把不常用的页有效位设0，内容存磁盘，物理页给别人用
当 MMU 遇到有效位为 0 的 PTE 时触发缺页异常, 看起来好像该页面尚未初始化, 然后触发内核的缺页处理程序, 然后内核可以将该页面复制到物理内存中
程序和数据实际上并不是没有加载, 它们不是简单地复制到内存, 只有在缺页时才会复制它们, 也就是说在未命中时复制
只有第一次访问页面中的字节时才会复制这个页面, 这叫做按需分页
所以加载实际上是一个非常高效的机制, 因为你可能有一个程序, 其中包含一个巨大的数组, 但是你只是访问该数组的一部分
因此, 实际上不会给整个数组都分配页面, 这些页面只有在其中某个字被访问时才会加载到 DRAM 中
内存保护工具
虚拟地址空间的有些部分是只读的, 比如代码段, 地址空间中有些部分只能由内核执行
在像 x86-64 这样的 64 位系统上, 尽管指针和地址是 64 位的, 但真正的虚拟地址空间是 48(2^48) 位的
48 位之后的高位比特全部为 0 或全部为 1: 高位都是 1 的地址是为内核代码和内核数据保留, 高位都为 0 的地址是为用户代码保留的
因此可以在 PTE 中设置一些位, 表明用户代码是否可以访问某些虚拟页面, 或者它们是否必须由内核访问, 这就是所谓的管理员模式
可以设置一些位, 表示该页面是否可以读、写或执行: 这个执行位是 x86-64 的新功能, 它在 32 位 x86 系统中不存在
这是现在用来防止类似 AttackLab 中代码注入攻击的技术, 因为它使这种攻击变得不可能
如果此位设为 0, 则无法从该页面中的任何字节加载指令
事实上, 正因为引入了这个执行位, 才会催生出像 AttackLab 中那样的利用 ret 指令引导的攻击
通过向 PTE 添加位的简单技术, 保护虚拟地址空间的不同部分免受未经授权的访问: MMU 在每次访问时检查这些位, 如果相应的权限位是 0, 就抛出异常由内核处理