垃圾回收
========================================

简介
---------------------------------------
垃圾回收(Garbage Collection, GC)指程序不用的内存空间。

满足 `找到内存空间里的垃圾` + `回收垃圾，让程序员能再次利用` 两项功能的程序就是GC。由John McCarthy在1960年首次发布。

常用概念
---------------------------------------

mutator
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
用于生成对象和更新指针。

堆
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
用于动态存放对象的内存空间，当mutator申请存放对象时，所需的内存空间就会从堆分配给mutator。

活动对象/非活动对象
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
活动对象指能通过mutator引用的对象，非活动对象指不能通过程序引用的对象。

分配
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
分配（allocation）在内存空间中分配对象。当没有可分配空间时，GC有两种选择：销毁所有的计算结果，输出错误信息，扩大堆，分配可用空间。

评价标准
---------------------------------------
评价GC算法的性能，采用吞吐量、最大暂停时间、堆使用效率、访问的局部性4个标准。

其中吞吐量指单位时间内的处理能力。最大暂停时间指因执行GC而暂停执行mutator的最长时间。

GC算法
---------------------------------------

标记 - 清除算法 （Mark Sweep GC）
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
分为标记阶段和清除阶段两个阶段。
标记阶段为对象打上标签。
collector会遍历整个堆，回收没有打上标签的对象

分配策略：

- First-fit 分配找到的第一个大于等于size的分块
- Best-fit 返回大于等于size的最小分块
- Worst-fit 找最大的分块

优点在于实现简单，与保守式GC算法兼容。

缺点在于碎片化，分配速度慢，与写时复制技术不兼容。

引用计数算法
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
引入计数器的概念，表示对象的人气指数。

优点在于可即刻回收垃圾，最大暂停时间短，没有必要沿指针查找。

缺点在于计数器值增减处理繁重，计数器需要占用很多位，实现烦琐复杂，循环引用无法回收。