虚拟存储器

前几天又翻了翻《深入理解计算机系统》,相比几年前刚看这本书有了更多的理解,这也许就是一本好书的价值吧。因此尝试提炼和总结出对自己有用的东西,把书读薄。其中也加了一些自己的理解和查阅的相关资料。

虚拟存储器的意义

虚拟存储器提供了三个重要的能力:

  • 将主存看作是存储在磁盘上的高速缓存,并根据需要在磁盘和主存中传送数据,高效地运用主存
  • 为每个进程提供一致性的地址空间,简化了存储器管理
  • 保护每个进程的地址空间不被其它进程破坏

下面分别从这三个方面来谈虚拟存储器

1. 内存是磁盘的Cache

虚拟存储器和物理存储器一样,都分页管理,并且页大小是一致的。在任意时刻,虚拟页面(VP)的集合都分为三个不相交的子集:

  • 未分配:VM系统还未分配或创建的页,没有任何数据和它们相关联,因此不占用任何磁盘空间
  • 已缓存:当前缓存在物理存储器中的已分配页
  • 未缓存:没有缓存在物理存储器中的已分配页

同任何缓存一样,虚拟存储系统必须有某种方法来判定一个虚拟页是否被缓存在主存中,如果是,系统还必须确认这个虚拟页放在哪个物理页中,如果不命中,系统需要判断这个虚拟页存放在磁盘的哪个位置,并且该磁盘对应数据加载到主存中,并且在必要时,选择一个牺牲页(页面调度)。VM通过页表(page table)来维护虚拟页的状态和当前实际地址(主存地址/磁盘地址):

每个进程都有一份页表,页表本身是进程数据的一部分,操作系统负责维护页表的内容,并在磁盘和主存之间来回传送页。CPU通过虚拟地址访问主存时,MMU会先查看页表中该虚拟地址的页表条目:

  • 已缓存:如果页表条目标志位为已缓存,MMU则取出对应的物理页面地址,返回给CPU
  • 未缓存:如果页表条目标志位为未缓存,则DRAM缓存不命中,又称为缺页(page fault),此时会触发一个缺页异常,缺页异常会调用缺页异常处理程序,该程序选择一个牺牲页VP2(如果VP2已经被修改了,则将其写回磁盘),更新VP2的页表条目为未缓存,之后内核从磁盘拷贝目标页VP1到物理页,更新VP1的页表条目,最后返回。此时,页面置换已经完成,当异常处理程序返回时,会重新发起导致缺页的指令,而此时VP1对应的页表条目状态为已缓存,即按照页命中流程正常处理
  • 未分配:导致非法地址访问,段错误(segment fault)

巨大的不命中开销(磁盘读写效率比主存低10000倍)驱动着整个DRAM缓存设计的方方面面,由于磁盘读第一个字节的效率是读连续字节的效率的100000倍,因此页不能太小,通常是在4KB~2MB之间,并且DRAM Cache是全相连的,也就是说任何虚拟页都可以放置在任何的物理页中,而对于不命中的替换算法也更为精密,最后,由于对磁盘的访问时间很长,DRAM缓存总是使用写回,而不是直写。DRAM通常都工作得很好,这是因为程序的局部性(时间局部性和空间局部性)原理,但是如果程序的常驻集(工作集)超过了DRAM的大小,则会导致页面不断被换入换出,也就是页面颠簸。

另外,前面我们讨论的页面调度,都是在不命中发生时,才换入页面,这种策略称为按需页面调度(demand paging),也可以采用其它方法,比如尝试预测不命中,在页面实际被引用之前就换入页面。目前,所有现代系统使用的都是按需页面调度的方式。

2. 虚拟存储器提供的存储器管理

由于每个进程都有独立的页表,因此也提供了一个独立的虚拟地址空间,多个虚拟页面可以映射到同一个共享物理物理上。独立虚拟地址空间和按需调度的结合,对系统中存储器的使用和管理有深远的影响。VM机制简化了链接,加载,代码和数据共享,以及应用程序的存储器分配。

  • 简化链接:独立的地址空间,允许每个进程的存储器映像使用相同的基本格式,而不管代码和数据实际存放在物理存储器的何处。如Linux系统上每个进程都使用类似的存储器格式(.text,.data), 这样的一致性极大地简化了链接器的设计与实现,允许链接器生成全链接的可执行文件,这些可执行文件独立于物理存储器中的代码和数据的最终位置。

  • 简化加载:虚拟存储器还可以很容易地实现可执行文件和共享对象文件的加载,要把可执行文件加载到内存中,系统先分配虚拟页的一个连续的块(chunk),将页表条目指向目标文件中的适当位置,并且标记为未缓存的,即可将可执行文件中的指定节加载到虚拟内存中。需要注意的是,此时文件并未被真正加载到物理内存中,而是要等每个页初次被引用时,才会真正执行页面调入(按需调度)。另外,虽然分配的虚拟内存是连续的,但是具体缓存的物理页面,可以是离散的。

  • 简化存储器分配:虚拟存储器为用户提供一个简单的分配额外存储器的机制,当程序要求额外的堆空间时(如调用malloc),操作系统分配k个连续的存储器页面,并且将它们映射到物理存储器中的任意位置的k个物理页面。由于页表的存在,存储系统没有必要分配k个连续的物理页,页面可以随机分散在物理存储器中

3. 虚拟存储器提供的存储器保护

由于每个进程都有自己的独立虚拟地址空间,因此分离不同进程的私有存储器变得很容易。但进程私有存储器和共享存储器仍然需要访问控制(只读,可写等),这只需要在页表标志位上加上可读,可写等许可位来控制即可。如果一些指令违反了许可条件,CPU会触发异常,Unix Shell将这种异常报告为”段错误”(segmentation fault)。

虚拟存储器的应用

1. Linux虚拟存储器系统

如上,是Linux进程的虚拟存储器,Linux进程虚拟存储器有如下特性:

1.1 分段管理

Linux将虚拟存储器组织成一些区域(段)的集合,一个区域就是已经分配虚拟存储器的连续片,这些页是以某种方式相关联的。如代码段,数据段,堆,栈,共享库等。该进程每个存在的虚拟页都保存在某个段中,不属于某个段的虚拟页是不存在的,并且不能被进程引用。段的概念很重要,因为它允许虚拟地址空间有间隙,内核不用记录哪些不存在的虚拟页,这样的页也不会占用存储器,磁盘,内核等任何额外资源。(页表中应该还是存在所有虚拟页的条目的)。

如图,每个task_struct对应一个进程,其中pgd字段为第一级页表(页全局目录)基址,mmap字段则指向进行的虚拟内存结构信息,Linux为每个段分配一个vm_area_struct结构,这个结构是个链表,在对虚拟地址执行地址翻译时,Linux会先遍历vm_area_struct链表,判断VA是否合法,即是否在某个段中。之后根据vm_area_struct中的信息判断进程是否对VA有访问权限。由于遍历vm_area_struct可能带来的开销,Linux还使用AVL树来加速查询。

1.2 数据共享与访问控制

通过VM提供强大抽象能力,Linux进程可以实现多进程虚拟内存布局的灵活控制,从访问权限来看,进程虚拟存储器包括内核虚拟存储器和进程存储器,从共享/私有来看,所有进程共享内核代码与全局数据结构,并且有自己独立的页表,堆栈段,task_struct结构等。

这里有一些参考:Linux进程内存布局Linux地址翻译

2. 存储器映射

除了本身的段管理之外,Linux还允许用户手动建立段到磁盘对象之间的映射。虚拟存储器段可以映射到两种类型的文件对象:

  • 普通文件:一个段可以映射到普通磁盘文件的连续部分,文件区被分为页大小的片,每一片即为对应虚拟页面的初始内容(剩余部分用0填充)。由于按需页面调度,所有在进行存储器映射时,虚拟页面并没有实际交换如物理存储器,直到CPU第一次引用页面。
  • 匿名文件:匿名文件是由内核创建的,包含的全是二进制0,虚拟存储器段被映射到匿名文件时,当CPU第一次引用到虚拟页,该虚拟页面将被0覆盖。磁盘和存储器之间并没有实际的数据传送。因此,映射到匿名文件的段,也叫做请求二进制0的页。

无论在那种情况下,一旦虚拟页面被初始化了,就在一个由内核维护的交换文件(交换空间)中换来换去,在任何时刻,交换空间都限制这当前运行着的进程能够分配的虚拟页面总数。

一个对象可以以共享对象或私有对象的方式被映射到存储器段,前者对段的写操作其它进程可见,并且会写回到磁盘的原始对象中。后者的改动是私有的,只有自己可见,并且不会被写回。对于私有对象,Linux使用一种叫写时拷贝的机制来高效地执行映射,在执行私有映射时,物理内存在只有一份私有对象拷贝(但却被映射到不同虚拟地址空间中的段),只有当有进程尝试写私有区域的某个页面时,才会创建拷贝。fork()函数内部就是写时拷贝原理。

内核通过唯一的文件名来判断文件是否已经被加载,从而复用已映射的物理页面,使映射到多个共享区域的对象,在内存中,只需要存放一份拷贝。存储器映射有很多实际应用,如进程快速加载文件,进程间共享文件,动态链接库,execve()等。在Linux下,用户可通过mmap()来手动建立一个映射,这里有一篇不错的[mmap()的用法详解][]。

3. 存储器分配

应用程序可通过malloc申请一块连续的虚拟内存,在Linux下,虚拟内存的布局规定了malloc申请位置以及大小,当malloc申请小于MMAP_THRESHOLD(目前为128KB)的内存时,分配的是在堆区,用sbrk()进行对齐生长,而malloc一次性申请大内存(大于128K)时,分配在映射区(位于堆栈之间),而不是在堆区,glibc会返回一块匿名的mmap内存块。虽然malloc得到的虚拟内存对应用程序来说是连续的,而实际上可以是离散的物理页面,这一点大家都应该很清楚了。