虚拟内存--机制说明，地址映射

1. 内存不够用怎么办？

众所周知, 在早期, 操作系统还没有分时的概念, 当时都是单进程执行, 只有一个进程结束了, 才能执行后一个进程. 但是这样的执行很容易想到的一个问题, 若进程在空闲状态, 则 CPU 就空下来了, 造成无谓的浪费. 后来为了解决这个问题, 于是进程可以主动申请轮换, 将当前时间交由其他进程. 但若是一个进程一直不出让控制权的话, 又退回到之前的情况了. 于是有了现在的分时系统, 即每个进程执行一小段时间, 然后强制切换到另一个进程执行, 由于切换的时间很短, 视觉上造成了很多进程同时执行的错觉.

但是, 当允许同时运行多个进程的时候, 就出现了新的问题, 内存不够。

假设你现在共有内存128m, 程序 A 运行需要100m, 程序 B 需要10m. 当分别运行的时候, 内存是足够的, 若同时运行程序 A 和 B, 将内存的0-100分给 A, 100-110 分给 B, 也够. 但是这种简单的内存分配有几个问题:

• 内存空间不隔离. 在早期的程序都是直接访问内存的, 同样也能够访问到相邻的地址, 恶意程序就有可能篡改其他程序的数据.
• 内存使用效率低. 因为运行程序的时候, 需要将整个程序全部读到内存中, 而其中很多内容其实并不会被访问到.
  运行地址不确定. 因为早期程序使用汇编编写, 读取数据一般通过地址硬编码的.
• 不可同时运行总内存超出128m 的程序.
• 等等吧

于是衍生出了虚拟内存的技术, 虚拟内存将内存存储在磁盘中, 待到需要的时候再读取到物理内存中.

1.1 解决方案1：分段

计算机中的一切问题, 都可以通过增加一个中间层来解决.

为了解决内存空间的隔离问题, 通过在程序与内存中添加一个中间层来解决. 于是, 将每一个程序的内存, 分别和物理内存进行映射, 如下:

操作系统维护着这样一个虚拟内存到物理内存之间的映射关系, 进程访问的地址通过映射, 转换为实际的物理地址.

这样, 当操作系统检测到访问的内存超出范围时可以进行干预. 同时, 映射关系对于进程来说是透明的, 每个进程不需要关心实际物理内存的变化, 只需要认为地址从0开始即可. 使用分段的操作, 解决了内存空间不隔离 和 运行地址不确定的问题.

但是, 分段操作也存在这一定的问题:

• 问题1. 不可同时运行100mb 的进程

  若总内存100mb, 进程 A 占用50mb, 进程 B 占用30mb, 此时想运行进程 C 需要50mb内存,因为剩余内存不足, 将进程 C 读入物理内存后, 势必会覆盖其他进程的内存空间. 这又该如何是好呢?

  其实也是有解决方法的, 那就是利用磁盘. 在进程 C 运行期间, 进程 A 肯定是不会得到执行的, 只需要暂时将进程 A 放到磁盘中, 就可以将进程 C 装入内存了. 之后再重复这个操作, 就可以重复执行进程 A 了. 但是磁盘的速度是十分缓慢的, 效率较低

• 问题2.内存碎片严重

  可以看到, 不同进程之间是存在内存碎片的. 如果内存中剩余空闲空间50mb, 但因为碎片的存在, 此时也无法申请一块50mb的连续内存.

  当然, 内存碎片也是提出过解决方案的, 和 GC 的标记复制思路一样, 将进程挪动到一块连续的地址空间中, 就可以将碎片连起来了, 但是内存复制的开销着实有点大.

以上…

试想一下, 现在运行两个进程, 每个占用内存100m, 那么每次切换进程时几乎都要重写整个内存. 而这个切换操作对于分时系统来说又十分频繁. 根据程序的局部性原理, 在一段时间内仅使用了一小部分数据. 也就是说, 如果分别给两个进程50m 的空间, 就可以满足一段时间内的运行需要的所有数据, 大大避免了内存的频繁置换.

1.2 解决方案2：分页

于是人们想到, 如果在上面的基础上将虚拟内存再切割成一个一个小块, 用到哪块读哪块, 岂不是就解决这个问题了么. 于是有了这样的模型:

进程能够看到的仍然只有虚拟内存, 不过, 操作系统将虚拟内存按照4k(比如) 的大小分成了很多块, 每一块称为一页. 其维护了虚拟内存中每一页到物理内存的映射关系, 这样就可以做到, 只将目前需要的部分内容读取到内存中.

同时, 可以针对页设置读写权限, 仅特定的进程可以对页进行读或写的操作, 非法读写会被系统捕捉到.

另外这种虚拟内存到物理内存转换, 是可以通过硬件支持的, 及内存管理单元MMU. CPU 将虚拟地址, 通过MMU转换后, 得到物理地址进行访问. MMU在进行地址翻译的时候, 会在物理内存中读取查询表来动态翻译地址, 而这张查询表是由操作系统进行维护的. 若读取时, 发现还没有读到物理内存内存中, 则交由操作系统将其读取到物理内存中, 并更新查询表.

因为有了虚拟内存的存在, 才可以在一个物理内存128m 的机器上, 运行需要内存200m 的进程, 虽然相比直接运行在物理内存上, 速度上要有一些牺牲. 在32位机器上, 虚拟内存最大为4G.

分页技术也是现在的操作系统使用的技术, 可以看到, 在进程看来连续的内存, 在物理内存中不一定连续. 也就是说你定义的数组, 可能分布在物理内存相隔很远的两个地方.

最后, 其实在虚拟内存出现之前, 内存分页就已经存在了

2. 虚拟内存的地址如何映射到磁盘的？

一个疑问, 那就是如何将虚存中的逻辑地址映射为物理地址呢? 今天就来简单分析一下.

对于一个分页的地址来说, 一般包含两个元素:

• 页号: 第几页
• 偏移量: 当前页的第几个字节

以下以 addr_virtual(p, o)表示一个逻辑地址, 以addr_real(p, o)表示一个物理地址(物理地址也是分页的).

2.1 映射关系存储在页表

第一步先想一下, 如果要根据一个逻辑地址找到对应的物理地址, 那么这个对应关系必然是存放在某个地方的, 因为映射是没有规律的嘛. 应该使用什么数据结构来存储呢?

因为在分页中, 页是一个最小单位, 故我们只需要页号的映射关系即可, 逻辑地址和物理地址的页大小相同, 偏移量也是完全一样的.

根据 key 寻找 value, 这不就是一个map嘛. 再一看这个map的key, 页号都是数字, 而且是顺序连续的. 这不就是个数组嘛. 漂亮, 就是一个数组.

也就是说, 这个页表是一个以逻辑页号为索引, 物理页号为值的一维数组. 那么这么一个地址转换流程大致如下:

页表中的元素并不是仅仅存储物理页号, 还存储了一些额外的标志位, 用来标识当前页的属性, 简单举几个例子:

• 存在位: 当前也是否加载到内存中了. 若没有加载需要操作系统进行加载
• 修改位: 当前页在内存中是否被修改过. 若修改过, 则回收物理内存时需要将其写会硬盘
• 内核权限: 当前页是否需要内核模式才能访问
• 是否可读位
• 是否可写位
• 是否可执行
• 等等

因为每个进程都拥有独自的虚拟内存, 故每个进程都需要自己的页表.

为了提高运行效率, 这个翻译过程是通过硬件完成的, 既CPU中的内存管理单元mmu来完成的.

现在简单分析一下这个简单模型存在的问题. 根据算法的经验, 大部分算法实现, 要么时间复杂度太高, 要么空间复杂度太高.

2.2 使用虚拟内存引发的时间复杂度问题

试想一下访问一个内存的步骤:

查找页表找到对应的物理地址

• 访问物理地址
• 查找页表的操作也是一次内存访问.

也就是说, CPU每访问一次内存就需要一次额外的内存访问. 执行时间直接翻倍.

2.2.1 解决方案：TLB

解决的方法就是我们现在已经用烂了的: 缓存. 内存到 CPU之间已经有了L1 L2缓存, 在mmu中还存在着一个页表的缓存TLB. 每次地址翻译的步骤如下(忽略缺页的情况):

• 查看TLB中是否存在缓存, 若存在直接获取
• 若TLB中不存在, 从内存页表中获取并放入TLB

TLB存在的前提, 是程序的访问具有局部性. 终于, 又是程序的局部性救了我们.

2.3 使用虚拟内存引发的空间复杂度问题

我们简单计算一下要存放这个页表需要多少空间.

在32位CPU 中, 可访问的逻辑地址空间为4G. 假设页大小为: 4kb, 那么总页数为:

4G / 4kb = (2^32) / (2^12) = 2^20 = 1mb

再假设, 页表的每个元素需要4个字节, 那么需要的总空间为: 4mb. 每个进程仅仅是存储页表就需要4mb. 而且这还是32位, 如果是64位呢? 可以计算下看看, 结果很夸张.

2.3.1 解决方案：多级页表

借鉴一下内存分页的思路, 我们将内存分为 n 个页, 就可以按需加载了. 同样, 也可以将一个大的页表分为n个小的页表, 就可以进行部分加载了, 既多级页表

以最简单的二级页表进行说明, 其虚拟内存划分大致如下:

页表的结构大致如下:

注意, 此时逻辑地址中页号内容存储了两个内容:

• 一级页表的索引
• 二级页表的索引

为什么说多级页表解决了空间的问题呢? 再次根据程序的局部性原理, 一级页表中的大部分对应的值为空, 既大部分二级页表并没有加载到内存中.

此时再算一下, 还是32位CPU, 页的大小还是4kb, 页中元素大小还是4字节. 此时假设一级页表每个元素负责4mb的空间. 那么一级页表占用的总页数为: 4G / 4mb = (2^32) / (2^22) = 2^10. 一级页表占用空间为: (2^10) * (2^2)=4kb

每个二级页表的总页数为: 4mb / 4kb = (2^22) / 2(12) = 2^10 = 1024, 占用空间: (2^10) * (2^2) = 4kb

其中只有一级页表是常驻内存的, 二级页表只需要加载其中一部分. 空间直接降下来了.

但是, 又带来一个新的问题, 现在获取一个物理地址, 需要访问两次内存, 这不是比原来还要慢么? 别忘了刚刚的TLB, 有了这一层缓存, 大部分访问都在mmu内部进行了. 又又又一次, 程序的局部性原理救了我们.

多级页表 , 将二级页表进一步扩展, 就可以得到多级页表了, 不再赘述.

2.4 聊聊所谓局部性原理

知道了地址是如何映射的, 对我们平常写程序有什么帮助呢?

页的转换是根据程序的局部性, 所以我们在写代码的时候, 要尽量保证写出来的是具有局部性的, 举个例子:

int main() {
    int i, j;int arr[1024][1024];// 第一种方式for(i = 0; i < 1024; i++){
    for(j = 0; j < 1024; j++){
    global_arr[i][j] = 0;}}// 第二种方式for(j = 0; j < 1024; j++){
    for(i = 0; i < 1024; i++){
    global_arr[i][j] = 0;}}
}

上面这段代码目的很简单, 给一个1024*1024的二维数组进行初始化. 你能看出这两种方式有什么不同么?

遍历方式不同, 方式一是一行一行的遍历, 方式二则是一列一列的遍历.

我们知道, 二维数组在内存中是顺序存储的. 也就是说, 一个二维数组: [[1, 2, 3], [4, 5, 6]], 在内存中的存储顺序是: 1, 2, 3, 4, 5, 6.

而我们这个数组, 每行1024个int元素, 正好是4kb 一页的大小.

因此, 方式一访问页的顺序是: page1, page1 … page1024, page1024, 每页访问1024次后,切换到下一页, 共发生 1024 次页的切换

而, 方式二访问页的顺序是: page1, page2…page1024 … page1, page2…page1024, 依次访问每一页, 每页访问1024次, 共发生 1024*1024次页的切换

性能高下立判, 方式一更加符合局部性原理, 方式二的访问太跳跃了.

当然, 现在内存很大的时候, 所有内容都加载到了内存中, 同时TLB缓存了所有页的映射, 此时两种方式是没有差别的. 但是:

• 若TLB容量不足, 新的缓存会淘汰旧的缓存, 频繁访问不同的页会造成更多的缓存失效
• 若内存容量不足, 写入新的页会淘汰旧的页, 频繁访问不同的页会导致更多内存的换入换出.

2.4.1 用代码验证局部性的存在

当然, 口说无凭, 为了对上面页的切换机制有个直观的感受, 我们通过getrusage函数来获取程序运行的页切换信息. 代码如下:

#include <stdio.h>
#include <sys/resource.h>const int M = 1024;
// 增加列的大小, 以使得效果明显. 10mb
const int N = 1024*10;
// 因为限制了栈的大小, 故将变量提升为全局, 放到堆中
int global_arr[1024][1024*10];int main() {
    int i, j;// 第一种方式for(i = 0; i < M; i++){
    for(j = 0; j < N; j++){
    global_arr[i][j] = 0;}}// 第二种方式
// for(j = 0; j < N; j++){
    
// for(i = 0; i < M; i++){
    
// global_arr[i][j] = 0;
// }
// }struct rusage usage;getrusage(RUSAGE_SELF, &usage);printf("页回收次数: %ld\n", usage.ru_minflt);printf("缺页中断的次数: %ld\n", usage.ru_majflt);
}

现在电脑跑这么个小程序还是比较简单的, 不会有什么区别, 因此还要对进程的内存进行限制. 我是通过限制docker可用内存来实现的:

docker run -it -m 6m --memory-swap -1 debian bash

好, 万事具备, 来看看结果:

方式一

方式二

可以看到, 方式一想比方式二要好很多.

故, 对于性能要求很高的程序, 当你没有优化方向了, 局部性可能会帮到你.

原文链接

• 虚拟内存
• 虚拟内存分页机制的地址映射
• 虚拟内存分页机制的页面置换