第9章 虚拟内存
参考资料
异常控制流
概念
为了更加有效地管理内存并减少出错,现代系统提供了一种对主存的抽象概念,叫做虚拟内存(VM)。
虚拟内存是硬件异常、硬件地址翻译、主存、磁盘文件和内核软件的完美交互,它为每个进程提供了一个大的、一致的和私有的地址空间。
虚拟内存提供了三个重要能力:
- 将主存看成一个存储在磁盘上的地址空间的高速缓存,在主存中只保存活动区域,并根据需要在磁盘和主存中传送数据。
- 为每个进程提供了一致的地址空间,简化了内存管理。进而简化了链接、进程间共享数据、进程的内存分配、程序加载。
- 保护了每个进程的地址空间不被其他进程破坏。
存储器层次结构:
从这个层次结构来看,从上到下,设备的访问速度越来越慢,容量越来越大,每字节的造价也越来越便宜。这个层次结构的主要思想就是:上一层存储设备是下一层存储设备的高速缓存。例如,寄存器文件就是 L1 的高速缓存,L1 是 L2 的高速缓存,内存是磁盘的高速缓存等等。
虚拟内存的几个特点:
- 虚拟内存遍及计算机系统的所有层面,在硬件异常、汇编器、链接器、加载器、共享对象、文件和进程的设计中都扮演着重要角色。
- 虚拟内存给予应用程序强大的能力,可以创建和销毁内存片(chunk),将内存片映射到磁盘文件的某个部分,以及与其他进程共享内存。
- 虚拟内存很危险。每次应用程序引用一个变量、间接引用一个指针或调用一个如 malloc 的动态分配程序时,都会和虚拟内存交互,如果使用不当就会发生错误。
物理和虚拟寻址
计算机系统的主存被组织成一个由 M 个连续的字节大小的单元组成的数组。每字节都有一个唯一的物理地址。CPU 访问内存最自然的方式就是使用物理地址,称为物理寻址。
现代 CPU 使用的是虚拟寻址:CPU 通过生成一个**虚拟地址(VA)**来访问主存,这个虚拟地址首先通过地址翻译转换为物理地址。
地址翻译需要 CPU 硬件和操作系统之间的紧密合作。CPU 芯片上名为内存管理单元(MMU)的专用硬件,利用存放在主存中的查询表来动态翻译虚拟地址,该表的内容由操作系统管理。
地址空间
地址空间是一个非负整数地址的有序集合:{0, 1, 2, ...}
如果地址空间中的整数是连续的,就称为线性地址空间(line address space)。
假定使用的线性地址空间,在一个带虚拟内存的计算机系统中,CPU 从一个有 N=2^n 个地址的地址空间中生成虚拟地址,这个地址空间称为虚拟地址空间(virtual address space):{0,1,2,...,N-1}
一个地址空间的大小是由表示最大地址所需要的位数来描述的,例如现代的 64 位计算机一般支持 64 位虚拟地址空间。
主存中的每个字节都有一个虚拟地址和一个物理地址。
虚拟内存作为缓存的工具
虚拟内存作为磁盘的高速缓存,和存储器层次结构中的其他缓存一样,磁盘(较低层)中的数据被分割成块,作为磁盘和主存(较高层)之间的传输单元。
VM(虚拟内存)系统通过将虚拟内存分割为虚拟页(Virtual Page,VP)来处理此问题。每个虚拟页的大小为 P=2^p。
类似的,物理内存被分割为物理页(PP),大小也是 P 字节。物理页也被称为页帧。(虚拟页VP存储在磁盘上,物理页PP缓存在DRAM中)
任何时刻,所有的虚拟页都被分为了三个不相交的子集:
- 未分配的:VM 系统还未分配(未创建)的页。未分配的块没有任何数据与它们相关联,因此不占用任何磁盘空间。
- 已缓存的:当前已缓存在物理内存中的已分配页。
- 未缓存的:未缓存在物理内存中的已分配页。
示例如下:虚拟页0和3未分配;1,4,6为已缓存的;2,5,7为已分配但未缓存的。
DRAM缓存的组织结构
术语DRAM缓存表示虚拟内存系统的缓存,她在主存中缓存虚拟页。
主存一般采用 DRAM,DRAM 与磁盘之间的速度差要比 SRAM 与 DRAM 之间的速度差大很多,并且从磁盘的一个扇区读取第一个字节的时间开销比读这个扇区中的连续字节要慢很多。因此 DRAM 缓存的组织结构与高速缓存有很大不同。
因为严重的不命中处罚和访问第一个字节的开销,虚拟页一般很大,通常在 4KB~2MB,且 DRAM 缓存是全相联的,即任何虚拟页都可以放在任何的物理页中。不命中时的替换策略也很重要。
因为访问磁盘很慢,所以 DRAM 都采用写回(即延时写),而非直写。
页表
VM 系统需要判定一个虚拟页是否缓存在 DRAM 中的某个地方,如果是,需要确定虚拟页存放在哪个物理页中,如果不命中,需要判断虚拟页存放在磁盘的哪个位置;在 DRAM 中选择一个牺牲页,并把虚拟页从磁盘复制到 DRAM 中,替换这个牺牲页。
这些功能是由软硬件联合提供的,包括操作系统软件、MMU 中的地址翻译硬件和一个存放在物理内存中的页表(page table)。
- 页表是一个存放在 DRAM 中的数据结构,它将虚拟页映射到物理页。
- 每次地址翻译硬件将一个虚拟地址转换为硬件地址时都会读取页表。
- 操作系统负责维护页表的内容,以及在磁盘和 DRAM 间传送页。
页表是一个页表条目(Page Table Entry ,PTE)的数组,虚拟地址空间中的每个页在页表中的一个固定偏移量处都有一个 PTE。可以认为 PTE 由一个有效位和一个 n 位地址字段组成。有效位表明该虚拟页是否被缓存在 DRAM 中。
对于三种不同的页,其页表条目的内容不同:
- 已缓存的页:有效位=1,n 位地址字段表示该页在 DRAM 中相应的物理页的起始地址。
- 未缓存的页:有效位=0,n 位地址字段表示该虚拟页在磁盘上的起始地址。
- 未分配的页:有效位=0,地址字段为空。
页命中
考虑一下当CPU想要读包含在VP2中的虚拟内存的一个字时会发生什么,如下图所示,VP2被缓存在DRAM中。
地址翻译硬件使用虚拟地址作为索引从页表中查找相应的页表条目PTE2,然后读取条目中的内容。因为设置了有效位,地址翻译硬件就知道VP2是缓存在内存中的,所以它使用PTE中的物理内存地址,构造出这个字的物理地址。
缺页
DRAM 缓存不命中称为缺页。如 CPU 要读取上图中的 VP3 时,会从页表条目的有效位发现该页没有被缓存。VM缺页之前如下图所示:
地址翻译硬件使用虚拟地址作VP3为索引从页表中查找相应的页表条目PTE3,从有效位可以判断出VP3未被缓存,并且触发一个缺页异常。
当发生缺页会触发一个缺页异常。缺页异常会调用内核中的缺页异常处理程序,该程序会从已缓存的页中选择一个牺牲页。如果该牺牲页之前已经被修改,内核会先将它复制回磁盘(即写回),然后内核会占用它的物理页并修改它的页表条目为未缓存的。
此例中需要牺牲的是存放在PP3的VP4,如果VP4已被修改,则内核先将它复制回磁盘,然后内核从磁盘复制VP3到内存中的PP3,更新PTE3
缺页异常处理完成后,会重新启动导致缺页的指令,该指令重新进行对该虚拟地址的操作。
此时,VP3已经缓存在主存中了,那么页命中能由地址翻译硬件正常处理了。
虚拟内存中相关概念:
- 页面调用(paging)或交换(swapping):在磁盘和内存之间传送页的活动。
- 页面调入:从磁盘换入DRAM
- 页面调出:从DRAM换出磁盘
- 按需页面调用:当有不命中发生时,才去换入页面。
分配页面
初始的虚拟地址空间中的虚拟页基本都是未分配的,当调用了 malloc 就会分配一个或一些新的虚拟页,这些页指向磁盘上的对应页面。
理解:或许是因为 malloc 只负责分配内存,不负责创建对象,所以 malloc 分配得到的页是未缓存的。
又是局部性救了我们
虚拟内存利用了局部性。通过将活动页面集合(称为工作集)缓存到 DRAM 中来减少出现缺页的情况。
如果工作集的大小超出了 DRAM 的大小,程序将会发生抖动,页面会不断地换进换出。
根据本节内容可以区分主存缓存与各高速缓存的组织结构的不同之处:
- 高速缓存将地址位划分为有效位、标记位、组索引位、块偏移位,通过组选择、行匹配、字抽取来完成对数据的操作。
- 主存采用了 VM 系统,使用页表来实现对数据的查找。
虚拟内存作为内存管理的工具
实际上每个进程都会有一个独立的虚拟地址空间,也都有一个独立的页表。不同进程的虚拟页面可能映射到同一个物理页面上。
通过按需页面调度与独立的虚拟地址空间,VM 在内存管理时实现了以下功能:
简化链接。独立的地址空间允许为每个进程的内存映像使用相同的基本格式,如代码段都是从 0x400000 开始,数据段都在代码段后,栈从用户进程地址空间最高的地方向下生长等。因为采用了虚拟地址,所以这些可执行文件是独立于物理内存中代码和数据的最终位置的。
简化加载。当要向内存中加载可执行文件和共享对象文件时,Linux 加载器为代码段和数据段分配虚拟页并将其标记为无效的(即未缓存的),将页表条目指向目标文件中适当的位置即可。
- 将一组连续的虚拟页映射到任意一个文件中的任意一个位置叫做内存映射。
简化共享。独立地址空间为操作系统提供了一个管理用户进程与操作系统自身之间共享的一致机制。操作系统通过将不同进程中适当的虚拟页面映射到相同的物理页面,从而安排多个进程共享这部分代码的一个副本,而不是在每个进程中创建单独的副本。
简化内存分配。当一个进程要求分配堆空间时,操作系统分配 k 个的连续的虚拟内存页面,并将它们映射到物理内存中任意位置的 k 个任意的物理页面。由于页表工作的方式,物理页面不需要是连续的。
虚拟内存作为内存保护的工具
每次 CPU 生成一个虚拟地址时,地址翻译硬件都会读一个 PTE,可以通过在 PTE 上添加一些额外的许可位来控制对一个虚拟页面内容的访问。
上图中每个 PTE 都添加了三个许可位:
- SUP:表示进程是否必须运行在内核模式下才能访问该页。
- READ:控制读的权限。
- WRITE:控制写的权限。
地址翻译
地址翻译是通过硬件实现的。地址翻译符号如下:
地址翻译是一个 N 元素的虚拟地址空间(VAS)和一个 M 元素的物理地址空间(PAS)之间的映射。
CPU 中有一个页表基址寄存器指向当前页表。n 位的虚拟地址包含 p 位的虚拟页面偏移和 n-p 位的虚拟页号。
MMU(内存管理单元) 利用虚拟页号来选择适当的 PTE,然后将 PTE 中的物理页号和虚拟地址中的虚拟页偏移量串联起来就得到了对应的物理地址。
页面命中时 CPU 硬件执行的步骤:
- 处理器生成一个虚拟地址,并把它传送给 MMU。
- MMU 根据虚拟地址生成 PTE 地址,并从主存请求得到它。
- 主存向 MMU 返回 PTE。
- MMU 构造物理地址,并把它传送给主存。
- 主存返回所请求的数据字给处理器。
上述步骤可以概括为:MMU 收到处理器传来的虚拟地址后,根据虚拟地址中的虚拟页号和页表基址寄存器的内容从主存的页表中获取对应 PTE 项,根据 PTE 项中的物理页号构造出物理地址并从主存中取回数据。
页面不命中时需要通过内核的缺页异常处理程序替换页,然后重新进行一遍上述步骤。
结合高速缓存和虚拟内存
大多数系统采用物理寻址来访问 SRAM 高速缓存,即先完成了地址翻译,再根据得到的物理地址到 SRAM 高速缓存中查找。因为访问权限的检查已经在地址翻译时完成,所以高速缓存无需处理保护问题。
利用TLB加速地址翻译
每次 CPU 产生一个虚拟地址,MMU 都要查阅一个 PTE,这带来了额外的开销。
许多系统在 MMU 中包括了一个关于 PTE 的小的缓存——翻译后备缓冲器(Translation Lookaside Buffer,TLB)。这样所有的地址翻译步骤在 MMU 中就可以执行完成。
TLB 采用了具有较高相联度的组相联方式,用于组选择和行匹配的索引和标记字段从虚拟地址的虚拟页号中提取出来。
当 TLB 不命中时,MMU 需要从 L1 高速缓存中取出相应的 PTE 替换 TLB 中的某个已存在的条目。
多级页表
如果只用一个页表来进行地址翻译,该页表就会很大,比如一个 32 位的地址空间、4KB 的页面、4 字节的 PTE,就需要一个大小为 4MB 的页表。
计算方法:
32位地址空间,即共有2^32个虚拟地址
每个页面(即页)4KB,即2^12
那么虚拟地址空间中共有2^32除以2^12,即2^20个页面(即页)
每个页都需要对应一个页表条目(即PTE),故页面条目的个数也是2^20
而每个 PTE 的大小是 4 字节,即2^2,那么2^20页表条目的总大小就是 2^22 字节了,即 4MB
2
3
4
5
对于64 位的系统而言,问题将变得更复杂。常用多级页表来压缩页表。
一个两级页表的例子
假设一个 32 位的虚拟地址空间被分为4KB的页,而每个页表条目都是4字节。同时,虚拟地址空间有如下形式:
- 内存的前2K页面分配给了代码和数据
- 接下来6K的页面未分配
- 再接下来的1023个页面也未分配
- 接下来的1个页面分配给用户栈
一级页表的每个 PTE 负责映射虚拟地址空间中的一个4MB的片,这里的每一片都是由1024个连续的页面组成的。
即4MB的片 X 1024 页面 = 4GB,覆盖了整个4G的虚拟地址空间。
如果某个片的 1024 个页面都没有被分配,那一级页表中这个片的 PTE 就是空的,只有该片中的页面被分配了,一级页表的 PTE 才会指向该片对应的二级页表的基址。
多级页表从两个方面降低了内存需求:
- 如果一级页表的 PTE 是空的,那相应的二级页表根本就不存在。
- 只有一级页表和最常用的二级页表才总是在主存中,VM 系统可以在需要时才创建、页面调入或调出二级页表。
多级页表
下图中虚拟地址被划分为了 k 个 VPN 和一个 VPO。每个 VPN i 都是一个到第 i 级页表的索引。
第 k 级页表中的每个 PTE 包含某个物理页面的 PPN(物理页号)或一个磁盘页的地址。其他页表中的 PTE 则包含对应的下一级页表的基址。
对于多级页表,要确定虚拟地址的物理页号,需要访问 k 个页表的 PTE。通过 TLB 将不同层次上页表的 PTE 缓存起来,但多级页表的地址翻译不比单级页表慢很多。
内存映射
内存映射:Linux 通过将一个虚拟内存区域与一个磁盘上的对象关联起来,来初始化这个虚拟内存区域的内容。
虚拟内存区域可以映射到两种类型的对象:
- Linux 文件系统中的普通文件:一个区域可以映射到一个普通磁盘文件的连续部分,如一个可执行目标文件。如果区域比文件区要大,就用 0 填充剩下的部分。
- 匿名文件:一个区域可以映射到一个匿名文件,匿名文件由内核创建,包含的全是二进制零。
无论哪种情况,一旦一个虚拟页面被初始化了,它就在一个由内核维护的专门的交换文件(也叫交换空间)之间换来换去。
交换空间的大小限制着当前运行着的进程能够分配的虚拟页面的综述。
再看共享对象
内存映射提供了清晰的机制,用来控制多个进程如何共享对象。
一个对象可以被映射到虚拟内存的一个区域,要么作为共享对象,要么作为私有对象。
- 共享对象的任何写操作,对其他进程都是可见的。(有区域)
- 私有对象的任何操作,对其他进程是不可见的。(私有区域)
共享对象的示意图:
私有对象使用一种写时复制的技术被映射到虚拟内存中。
再看fork函数
当fork函数被当前进程调用的时候,内核为新进程创建各种数据结构,并且分配它一个唯一的PID。为了给这个新进程创建虚拟内存。它创建了当前进程的mm_struct,区域结构和页表的原样副本。它将两个进程的每个页面都标记成只读,并且将两个进程中的每个区域接结构都标记成私有的写时复制。
当fork在新进程返回的时候,新进程现在的虚拟内存刚好和调用的fork时存在的虚拟内存相同。当这两个进程中的任意一个后来进行写操作,写时复制机制就会创建新的页面,因此,也就为每个进程保持了私有地址空间的抽象概念。
再看execve函数
execve函数在虚拟内存和内存映射中将程序加载到内存的过程中扮演了关键的角色。例如:
execve("a.out",NULL,NULL);
execve函数在当前进程中加载并运行包含在可执行目标文件a.out中的程序,用a.out程序有效地替代了当前程序。加载并运行a.out需要经过以下几个步骤:
删除已存在的用户区域:删除当前进程虚拟地址的用户部分中的已存在的区域(段)结构。
映射私有区域:为新程序的文本、数据、bss和栈区域创建新的区域(段)结构。
映射共享区域:如果a.out程序与共享库链接,那么这些对象都是动态链接到这个程序的,然后再映射到用户虚拟地址空间中的共享区域内。
设置程序计数器:execve做的最后一件事就是设置当前进程上下文中的程序计数器,使之指向文本段的入口点。
使用mmap函数的用户级内存映射
Linux程序可以使用mmap函数来创建新的虚拟内存区域,并将对象映射到这些区域中。
#include <unistd.h>
#include <sys/mman.h>
void* **mmap**(void* start, size_t length, int prot, int flags, int fd, off_t offset) ;
2
3
mmap函数要求内核创建一个新的虚拟存储器区域,最好是从地址start开始的一个区域,并将文件描述符fd指定的对象的一个连续的片(chunk)映射到这个新的区域。连续的对象片大小为length字节,从距文件开始处偏移量为offset字节的地方开始。start地址仅仅是一个暗示,通常被定义为NULL。
参数prot:描述新映射的虚拟内存区域的访问权限位。
PROT_EXEC:可被执行。
PROT_READ:可读。
PROT_WRITE:可写。
PROT_NONE:禁止访问
参数flags:描述被映射对象的类型。
MAP_ANON:被映射的对象是一个匿名对象。
MAP_PRIVATE:被映射对象是一个私有、写时拷贝的对象。
MAP_SHARED:被映射对象是一个共享对象。
例如:
bufp = mmap(-1, size, PROT_READ, MAP_PRIVATE | MAP_ANON, 0, 0) ;
让内核创建一个新的包含size字节的只读、私有、请求二进制零的虚拟内存区域。
munmap函数删除虚拟内存区域:
#include <unistd.h>
#include <sys/mman.h>
int munmap(void* start, size_t length) ;
munmap(bufp,size);
2
3
4
5
动态内存分配
动态内存分配器维护着一个进程的虚拟内存区域,称为堆。紧接未初始化的数据区域后面开始向上(高地址增长)。对于每一个进程,内核维护者一个变量brk,它指向堆的顶部。
分配器有两种基本的风格。两种风格都要求应用显式分配块。不同之处在于哪个实体负责释放已分配块:
- 显式分配器(explict allocator): 要求应用显示地释放任何已分配的块。例如, C标准库的 malloc 与 free函数
- 隐式分配器(implict allocator): 要求分配器检测一个已分配块何时不被程序使用时,再去释放块。隐式分配器也叫做垃圾收集器,而自动释放未使用的已分配块的过程叫做垃圾收集。Java语言做的比较出色
为什么要使用动态内存分配
最重要的原因:经常直到程序运行时,才知道某些数据结构大小。当然正确高效使用分配器十分重要。
分配器要求与目标:
- 处理任意请求序列
- 立即响应请求
- 只使用堆
- 对齐块
- 不修改已分配块,分配器只能操作或改变(空闲块)
分配器设计始终是在最大化吞吐率与最大化内存利用率之间平衡。
- 吞吐率:每个单位时间内完成的请求数。例如,一个分配器如果在一秒内完成500次分配请求和500次释放请求,那么吞吐率就是每秒1000次操作
- 利用率:当前已分配的块的有效载荷之和除以堆的当前大小。
碎片
碎片现象是造成堆利用率很低的主要原因。当虽然有未使用的内存但不能用来满足分配请求时,就发生这种现象。
- 内部碎片:是在一个已分配块比有效载荷大时发生的。例如,分配器字节对齐策略。
- 量化方式简单明了,就是已分配块大小和它们之间的有效载荷大小之差的总和。
- 碎片的数量:取决于以前请求的模式和分配器的实现方式。
- 外部碎片:是当空闲内存合计起来足够满足一个分配请求时,但是没有一个单独的空闲块足够大可以来处理这个请求时发生的。
- 即空闲内存块不是连续的块。
- 碎片的数量:不仅取决于以前请求的模式和分配器的实现方式,还取决于将来请求的模式。
- 难以量化或不可预测,所以分配器通常采用启发式策略来试图未出少量的大空闲块,而不是维持大量的小空闲块。
实现问题:
一个实际分配器要在吞吐率和利用率之间把握平衡,就必须考虑以下几个问题:
- 空闲块组织:空闲块如何记录?
- 隐式空闲链表
- 放置:如何选择一个合适的空闲块来放置一个新分配的块?
- 放置策略:首次适配、下一次适配和最佳适配
- 分割:在将一个新分配的块放置到某个空闲块之后,如何处理这个空闲块中的剩余部分?
- 策略会导致内部碎片的多少。
- 合并:如何处理一个刚刚被释放的块?
- 合并相邻的空闲块,以解决假碎片问题
垃圾收集
垃圾收集器是种动态内存分配器,它自动释放程序不再需要的已分配块。
垃圾收集器将内存视为一张有向可达图。
编程语言方面,像ML、Java这样的编程语言的垃圾收集器,对于创建指针比较有严格的规定,能够维护可达图的精准表达
Mark & Sweep 垃圾收集器
由标记阶段和清除阶段组成
C语言使用Mark & Sweep 垃圾收集器来处理的时候是必须保守的,其根本原因是因为C语言不会使用类型信息来标记内存位置
C程序中常见的与内存有关错误
与内存有关的错误经常在时间上和空间上距离错误源一段距离后才表现出来。
注意:以下错误都是 C 程序中的常见错误,不完全适用于 C++ 程序。
间接引用坏指针
虚拟地址空间中有一些大洞(即区域之间的部分),当试图间接引用一个指向这些洞的指针就会触发段异常。试图写一些只读的区域会触发保护异常。
经典的scanf错误
scanf("%d", val); //经典的 scanf 错误:试图将一个字写到 val 的值表示的地址处。
如果 val 的值对应一个空洞或不能写的位置,将触发异常。如果 val 的值对应一个合法的读写位置,将会修改该处的值,通常会产生灾难性后果。
读未初始化的内存
bss 段(如未初始化的全局变量)总是被加载器初始化为 0,但是堆内存并非如此。
常见错误:假设堆内存初始化为 0。
允许栈缓冲区溢出
如果不检查输入串的大小就写到栈中的目标缓冲区就可能导致缓冲区溢出错误。
gets(buf); //可能发生缓冲区溢出错误
fgets(buf); //fgets 限制了输入串的大小,避免了上述错误
2
其他错误
还有其他错误如下:
- 假设指针和它们指向的对象是相同大小的。如混淆 sizeof(int *) 和 sizeof(int)。
- 造成错位错误。访问数组元素时越界:A[n]。
- 引用指针,而不是它所指向的对象。如混用 *size-- 和 *(size--)。
- 误解指针计算。如忘记指针加一的单位是指针指向的对象的大小,而不是一个字节。
- 引用不存在的变量。如函数返回一个函数中的局部变量的地址。
- 引用空闲堆块中的数据。如引用已经被释放了的堆中的数据。
- 引起内存泄露。内存泄漏是缓慢、隐性的杀手,当忘记释放分配的块时会引发内存泄漏。
← 第8章 异常控制流 第10章 系统级I/O →