基本垃圾回收策略
- 标记-清扫 （mark-sweep）
- 标记-复制 （mark-copy）
- 标记-整理 （mark-compact）
- 引用计数 （reference-counting）
主要着重于前三中基本回收策略，由于目前主流的垃圾回收器都不是基于引用计数的，所以只是简单提一提，并不详细介绍
在对这几种基本回收策略进行描述时，我们假定的前提是赋值器运行在一个或多个线程上，而回收器则是单线程的，并且回收器运行时，所有赋值器线程均处于停止状态。这种“万物静止”（stop the world）的策略排除了赋值器与回收器间的互相干扰，大幅简化了回收器的实现。更为复杂的，赋值器与回收器并发执行的垃圾执行策略，将留给以后再做介绍。
标记-清扫算法
标记-清扫算法通过对赋值器根进行追踪，标记所有从赋值器根可达的对象，从而间接的找出不可达（垃圾）对象对其进行回收，它的回收过程分为两个阶段：
- 追踪：回收器从根集合开始遍历对象图，并标记遇到的所有对象
- 清扫：检查堆中所有对象，并回收未被标记的对象
追踪阶段
让我们先来关注追踪阶段，对于学习过图算法的人一定并不陌生，对根对象进行追踪过程，其实就是一个图遍历的过程，以下给出基于递归的深度优先遍历对象图的伪代码（书中给出的是基于栈的非递归形式，这里给出递归形式方便自己理解）
markFromRoots():
foreach obj in Roots // 遍历标记根对象
if obj != null && !isMarked(obj)
mark(obj)
mark(obj):
setMarked(obj) // 标记对象
foreach field in obj.fileds // 遍历对象域
if field != null && !isMarked(field)
mark(field) // 通过递归标记该对象所应用的对象
清扫阶段
完成对象的标记后，可以开始比遍历检查堆中所有对象，并回收未被标记的对象
sweep()：
foreach obj in heap
if isMarked(obj)
unSetMarked(obj) // 清除标记
else
free(obj) // 回收对象
可以看出，清扫阶段仅仅是回收未被标记的对象，并不会移动任何对象，因此会产生内存碎片
追踪过程中对象的三色抽象
三色抽象用以描述追踪过程中对象状态的变化，在三色抽象中，将对象划分为黑色，灰色及白色对象，追踪阶段初始状态下所有对象均为白色，当回收器初次扫描到一个对象时，将其着为灰色，当该对象所有的子节点都被扫描到后，将该对象标记为黑色。追踪结束后，所有黑色对象为可达对象，所有白色对象为不可达对象，并且不存在灰色对象。
上述算法中存在一个重要的不变式：标记完成后，对象图中将不会存在黑色对象引用白色对象，这称为三色不变式。在之后研究赋值器与回收器并发执行的并发垃圾回收时三色不变式将十分有用。
标记-整理算法
标记整理算法同样分为追踪对象与回收对象两个阶段，追踪阶段与标记清扫算法基本相同，不同点在于对对象的回收阶段，前面提到标记清扫并不会移动对象，这将带来内存碎片问题，而标记整理算法，顾名思义，将在回收对象过程中对存活对象进行整理压缩，将存活的对象”滑动”到堆的一端。
标记-复制算法
最简单的标记复制算法将内存划分为2个半区，分别是来源空间(fromspace)与目标空间(tospace)，赋值器只在来源空间分配内存，当来源空间内存不足发起垃圾回收，回收器会将来源空间存活对象复制到目标空间。在复制的过程中完成了对象的整理工作。
需要考虑的问题
赋值器开销
作为最基本的垃圾回收算法，标记清扫，标记回收与标记复制在算法上赋值器与回收器不会发生任何交互，因此并不会给赋值器带来任何额外的读写开销。而之后会介绍到的更为复杂的回收器，分代回收器，并发回收器以及增量回收器都要求赋值器在修改指针时通知回收器，因而产生一些开销。
值得一提的是，虽然基本算法回收器对于赋值器没有直接上带来开销。但是对于移动式垃圾回收来说，赋值器在没有内存碎片的情况下进行顺序分配，分配策略简单且速度很快。而对于应用标记整理算法的非移动式垃圾回收器，赋值器分配策略要更为复杂，并且空间局部性要差
吞吐量
标记-清扫算法的吞吐量通常很高，因为清扫回收对象并不需要移动对象，只是遍历堆并回收对象。相比之下，标记-复制算法需要将存活对象复制到目标空间，而标记-整理算法在整理过程中需要多次遍历堆对对象进行移动整理，这些额外的步骤将造成开销导致吞吐量下降
空间利用率
在空间利用率上，标记-整理无疑是最高的。标记-清扫算法由于内存碎片的原因，降低了空间利用率。标记-复制算法由于必须划分内存，同一时刻只能在一个分区进行内存分配，空间利用率更低
长寿对象的处理
在标记-整理算法中，经历过多次垃圾回收的长寿对象将会”沉淀”在堆的底部，从而避免对长寿对象的多次移动。而标记-复制算法对此表现很差，需要不停的将长寿对象在两个分区移动
对象移动还是不移动，整理还是复制
移动式回收算法是解决内存碎片的唯一办法，然而非移动式回收具有较高的吞吐量。在移动式回收算法中复制相比整理吞吐量高，但是空间利用率却很差。俗话说的好，天底下没有免费的午餐，开发人员需要对一个算法带来的收益以及负面影响进行权衡，之后我们将会在后续中看到开发人员基于这些基本的垃圾回收算法，构建更为复杂的垃圾回收策略。