CLR拖管堆，GC垃圾回收机制
发表于2018-09-21
在各类优化的文章中，反复多次的提到了GC这个概念，大家都知道是垃圾回收，但很多资料都没有提到过一些关于GC的细节，这里我拜读了一些资料，比如CLR via C#这本厚厚的指南，对垃圾回收处理做了比较详细的解释，可以了解到更多细节的地方。
现在内存的泄露很多都出现在我们在集合中存储了某个对象，在不需要的时候，却没有删除掉，比如UI，粒子，敌人等等
#拖管堆
首先是托管堆，又叫托管资源，即由CLR来负责拖管，分配及垃圾回收处理，CLR要求所有的对象都要在拖管堆上进行分配，在进程初始化的时候，CLR会划出一个地址空间做为拖管堆，CLR还要维护一个指针，NextObjPtr，他指向下一个对象在堆中之后的位置，默认指向CLR分配地址空间的首地址。
一个区域被非垃圾对象填满以后，CLR会分配更多的区域。这个过程一直重复，直到整个进程的地址空间被填满。
所以拖管堆内存的大小是受进程的虚拟地址空间限制的。
（在托管堆上，分配了三个对象ABC，NextObjPtr指向最后一个分配的对象C在堆中的下一个位置。）
ABC是三个连续的地址空间，连续的地址空间有很大的好处，这里英文原文叫Data Locality,数据的局化，这是个很重要的概念：
######简单说就是通过CPU的缓存(CPU Cache)来提高，加速数据的访问。
CPU每年都在升级，芯片的处理能力也在不断的加强，可以更快的处理数据，但这不代表，我们也可以更快的获取(get)数据。
在现代的CPU当中，每个芯片(chip)里都会有一小块(a little chunk of memory)的内存，这小块的内存就是Cache（确切的说是L1 Cache 高速缓存),CPU从Cache中获取数据的速度，要远远快于从主存中获取。 但Cache空间很小，因为它要能容纳在微小的芯片当中，但是Cache使用了更快的内存类型(static RAM or "SRAM")，可以更快的读取，同时，它的造价也要昂贵很多。
当CPU从主存中获取一段数据的时候，CPU同时会抓取一段连续的地址空间（内存）放到Cache当中，那么下一次我访问数据的时候，CPU会先从Cache中访问，如果存在，则直接从Cache中获取，速度非常快，如果不存在，再继续到主存中获取。
在Cache中成功的找到数据被称为Cache bit(缓存命中），反之，称为Cache miss(缓存未命中）。
所以，如果你的内存是分散的，不连续的，那么你便不会发挥CPU Cache的特性。一段连续的内存地址，可以被抓取到CPU Cache中，可以得到更快的访问速度。
#为何使用Object Pool对象池
大家都会在项目中使用Object Pool技术，通过上面的解释，可以知道，使用对象池，不仅仅是因为“已经初始化好的对象”可以更快的访问，对象池是一段连续的内存地址，他会有可能被CPU抓取到Cache中（考虑到Cache的空间），以此来获得惊人的访问速度。当然，还有另一个原因，对于频繁的new和delete的对象，也要使用对象池是为了避免内存碎片的产生。 当内存碎片越来越多的时候，拖管堆空间出现不足，便会引起GC，进行无用对象的内存释放以及碎片整理。
这并不是说，你在使用了连续的内存地址后，它一定会被抓取到Cache中，这里也有很多的注意事项和细节，具体大家可以自行查找相关的资料。
#内存碎片如何产生的？
关于内存碎片是如何产生的，举个小例子，我在堆内存中划分了一块地址空间，100个字节，我现在分配一个A对象，占用30个字节，那么，100个字节还剩下70个字节，这时候我又分配了一个新的对象B，占用50个字节，他分配在A的后面，这样，100个字节还剩下20个字节，这时候，我删除了A，释放出来30个字节的空间，然后我又生成一个C对象，也是50个字节，虽然100个字节中，还剩下50个字节，空间足够，但他不是一段连续的内存，所以，只能再申请一段新的地址空间。之前的20，30字节就有可能成为内存碎片。
如下图：
我们回过来继续讲，在堆内存中的每个对象都是有生命周期的，关于对生命周期的管理，有的系统采用引用计数算法，如果大家使用过cocos2d-x，他就是采用的引用计数（至少我那时候使用是这样，不知道后期是否有改变），每个对象都会有个计数来表示他的生命周期，当引用计数为0的时候，对象就可以从内存中删除了。
但引用计数有个最大的问题是不好处理循环引用，比如A引用了B，B也引用了A，这种会阻止两个对象的计数器达到0，所以两个对象永远不会删除。
CLR采用的是引用跟踪算法，他只关心引用类型的变量，我们将所有引用的变量都称为根。
CLR开始GC的时候，首先会暂停进程中所有的线程，这样可以防止线程在CLR检查期间访问对象并更改其状态。
然后CLR进入GC的“标记”阶段，在这个阶段，CLR遍历堆中所有的对象。将同步块索引字段中的一位设为0（同步块索引是我们new分配对象的一部分），这表明所有对象都应该删除（相当于reset一次），然后CLR检查所有的活动根，查看他们引用了哪些对象，如果一个根包含null，CLR就忽略并检查下一个根。
任何根如果引用了堆上的对象，CLR都会标记那个对象，也就是将该对象的同步块索引中的位设为1，一个对象被标记后，CLR会检查那个对象中的根，标记它们引用的对象，如果发现对象已经被标记，就不重新检查对象的字段，这就避免了因为循环引用而产生的死循环。
如图展示了一个堆，其中包含了几个对象，应用程序的根直接引用了对象A，C，D和F，所有对象都已经标记，在标记对象D的时候，GC发现这个对象含有一个引用对象H的字段，造成H字段被标记，这个过程会持续，直到所有的根检查完毕。
检查完毕以后，堆中的对象要么处于已标记状态，要么未标记。已标记的对象不能被垃圾回收，因为至少有一个根在引用它，我们称为可达（reachable)的，未标记的对象称为不可达（unreachable），没有根引用它。可以被垃圾回收处理。
这时候，GC就进入compact(碎片整理或是压缩）阶段，CLR会将堆中已经标记的的对象(小对象，后面会有说明）进行“转移“，将他们放在一段连续的内存空间上，这样做有许多的好处，首先，上面提到过的Data locality引用局部化，提高访问数据的速度，另一方面，可用空间也变得连续（即上面断开的碎片空间形成了连续空间），这段空间得到了解放 ，允许其它对象进驻。
这里，内存位置的改变，CLR也会自动处理旧引用位置的变更。以避免访问旧的内存位置，造成内存损坏。
compact以后，拖管堆的NextObjPtr指针指向了最后一个幸存对象之后的位置。下一个分配的对象将放在这个位置。下图展示了compact阶段之后的托管堆。该阶段完成后，CLR恢复应用程序的所有线程，这些线程会继承访问对象。就好像GC从来没有发生过一样。
如果CLR在一次GC后回收不了内存，而且进程中没法有空间来分配新的GC区域，就说明该进程的内存已经耗尽，此时，试图创建更多的对象会抛出OutOfMemoryException异常。
以上就是GC在垃圾回收过程中“发生的故事”。
上面提到的“小对象”，CLR将对象分为大对象和小对象，目前认为85000字节或是更大的对象是大对象（未来CLR可能会更改这个标准，85000不是常数），大对象不是在第0代地址空间中分配内存的，他会有自己的一段称为Large Object Space区域，专用于分配大数据对象，GC不会压缩大对象，因为大对象在内存中移动的代价过高，所以大对象还是可能会产生内存碎片的。CLR未来的版本可能会支持compact大对象。
GC在进行堆内存回收时，不是对整个堆进行回收，而是回收堆的一部分，这样可以提高性能。CLR的GC是基于代的垃圾回收器（generational garbage collector).
它对你的代码做出了以下几点假设：
1.对象越新，生存期越短
2.对象越老，生存期越长
3.回收堆的一部分，速度快于回收整个堆。
托管堆在初始化时不包含对象，添加到堆的对象被称为第0代对象，即是那些第一次新构造的对象，垃圾回收器从未检查过他们（垃圾回收还没有发生）。
如下图，它分配了5个对象（从A到E），他们都是第0代，过了一会儿，C和E变得不可达(unreacheable，没有根引用它们）
CLR初始化时为第0代对象选择一个预算容量（以KB为单位），如果分配一个新的对象造成第0代超过预算，就必须启动一次垃圾回收。
所以我们手动调用GC会立即执行吗，不会，何时会执行？ 在第0代的空间超出预算，没有足够的空间分配给新对象的时候。
假设对象A到E刚好用完第0代的空间，那么分配新的对象F就必须启动垃圾回收，垃圾回收判断 C和E是垃圾（不可达），就会compact对象D，使之于对象B相邻居（形成连续的地址空间），在这次垃圾回收中存活的对象A，B和D，现在成为了第1代对象，此时堆如图：
一次垃圾回收以后，第0代就不包含任何对象了(C和E被清理了，A,B,D变成了第1代对象），那么新对象的分配，就会在第0代中进行，这时候，新分配了对象F到K，这时候，随着应用程序的继续运行，对象B，H和J变得不可达，它们的内存将在某一时刻回收。
现在，假定新分配的对象L会造成第0代超出预算，必须启动垃圾回收。开始垃圾回收时，垃圾回收必须决定检查哪些代。
前面说明，CLR初始化时，会为第0代对象选择预算。事实上，它还必须为第1代选择预算。
开始垃圾回收时，垃圾回收器还会检查第1代占用了多少内存。在本例中，由于第1代占用的内存远少于预算，所以垃圾回收器只检查第0代中的对象，回看之前的假设，越新的对象活得越短，因此，第0代中包含更多垃圾的可能性最大，能回收更多的内存。
由于忽略了第1代中的对象，所以加快了垃圾回收速度。因为你不必遍历拖管堆中所有的对象。
基于代的垃圾回收器还假设，越老的对象活得越长，也就是说，第1代对象在应用程序中很有可能是继续可达的，如果垃圾回收器检查第1代中的对象，有可能找不到多少垃圾，结果是回收不了多少内存，因此，对第1代进行垃圾回收很可能是浪费时间，如果真有的有垃圾在第1代中，它将留在那里，此时的堆如图：
所有幸存下来的对象，都成为了第1代的一部分，由于垃圾回收器没有检查第1代，所以对象B虽然已经不可达，但他并没有被回收，同样，在一次垃圾回收后，第0代不包含任何对象（之前分配的对象变成了第1代，不可达的对象被清理），这时候应用程序继续执行，并分配对象L到O，在运行过程中，对象G，L和M变得不可达，此时的托管堆如下：
假设分配对象P导致第0代超过预算，垃圾回收发生。由于第1代中所有对象占据的内存仍小于预算，所以垃圾回收器决定再次只回收第0代，忽略第1代中不可达的对象（对象B和G），回收后的情况如下：
从上图可以看到，第1代正在缓慢的增长，假如第1代的增长也超出了预算，这时候应用程序继续运行，并分配对象P到S，使第0代对象超出了预算，这时候堆如下图：
这时候，应用程序试图分配对象T时，由于第0代已满，所以必须进行垃圾回收，但这一次，垃圾回收器发现第1代占用了太多的内存，以至于用完了预算，所以这次垃圾回收器决定检查第1代和第0代中所有的对象，两代都被垃圾回收后，堆的情况如下：
和之前一样，垃圾回收后，第0代幸存者成为了第1代，第1代的幸存者成为了第2代，第0代再次空出来了，准备迎接新对象的到来，第2代中的对象经过2次或是更多次的检查，但只有在第1代超了预算才会检查第1代的对象，而在此之前，一般都已经对第0代进行了好几次的垃圾回收。
CLR初始化时，会为每一代选择预算。这个预算是使用类似于启发式算法自动进行调节的。
比如在一次垃圾回收后，发现第0代后存活下来的对象很少，就有可能减少第0代的预算，分配空间的减少就意味着垃圾回收会更频繁的发生。但每次做的事情就更少了。相反，如果每次回收后，发现第0代存活的对象很多，就有可能增加第0代的预算，这样，垃圾回收的次数就会减少，但进行回收时，可以回收的内存也就更多。如果没有回收到足够的内存，垃圾回收器会执行一次完整的回收，如果还不够，就会抛出OutOfMemoryException异常。
上面说到托管资源，对应的是非拖管资源，非拖管资源不是由CLR进行垃圾回收的，需要我们手动释放，非拖管资源有I/O流，网络，数据库，线程等等，比如I/O读写文件，需要获取文件句柄，我们在使用的过程中，要进行手动的释放。比如使用using语句。
更多的细节请查阅CLR via C#第21章节 托管堆和垃圾回收
如果大家对.Net Mono的垃圾回收感兴趣，可以看下面的链接
https://www.mono-project.com/docs/advanced/garbage-collector/sgen/working-with-sgen/
Mono是基于SGen,原理都是采用的分代技术(generational collector)
感谢您的阅读，如文中有误，欢迎指正，谢谢！