读CSAPP(4) - 虚拟内存

2019-09-28 约 3164 字

虚拟内存系统解决了物理寻址的缺点。利用内存管理单元（MMU）和页表（Page Table）将虚拟地址转换为物理内存地址。进程运行过程不再加载全部数据，而是只保留当前运行需要的数据在内存中。为了让MMU更高效加入了TLB，缓存映射关系，还利用多级页表降低页表内存占用有了

虚拟内存系统

计算机系统主存被组织成一个连续字节大小的数组，每一个数组成员都有一个唯一的物理地址（Physical Address）早期计算机使用物理寻址方式，这样的坏处是

系统中多个进程所使用的内存，进程之间容易互相读写数据造成各种问题
每个进程内存分布不同，管理不便
进程中暂无用处的数据也会被加载，进程过多就会导致内存不够用

现代处理器使用虚拟寻址（Virtual Address），利用虚拟地址映射成物理地址再进行访问，解决了上面的主要问题。既然需要地址转换，这就需要内存管理单元（Memory Management Unit，MMU）和页表（Page Table，PT）来处理

因为每个进程都有统一的访问方式，这样进程之间也不会互相影响
内存管理更加简单，每个进程看起来都在独享全部内存
节省内存空间，利用内存分页，物理内存中只保留进程当前活动区域，并根据需要在磁盘和主存之间来回传送数据

页表

虚拟内存系统将虚拟内存分割成一个个大小相同的虚拟页（Virtual Page，VP），类似的物理内存也被分割成物理页（Physical Page，PP）大小和VP相同，物理页也被称为叶帧（Page Frame）。页表其实就是一个数组，每个元素称为页表项（Page Table Entry，PTE），PTE负责把虚拟页映射到磁盘或者物理页上。

任意时刻虚拟页面的集合都分为三个不想交的子集：

未分配的：VM系统还未分配的页，物理内存，磁盘都没有与之关联的数据（图中0，3）
已分配已缓存的：已分配到了物理内存中（图中1，4，6）
已分配未缓存：数据块存在于磁盘中，还未被加载到内存（图中2，5，7）

页表项

当MMU从PTE获取物理内存地址，要根据PTE知道：

虚拟页是否被缓存了
缓存命中需要知道具体存在于哪个物理内存页中
缓存未命中需要知道此虚拟页在磁盘的什么地方进行缓存替换操作

整个页表数据结构由操作系统进行负责维护，以及在磁盘与主存之间来回传送页，进行替换的时候需要向系统内核发送一个缺页异常，内核会做一些处理。 PTE负责把虚拟页映射到磁盘或者物理页上，假设需要两个数据：

地址字段：存放映射的地址
有效位：判断此页是否被缓存

有了这两个字段就可以进行判断：

设置了有效位，地址字段不为空：数据缓存在物理内存页中，地址字段为物理页的起始位置
没有设置有效位，地址字段为空：此虚拟页还未被分配
没有设置有效位，地址字段不为空：虚拟页被分配，但还未缓存到物理内存中，只在磁盘上，地址字段指向该虚拟页在磁盘上的起始位置

映射流程

虚拟地址有两部分VPN+VPO。MMU利用VPN找到对应的PTE，例如 VPN 0 对应 PTE 0，找到PTE后，PTE中的有效位决定是否有效，是否需要缺页处理。如果有效，则得到其中的PPN，使用PPN+VPO 得到最终的物理内存地址

页面命中，cpu硬件流程：

缺页流程，页面命中完全由硬件处理，处理缺页需要硬件和操作系统内核协作完成：

虚拟内存系统带来的优势

权限控制

每个PTE（页表项）高位部分存储了表示权限的位，MMU通过检查这些位来进行权限控制（sup表示进程是否必须运行在内核（超级管理员）模式下才能运行）。如果违反了权限cpu会触发一个一般保护故障，将控制传给内核的异常处理程序，linux shell一般称之为段错误（segmentation fault）

节省内存

MMU根据虚拟地址读取页表，发现设置了有效位，表明缓存命中，地址字段存储了物理页地址，就可以找到数据在物理内存中的位置，这是页命中，相对的就会触发缺页异常（缓存不命中 page fault）：（见上图）

MMU读取页表想获得VP1地址的时候发现未设置有效位，缓存未命中，只存在于磁盘，并触发一个缺页异常
缺页异常会调用内核中的缺页异常处理程序，该程序选择一个牺牲页，将其复制回磁盘（页面调出），取消设置PTE的有效位
异常处理程序再把磁盘上的VP1复制到物理内存中（页面调入），设置有效位
将指令重新发到MMU，再次执行的时候就可以命中了

上述中磁盘与物理内存中传送页的活动叫交换（swapping）或者页面调度（paging），当不命中的时候才进行换页操作这种策略称为按需页面调度（demand paging）空间局部性和工作集导致效率高，如果不高说明发生了抖动（thrashing）

内存管理更加方便

进程看起来就可以独享整个计算机空间了，因为在进程眼里全部虚拟内存都可以使用，所以每个进程也需要有自己的页表来进行映射，操作系统为每个进程都提供了一个独立的页表。

这样做有很多好处：

简化链接器：每个进程都有独立空间，数据段相同，这样的一致性，简化了链接器的设计与实现
简化加载：把目标文件（可执行文件和共享对象文件）中的.text和.data节加载到一个新创建的进程中，Linux加载器为代码和数据段分配虚拟页，把他们标记为无效的（即未被缓存的），将页表条目指向目标文件中适当的位置。整个行为加载器不会从磁盘复制内容到内存，而是靠虚拟内存系统的按需页面调度来处理
简化共享：每个进程有了独立地址空间，一致性的处理方式，让多个进程之间共享一些内核库更加简单（如上图）
简化内存分配：页表进行了和物理内存的映射，所以在分配内存的时候不需要考虑连续个物理页空间，可以随机分配

让虚拟内存系统更健壮

缓存方式

在存储器章节说过，梯形存储体系中，本层存储器是为上一层提供缓存的，当高速缓存未命中由物理内存提供缓存服务，物理内存比高速缓存慢10倍。当物理内存缓存未命中由磁盘提供缓存服务，而磁盘比物理内存慢10w倍。所以物理内存的未命中代价开销要比高速缓存未命中大得多，而且读取磁盘中一个扇区的第一个字节时间开销比读这个扇区中连续字节要慢大约10w倍。所以：

物理页有更大的尺寸 4KB ~ 2MB：为了不命中处罚和访问第一个字节的开销
全相连：由于不命中处罚，任何虚拟页都可以放置在任何物理页中
缓存替换策略更复杂：不命中的时候替换进行替换页，替换错了还会出现缓存未命中，所以开销也会很大，需要更强大的替换算法（由操作系统提供）
写回而不是直写：访问磁盘很慢，所以需要一个修改位标记是否被修改，没有被修改就无需在替换的时候写入磁盘。

多级页表

32位操作系统就需要管理 $2^{32}$ 字节的虚拟内存地址 4GB

假设一个PTE需要4KB（$2 ^ {12}$ 字节），一共需要：$2^{32}$ * $2^{-12}$ = $2^{20}$ 个PTE

假设一条PTE记录有4个字节（$2^2$），一共需要 $2^{20}$ * $2^2$ = $2^{22}$字节 = 4MB

不分页情况下用4MB覆盖全部虚拟内存地址，也就是每个进程都有4MB的页表

多级页表主要从两部分降低内存：

如果一级页表中的一个PTE为空，那么对应的二级页表就不会存在
只有一级页表存在于主存中，虚拟内存系统可以按需创建，调入或调出二级页表

下图中，第一级页表每个PTE映射一个片（chunk）大小为$2^{10}$字节（可以理解为一个页表）。这样计算下来，一级页表总共4KB，二级页表共1024个chunk，但中只用到了3个也就是 3*4KB = 12KB。

下图展示了多级页表情况下整个映射过程，一级一级的索引到最终物理内存地址

虽然多级页表用空间换时间，但TLB和局部性让他并不比单级慢很多

TLB加速翻译

为了加速翻译 Translation Lookaside Buffer(TLB)，可以理解为页表在处理芯片上的缓存

第1步 cpu产生一个虚拟地址
第2，3步MMU从TLB取出对应PTE
第4步将这个虚拟地址翻译成物理内存地址然后发送到高速缓存/主存
返回数据

如果TLB不命中，则需要从高速缓存/主存取出相应PTE，存放到TLB，可能会覆盖已有TLB条目

目录