垃圾回收算法基本思想：
1.枚举根节点（GC Roots)
在垃圾回收时，我们要想办法找出哪些对象是存活的，一般会选取一些被称为GC Root的对象,从这些对象开始枚举。枚举时要求所有对象停下来，也就是大家所称的“Stop the world”。所有的算法实现都会将虚拟机停下来的，否则分析结果的准确性将无法保证。当执行系统停顿下来之后，虚拟机不需要遍历所有的根节点和上下文去确定GC Roots，而是存在着一个OopMap的数据结构来达到这个目的。在类加载完成的时候，虚拟机就会把什么类的什么偏移上是什么类型的数据计算出来。在JIT编译的时候也会在特定位置记下在寄存器和栈中哪些位置是引用，GC在扫描时就可直接得到信息。

2.安全点
因为程序在运行时不是所有的时候停下来都是安全的（比如运算进行到一半，数据值是一个脏数据），安全点是所有线程在”Stop the world”时到达的一个安全的点。由于堆中的对象庞大，若为每个对象都生成OopMap数据结构将占用大量空间，所以HotSpot只在”安全点“上生成这些数据结构。同时程序并非在所有位置都可以停止，而是只能在安全点才会停止。所以”安全点“还会影响到GC的及时性。”安全点“选取时不能太多，以造成空间上的支出，也不能太少，以让GC等待较长时间。
对于”安全点“还有另外一个需要考虑的问题是，当GC发生时如何让所有线程都跑到最近的”安全点“，一般都两种方案。抢先式中断，抢先式中断是虚拟机将所有线程停下来，然后一一检查是否已达安全点，若没有到达安全点则恢复线程让其到达最近的”安全点”,此种方式几乎没有虚拟机使用。主动式中断的思路是中断发生时，虚拟机在所有的线程上设置一个标志，线程自行检查该标志，然后进入“安全点”。检查标志的地方和安全点是重合的。

3.安全区域
上面没有解决的问题是当一个线程处于休眠，或未分配CPU时钟，比如sleep或blocked状态时，他就无法走到安全点去挂起自己。对于这种情况，就需要通过安全区域来解决，安全区域是一个程序不会更改自己引用的区间，在这个区域的任何地方开始GC都是安全的，可以被认为是扩展了的安全点。当线程执行到SafeRegion的代码时，他就会标记自己已经进入Safe Region,此时发生GC，将不会管这些线程。快要离开安全区域的时候他就会去检查当前的状态，如果是在GC中，那边他就会挂起等待可以离开Safe Region的信号，否则他就可以继续运行。

二、垃圾收集器算法简介
JDK1.7版本，包含的垃圾收集处理器如下：

上图是jdk1.7提供了垃圾回收器图，两者有连线说明可以搭配使用，回收器还因为其适用的区域分为年青代，年老代。另外垃圾回收处理器没有优劣之分，只有适用与不适用之分。
在介绍垃圾回收器之前，先说明两个概念。
并行（Parallel）：指多条垃圾回收处理器产并行工作，但此时用户线程是暂停的。
并发(Concurrent)：指用户线程和垃圾收集线程同时执行（也有可能是交替执行），可能用户线程运行在这个CPU上，而垃圾回收线程运行在另一个CPU上。

年青代的垃圾回收器

1.Serial收集器（年老代单线程收集器）

单线程的收集器，收集时还会暂停所有工作线程，直到它收集结束。
Serial收集年青时使用复制算法。暂停所有用户线程
备注：是在client模式下默认的新生代收集器，原因是在桌面模式下管理的内存比较小，几十M，单线程相比多线程回收，少了线程间交互，效率更高。所以单线程模式是一个不错的选择。

2.ParNew收集器（年青代多线程收集器）

ParNew是Serial的多线程版本。新生代收集采用复制算法，收集时会暂停所有用户线程。他是server模式下年青代的默认垃圾回收处理器，一个重要的原因是只有他能与年老代的CMS处理器配合使用。
ParNew处理器在单CPU环境下绝对不会比Serial有更好的表现。因为有线程交互的成本，但是随着CPU数量的增加，使用还是很有好处的。

3.Parllel Scavenge收集器

Parllel Scavenge收集器也是一个并行的多线程收集器，看起来似乎同ParNew收集器无本质的区别，但是他的目标是不一样的。他的目标是达到一个可控制的吞吐量。吞吐量＝运行代码时间/(运行代码时间+垃圾回收时间)。其实高吞吐量是指较高程度的利用了CPU。但不意味着其用户体验一定是最好的，因为单次暂停可能会非常长。他有两个参数来控制：

MaxGCPauseMillis:期望的最大GC停顿时间，当这个时间就少，他是通过将新生代调小来减少停顿时间（收集300M比收集500M来得快，但这样会导致垃圾收集发生得更频率，原来10秒一次，每次停100ms,现在每5秒停一次，每次停70秒),但会降低总体的吞吐量。
GCTimeRatio:配置的是用户时间同GC时间的比值，比如19,则是指GC时间同用户使用时间的比值是1：19。那么允许的最大GC时间就是1/(1+19),即5%.
-XX:+UseAdaptiveSizePolicy:这个收集器另外可配置的一个参数，虚拟机会自动根据运行时的情况来动态调整年青代，年老代的大小，以提供最合适的停顿时间或者最大的吞吐量。这个被称为GC自适应的调节策略。
也就是说只需要给虚拟机设定吞吐量目标和管理的最大堆的大小，然后就让自适应调节策略去自动优化吧，这是和ParNew收集器的一个重要区别。

年老代的垃圾回收器

1.Serial Old

Serial Old是单线程版本的老年代收集器，收集时使用“标记-整理”算法，收集时暂停所有用户线程。他存在的主要意义是供Client模式下的虚拟机使用，原因同serial收集器是client模式下的默认收集器一样。
如果是Server模式下，他还有两个用户，一个是和Parallel Scavenge收集器搭配使用。另一个是做为CMS收集器的后备预案，用于在CMS在Concurrent Mode Failure时使用。

2.Parallel Old收集器

Parallel Old是Parallel Scavenge收集器的老年代版本，使用多线程的“标记-整理”算法。他们俩适合配套使用。由于Parallel Scavenge不能同CMS配合使用，一般就只能同Serial Old配合使用，所以jdk1.6才引入的Parallel Old收集器填补了这块空白。

3.CMS（Concurrent Mark Sweep）并发标记清扫收集器

CMS是一种以获得最短停顿时间为目标的收集器。由于大部分的互联网应用都倾向于向用户提供更好的交互体验，所以希望较短的停顿时间，以带来更好的体验。他的实现相较更复杂，分为如下步骤

• 初始标记（stop the world）
• 并发标记
• 重新标记（stop the world）
• 并发清除

除1，3步骤是暂停的，其它步骤是并发的。初始标记主要是标记的GC Root直接关联到的对象。并发标记则是走的GC Root Tracing的过程。重新标记是修正在并发标记期间由于用户线程的并发运行引起的变动，耗时会较长，但远比并发标记耗时来得短。整个过程中较耗时的并发标记和并发清除阶段都是和用户进程并发的，所以他较小的减少了停顿时间。
总体而言，CMS是并发的，低停顿收集器，但他还远算不上完美，他有如下一些缺点

• CPU敏感，会占用系统CPU资源，并发回收时一般开启（CPU数量+3)/4个线程，会导致总吞吐量降低。
• CMS不能处理浮动垃圾，可能出现”Concurrent Mode Failure”失败而导致一次Full GC.浮动垃圾是指在回收期间新产生的垃圾，这部分垃圾只有留待下次清扫。另外由于用户线程并发运行，他还需要内存来支持，所以收集器会在一个较低的使用率时就开始工作，以便有空间供垃圾回收期间程序并发时使用。使用-XX：CMSInitiatingOccupancyFraction来修改触发时的比例，JDK1.6设置的比率是92%。如果CMS在运行期间预留的内存无法满足程序使用，就会出现“Concurrent Mode Failure”， 从而会启动备选的Serial Old来进行垃圾回收，这样会耗更长的时间，所以一个较合适的比值会提高吞吐量。
• 使用”标记-清扫”算法会产生碎片，此时需暂停所有用户线程以进行整理，会消耗更多的时间。

4.G1收集器

G1是一款面向服务器端的垃圾收集器，被视为是CMS收集器的后继者，他具有以下特点。

• 并行与并发。充分利用多CPU来缩短垃圾回收的停顿时间，原本需要停顿的，仍然可以通过并发方式让JAVA程序继续运行
• 分代收集。G1不需要同其它收集器配合使用。其内部会根据对象的存活长短使用不同的回收算法。
• 空间整合。整体来看是基于“标记-整理”算法，从局部上来看是基于“复制”算法。这种方式会减少碎片的产生。
• 可预测的停顿。除了完成尽量减少停顿的目标以外，还建立了可预测停顿时间的模型。

后面我们来看看G1是如何做到这一切的。
G1收集器的内部内存而已与之前收集器有很大不同。他将整个堆划分成多个大小相等的独立区域（Region）。虽然还保留有新生代和老年代的概念，但是他们之间不再物理隔离，他们都是一部分Region（不需要连续）的集合。
为什么G1能做到对垃圾停顿时间的预测，是因为他有计划的避免进行全区域的垃圾回收。他会扫描各区域，分析垃圾回收的价值，在后台维护一个优先列表，只有有较高回收价值的区域才启动回收，这也是Garbage-First名字的由来。
整体上来说，G1的思路就是化整为零。但是其实现具有较大的复杂性，因为Region间是互相引用的，回收一个Region需要遍历到其它Region的内容。
在G1收集器中Region中使用Remebered Set来避免全堆扫描的。当虚拟机发现对引用型数据进行写操作时，会产生一个Write Barrier暂时中断写操作，检查是否引用到不同的Region,如果是则使用CardTable把相关的信息记录被引用对象所属的Region的Rember Set中。当进行垃圾回收时，GC Root的枚举范围增加Rember Set就不会有遗漏。如果不记对Remembered Set的维护操作，收集步骤大概分为如下几步：

• 初始标记
• 并发标记
• 最终标记
• 筛选回收

初始标记
此阶段只是标记GC Roots关联到的对象，并且修改TAMS（Next Top at Mark Start)的值 。让下一阶段并发的用户能在正确的Region上创建新对象，此过程需要停线程，但是耗时很短。
并发标记
遍历GC Roots关联对象，判断可达性，找出存活对象，可并发。
最终标记
在并发标记阶段发生的更改会记录到Remembered Set Log中。需将这些Log数据合并到Remembered Set中。
筛选回收
此阶段是评估回收价值的阶段。回收时会停顿用户线程，因为是对单个子Region回收，由于较小时间可控，停止线程会提高收集效率。后续可能可以做到并发。

关于G1算法的深入原理参见此文：http://hllvm.group.iteye.com/group/topic/44381#post-272188