深入理解计算机系统10，虚拟存储器 垃圾收集器

虚拟存储器是对主存的一个抽象
支持虚拟存储器的处理器通过使用一种叫虚拟寻址的间接形式来使用主存
处理器产生一个虚拟地址，在被发送到主存之前，这个地址被翻译成一个物理地址
从虚拟地址空间到物理地址空间的地址翻译要求硬件和软件紧密合作
专门的硬件通过使用页表来翻译虚拟地址，而页表的内容是由操作系统提供的

虚拟存储器的三个重要功能：
1，它在主存中自动缓存最近使用的存放磁盘上的虚拟地址空间的内容
虚拟存储器缓存中的块叫做页。对磁盘上页的引用会触发缺页，缺页将控制转移到操作系统中的一个缺页处理程序
缺页处理程序将页面从磁盘拷贝到主存缓存，如果必要，将写回被驱逐的页
2，虚拟存储器简化了存储器管理，进而又简化了链接、在进程间共享数据、进程的存储器分配、以及程序加载
3，虚拟存储器通过在每条页表条目中加入保护位，从而简化了存储器保护

地址翻译的过程必须和系统中任意硬件缓存的操作集成在一起
大多数页表条目位于L1高速缓存中，但是一个称为TLB的页表条目在芯片上的高速缓存，通常会消除访问在L1上的页表条目的开销

现代系统通过将虚拟存储器组块和磁盘上的文件组块关联起来，来初始化虚拟存储器组块，这个过程称为存储器映射
存储器映射为共享数据、创建新的进程以及加载程序，提供了一种高效的机制
应用可以使用mmap函数来手工地创建和删除虚拟地址空间的区域
然而大多数程序依赖于动态存储器分配器，如malloc，它管理虚拟地址空间区域内的一个称为堆的区域
动态存储器分配器是一个有系统级感觉的应用级程序，它直接操作存储器，而无需类型系统的很多帮助
分配器有两种类型：显示分配器要求应用显式地释放它们的存储器块：隐式分配器（垃圾收集器）自动释放任何无用的和不可达的块

对于C程序员来说，管理和使用虚拟存储器是一件困难和容易出错的任务
常见的错误示例包括：间接引用坏指针，读取未初始化的存储器，允许栈缓冲区溢出，假设指针和它们指向的对象大小相同，
引用指针而不是它所指向的对象，误解指针运算，引用不存在的变量，以及引起存储器泄漏

垃圾收集可以追溯到John McCarthy在20世纪60年代早期在MIT开发的Lisp系统
McCarthy独创的Mark&Sweep(标记&清除)算法可以建立在已存在的malloc包的基础之上，为C和C++程序提供垃圾收集

垃圾收集器将存储器视为一张有向可达图，该图的节点被分成一组根节点和一组堆节点
每个堆节点对应于堆中的一个已分配块，有向边p->q意味着块p中的某个位置指向块q中的某个位置
根节点对应于不在堆中的位置，它们中包含着指向堆中的指针
这些位置可以是寄存器、栈里的变量或者是虚拟存储器中读写数据区域内的全局变量
当存在一条从任意根节点出发并到达p的有向路径时，我们说一个节点p是可达的
在任何时刻，和垃圾对应的不可达节点是不能被应用再次使用的
垃圾收集器的角色是维护可达图的某种表示，并通过释放不可达节点并将它们返回给空闲链表，来定期地回收它们

ML和Java这样的语言的垃圾收集器对应用如何创建和使用指针有很严格的控制，能够维护可达图的一种精确的表示，因此也就能够回收所有垃圾
而诸如C和C++这样的语言的收集器通常不能维持可达图的精确表示，这样的收集器也叫保守的垃圾收集器

收集器可以按需提供它们的服务，或者它们可以作为一个和应用并行的独立线程，不断地更新可达图和回收垃圾

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

C程序的Mark&Sweep收集器必须是保守的，其根本原因是C语言不会用类型信息来标记存储器位置
因此，像int或者float这样的标量可以伪装成指针
例如，假设某个可达的已分配块在它的有效载荷中包含一个int，其值碰巧对应于某个其他已分配块b的有效载荷中的一个地址
对收集器而言，是没有办法推断出这个数据实际是int而不是指针
因此，分配器必须保守地将块b标记为可达，尽管事实上它可能是不可达的