这次回顾深入理解计算机系统第9章动态内存分配部分。

电子书地址：

http://eol.bnuz.edu.cn/meol/common/script/preview/download_preview.jsp?fileid=2169600&resid=242120&lid=28605

备注：图片和总结内容均来自于电子书。

第9章：虚拟内存

重要概念

一个区域(area)就是已经存在着的（已分配的）虚拟内存的连续片(chunk)，这些页是以某种方式相关联的；
任务结构(task_struct)；
内存映射(memory mapping)；
普通文件，匿名文件（请求二进制零的页(demand-zero page)），交换文件；
共享对象，私有对象，共享区域，私有区域；
- 私有的写时复制；
vm_area_structs（区域结构）；
显式分配器(explicit allocator)，隐式分配器(implicit allocator)；
聚集有效载荷(aggregate payload)；
动态内存分配器考虑的问题：空闲块组织，放置，分割，合并；
内部碎片，外部碎片，假碎片；
放置策略：
- 首次适配(first fit)；
- 下一次适配(next fit)；
- 最佳适配(best fit)；

Linux 虚拟内存系统

Linux为每个进程维护了一个单独的虚拟地址空间，如下图所示：

Linux虚拟内存区域

Linux将虚拟内存组织成一些区域（也叫做段）的集合。
一个区域(area)就是已经存在着的（已分配的）虚拟内存的连续片(chunk)，这些页是以某种方式相关联的。
- 例如，代码段、数据段、堆、共享库段，以及用户栈都是不同的区域。
每个存在的虚拟页面都保存在某个区域中，而不属于某个区域的虚拟页是不存在的，并且不能被进程引用。

内核为系统中每个进程维护了一个单独的任务结构(task_struct)，记录一个进程中虚拟内存区域的内核数据结构如下：

说明：

task_struct：每个进程对应的任务结构；
mm_struct：描述虚拟存当前状态；
- pgd：指向第一级页表（页全局目录）的基址，运行进程时位于CR3控制寄存器中；
- mmap：指向vm_area_structs（区域结构）的链表；
vm_area_structs：描述当前虚拟地址空间的一个区域；
- vm_start：指向这个区域的起始处；
- vm_end：指向这个区域的结束处；
- vmprot：描述这个区域内包含的所有页的读写许可权限；
- vm_flags：描述这个区域内的页面是与其他进程共享的，还是这个进程私有的（还描述了其他一些信息）；
- vm_next：指向链表中下一个区域结构；

Linux缺页异常处理

如果翻译虚拟地址$A$时触发了缺页异常，那么控制转移到内核的缺页处理程序，按照如下步骤进行处理：

判断虚拟地址$A$是否合法？
- 判断地址$A$是否在某个区域结构定义的区域内，即把$A$和每个区域结构中vm_start和vm_end作比较，如果不合法则对应图中“1”；
判断内存访问是否合法？
- 即判断是否有读，写或执行这个区域的权限，如果不合法则对应图中“2”；
其余情形对应“3”；
- 正常缺页；

内存映射

简介

内存映射(memory mapping)：
- 将虚拟内存与一个磁盘上的对象关联起来，以初始化虚拟内存区域的内容；
虚拟内存区域可以映射到如下两种类型的对象：
- Linux文件系统中的普通文件，即映射到一个普通磁盘文件的连续部分；
- 匿名文件，由内核创建，包含全是二进制零，也叫请求二进制零的页(demand-zero page)；
  - CPU第一次引用该区域的虚拟页面时，内核在物理内存中找到一个牺牲页面，用二进制零覆盖牺牲页面并更新页表；
一旦一个虚拟页面被初始化了，就在一个由内核维护的专门交换文件(swap file)之间换来换去；
- 交换文件也叫作交换空间(swap space)或者交换区域(swap area)；
- 在任何时刻，交换空间都限制这当前运行着的进程能够分配的虚拟页面的总数；

再看共享对象

一个对象可以被映射到虚拟内存的一个区域，要么作为共享对象，要么作为私有对象；
- 映射到共享对象的虚拟内存区域叫做共享区域；
- 映射到私有对象的虚拟内存区域叫做私有区域；
- 对于一个映射到共享对象的区域的改变，对于也把该共享对象映射到虚拟内存的其他进程而言是可见的，这些变化也会反映在磁盘上的原始对象中；
- 对于一个映射到私有对象的区域做的改变，对于其他进程来说是不可见的，并且进程对这个区域所做的任何写操作都不会反映在磁盘上的对象中；

共享对象

私有对象

私有对象在物理内存中只保存私有对象的一份副本。

示例：

在下图中，两个进程将一个私有对象映射到它们虚拟内存的不同区域，但是共享这个对象的同一个物理副本；
相应私有区域的页表条目被标记为只读，区域结构被标记为私有的写时复制；
如果一个进程试图写它自己的私有区域内的某个页面，那么会触发一个保护故障：
- 在物理内存中创建这个页面的新副本，更新页表条目指向这个新副本，恢复这个页面的写权限，然后写操作就可以正常执行了；

再看fork函数

当fork函数被当前进程调用时，内核为新进程创建各种数据结构，并分配给它一个唯一的PID。为了给这个新进程创建虚拟内存，它创建了当前进程的mm_struct、区域结构和页表的原样副本。它将两个进程中的每个页面都标记为只读，并将两个进程中的每个区域结构都标记为私有的写时复制。
当fork在新进程中返回时，新进程现在的虚拟内存刚好和调用fork时存在的虚拟内存相同。当这两个进程中的任一个后来进行写操作时，写时复制机制就会创建新页面，因此，也就为每个进程保持了私有地址空间的抽象概念。

再看execve函数

假设运行了如下execve调用：

execve("a.out", NULL, NULL);

加载并运行a.out需要以下几个步骤：

删除已存在的用户区域。
- 删除当前进程虚拟地址的用户部分中的已存在的区域结构。
映射私有区域。
- 为新程序的代码、数据、bss和栈区域创建新的区域结构。所有这些新的区域都是私有的、写时复制的。
- 代码和数据区域被映射为a.out文件中的.text和.data区。
- bss区域是请求二进制零的，映射到匿名文件，其大小包含在a.out中。
- 栈和堆区域也是请求二进制零的，初始长度为零。
映射共享区域。
- 如果a.out程序与共享对象（或目标）链接，比如标准C库libc.so，那么这些对象都是动态链接到这个程序的，然后再映射到用户虚拟地址空间中的共享区域内。
设置程序计数器(PC)。
- 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);

返回:若成功时则为指向映射区域的指针，若出错则为MAP_FAILED(-1)。

图示：

具体参数见：

9.8.4

munmap函数删除虚拟内存区域：

#include <unistd.h>
#include <sys/mman.h>

int munmap(void *start, size_t length);

返回: 若成功则为0，若出错则为-1。

动态内存分配

简介

实际中一般不使用mmap，munmap创建和删除虚拟内存的区域，而是使用动态内存分配器(dynamic memory allocator)申请额外的虚拟内存。
动态内存分配器维护着一个进程的虚拟内存区域，称为堆(heap) 。假设堆是一个请求二进制零的区域，它紧接在末初始化的数据区域后开始，并向上生长（向更高的地址）。对于每个进程，内核维护着一个变量brk指向堆的顶部。
分配器将堆视为一组不同大小的块集合来维护，每个块就是一个连续的虚拟内存片，要么是已分配，要么是空闲；
- 空闲块保持空闲，直到它显式地被应用所分配。
- 一个分配的块保持已分配状态，直到它被释放，这种释放要么是应用程序显式执行的，要么是内存分配器自身隐式执行的。
两种分配器：
- 显式分配器(explicit allocator)，要求应用显式地释放任何已分配的块。
  - 例子：C语言中的malloc和free。
- 隐式分配器(implicit allocator)，要求分配器检测一个已分配块何时不再被程序所使用，那么就释放这个块。
  - 隐式分配器也叫做垃圾收集器(garbage collector)，自动释放末使用的已分配的块的过程叫做垃圾收集（garbage collection)。
  - 例子：Lisp, ML, Java依赖垃圾收集来释放已分配的块。

堆示意图：

函数接口

malloc返回一个指针，指向大小至少为size字节的内存块，该块可能做对齐，例如32位模式中返回的块地址总是8的倍数，在64位模式中返回的块地址总是16的倍数：

#include <stdlib.h>
void *malloc(size_t size);

返回:若成功则为已分配块的指针, 若出错则为NULL。

说明：这里假设一个字为4字节，双字为8字节。

sbrk函数通过将内核的brk指针增加incr来扩展和收缩堆：

#include <unistd.h>
void *sbrk(intptr-t incr);

返回:若成功则为旧的brk指针, 若出错则为-1并设将errno设置为ENOMEM。

free释放已分配的堆块，ptr参数必须指向一个从malloc, calloc或者realloc获得的已分配块的起始位置，否则行为是未定义的：

#include <stdlib.h>
void free(void *ptr);

返回:无。

示例：

分配器的要求和目标

显式分配器需要在如下约束下工作：

处理任意其请求序列；
立即响应请求；
- 即不允许分配器为了提高性能重新排列或者缓冲请求；
只使用堆；
对齐块（对齐要求）；
不修改已分配的块；

优化两个性能指标：

目标1：最大化吞吐率。
- 即单位时间里完成的请求数。
目标2：最大化内存利用率。
- 常见的指标为峰值利用率(peak utilization)，计算方式如下：
  - 请求一个$p$字节的块，那么得到的已分配块的有效载荷(payload)是$p$字节；
  - 给定$n$个分配和释放请求的某种顺序：
    $R_{0}, R_{1}, \cdots, R_{k}, \cdots, R_{n-1}$
  - 在请求$R_k$完成之后，聚集有效载荷(aggregate payload)$P_k$为当前已分配的有效载荷之和，$H_k$为堆的当前大小（单调非递减），那么前$k+1$个请求的峰值利用率$U_k$为：
    $U_{k}=\frac{\max _{i \le\ k} P_{i}}{H_{k}}$
- 这两个目标是相互牵制的，所以难点是找到平衡。

碎片

碎片现象：
- 有未使用的内存，但不能用来满足分配。
两种碎片：
- 内部碎片：
  - 发生在已分配块比有效载荷大，例如课本中使用的隐式空闲链表；
  - 只取决于以前请求的模式和分配器的实现方式；
  - 易于量化，为已分配块大小和有效载荷大小之差之和；
- 外部碎片：
  - 发生在当空闲内存合集起来足够满足一个分配请求，但是没有一个单独的空闲块足够大可以来处理这个请求；
  - 不仅取决于以前的请求模式和分配器的实现方式，还取决于将来的请求模式；
  - 难以量化，无法预测；

实现问题

动态内存分配器的实现需要考虑以下几个问题：

空闲块组织：如何记录空闲块?
放置：如何选择一个合适的空闲块来放置一个新分配的块?
分割：在将一个新分配的块放置到某个空闲块之后，如何处理这个空闲块中的剩余部分?
合并：如何处理一个刚刚被释放的块?

几种数据结构（空闲块组织）

任何实际的分配器都需要一些数据结构，用来区分边界，已分配块和空闲块，具体如下。

隐式空闲链表

隐式空闲链表包含：

头部
有效载荷
填充

说明：

假设双字对齐，那么块大小是8的倍数，块大小的最低三位是0，利用最后低位来指明块是已分配的还是空闲的。

示例：

优点：

简单；

缺点：

任何操作开销和已分配块和空闲块的大小成正比；

带边界标记的隐式空闲链表

在块的结尾添加脚步，方便进行块合并。

显式空闲链表

变化：

首次适配的分配时间从块总数的线性时间减少到空闲块数量的线性时间；
释放块的时间和策略有关：
- 后进先出(LIFO)：将新释放的块防止在链表的开始处，时间复杂度为常数；
- 按照地址顺序来维护：链表中每个地址都小于它的后继地址，时间复杂度是线性的，优点是比LIFO排序的首次适配有更高的内存利用率，接近最佳适配的利用率；

分离的空闲链表

简介

分离存储是为了减少分配时间，思路为维护多个空闲链表，每个链表中的块大小大致相等，一般的思路是将所有可能的块大小分成一些等价类，叫做大小类；
分配器维护着空闲链表数组，每个大小类一个空闲链表，按照大小的升序排列；
当分配器需要一个大小为$n$的块时，就搜索相应的空闲链表；如果不能找到合适的块，就搜索下一个链表；

简单分离存储(simple segregated storage)

介绍：

分配器维护着空闲链表数组，每个大小类一个空闲链表；
每个大小类包含大小相等的块，块大小是这个大小类中最大元素的大小；

分配：

检查相应的空闲链表，如果链表非空，则分配其中第一块的全部，不会分割以满足分配请求；
如果链表为空，分配器向操作系统请求一个固定大小的额外内存片，将这个片分成大小相等的块，并将这些块链接起来形成新的空闲链表；

释放：

简单地将这个快插入到响应的空闲链表前部；

优点：

分配和释放块都是很快的常数时间操作；

缺点：

很容易造成内部和外部碎片；

分离适配(segregated fit)

介绍：

分配器维护着空闲链表数组，每个大小类一个空闲链表；
每个空闲链表和一个大小类相关联，并且被组织成某种类型的显式或隐式链表；

分配：

确定请求的大小类，对适当的空闲链表做首次适配；
- 如果找到就（可选地）分割它，将剩余部分插入到适当的空闲链表中；
- 如果找不到，就搜索下一个更大的大小类的空闲链表，直到找到一个合适的块；
如果空闲链表中没有合适的块，就像操作系统额外请求堆内存，从这个新的堆内存中分配一个块，将剩余部分放置在适当的大小类中；

释放：

是否后执行合并，将结果放置到相应的空闲链表；

优点：

搜索被限制在堆的某个部分，提高了搜索效率；
对分离空闲链表的简单的首次适配搜索，其内存利用率近似于对整个堆的最佳适配搜索的内存利用率；

伙伴系统(buddy system)

介绍：

分离适配的一种特例，每个大小类都是2的幂；
假设堆大小为$2^m$，我们为每个块大小$2^k$维护一个分离空闲链表，其中$0\le k \le m$；
请求块大小向上舍入到最接近2的幂；
最开始时只有一个大小为$2^m$的字的空闲块；

分配：

为了分配大小为$2^k$的块，找到第一个可用的，大小为$2^j$的块，其中$k\le j\le m$；
- 如果$j=k$，则完成；
- 否则递归的二分这个快，直到$j=k$；将每个剩下的半块（伙伴）放置在相应的空闲链表中；

释放：

要释放一个大小为$2^k$的块，继续合并空闲的伙伴，当遇到一个已分配的伙伴时，就停止合并；

优点：

快速搜索和快速合并；

缺点：

可能导致显著的内部碎片；

伙伴地址计算方式：

给定地址和块的大小，很容易计算出伙伴的地址，例如一个块大小为32字节，地址为：

$x x x \cdots x 00000$

它的伙伴地址为：

$x x x \cdots x 10000$

计算方式：

$2^5=32$

放置已分配的块

当一个应用请求一个$k$字节的块时，分配器搜索空闲链表，查找一个足够大可以放置所请求的空闲块，搜索方式由放置策略(placement policy)确定，常见策略为：
- 首次适配(first fit)：从头开始搜索链表，选择第一个合适的空闲块；
- 下一次适配(next fit)：从上一次查询结束的地方开始搜索链表，选择第一个合适的空闲块；
- 最佳适配(best fit)：检查每个空闲块，选择适合所需请求大小的最小空闲块；

分割空闲块

分配器找到一个匹配的空闲块后需要决定分配空闲块中多少空间：
- 分配整个空闲块；
- 将空闲块分割为两部分，第一部分变成分配块，剩下的变成一个新的空闲块；

合并空闲块

当分配器释放一个已分配块时，可能有其他空闲块和这个新释放的空闲块相邻，这可能引起称为假碎片(fault fragmentation)的现象：
- 即有许多可用的空闲块被分割称为小的，无法使用的空闲块；
- 例子：
解决假碎片现象的方式为合并(coalescing)：
- 合并分为立即合并和推迟合并；
利用带边界标记的隐式空闲链表，可以高效的进行合并：
- 改进：
  - 当合并当前块和前后块时，只有前面的块是空闲时，才会需要用到脚步；
  - 可以将前面块已分配/空闲位存放在当前块多出来的低位（第二位）；
    - 注意低位一共有3位；
  - 此时空闲块需要脚部，已分配块不需要脚部；

垃圾收集

介绍

垃圾收集器(garbage collector) 是一种动态内存分配器，它自动释放程序不再需要的已分配块。这些块被称为垃圾(garbage)（因此术语就称之为垃圾收集器) 。
自动回收堆存储的过程叫做垃圾收集(garbage collection)。
在一个支持垃圾收集的系统中，应用显式配堆块，但是从不显示地释放它们。
- 在C程序的上下文中，应用调用malloc，但是从不调用free。反之，垃圾收集器定期识别垃圾块，并相应地调用free，将这些块放回到空闲链表中。

垃圾收集器的基本知识

垃圾收集器将内存视为一张有向可达图(reachability graph)，如下图所示。
该图的节点被分成一组根节点(root node)和一组堆节点(heap node)。
每个堆节点对应于堆中的一个已分配块。有向边$p \rightarrow q$意味着块$p$中的某个位置指向块$q$中的某个位置。
根节点对应于这样一种不在堆中的位置，它们中包含指向堆中的指针。这些位置可以是寄存器、栈里的变量, 或者是虚拟内存中读写数据区域内的全局变量。
当存在任意根节点出发并到达$p$的有向路径时，我们说节点$p$是可达的；不可达的节点集对应于垃圾；
垃圾收集器的角色是维护可达图的某种表示，通过释放不可达节点且将它们返回给空闲链表，来定期地回收它们；
保守的垃圾收集器：可达块都被正确地标记为可达了，一些不可达节点却可能被错误地标记为可达；
malloc包和垃圾收集器结合：

Mark&Sweep垃圾收集器

Mark &Sweep垃圾收集器由标记(mark)阶段和清除(sweep)阶段组成，标记阶段标记出根节点的所有可达的和已分配的后继，而后面的清除阶段释放每个末被标记的已分配块。块头部中空闲的低位中的一位通常用来表示这个块是否被标记了。

我们对Mark\&Sweep的描述将假设使用下列函数, 其中ptr定义typedef void *ptr:

ptr isPtr(ptr p)。
- 如果p指向一个已分配块中的某个字，那么就返回一个指向这个块的起始位置的指针b。否则返回NULL。
int blockMarked(ptr b) 。
- 如果块b是已标记的，那么就返回true。
int blockAllocated(ptr b) 。
- 如果块b是已分配的，那么就返回true.
void markBlock(ptr b) 。
- 标记块b。
int length(b) 。
- 返回块b的以字为单位的长度(不包括头部)。
void unmarkBlock(ptr b) 。
- 将块b的状态由已标记的改为末标记的。
ptr nextBlock(ptr b) 。
- 返回堆中块b的后继。

mark函数（深搜）：

void mark(ptr p){
    if ((b = isPtr(p)) == NULL)
    	return;
    if (blockMarked(b))
    	return;
    markBlock(b);
    len = length(b);
    for (i=0; i < len; i++)
    	mark(b[i]);
    return;
}

sweep函数：

void sweep(ptr b, ptr end){
	while (b < end){
		if (blockMarked(b))
			unmarkBlock(b);
		else if (blockAllocated(b))
			free(b);
		b = nextBlock(b);
    }
	return;
}

示例：

C程序的保守Mark&Sweep

C语言为isPtr函数的实现造成了一些有趣的挑战：

第一，C不会用任何类型信息来标记内存位置；
第二，即使知道p是一个指针，isPtr也没有没有明显的方式来判断p是否指向一个已分配块的有效载荷中的某个位置。
- 对于第二个问题，解决方法是将已分配块集合维护成一个二叉树，左子树的所有块都存放在较小的地址处，右子树的所有快都放在较大的地址处；
- 接着给每个已分配块增加两个附加字段left, right，每个字段指向某个已分配块的头部；
- 那么isPtr(ptr p)函数用树来指向对已分配块的二分查找即可；
- 图示：
- 该方法可能会将不可达的块标记为可达，所以是保守的，这不影响程序的正确性，但是可能导致不必要的外部碎片；

C语言的Mark&Sweep收集器必须是保守的，因为int, float可以伪装成指针。