第 9 章 虚拟内存
# 第 9 章 虚拟内存
虚拟内存是对主存的一个抽象
- 虚拟内存提供了三个重要的能力
- 它将主存看成是一个存储在磁盘上的地址空间的高速缓存
- 在主存中只保存活动区域
- 并根据需要在磁盘和主存之间来回传送数据
- 通过这种方式,它高效地使用了主存
- 在主存中只保存活动区域
- 它为每个进程提供了一致的地址空间,从而简化了内存管理
- 它保护了每个进程的地址空间不被其他进程破坏
- 它将主存看成是一个存储在磁盘上的地址空间的高速缓存
# 9.1 物理和虚拟寻址
物理寻址
- 物理地址 (Physical Address,PA)
- 计算机系统的主存被组织成一个由 M 个连续的字节大小的单元组成的数组
- 每字节都有一个唯一的物理地址
- 第一个字节的地址为 0,接下来的字节地址为 1,再下一个为 2,依此类推
- 使用物理地址访问内存,即被称为物理寻址(physical addressing)
- 一个使用物理寻址的系统
- 早期的 PC 使用物理寻址
- 而且诸如数字信号处理器、嵌入式微控制器以及 Cray 超级计算机这样的系统仍然继续使用这种寻址方式
虚拟寻址
- 现代处理器使用的是一种称为虚拟寻址(virtual addressing)的寻址形式
- 使用虚拟寻址,CPU 通过生成一个虚拟地址(Virtual Address,VA)来访问主存
- 将一个虚拟地址转换为物理地址的任务叫做地址翻译(address translation)
- 地址翻译需要 CPU 硬件和操作系统之间的紧密合作
- CPU 芯片上叫做内存管理单元(Memory Management Unit,MMU)的专用硬件
- 其利用存放在主存中的查询表来动态翻译虚拟地址
- 该查询表的内容由操作系统管理
- CPU 芯片上叫做内存管理单元(Memory Management Unit,MMU)的专用硬件
- 地址翻译需要 CPU 硬件和操作系统之间的紧密合作
# 9.2 地址空间
地址空间(address space)是一个非负整数地址的有序集合
- 如果地址空间中的整数是连续的,则它是一个线性地址空间(linear address space)
- 地址空间分为虚拟地址空间(virtual address space)和物理地址空间(physical address space)
# 9.3 虚拟内存作为缓存工具
页的概念
- VM 系统将虚拟内存分割为称为虚拟页(Virtual Page,VP)的大小固定的块
- 这些块是磁盘和主存(较高层)之间的传输单元
- 每个虚拟页的大小为
字节
- 类似地,物理内存被分割为物理页(Physical Page,PP)
- 大小也为
字节 - 物理页也被称为页帧(page frame)
- 大小也为
在任意时刻,虚拟页面的集合都分为三个不相交的子集
- 未分配的
- VM 系统还未分配(或者创建)的页
- 未分配的块没有任何数据和它们相关联,因此也就不占用任何磁盘空间
- 缓存的
- 当前已缓存在物理内存中的已分配页
- 未缓存的
- 未缓存在物理内存中的已分配页
- 示意图
# 9.3.1 DRAM 缓存的组织结构
约定用术语 SRAM 缓存来表示位于 CPU 和主存之间的 Ll、L2 和 L3 高速缓存,并且用术语 DRAM 缓存来表示虚拟内存系统的缓存,它在主存中缓存虚拟页
DRAM 缓存的组织结构完全是由巨大的不命中开销驱动的
- 因为大的不命中处罚和访问第一个字节的开销,虚拟页往往很大,通常是 4KB ~ 2MB
- 读第一个字的开销是指从磁盘的扇区读取数据
- 由于大的不命中处罚,DRAM 缓存是全相联的
- 即任何虚拟页都可以放置在任何的物理页中
# 9.3.2 页表
判定虚拟页的位置
- 虚拟内存系统必须有某种方法来判定一个虚拟页是否缓存在 DRAM 中的某个地方
- 如果命中,系统还必须确定这个虚拟页存放在哪个物理页中
- 如果不命中,系统必须判断这个虚拟页存放在磁盘的哪个位置
- 还可能需要在物理内存中选择一个牺牲页,并将虚拟页从磁盘复制到 DRAM 中,替换这个牺牲页
- 这些功能是由软硬件联合提供的
- 包括操作系统软件、MMU(内存管理单元)中的地址翻译硬件和一个存放在物理内存中叫做**页表(page table)**的数据结构
页表将虚拟页映射到物理页
- 每次地址翻译硬件将一个虚拟地址转换为物理地址时,都会读取页表
- 操作系统负责维护页表的内容,以及在磁盘与 DRAM 之间来回传送页
- 页表就是一个页表条目(Page Table Entry,PTE)的数组
- 虚拟地址空间中的每个页在页表中一个固定偏移量处都有一个 PTE
- 每个 PTE 是由一个有效位(valid bit)和一个 n 位地址字段组成的
- 有效位表明了该虚拟页当前是否被缓存在 DRAM 中
- 如果设置了有效位,那么地址字段就表示 DRAM 中相应的物理页的起始位置
- 这个物理页中缓存了该虚拟页
- 如果没有设置有效位
- 那么一个空地址表示这个虚拟页还未被分配
- 否则,这个地址就指向该虚拟页在磁盘上的起始位置
- 如果设置了有效位,那么地址字段就表示 DRAM 中相应的物理页的起始位置
- 示意图
# 9.3.3 页命中
下图中,对 VP 2 中一个字的引用就会命中
# 9.3.4 缺页
缺页的处理过程
- DRAM 缓存不命中称为缺页(page fault)
- 缺页会触发缺页异常
- 缺页异常调用内核中的缺页异常处理程序,该程序会选择一个牺牲页
- 如果此牺牲块已经被修改了,那么内核就会将它复制回磁盘
- 内核会修改牺牲块的页表条目,反映出其不再缓存在主存中这一事实
- 当异常处理程序返回时,它会重新启动导致缺页的指令
- 示意图
- VM 缺页(之前)。对 VP3 中的字的引用会不命中,从而触发了缺页
- VM 缺页(之后)。缺页处理程序选择 VP 4 作为牺牲页,并从磁盘上用 VP 3 的副本取代它
- 在缺页处理程序重新启动导致缺页的指令之后,该指令将从内存中正常地读取字,而不会再产生异常
- VM 缺页(之前)。对 VP3 中的字的引用会不命中,从而触发了缺页
按需调度页面
- 在磁盘和内存之间传送页的活动叫做交换(swapping)或者页面调度(paging)
- 页从磁盘换入(或者页面调入)DRAM 和从 DRAM 换出(或者页面调出)磁盘
- 按需页面调度(demand paging) 会一直等待,直到最后时刻
- 也就是当有不命中发生时,才换入页面
# 9.3.5 分配页面
操作系统分配一个新的虚拟内存页的过程
- 示意图: VP5 的分配过程是在磁盘上创建空间并更新 PTE 5,使它指向磁盘上这个新创建的页面
# 9.3.6 又是局部性救了我们
程序的局部性保证了虚拟内存的性能
- 尽管在整个运行过程中程序引用的不同页面的总数可能超出物理内存总的大小
- 但是局部性原则保证了在任意时刻,程序将趋向于在一个较小的活动页面(active page)集合上工作
- 这个集合叫做工作集(working set)或者常驻集合(resident set)
- 在初始开销,也就是将工作集页面调度到内存中之后
- 接下来对这个工作集的引用将导致命中,而不会产生额外的磁盘流量
抖动
- 如果工作集的大小超出了物理内存的大小,这时页面将不断地换进换出
- 这种状态叫做抖动(thrashing)
# 9.4 虚拟内存作为内存管理的工具
按需页面调度和独立的虚拟地址空间的结合,对系统中内存的使用和管理造成了深远的影响
VM 简化了链接和加载、代码和数据共享,以及应用程序的内存分配
简化链接
- 独立的地址空间允许每个进程的内存映像使用相同的基本格式
- 而不管代码和数据实际存放在物理内存的何处
- 一个给定的 Linux 系统上的每个进程都使用类似的内存格式
- 对于 64 位地址空间,代码段总是从虚拟地址 0x400000 开始
- 数据段跟在代码段之后,中间有一段符合要求的对齐空白
- 栈占据用户进程地址空间最高的部分,并向下生长
- 这样的一致性极大地简化了链接器的设计和实现
- 允许链接器生成完全链接的可执行文件
- 这些可执行文件是独立于物理内存中代码和数据的最终位置的
- 独立的地址空间允许每个进程的内存映像使用相同的基本格式
简化加载
- 虚拟内存还使得容易向内存中加载可执行文件和共享对象文件
- 要把目标文件中
.text
和.data
节加载到一个新创建的进程中- Linux 加载器为代码和数据段分配虚拟页,把它们标记为无效的(即未被缓存的)
- 并将页表条目指向目标文件中适当的位置(一般在磁盘上)
- 加载器从不从磁盘到内存实际复制任何数据
- 在每个页初次被引用时
- 要么是 CPU 取指令时引用的
- 要么是一条正在执行的指令引用一个内存位置时引用的
- 虚拟内存系统会按照需要自动地调入数据页
- 在每个页初次被引用时
- Linux 加载器为代码和数据段分配虚拟页,把它们标记为无效的(即未被缓存的)
简化共享
# 9.5 虚拟内存作为内存保护的工具
通过在 PTE 上添加一些额外的许可位来控制对一个虚拟页面内容的访问十分简单
- 每个 PTE 中已经添加了三个许可位
- SUP 位表示进程是否必须运行在内核(超级用户)模式下才能访问该页
- 运行在内核模式中的进程可以访问任何页面
- 运行在用户模式中的进程只允许访问那些 SUP 为 0 的页面
- READ 位和 WRITE 位控制对页面的读和写访问
段错误(segmentation fault)
- 如果一条指令违反了许可条件,那么 CPU 就触发一个一般保护故障
- 将控制传递给一个内核中的异常处理程序
- Linux shell 一般将这种异常报告为段错误(segmentation fault)
# 9.6 地址翻译
相关符号及其含义
使用页表的地址翻译
- 因为物理和虚拟页面都是 P 字节的,所以物理页面偏移(Physical Page Offset,PPO)和 VPO 是相同的
页面命中时,CPU 的执行步骤
缺页时,CPU 的执行步骤
# 9.6.1 结合高速缓存和虚拟内存
将物理寻址的高速缓存与虚拟内存结合起来
- 将地址翻译放在调整缓存查找之前即可
- 页表条目也可以缓存,就像其他的数据字一样
- 示意图
# 9.6.2 利用 TLB 加速地址翻译
MMU 中包括了一个关于 PTE 的小的缓存,称为翻译后备缓冲器(Translation Lookaside Buffer,TLB)
TLB 命中和不命中的操作图
# 9.6.3 多级页表
多级页表的目的是为了减小驻留在内存中的页表的大小
- 一个两级页表层次结构
- 图中一级页表中的每个 PTE 负责映射虚拟地址空间中一个 4MB 的片(chunk)
- 使用 4 字节的 PTE,每个一级和二级页表都是 4KB,刚好和一个页面的大小是一样的
- 如果一级页表中的一个 PTE 是空的,那么相应的二级页表就根本不会存在
- 只有一级页表才需要总是在主存中;虚拟内存系统可以在需要时创建、页面调入或调出二级页表
- 只有最经常使用的二级页表才需要缓存在主存中
- 这就减少了主存的压力
- 只有最经常使用的二级页表才需要缓存在主存中
使用 k 级页表的地址翻译
-
- TLB 可以将不同层次上页表的 PTE 缓存起来
- 因此带多级页表的地址翻译并不比单级页表慢很多
- TLB 可以将不同层次上页表的 PTE 缓存起来
# 9.6.4 综合: 端到端的地址翻译
# 9.7 案例研究: Intel Core i7/Linux 内存系统
Intel Core i7 的内存系统
- Core i7 实现支持 48 位(256 TB)虚拟地址空间和 52 位(4 PB)物理地址空间
- 还有一个兼容模式,支持 32 位(4 GB)虚拟和物理地址空间
# 9.7.1 Core i7 地址翻译
Core i7 地址翻译的概况
-
- 为了简化,没有显示 i-cache、i-TLB 和 L2 统一 TLB
页表条目格式
- 第一级、第二级和第三级页表条目格式。每个条目引用一个 4 KB 子页表
- 第四级页表条目的格式。每个条目引用一个 4 KB 子页
- PTE 有三个权限位,控制对页的访问
- R/W 位确定页的内容是可以读写的还是只读的
- U/S 位确定是否能够在用户模式中访问该页
- 从而保护操作系统内核中的代码和数据不被用户程序访问
- XD(禁止执行)位是在 64 位系统中引入的,可以用来禁止从某些内存页取指令
- 通过限制只能执行只读代码段,使得操作系统内核降低了缓冲区溢出攻击的风险
- 当 MMU 翻译每一个虚拟地址时,它还会更新另外两个内核缺页处理程序会用到的位
- 每次访问一个页时,MMU 都会设置 A 位,称为引用位(reference bit)
- 内核可以用这个引用位来实现它的页替换算法
- 每次对一个页进行了写之后,MMU 都会设置 D 位,又称修改位或脏位(dirty bit)
- 修改位告诉内核在复制替换页之前是否必须写回牺牲页
- 内核可以通过调用一条特殊的内核模式指令来清除引用位或修改位。
- 每次访问一个页时,MMU 都会设置 A 位,称为引用位(reference bit)
Core i7 页表翻译
- (PT:页表,PTE:页表条目,VPN:虚拟页号,VPO:虚拟页偏移,PPN:物理页号,PPO:物理页偏移量。图中还给出了这四级页表的 Linux 名字)
优化地址翻译
- 对地址进行翻译包括两个步骤
- MMU 将虚拟地址翻译成物理地址
- 将物理地址传送到 L1 高速缓存
- 实际上这两个步骤可以部分重叠,以加速对 L1 调整缓存的访问
- 因为 12 位的 VPO 和相应物理地址中的 PPO 的 12 位是相同的
- 因为八路组相联的、物理寻址的 L1 高速缓存有 64 个组和大小为 64 字节的缓存块
- 每个物理地址有 6 个缓存偏移位和 6 个索引位。这 12 位恰好符合虚拟地址的 VPO 部分
- 如此,PPN 正好对应于 CT (高速缓存标记) 的内容
- 当 CPU 需要翻译一个虚拟地址时,它就发送 VPN 到 MMU,发送 VPO 到高速 L1 缓存
- 当 MMU 向 TLB 请求一个页表条目时,L1 高速缓存正忙着利用 VPO 位查找相应的组
- 并读出这个组里的 8 个标记和相应的数据字
- 当 MMU 从 TLB 得到 PPN 时,缓存已经准备好试着把这个 PPN 与这 8 个标记中的一个进行匹配了
- 当 MMU 向 TLB 请求一个页表条目时,L1 高速缓存正忙着利用 VPO 位查找相应的组
# 9.7.2 Linux 虚拟内存系统
一个虚拟内存系统要求硬件和内核软件之间的紧密协作
Linux 为每个进程维护了一个单独的虚拟地址空间
-
- 内核虚拟内存包含内核中的代码和数据结构
- 内核虚拟内存的某些区域被映射到所有进程共享的物理页面
- Linux 也将一组连续的虚拟页面(大小等于系统中 DRAM 的总量)映射到相应的一组连续的物理页面
- 这就为内核提供了一种便利的方法来访问物理内存中任何特定的位置,例如
- 当它需要访问页表
- 或在一些设备上执行内存映射的 I/O 操作,而这些设备被映射到特定的物理内存位置时
- 这就为内核提供了一种便利的方法来访问物理内存中任何特定的位置,例如
- 内核虚拟内存的其他区域包含每个进程都不相同的数据。比如说
- 页表、内核在进程的上下文中执行代码时使用的栈
- 以及记录虚拟地址空间当前组织的各种数据结构
- 内核虚拟内存包含内核中的代码和数据结构
Linux 虚拟内存区域
- Linux 将虚拟内存组织成一些区域(也叫做段)的集合
- 一个区域(area)就是已经存在着的(已分配的)虚拟内存的连续片(chunk),这些页是以某种方式相关联的
- 例如,代码段、数据段、堆、共享库段,以及用户栈都是不同的区域
- 每个存在的虚拟页面都保存在某个区域中,而不属于某个区域的虚拟页是不存在的,并且不能被进程引用
- 区域的概念很重要,因为它允许虚拟地址空间有间隙
- 内核不用记录那些不存在的虚拟页,而这样的页也不占用内存、磁盘或者内核本身中的任何额外资源。
内核中虚拟内存区域的数据结构
- 图示
- 内核为系统中的每个进程维护一个单独的任务结构(源代码中的 task_struct)
- 任务结构中的元素包含或者指向内核运行该进程所需要的所有信息,例如
- PID、指向用户栈的指针、可执行目标文件的名字,以及程序计数器
pgd
指向第一级页表的基址mmap
指向一个vm_area_structs
(区域结构) 的链表
- 当内核运行这个进程时,就将 pgd 存放在 CR3 控制寄存器中
- 一个具体区域的区域结构包含下面的字段:
vm_start
- 指向这个区域的起始处
vm_end
- 指向这个区域的结束处
vm_prot
- 描述这个区域内包含的所有页的读写许可权限
vm_flags
- 描述这个区域内的页面是与其他进程共享的,还是这个进程私有的(还描述了其他一些信息)
vm_next
- 指向链表中下一区域结构
- 图示
Linux 缺页异常处理
- 假设 MMU 在试图翻译某个虚拟地址 A 时,触发了一个缺页
- 这个异常导致控制转移到内核的缺页处理程序,处理程序随后就执行下面的步骤
- 虚拟地址 A 是合法的吗?
- 换句话说,A 在某个区域结构定义的区域内吗?
- 实际应用中,Linux 在区域链表中构建了一棵树,并在这棵树上进行查找
- 试图进行的内存访问是否合法?
- 换句话说,进程是否有读、写或者执行这个区域内页面的权限
- 如果上面两项均合法,则内核知道了这个缺页是由于对合法的虚拟地址进行合法的操作造成的
- 虚拟地址 A 是合法的吗?
- 示意图
# 9.8 内存映射
内存映射的基本概念
- Linux 通过将一个虚拟内存区域与一个磁盘上的对象(object)关联起来,以初始化这个虚拟内存区域的内容
- 这个过程称为内存映射(memory mapping)
- 虚拟内存区域可以映射到两种类型的对象中的一种
- Linux 文件系统中的普通文件
- 一个区域可以映射到一个普通磁盘文件的连续部分
- 例如一个可执行目标文件
- 文件区(section)被分成页大小的片,每一片包含一个虚拟页面的初始内容
- 因为按需进行页面调度,所以这些虚拟页面没有实际交换进入物理内存,直到 CPU 第一次引用到页面
- 即发射一个虚拟地址,落在地址空间这个页面的范围之内
- 如果区域比文件区要大,那么就用零来填充这个区域的余下部分。
- 一个区域可以映射到一个普通磁盘文件的连续部分
- 匿名文件
- 一个区域也可以映射到一个匿名文件
- 匿名文件是由内核创建的,包含的全是二进制零
- CPU 第一次引用这样一个区域内的虚拟页面时,内核就在物理内存中找到一个合适的牺牲页面,如果该页面被修改过,就将这个页面换出来,用二进制零覆盖牺牲页面并更新页表,将这个页面标记为是驻留在内存中的
- 注意在磁盘和内存之间并没有实际的数据传送
- 因为这个原因,映射到匿名文件的区域中的页面有时也叫做请求二进制零的页(demand-zero page)
- Linux 文件系统中的普通文件
交换空间(swap space)或者交换区域(swap area)
- 一旦一个虚拟页面被初始化了,它就在一个由内核维护的专门的交换文件(swap file)之间换来换去
# 9.8.1 再看共享对象
内存映射提供了一种清晰的机制,用来控制多个进程如何共享对象
- 一个对象可以被映射到虚拟内存的一个区域,要么作为共享对象,要么作为私有对象
- 如果一个进程将一个共享对象映射到它的虚拟地址空间的一个区域内
- 那么这个进程对这个区域的任何写操作
- 对于那些也把这个共享对象映射到它们虚拟内存的其他进程而言,也是可见的
- 而且,这些变化也会反映在磁盘上的原始对象中
- 那么这个进程对这个区域的任何写操作
- 对于一个映射到私有对象的区域做的改变
- 对于其他进程来说是不可见的
- 并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中
- 一个映射到共享对象的虚拟内存区域叫做共享区域。类似地,也有私有区域
共享对象的共享过程
- 示意图
- 因为每个对象都有一个唯一的文件名,内核可以迅速地判定进程 1 已经映射了这个对象
- 因而可以使进程 2 中的页表条目指向相应的物理页面
- 关键点在于即使对象被映射到了多个共享区域,物理内存中也只需要存放共享对象的一个副本
私有对象的写时复制 (copy-on-write)
- 示意图
- 一个私有对象开始生命周期的方式基本上与共享对象的一样,在物理内存中只保存有私有对象的一份副本
- 图中两个进程将一个私有对象映射到它们虚拟内存的不同区域,但是共享这个对象同一个物理副本
- 对于每个映射私有对象的进程,相应私有区域的页表条目都被标记为只读
- 并且区域结构被标记为私有的写时复制
- 只要没有进程试图写它自己的私有区域,它们就可以继续共享物理内存中对象的一个单独副本
- 然而,只要有一个进程试图写私有区域内的某个页面,那么这个写操作就会触发一个保护故障
- 当故障处理程序注意到保护异常是由于进程试图写私有的写时复制区域中的一个页面而引起的
- 它就会在物理内存中创建这个页面的一个新副本
- 更新页表条目指向这个新的副本,然后恢复这个页面的可写权限
- 当故障处理程序返回时,CPU 重新执行这个写操作,现在在新创建的页面上这个写操作就可以正常执行了
- 当故障处理程序注意到保护异常是由于进程试图写私有的写时复制区域中的一个页面而引起的
通过延迟私有对象中的副本直到最后可能的时刻,写时复制最充分地使用了稀有的物理内存
# 9.8.2 再看 fork
函数
fork
函数的调用过程
- 当
fork
函数被当前进程调用时,内核为新进程创建各种数据结构,并分配给它一个唯一的 PID- 为了给这个新进程创建虚拟内存,它创建了当前进程的
mm_struct
、区域结构和页表的原样副本 - 它将两个进程中的每个页面都标记为只读,并将两个进程中的每个区域结构都标记为私有的写时复制
- 为了给这个新进程创建虚拟内存,它创建了当前进程的
- 当
fork
在新进程中返回时,新进程现在的虚拟内存刚好和调用fork
时存在的虚拟内存相同- 当这两个进程中的任一个后来进行写操作时,写时复制机制就会创建新页面
- 因此,也就为每个进程保持了私有地址空间的抽象概念
# 9.8.3 再看 execve
函数
execve
函数的调用过程
- 以
execve("a.out", NULL, NULL);
为例 - 加载并运行
a.out
需要以下几个步骤- 删除已存在的用户区域
- 删除当前进程虚拟地址的用户部分中的已存在的区域结构
- 映射私有区域
- 为新程序的代码、数据、bss 和栈区域创建新的区域结构
- 所有这些新的区域都是私有的、写时复制的
- 代码和数据区域被映射为
a.out
文件中的.text
和.data
区 - bss 区域是请求二进制零的,映射到匿名文件,其大小包含在 a.out 中
- 栈和堆区域也是请求二进制零的,初始长度为零
- 映射共享区域
- 如果
a.out
程序与共享对象(或目标)链接- 比如标准 C 库 libc.so
- 那么这些对象都是动态链接到这个程序的,然后再映射到用户虚拟地址空间中的共享区域内
- 如果
- 设置程序计数器(PC)
execve
做的最后一件事情就是设置当前进程上下文中的程序计数器,使之指向代码区域的入口点
- 删除已存在的用户区域
- 示意图
# 9.8.4 使用 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);
// 返回:若成功时则为指向映射区域的指针,若出错则为 MAP_FAILED(-1)。
2
3
4
5
6
7
mmap
函数要求内核创建一个最好是从地址start
开始的新的虚拟内存区域- 并将文件描述符
fd
指定的对象的一个连续的片(chunk)映射到这个新的区域 - 连续的对象片大小为
length
字节,从距文件开始处偏移量为offset
字节的地方开始 start
通常被定义为NULL
,此时由内核来确定虚拟内存区域的起始地址- 各个参数的示意图如下
- 参数
port
含描述新映射的虚拟内存区域的访问权限位(即在相应区域结构中的vm_prot
位)PROT_EXEC
- 这个区域内的页面由可以被 CPU 执行的指令组成
PROT_READ
- 这个区域内的页面可读
PROT_WRITE
- 这个区域内的页面可写
PROT_NONE
- 这个区域内的页面不能被访问
- 参数
flags
由描述被映射对象类型的位组成MAP_ANON
- 被映射的对象就是一个匿名对象,而相应的虚拟页面是请求二进制零的
MAP_PRIVATE
- 表示被映射的对象是一个私有的、写时复制的对象
MAP_SHARED
- 表示是一个共享对象
- 并将文件描述符
bufp = Mmap(NULL, size, PROT_READ, MAP_PRIVATE|MAP_ANON, 0, 0);
- 让内核创建一个新的包含
size
字节的只读、私有、请求二进制零的虚拟内存区域 - 如果调用成功,那么
bufp
包含新区域的地址
- 让内核创建一个新的包含
munmap
函数删除虚拟内存的区域
#include <unistd.h>
#include <sys/mman.h>
int munmap(void *start, size_t length);
// 返回:若成功则为 0,若出错则为 -1
2
3
4
5
6
munmap
函数删除从虚拟地址start
开始的,由接下来length
字节组成的区域- 接下来对已删除区域的引用会导致段错误
# 9.9 动态内存分配
当运行时需要额外虚拟内存时,用动态内存分配器(dynamic memory allocator)更方便,也有更好的可移植性
堆
- 动态内存分配器维护着一个进程的虚拟内存区域,称为堆(heap)
- 系统之间细节不同,但是不失通用性,假设堆是一个请求二进制零的区域
- 它紧接在未初始化的数据区域后开始,并向上生长(向更高的地址)
- 对于每个进程,内核维护着一个变量
brk
(读做 “break”),它指向堆的顶部
分配器对堆的维护过程
- 分配器将堆视为一组不同大小的块(block)的集合来维护
- 每个块就是一个连续的虚拟内存片(chunk),要么是已分配的,要么是空闲的
- 已分配的块显式地保留为供应用程序使用
- 一个已分配的块保持已分配状态,直到它被释放
- 这种释放要么是应用程序显式执行的,要么是内存分配器自身隐式执行的。
- 一个已分配的块保持已分配状态,直到它被释放
- 空闲块可用来分配
- 空闲块保持空闲,直到它显式地被应用所分配
- 已分配的块显式地保留为供应用程序使用
分配器的两种基本风格
- 两种风格都要求应用显式地分配块。它们的不同之处在于由哪个实体来负责释放已分配的块
- 显式分配器(explicit allocator)
- 要求应用显式地释放任何已分配的块
- 例如,C 标准库提供一种叫做
malloc
程序包的显式分配器- C 程序通过调用
malloc
函数来分配一个块,并通过调用free
函数来释放一个块
- C 程序通过调用
- C++ 中的
new
和delete
操作符与 C 中的malloc
和free
相当
- 例如,C 标准库提供一种叫做
- 要求应用显式地释放任何已分配的块
- 隐式分配器(implicit allocator)
- 要求分配器检测一个已分配块何时不再被程序所使用,然后释放这个块
- 隐式分配器也叫做垃圾收集器(garbage collector)
- 自动释放未使用的已分配的块的过程叫做垃圾收集(garbage collection)
- 例如,诸如 Lisp、ML 以及 Java 之类的高级语言就依赖垃圾收集来释放已分配的块
本节中假定字是 4 字节的对象,而双字是 8 字节的对象
# 9.9.1 malloc
和 free
函数
malloc
函数
#include <stdlib.h>
void *malloc(size_t size);
// 返回:若成功则为已分配块的指针,若出错则为 NULL。
2
3
4
5
malloc
函数返回一个指针,指向大小为至少size
字节的内存块- 这个块会为可能包含在这个块内的任何数据对象类型做对齐
- 实际中,对齐依赖于编译代码在 32 位模式(gcc -m32)还是 64 位模式(默认的)中运行
- 在 32 位模式中,
malloc
返回的块的地址总是 8 的倍数 - 在 64 位模式中,该地址总是 16 的倍数
malloc
出错时(例如,程序要求的内存块比可用的虚拟内存还要大),会返回NULL
,并设置errno
malloc
不初始化它返回的内存calloc
是一个基于malloc
的瘦包装函数,它将分配的内存初始化为零realloc
函数可以改变一个以前已分配块的大小
堆内存的分配和释放
- 动态内存分配器,例如
malloc
- 可以通过使用
mmap
和munmap
函数,显式地分配和释放堆内存 - 或者还可以使用
sbrk
函数
- 可以通过使用
sbrk
函数
#include <unistd.h>
void *sbrk(intptr_t incr);
// 返回:若成功则为旧的 brk 指针,若出错则为 -1。
2
3
4
5
sbrk
函数通过将内核的brk
指针(堆顶)增加incr
来扩展和收缩堆- 如果成功,它就返回
brk
的旧值 - 否则,它就返回
-1
,并将errno
设置为ENOMEM
- 如果成功,它就返回
- 如果
incr
为零,那么sbrk
就返回brk
的当前值 - 用一个为负的
incr
来调用sbrk
是合法的- 而且很巧妙,因为返回值(
brk
的旧值)指向距新堆顶向上abs(incr)
字节处
- 而且很巧妙,因为返回值(
程序通过调用 free
函数来释放已分配的堆块
#include <stdlib.h>
void free(void *ptr);
// 返回:无
2
3
4
5
ptr
参数必须指向一个从malloc
、calloc
或者realloc
获得的已分配块的起始位置- 如果不是,那么
free
的行为就是未定义的 - 更糟的是,既然它什么都不返回,
free
就不会告诉应用出现了错误
- 如果不是,那么
# 9.9.2 为什么使用动态内存分配
程序使用动态内存分配的最重要的原因是经常直到程序实际运行时,才知道某些数据结构的大小
# 9.9.3 分配器的要求和目标
显式分配器必须在一些相当严格的约束条件下工作
- 处理任意请求序列
- 一个应用可以有任意的分配请求和释放请求序列,只要满足约束条件
- 每个释放请求必须对应于一个当前已分配块,这个块是由一个以前的分配请求获得的
- 因此,分配器不可以假设分配和释放请求的顺序
- 一个应用可以有任意的分配请求和释放请求序列,只要满足约束条件
- 立即响应请求
- 分配器必须立即响应分配请求
- 因此,不允许分配器为了提高性能重新排列或者缓冲请求
- 只使用堆
- 为了使分配器是可扩展的,分配器使用的任何非标量数据结构都必须保存在堆里
- 不修改已分配的块
- 分配器只能操作或者改变空闲块
- 特别是,一旦块被分配了,就不允许修改或者移动它了
- 因此,诸如压缩已分配块这样的技术是不允许使用的
- 分配器只能操作或者改变空闲块
在上述限制条件下,分配器的编写者试图实现吞吐率最大化和内存使用率最大化,而这两个性能目标通常是相互冲突的
- 目标 1:最大化呑吐率
- 吞吐率定义为每个单位时间里完成的请求数
- 开发一个具有合理性能的分配器并不困难
- 所谓合理性能是指一个分配请求的最糟运行时间与空闲块的数量成线性关系
- 而一个释放请求的运行时间是个常数
- 目标 2:最大化内存利用率
- 描述分配器使用堆的效率的一个有用的标准是峰值利用率(peak utilization),其计算公式如下
表示第 个请求完成后聚集有效载荷(aggregate payload), 为当前已分配的块的有效载荷之和 - 而
表示堆的当前的(在本节中假设为单调非递减的)大小
- 分配器的目标是在
个分配和释放请求序列中使峰值利用率 最大化
- 描述分配器使用堆的效率的一个有用的标准是峰值利用率(peak utilization),其计算公式如下
在最大化吞吐率和最大化利用率之间是互相牵制的
- 特别是,以堆利用率为代价,很容易编写出吞吐率最大化的分配器
- 分配器设计中一个有趣的挑战就是在两个目标之间找到一个适当的平衡
# 9.9.4 碎片
碎片的定义
- 当虽然有未使用的内存但不能用来满足分配请求时,就产生碎片现象
- 碎片是造成堆利用率很低的主要原因
碎片的分类
- 有两种形式的碎片:内部碎片(internal fragmentation)和外部碎片(external fragmentation)
- 内部碎片是在一个已分配块比有效载荷大时发生的
- 很多原因都可能造成这个问题。例如
- 一个分配器的实现可能对已分配块强加一个最小的大小值,而这个大小要比某个请求的有效载荷大
- 或者,分配器可能增加块大小以满足对齐约束条件
- 内部碎片的量化是简单明了的
- 它就是已分配块大小和它们的有效载荷大小之差的和
- 因此,在任意时刻,内部碎片的数量只取决于以前请求的模式和分配器的实现方式
- 很多原因都可能造成这个问题。例如
- 外部碎片是当空闲内存合计起来足够满足一个分配请求,但是没有一个单独的空闲块足够大可以来处理这个请求时发生的
- 外部碎片比内部碎片的量化要困难得多
- 因为它不仅取决于以前请求的模式和分配器的实现方式
- 还取决于将来请求的模式
- 外部碎片比内部碎片的量化要困难得多
因为外部碎片难以量化且不可能预测,所以分配器通常釆用启发式策略来试图维持少量的大空闲块,而不是维持大量的小空闲块
# 9.9.5 实现问题
一个实际的分配器要在吞吐率和利用率之间把握好平衡,就必须考虑以下几个问题
- 空闲块组织
- 如何记录空闲块?
- 放置
- 如何选择一个合适的空闲块来放置一个新分配的块?
- 分割
- 在将一个新分配的块放置到某个空闲块之后,如何处理这个空闲块中的剩余部分?
- 合并
- 如何处理一个刚刚被释放的块?
# 9.9.6 隐式空闲链表
任何实际的分配器都需要一些数据结构,允许它来区别块边界,以及区别已分配块和空闲块。大多数分配器将这些信息嵌入块本身
- 在这种情况中,一个块是由一个字的头部、有效载荷,以及可能的一些额外的填充组成的
- 头部编码了这个块的大小(包括头部和所有的填充),以及这个块是已分配的还是空闲的
- 如果我们强加一个双字的对齐约束条件,那么块大小就总是 8 的倍数,且块大小的最低 3 位总是零
- 因此,我们只需要内存大小的 29 个高位,释放剩余的 3 位来编码其他信息
- 在这种情况中,可以用其中的最低位(已分配位)来指明这个块是已分配的还是空闲的
- 头部后面就是应用调用
malloc
时请求的有效载荷 - 有效载荷后面是一片不使用的填充块,其大小可以是任意的
- 需要填充有很多原因。比如,填充可能是分配器策略的一部分,用来对付外部碎片。
- 或者也需要用它来满足对齐要求
隐式空闲链表
- 可以将堆组织为一个连续的已分配块和空闲块的序列
- 这种结构即为隐式空闲链表
- 是因为空闲块是通过头部中的大小字段隐含地连接着的
- 分配器可以通过遍历堆中所有的块,从而间接地遍历整个空闲块的集合
- 这种情况下需要某种特殊标记的结束块
- 在本例中,就是一个设置了已分配位而大小为零的终止头部(terminating header)
# 9.9.7 放置已分配的块
放置策略
- 当一个应用请求一个
字节的块时,分配器搜索空闲链表,查找一个足够大可以放置所请求块的空闲块 - 分配器执行这种搜索的方式是由放置策略(placement policy)确定的
- 一些常见的策略是首次适配(first fit),下一次适配(next fit)和最佳适配(best fit)
- 首次适配从头开始搜索空闲链表,选择第一个合适的空闲块
- 优点是它趋向于将大的空闲块保留在链表的后面。缺点是它趋向于在靠近链表起始处留下小空闲块
- 下一次适配和首次适配很相似,只不过不是从链表的起始处开始每次搜索,而是从上一次查询结束的地方开始
- 其作为首次适配的一种代替品被提出,源于这样一个想法
- 如果上一次在某个空闲块里已经发现了一个匹配,那么很可能下一次也能在这个剩余块中发现匹配
- 下一次适配比首次适配运行起来明显要快一些,尤其是当链表的前面布满了许多小的碎片时
- 然而,一些研究表明,下一次适配的内存利用率要比首次适配低得多
- 其作为首次适配的一种代替品被提出,源于这样一个想法
- 最佳适配检查每个空闲块,选择适合所需请求大小的最小空闲块
- 研究表明最佳适配比首次适配和下一次适配的内存利用率都要高一些
- 然而,在简单空闲链表组织结构中,比如隐式空闲链表中
- 使用最佳适配的缺点是它要求对堆进行彻底的搜索
- 首次适配从头开始搜索空闲链表,选择第一个合适的空闲块
# 9.9.8 分割空闲块
一旦分配器找到一个匹配的空闲块,它就必须做另一个策略决定,那就是分配这个空闲块中多少空间
- 一个选择是用整个空闲块
- 虽然这种方式简单而快捷,但是主要的缺点就是它会造成内部碎片
- 如果放置策略趋向于产生好的匹配,那么额外的内部碎片也是可以接受的。
- 然而,如果匹配不太好,那么分配器通常会选择将这个空闲块分割为两部分
- 第一部分变成分配块
- 而剩下的变成一个新的空闲块
# 9.9.9 获取额外的堆内存
分配器不能为请求块找到合适的空闲块时的处理措施
- 一个选择是通过合并那些在内存中物理上相邻的空闲块来创建一些更大的空闲块(在下一节中描述)
- 然而,如果合并空闲块还是不能生成一个足够大的块,或者如果空闲块已经最大程度地合并了
- 那么分配器就会通过调用
sbrk
函数,向内核请求额外的堆内存 - 分配器将额外的内存转化成一个大的空闲块,将这个块插入到空闲链表中
- 然后将被请求的块放置在这个新的空闲块中。
- 那么分配器就会通过调用
# 9.9.10 合并空闲块
假碎片现象
- 当分配器释放一个已分配块时,可能有其他空闲块与这个新释放的空闲块相邻
- 这些邻接的空闲块可能引起一种现象,叫做假碎片(fault fragmentation)
- 就是有许多可用的空闲块被切割成为小的、无法使用的空闲块。
利用合并来解决假碎片问题
- 为了解决假碎片问题,任何实际的分配器都必须合并相邻的空闲块,这个过程称为合并(coalescing)
- 这就出现了一个重要的策略决定,那就是何时执行合并
- 分配器可以选择立即合并(immediate coalescing)
- 也就是在每次一个块被释放时,就合并所有的相邻块
- 或者它也可以选择推迟合并(deferred coalescing)
- 也就是等到某个稍晚的时候再合并空闲块
- 例如,分配器可以推迟合并,直到某个分配请求失败,然后扫描整个堆,合并所有的空闲块
- 分配器可以选择立即合并(immediate coalescing)
立即合并很简单明了,可以在常数时间内执行完成,但是对于某些请求模式,这种方式会产生一种形式的抖动,块会反复地合并,然后马上分割
- 比如反复地分配和释放一个 3 个字的块将产生大量不必要的分割和合并
- 在对分配器的讨论中,我们会假设使用立即合并
- 但是在实际应用中,快速的分配器通常会选择某种形式的推迟合并
# 9.9.11 带边界标记的合并
边界标记
- 边界标记(boundary tag),允许在常数时间内进行对前面块的合并
- 使用边界标记的堆块的格式
- 分配器释放当前块时,可能存在的情况
边界标记的概念是简单优雅的,它对许多不同类型的分配器和空闲链表组织都是通用的
边界标记的缺陷及改进方法
- 边界标记要求每个块都保持一个头部和一个脚部,在应用程序操作许多个小块时,会产生显著的内存开销
- 有一种非常聪明的边界标记的优化方法,能够使得在已分配块中不再需要脚部
- 当我们试图在内存中合并当前块以及前面的块和后面的块时
- 只有在前面的块是空闲时,才会需要用到它的脚部
- 如果我们把前面块的已分配/空闲位存放在当前块中多出来的低位中
- 那么已分配的块就不需要脚部了
- 这样我们就可以将这个多出来的空间用作有效载荷了
- 当我们试图在内存中合并当前块以及前面的块和后面的块时
注意,空闲块仍然需要脚部
# 9.9.12 综合: 实现一个简单的分配器
构造一个分配器是一件富有挑战性的任务
- 设计空间很大
- 有多种块格式、空闲链表格式,以及放置、分割和合并策略可供选择
- 需要依赖于容易出错的指针强制类型转换和指针运算
# 通用分配器的设计
使用 memlib.c
包所提供的一个内存系统模型
- 模型的目的在于允许我们在不干涉已存在的系统层 malloc 包的情况下,运行分配器。
memlib.c
/* Private global variables */ static char *mem_heap; /* Points to first byte of heap */ static char *mem_brk; /* Points to last byte of heap plus 1 */ static char *mem_max_addr; /* Max legal heap addr plus 1*/ /* * mem_init - Initialize the memory system model */ void mem_init(void) { mem_heap = (char *)Malloc(MAX_HEAP); mem_brk = (char *)mem_heap; mem_max_addr = (char *)(mem_heap + MAX_HEAP); } /* * mem_sbrk - Simple model of the sbrk function. Extends the heap * by incr bytes and returns the start address of the new area. In * this model, the heap cannot be shrunk. */ void *mem_sbrk(int incr) { char *old_brk = mem_brk; if ( (incr < 0) || ((mem_brk + incr) > mem_max_addr)) { errno = ENOMEM; fprintf(stderr, "ERROR: mem_sbrk failed. Ran out of memory...\n"); return (void *) - 1; } mem_brk += incr; return (void *)old_brk; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
分配器包含在一个源文件中(mm.c
)
用户可以编译和链接这个源文件到他们的应用之中
分配器输出三个函数到应用程序
extern int mm_init(void); extern void *mm_malloc (size_t size); extern void mm_free (void *ptr);
1
2
3
隐式空闲链表的恒定形式
-
- 序言块(prologue block)和结尾块(epilogue block)在初始化时创建的,并且永不释放
- 序言块和结尾块是一种消除合并时边界条件的技巧
# 操作空闲链表的基本常数和宏
定义一小组宏来访问和遍历空闲链表是很有帮助的
mm.c
/* Basic constants and macros */ #define WSIZE 4 /* Word and header/footer size (bytes) */ #define DSIZE 8 /* Double word size (bytes) */ #define CHUNKSIZE (1<<12) /* Extend heap by this amount (bytes) */ #define MAX(x, y) ((x) > (y)? (x) : (y)) /* Pack a size and allocated bit into a word */ #define PACK(size, alloc) ((size) | (alloc)) /* Read and write a word at address p */ #define GET(p) (*(unsigned int *)(p)) #define PUT(p, val) (*(unsigned int *)(p) = (val)) /* Read the size and allocated fields from address p */ #define GET_SIZE(p) (GET(p) & ~0x7) #define GET_ALLOC(p) (GET(p) & 0x1) /* Given block ptr bp, compute address of its header and footer */ #define HDRP(bp) ((char *)(bp) - WSIZE) #define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE) /* Given block ptr bp, compute address of next and previous blocks */ #define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp) - WSIZE))) #define PREV_BLKP(bp) ((char *)(bp) - GET_SIZE(((char *)(bp) - DSIZE)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 创建初始空闲链表
mm.c
中的 mm_init
int mm_init(void)
{
/* Create the initial empty heap */
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *) - 1)
return -1;
PUT(heap_listp, 0); /* Alignment padding */
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* Prologue header */
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* Prologue footer */
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); /* Epilogue header */
heap_listp += (2 * WSIZE);
/* Extend the empty heap with a free block of CHUNKSIZE bytes */
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
return -1;
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
mm.c
中的 extend_heap
static void *extend_heap(size_t words)
{
char *bp;
size_t size;
/* Allocate an even number of words to maintain alignment */
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
/* Initialize free block header/footer and the epilogue header */
PUT(HDRP(bp), PACK(size, 0)); /* Free block header */
PUT(FTRP(bp), PACK(size, 0)); /* Free block footer */
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header */
/* Coalesce if the previous block was free */
return coalesce(bp);
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 释放和合并块
mm.c
中的 mm_free
和 coalesce
void mm_free(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc) { /* Case 1 */
return bp;
}
else if (prev_alloc && !next_alloc) { /* Case 2 */
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
else if (!prev_alloc && next_alloc) { /* Case 3 */
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
else { /* Case 4 */
size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
return bp;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# 分配块
mm.c
中的 mm_malloc
void *mm_malloc(size_t size)
{
size_t asize; /* Adjusted block size */
size_t extendsize; /* Amount to extend heap if no fit */
char *bp;
/* Ignore spurious requests */
if (size == 0)
return NULL;
/* Adjust block size to include overhead and alignment reqs. */
if (size <= DSIZE)
asize = 2 * DSIZE;
else
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL) {
place(bp, asize);
return bp;
}
/* No fit found. Get more memory and place the block */
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
return NULL;
place(bp, asize);
return bp;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 9.9.13 显式空闲链表
因为块分配与堆块的总数呈线性关系,所以对于通用的分配器,隐式空闲链表是不适合的
双向空闲链表
- 可以将空闲块组织为某种形式的显式数据结构
- 因为根据定义,程序不需要一个空闲块的主体,所以实现这个数据结构的指针可以存放在这些空闲块的主体里面
- 例如,堆可以组织成一个双向空闲链表,在每个空闲块中,都包含一个
pred
(前驱)和succ
(后继)指针
- 例如,堆可以组织成一个双向空闲链表,在每个空闲块中,都包含一个
- 使用双向链表而不是隐式空闲链表,使首次适配的分配时间从块总数的线性时间减少到了空闲块数量的线性时间
显式链表的缺点
- 要求空闲块必须足够大,以包含所有需要的指针,以及头部和可能的脚部。
- 这就导致了更大的最小块大小,也潜在地提高了内部碎片的程度
# 9.9.14 分离的空闲链表
分离存储(segregated storage)
- 一个使用单向空闲块链表的分配器需要与空闲块数量呈线性关系的时间来分配块
- 一种流行的减少分配时间的方法,通常称为分离存储(segregated storage)
- 分离储存会维护多个空闲链表,其中每个链表中的块有大致相等的大小
- 一般的思路是将所有可能的块大小分成一些等价类,也叫做大小类(size class)
- 可以根据 2 的幂来划分块大小
- 也可以将小的块分派到它们自己的大小类里,而将大块按照 2 的幂分类
- 可以根据 2 的幂来划分块大小
# 简单分离存储(simple segregated storage)
简单分离储存的基本原理
- 使用简单分离存储,每个大小类的空闲链表包含大小相等的块,每个块的大小就是这个大小类中最大元素的大小
简单分离储存的基本工作流程
- 为了分配一个给定大小的块,我们检査相应的空闲链表
- 如果链表非空,我们简单地分配其中第一块的全部
- 空闲块是不会分割以满足分配请求的
- 如果链表为空,分配器就向操作系统请求一个固定大小的额外内存片(通常是页大小的整数倍)
- 将这个片分成大小相等的块,并将这些块链接起来形成新的空闲链表
- 要释放一个块,分配器只要简单地将这个块插入到相应的空闲链表的前部
- 不会进行合并操作
简单分离适配的优点
- 分配和释放块都是很快的常数时间操作
- 已分配的块不需要头部
- 由于每个片只有大小相同的块,那么一个已分配块的大小就可以从它的地址中推断出来
- 可以考虑在每页的开头储存块大小的相关信息
- 因为没有合并,所以已分配块的头部就不需要一个已分配/空闲标记
- 由于每个片只有大小相同的块,那么一个已分配块的大小就可以从它的地址中推断出来
- 因为没有合并,已分配的块也不需要脚部
- 因为分配和释放操作都是在空闲链表的起始处操作,所以链表只需要是单向的,而不用是双向的
因此,在任何块中都需要的唯一字段是每个空闲块中的一个字的
succ
指针- 因此最小块大小就是一个字
简单分离适配的缺点
- 显著的缺点是,简单分离存储很容易造成内部和外部碎片
- 因为空闲块是不会被分割的,所以可能会造成内部碎片
- 因为不会合并空闲块,所以某些引用模式会引起极多的外部碎片
# 分离适配(segregated fit)
分离适配的基本原理
- 分配器维护着一个空闲链表的数组
- 每个空闲链表是和一个大小类相关联的,并且被组织成某种类型的显式或隐式链表
- 每个链表包含潜在的大小不同的块,这些块的大小是大小类的成员
分离适配器的简单版本
- 为了分配一个块,必须确定请求的大小类,并且对适当的空闲链表做首次适配,査找一个合适的块
- 如果找到了一个,那么就(可选地)分割它,并将剩余的部分插入到适当的空闲链表中
- 如果找不到合适的块,那么就搜索下一个更大的大小类的空闲链表
- 如此重复,直到找到一个合适的块
- 如果空闲链表中没有合适的块,那么就向操作系统请求额外的堆内存
- 从这个新的堆内存中分配出一个块,将剩余部分放置在适当的大小类中
- 要释放一个块,我们执行合并,并将结果放置到相应的空闲链表中
分离适配方法的特点
- 分离适配方法是一种常见的选择,C 标准库中提供的 GNU malloc 包就是釆用的这种方法
- 分离适配方法
- 快速,对内存的使用也很有效率
- 减少了搜索时间,因为搜索被限制在堆的某个部分,而不是整个堆
- 内存利用率得到了改善
- 因为对分离空闲链表的简单的首次适配搜索,其内存利用率近似于对整个堆的最佳适配搜索的内存利用率
# 伙伴系统(buddy system)
伙伴系统的基本特点
- 伙伴系统是分离适配的一种特例,其中每个大小类都是 2 的幂
- 假设一个堆的大小为个
字 - 我们为每个
的块大小维护一个分离空闲链表,其中 - 请求块大小向上舍入到最接近的 2 的幂
- 我们为每个
- 最开始时,只有一个大小为
个字的空闲块
伙伴系统的基本原理
- 为了分配一个大小
为的块,我们找到第一个可用的、大小为 的块,其中 - 如果
,那么我们就完成了 - 否则,我们递归地二分割这个块,每个剩下的半块(也叫做伙伴)被放置在相应的空闲链表中
- 直到分隔产生的半块的大小为
- 直到分隔产生的半块的大小为
- 要释放一个大小为
的块,我们继续合并空闲的伙伴 - 当遇到一个已分配的伙伴时,我们就停止合并
给定地址和块的大小,可以很容易计算出它的伙伴的地址
伙伴系统的优缺点
- 伙伴系统分配器的主要优点是它的快速搜索和快速合并
- 主要缺点是要求块大小为 2 的幂可能导致显著的内部碎片
- 因此,伙伴系统分配器不适合通用目的的工作负载
- 然而,对于某些特定应用的工作负载,其中块大小预先知道是 2 的幂,伙伴系统分配器就很有吸引力了