垃圾回收

垃圾：广义上不需要再被引用的数据；狭义上不能被引用（不可达）的数据。

垃圾回收：自动回收不可达数据的机制，接触了程序员的负担。

垃圾回收器的设计目标

基本要求：语言必须是类型安全的，保证回收器能够知道数据元素是否为一个指向某内存块的指针。（静态类型ML、动态类型Java），类型不安全的语言（C/C++）。

性能目标：总体运行时间不显著增加应用程序的总运行时间；空间使用最大限度地利用可用内存；停顿时间当垃圾回收机制启动时，可能引起应用程序的停顿，这个停顿应该比较短（很少在实时应用中使用）；程序局部性改善空间局部性和时间局部性。

可达性

可达性就是指一个存储块可以被程序访问到。根集：不需要指针解引用就可以直接访问的数据。

根集的成员都是可达的；对于任意一个对象，如果指向它的一个指针被保存在可达对象的某字段或数组元素中，那么这个对象也是可达的。

性质：一旦一个对象变得不可达，它就不会再变成可达的。

改变可达对象集合的操作

• 对象分配：返回一个指向新存储块的引用

• 参数传递和返回值

• 引用赋值：u=v ，v的引用被复制到u中，u中原有引用丢失；（可能）使u原来指向的对象变得不可达，并递归使更多对象变得不可达。

• 过程返回：活动记录出栈，局部变量消失；根集变小，使一些对象变得不可达。

垃圾回收方法

• 关注不可达：跟踪相关操作，捕获对象变得不可达的时刻，回收对象占用的空间

• 关注可达：在需要时，标记出所有可达对象，回收其他对象

基于引用计数的垃圾回收器

每个对象有一个用于存放引用计数的字段，并按如下方式维护：

• 对象分配：引用计数设为1

• 参数传递：引用计数+1

• 引用赋值：u=v ，u指向的对象引用减1，v指向的对象引用加1

• 过程返回：局部变量指向对象的引用计数减1

如果一个对象的引用计数为0，在删除对象之前，此对象中各个指针所指对象的引用计数减1

特点：开销较大，但不会引起停顿

循环垃圾

三个对象相互引用，没有来自外部的指针，又不是根集成员，都是垃圾，但是引用计数都大于0。

基于跟踪的垃圾回收

标记-清扫式垃圾回收

一种直接的、全面停顿的算法，分成两个阶段：

• 标记：从根集开始，跟踪并标记出所有的可达对象

• 清扫：遍历整个堆区，释放不可达对象

如果把数据对象看作节点，引用看作有向边，那么标记的过程实际上是从根集开始的图遍历过程。

标记-复制式垃圾回收

目标：只处理可达对象（减少回收时间），将可达对象安排到一起（减少内存碎片）。

堆空间被分为两个半区，应用程序在某个半区内分配存储，当充满这个半区时，开始垃圾回收。回收时，复制可达对象到另一个半区（需修改引用地址）。回收完成后，两个半区角色对调。

缺点是一般预留区域的内存无法使用。

标记-整理式垃圾回收

对可达对象进行重定位可以消除存储碎片：

• 与标记-复制法将对象移动到预留另一半区不同，标记-整理法把可达对象移动到堆区的一端，另一端则是空闲空间

• 空闲空间合并成单一块，提高分配内存时的效率

垃圾回收算法比较

• 标记- 清扫式垃圾回收：回收效率不高，容易造成碎片

• 标记-复制式垃圾回收：只需遍历可达对象，管理区域大部分对象为垃圾对象时效率高（只需移动少量可达对象），反之则效率低

• 标记-整理式垃圾回收：将可达对象移动到堆区的一端，需遍历整个区域；管理区域内大部分对象为可达对象时效率高（经过之前的整理，大部分对象已经到位），反之则效率低。

分代式垃圾回收

对象生存周期特征：大多数对象刚创建不久后就不再使用（短命）；存在时间越长的对象，通常被回收的几率越小（命硬）。

根据生存周期，对对象分代管理。新创建的对象均放入年轻代区域（从幼年期开始），年轻代空间不足时，对该区域进行回收（标记-复制，因为垃圾比较多）；熬过回收的对象移入下一区域（进化）；老年代空间不足时，对该区域进行回收（标记-整理，因为垃圾比较少）。