[OS] 垃圾收集
1. 垃圾对象
在面向对象编程环境中，对象可以被自由的创建，使用，并且稍后当不再需要它们时被丢弃。
程序员被造成有一个无限的内存空间的错觉，并且不必为显式的分配和管理一个固定容量的内存而担心。
当然，在现实中，内存资源不是无限的，并且最终程序可能用完内存资源。
为了防止发生这种情况（或者至少组织它），不再访问的对象（即“垃圾”）可以被收集然后被新的对象复用。
垃圾收集器实质上是每个JVM实现的一部分，尽管没有严格要求它作为JVM规范的一部分。
当JVM在低内存资源上运行或者定时运行时，它调用垃圾收集器来找出不可达的无用对象，并收集它们的内存资源供以后使用。
引用的根集指向保存在全局内存堆中的对象。
这些对象中的一些依次包含指向其他对象的引用，等等。
同样，还有一些对象不能通过从根集开始的引用序列到达，这些是无用对象。
为了开始垃圾回收操作，首先有必要确定这些根指针。
我们看到根集必须包含在栈中某处的引用，包括局部存储和操作数栈，或者再常量池中。
根集还必须包括静态对象所含的引用。
垃圾收集从引用的根集开始找出所有可以访问的对象，
任何在这个过程中没有被发现的对象都是可以被回收的垃圾。
尽管一些垃圾收集器保存对堆中每个对象引用次数的计数器，并且把任何引用计数器为零的对象认为是垃圾，
但是这种引用计数收集器在JVM已相对不常见了。
大多数JVM使用前面提到的一般方法，即从一组根引用开始，然后通过堆中的引用链跟踪以找出所有可达的或者是“活动的”对象。
接着，所有不可达的对象被认为是垃圾并且被重复利用。
2. 常见的垃圾收集器
2.1 标记清扫收集器
（1） 标记 & 清扫
标记清扫收集器是一个基本的收集器，它从根引用开始并且跟踪所有可达的对象，
在到达每个对象时标记这个对象。
标记可以由设置标记位组成，标记位或者作为对象实现的一部分，或者再一个单独的位图中，
位图中的每个位于一个对象相关联。
如果到达一个已被标记的对象，那么停止向下跟踪这个特殊的路径。
在所有活动对象被发现和标记之后，还有一个清扫阶段。
其中检查所有的对象，凡是未被标记的对象被确定为垃圾，可以被复用。
在清扫阶段，当发现无用对象时，它们可以被组合成一个自由对象链表。
（2）内存碎片问题
大体来说，这是一种相对快速的识别和收集垃圾的方式。
然而，自由对象是可变大小的并且分散在堆空间中，并与活对象混杂在一起。
简单的将自由对象链接起来会导致内存碎片问题。
当创建一个新对象并且必须为之找出一个合适大小的空闲空间时，碎片问题接着会导致效率非常低。
特别的，分配算法必须查找链表以找到适当大小的连续空闲内存块。
最终，碎片数目会越来越多以至于需要紧压。
然而，可以通过使用多个分离的自由链表来降低低效性。
通常，动态内存分配是与垃圾收集紧密相关的。
（3）解决方法
在概念上，改善分配效率的最简单的方法是将所有的无用空间合并为一个大的连续区域，从中可以创建新的对象。
有两种合并无用空间的方式：通过紧压或者通过复制。
2.2 紧压收集器
（1）紧压
紧压收集器，像它的名字暗示的那样，
本质上将活动对象“滑动”到堆内存区域的底部（或顶部），使得所有活动的对象都是相邻的。
所剩下的就是一个连续的自由空间区域。
在紧压过程中，活动的对象被移到堆的一个连续区域中，
而未被使用的空间也变成一个连续的区域，从中可以分配新的对象。
尽管在概念上简单，紧压收集器还是相对缓慢的，因为它多次遍历整个堆。
一遍是做标记，随后的遍是为活动的对象计算新的位置，移动对象，并且更新指向新位置的引用。
其他方法简而言之都是通过减少遍的次数，和/或在每次收集步过程中只分析堆的一个子集来提高效率。
（2）移动对象问题
紧压回收也突出了一个问题，它与任何在内存中移动对象的方案同时出现，
而移动对象是垃圾收集的一部分。
亦即，当移动对象时，必须改变对象的引用，这使整个过程复杂化（和减慢）了。
不过，为了减少引用更新的数目，一些系统使用句柄池（handle pool）来合并指向每个单独对象的指针。
然后一个对象的引用指向句柄池中相关的指针。
利用句柄池，当移动对象时，就没有必要找到并更新所有对象的引用，
而是只必须改变句柄池中的指针，
于是在这个过程中就自动修改了所有的引用。
这种方法的最大缺点是每个对象访问包括一个额外的间接层。
2.3 复制收集器
（1）动机
为了减少在收集过程中遍历堆的次数，复制收集器用内存空间来换取收集时间。
（2）策略
它把堆分成两半，在任何时刻，一半是未使用的而另一半则包含活动的堆。
当活动的一半被填满时，收集器就像它在标记阶段中所做的那样遍历这个堆。
不过它将清扫与标记阶段相结合。
当它找到一个活动对象时，它立即将这个对象移动到堆中未使用的一半，并且继续遍历堆。
当完成对堆的遍历时，活动对象放在以前未使用的那一半的连续空间上，这第二半的剩余部分是空间的，
而堆的第一半（即以前是活动的）就变成未使用的了。
（3）空间问题
复制收集器比紧压收集器快，但是它也有较高的内存需求，
根据定义，堆空间的一半在任何给定时间内都是未使用的。
2.4 分代收集器
（1）动机
紧压和复制收集器在每次执行收集时，都要移动非常大的一部分动态对象。
一个长期活动的对象在它的生存期内会被移动许多次，
通过观察到对象的生存期有双峰的分布，
可以避免这种相当浪费的移动。
首先，许多对象的生存期非常短，这经常是好的面向对象编程实践的副产品。
其次，不具有短生存期的对象趋向于有非常长的生存期。
因此，为了避免反复复制长期活动的对象，分代的垃圾收集器试图根据对象的年龄将对象分组。
（2）实现
在基本的分代收集器中，堆被划分成子堆。
为了简便起见，我们用两个子堆来描述这个实现。
在两个子堆中，一个将保存较老的或者长期使用的对象，称为“老”区，
另一个则保存新创建对象，称为“年轻”区。
“年轻”区要比“老”区更频繁的执行垃圾收集。
如果一个对象在若干次（通常很小）收集后仍幸存于“年轻”区中，它就被移到“老”区中。
从而长期活动的对象最终将被放入到堆的“老”区中，
在那里垃圾收集是很少发生的，这样就避免了不必要的对象移动。
（3）优势
分代收集器不但降低了收集的整个开销，而且在每次调用收集器时只对一小部分堆进行收集。
这意味着如果当收集发生时暂停运行的进程，则可以大大降低“暂停”时间。
使用一个大堆以及传统的紧压或复制收集器，用户是很容易察觉到程序因收集而被暂停的时间。
在分代收集器中，两个子堆不必按相同的方式来管理。
实际上，它们可以按不同的方式来管理以很好的使用性能折衷。
例如，“年轻”区使用复制收集器，使得快速分配新对象，
而在“老”区使用标记清扫收集器，使得通过清除指针更新而降低收集时间。
2.5 增量收集器和并发收集器
（1）增量 & 并发
上述所有的基本收集器在执行收集时都会暂停程序执行，然后再将控制归还给程序。
收集是消耗时间的（即使是用分代收集器），因此当收集器工作时程序的执行会暂停一定量的时间。
如果收集是随程序的运行增量的进行，而不是一次性完成，那么收集时间是可以被分摊的。
此外，在实时应用中，垃圾收集时间会限制以提供足够的响应延迟。
如果有多个处理器可用，则采取下面的做法是有益的，即用一个线程并发的收集垃圾，
而使用其他进程继续进行正常的程序执行。
在两种情况下，当程序运行时被部分收集的堆可能处于波动状态。
这暗示着在运行的程序和垃圾收集器之间必须有某种同步，因此当一个对象正被移动时，即当指针可能暂时不一致时，程序不会试图引用这个对象。
否则，在收集器正跟踪一条引用路径时，如果程序改变这个引用，就会导致类似的同步问题。
（2）问题
许多传统的停止-收集方法可以转换成增量的版本。
关于并发或增量收集的一个基本问题是在任何给定时间内，一个对象可能已经被扫描并标记。
然后收集仍在进行中，已经扫描过的对象中的引用可以被改变以指向还没有被标记的对象。
（3）解决方案
这个问题有许多解决方法，它们都在运行的应用（可能改变堆的内容）和收集器之间提供了某种形式的同步。
通常的解决办法之一是为对已经标记过的对象的引用提供写路障（write barriers）。
这些写路障主要检查重写一个已经标记过的对象的指针的情况。
当这种情况发生时，标记所指向的对象（并且放入对象队列中，随着标记的进行它们的指针应该被监视）。
3. 垃圾收集器小结
没有一个收集器在所有的程序上都工作的最好，
因为程序在工作集大小，对象大小，堆大小，以及对象被创建（和释放）的速度上都有所不同。
因此，我们不能得出一个关于“最好的”收集器所必须遵守的结论。
然而我们可以概括的小结重要的性能折衷。
分代收集器的使用是一个有些正交的考虑，
因为分代收集器可以利用任何基本方法（或者混合的方法）来使用。
分代收集器的优点是通过只关注那些垃圾最可能被发现的地方（“年轻”区）中的对象来降低收集时间。
现在，分代收集器常被认为是一种成功的决策。
