垃圾回收算法

首先，需要先搞清楚两个问题。
1.什么是垃圾？
垃圾是指在运行程序中没有任何指针指向的对象，这个对象就是需要被回收的垃圾。
2.为什么要进行垃圾收集？
如果不即使对内存中的垃圾进行清理，那么垃圾对象所占的内存空间会保留到应用程序结束，甚至可能导致内存溢出。
其次，垃圾收集是分阶段的，分为标记阶段和清除阶段。
标记阶段作用是区分出内存中哪些是存活对象，哪些是已经死亡的对象，一般有两种方式：引用计数算法和可达性分析算法。
清除阶段是当成功区分出内存中存活对象和死亡对象后，GC接下来的任务就是执行垃圾回收，释放掉无用对象所占用的内存空间，以便又足够的可用内存空间为新对象分配内存。目前JVM中比较常见的三种垃圾收集算法是标记-清除算法、复制算法、标记-压缩算法。

1.标记阶段:引用计数算法

1.1概念

每个对象保存一个整型的引用计数器属性，用于记录对象被引用的情况。
对于一个对象A，只要有任何一个对象引用了A，则A的引用计数器就加1；当引用失效时，引用计数器就减1.只要对象A的引用计数器的值为0.即表示对象A不可能再被使用，可进行回收。

1.2优点

实现简单，垃圾对象便于辨识；判定效率高，回收没有延迟性。

1.3缺点

它需要单独的字段存储计数器，这样的做法增加了存储空间的开销。
每次复制都需要更新计数器，伴随着加法和减法操作，这增加了时间开销。
引用计数器有一个严重的问题，即无法处理循环引用的情况。见下图：

其中rc为引用计数器。
正因为这个致命缺陷，导致在Java的垃圾回收器中没有使用这类算法。但是在Python的垃圾回收中就使用了这个算法。
Python如何解决循环引用？
1.手动解除
2.使用弱引用weakref，weakref是Python的标准库。

2.标记阶段:可达性分析算法

2.1概念

通过GC Roots的对象为起点，向下搜索，能到达的对象为不可回收对象，不能到达的对象为需要回收的对象。Java中就是通过可达性分析算法来判定对象是否存活的。这种算法就是Java、C#选择的。也叫根搜索算法、追踪行垃圾收集。
GC Roots的对象
1）、方法区中常量引用的对象；
2）、方法区中类静态属性（static修饰）引用的对象；
3）、虚拟机栈（本地变量表）中引用的对象（正在被使用）；
4）、本地方法栈（native修饰方法）中引用的对象；

2.2优点

解决了在引用计数算法中循环引用的问题，防止内存泄漏的发生。Java和C#就是用这种算法。

2.3缺点

分析工作必须在一个保障一致性的快照中进行。这点不满足的分析结果的准确性就无法保证。这点也是导致GC进行时必须“Stop The World”的一个重要原因。

3.清除阶段:标记-清除算法

当堆中的有效内存空间被耗尽的时候，就会停止整个程序（STW），然后进行两项工作，第一项是标记，第二项则是清除。
需要注意的是这里所谓的清除并不是真的置空，而是把需要清除的对象地址保存在空闲的地址列表里。下次又新对象需要加载时，判断垃圾的位置空间是否够，如果够，就存放。
标记：从引用根节点开始便利，标记所有被引用的对象。一般是在对象的对象头中记录为可达对象。
清除：对堆内存从头到尾进行线性的遍历，如果发现某个对象在对象头中没有标记为可达对象，则将其回收。