zhouqijie

垃圾回收概述

不能被引用的数据通常称为垃圾(garbage)。很多高级程序设计语言提供了用以回收不可达数据的自动垃圾回收机制，从而解除了程序员进行手工存储管理的负担。



垃圾回收的目标

垃圾回收是重新收回那些存放了不能再被程序访问的对象的存储块。

我们把一个程序称为增变者(mutator)，它会修改堆区中的对象集合。

增变者从存储管理器处获取空间，创建对象，它还可以引入和消除已有对象的引用。

当增变者程序不能“到达”某些对象时，这些对象就变成了垃圾。

不是所有语言都适合进行自动垃圾回收。为了使垃圾回收器能够工作，它必须知道任何给定的数据元素（或者数据元素分量）是否是（或者能否用作）一个指向某块已分配空间的指针。

能在编译时刻确定数据的类型，称为静态类型安全。如果其类型不能在编译时刻确定，但是可以在运行时刻确定，称为动态类型安全(dynamically typed)。如果都不是，他就称为不安全(unsafe)的。

类型不安全的语言不适合使用垃圾回收机制。C和C++都是类型不安全的。存储地址可以进行任意操作，可以把任意整数转换为指针。从理论上说，一个程序可以在任何时候引用内存中任意位置。（但是C/C++可以用一些保守的垃圾回收技术）

CRE：智能指针？

垃圾回收的代价比较高昂，并且没有一种无可争议的最好的垃圾回收算法。

一些在设计垃圾回收器时必须考虑的性能度量标准：

  1. 总体运行时间。（不会显著地增加一个应用程序的总运行时间）
  2. 空间使用。（避免内存碎片，最大限度利用可用内存）
  3. 停顿时间。（停顿时间应该最小化）（一些实时应用很少使用垃圾回收）
  4. 程序局部性。（垃圾回收会影响程序局部性）

这些设计目标中的某些目标可能互相冲突，设计者必须认真考虑程序的典型行为之后做出权衡。



可达性

所有不需要对任何指针解引用就可以被程序直接访问的数据称为根集(root set)。例如在Java中一个程序的根集由所有静态字段成员和栈中的所有变量组成。

程序可以在任何时候访问根集中的任何成员。递归地，对于任何一个对象，如果指向它的引用被保存在任何可达对象的字段或成员数组元素中，那么这个对象本身也是可达的。

当程序被编译器优化之后，可达性问题会变得更加复杂。为了使得垃圾回收器能够找到正确的根集，优化编译器可以做一些处理。（《编译原理》p301）

总而言之：

  1. 新的对象通过对象分配被引用。参数传递和赋值可以传递可达性；
  2. 赋值和过程结束可能结束对对象的可达性。当一个对象变得不可达时，可能导致更多的对象变得不可达。

两种寻找不可达对象的方法：

  1. 捕获可达对象变得不可达的转变时刻。（例如引用计数技术）
  2. 周期性地定位所有可达对象，然后推出所有其他对象都是不可达的。（例如基于跟踪的垃圾回收技术）



引用计数垃圾回收器

使用引用计数垃圾回收器时，每个对象必须要有一个用于存放引用计数的字段。

引用计数可以按照下面的方法进行维护：

  1. 对象分配。（新对象的引用计数设置为1）
  2. 参数传递。（被传递给过程的每个对象的引用计数+1）
  3. 引用赋值。（左边指向的原本对象的引用计数-1，右边指向的对象的引用计数+1）
  4. 过程返回。（该过程活动记录中的局部变量所指向的对象的引用计数必须-1，如果多个局部变量存放了指向同一个对象的引用，那么对每个这样的引用，该对象的引用计数都要-1）
  5. 可达性的传递丢失。（当一个对象的引用计数变为0时，我们必须将该对象中的各个引用所指向的每个对象的引用计数-1）

引用计数的开销较大，因为每一次引用赋值，以及每个过程的入口和出口处。都会增加一个额外运算。
为了防止局部访问栈引起的引用计数更新开销，提出了延迟引用计数的概念。

另一方面，引用计数的优势在于垃圾回收是以增量方式完成的。尽管总的开销很大，但是这些运算分布在增变者的整个计算过程中。尽管删除一个引用可能致使大量对象变得不可达，我们可以很容易地延期执行递归地修改引用计数的运算，并在不同的时间点上逐步完成修改。（对于不能接受长时间突然停顿的交互式系统而言是一种很有吸引力的算法）
这个方法的另一种优势是垃圾被及时回收，从而保持了较低的空间使用率。

（END）