垃圾判定, 回收算法

垃圾判定

垃圾回收的重要环节是判定哪些对象需要回收, 重要的回收算法有:

1. 引用计数算法(COM, ActionScript, Python)
2. 可达性分析算法(Java, C#, Lisp 采用)

引用计数算法

什么是引用计数算法?

每个对象中有一个引用计数器:

• 每当有一个地方引用它, 计数器的值就会加一
• 每当有一个引用失效, 计数器的值就会减一

优点和不足

引用计数的优点是:

1. 实现简单
2. 效率高

缺点是:

难以解决循环引用的问题.

可达性分析算法

通过 GC Roots 的对象作为起点, 从这些节点开始往下搜索, 搜索经过的路径称为 "引用链".

当一个对象和 GC Roots 之间没有"引用链"可以连接, 则 GC Roots 到此对象不可达, 此对象需要回收.

那么作为顶点的 GC Roots 包括哪些呢?

1. 虚拟机栈(栈帧中的本地变量表)中引用的对象
2. 本地方法栈中引用的对象
3. 方法区中, 静态变量引用的对象
4. 方法区中常量引用的对象

引用

JDK 1.2 之前, Java 引用只有一种:

reference 类型的数据中存储的数值代表的是另外一块内存的起始地址

JDK 1.2 之后, Java 拓展出 4 种引用:

• 强引用(Strong), 普通引用对象, 如 Object obj = new Object(). 永远不会被回收掉的引用对象.

• 软引用(Soft), 非必须对象, 内存逸出异常抛出之前回收
• 弱引用(Weak), 比软引用弱, 非必须对象, 无论内存是否足够都会被回收

• 虚引用(Phantom), 最弱的引用关系, 无法通过引用获取实例

方法区的回收

方法区回收主要回收以下两类:

1. 废弃常量, 回收条件: 系统中没有任何一个对象引用到此常量
2. 无用的类, 回收条件:

• 该类所有实例都已经被回收
• 加载该类的 ClassLoader 已经被回收
• 该类的对应的 java.lang.Class 没有任何地方被引用.

回收算法

标记-清除 (Mark-Sweep) 算法

算法分 "标记" 和 "清除" 两个阶段, 首先标记出所有需要回收的对象, 在标记完成后统一回收所有被标记的对象.

优点是简单, 不足之处是:

1. 效率比较低
2. 空间不连续, 原地清除, 碎片多, 若分配大对象时, 可能会因为空间不足而触发一次 GC.

常用在老年代.

复制 (Copying) 算法

此算法将内存分成两块, 当一块内存用完之后, 就将 __还存活着的对象__复制到另外一块上面.

优点是: 效率高
缺点是: 内存利用不充分

常用在新生代.

HotSpot 中将新生代划分为 Eden 和两块 Survivor 区域, 默认 Eden 与一块 Survivor 的比例是 8:1.

每次 Eden 和 一块 Survivor(A) 负责分配, 另一块 Survivor(B) 为替补.

• 当空间需要回收且 B 大小足够容纳 Eden+A 中的存活对象时, 会将 Eden 和 A 中的对象复制到 Survivor 中, 然后 Eden 和 复制后的 Survivor(B) 一起作为负责分配的空间, A 成为替补.

• 当空间需要回收且 B 大小不够容纳 Eden+A 中的存活对象时, 会将 Eden+A 中的对象复制到 老年代.

标记-整理 (Mark-Compact) 算法

算法分 "标记" 和 "整理" 两个阶段, 首先标记出所有需要回收的对象, 然后让所有存活的对象都向一端移动.

它解决了 标记-清除 算法中, 碎片过多的问题.

安全点和安全区域

为什么 GC 时需要卡顿(__Stop the world)?

因为 GC 需要将某一刻全局(常量和静态变量)和执行上下文中(栈)的中的所有 GC Roots 找到并枚举, 进行可达性分析.

现在主流的 GC 都使用 OopMap 来保存每个对象什么偏移量存什么数据, 以及栈和寄存器中哪些位置是引用. 这样 GC 就不用每次在停顿后通过遍历来得知 GC Roots 了.

安全点 (Safepoint)

OopMap 记录的信息不需要记录太频繁, 否则占额外空间太多也运行时效率; 也不能太长时间不记录, 否则影响 GC 效率.

OopMap 记录的位置叫 安全点, 位置的选取标准为: 让程序长时间执行.

那么如何让线程在安全点停下来呢? 有两种方式:

1. 抢先式中断, JVM 强制中断全部线程, 检查他们是否在安全点上, 若有的线程不在安全点, 则, 让他们运行直到在安全点.
2. 主动式中断, JVM 需要中断线程时, 就设置一个全局的中断标志, 让线程轮询这个中断标志.

安全区域 (Safe Region)

安全区域是扩展了的安全点, 代表此区域中, 引用关系不会发生改变, GC 总是安全的. 它主要解决以下问题:

GC 时, 并不是所有线程都是在 "活动" 状态的, 有的时候, 线程无法轮询中断标志, 因为他们正在被挂起(Sleep 或者 Blocked).

对于 Sleep 和 Blocked 而言, 本地变量栈是线程私有的, 栈上对象的引用当然不会变, 所以 Sleep 和 Block 属于安全区域代码.

当线程执行到安全代码时,

1. 线程先标明已经进入 安全区域 区
2. 若 JVM 此时发起 GC, 这些线程就会被忽略
3. 当线程离开 安全区域 时, 会检查系统是否完成了根节点枚举
4. 若完成, 线程继续执行, 否则, 它会等待直到收到可以离开 安全区域 的信号