【GC算法几人知？】二、标记清除法 全解析小松与蘑菇-

所谓标记-清除，顾名思义，就是先标记那些活动的对象，然后再遍历堆，所有非标记对象都是需要清除清除的对象，类似于某些hr筛选简历时没有看到985-211学校直接拒绝~【手动狗头】

步骤

• 标记
  根据前置知识
  我们知道，一个对象有头有域，如何进行标记呢？就是在对象的头中设置一个mark标志位，然后从根开始，通过指针所找到的所有对象，都将其mark设置为true，即可完成标记
  标记前堆的状态
  
  标记后堆的状态（在头部设置的标志位）
  

• 清除
  接下来，我们开始遍历堆，凡是mark==false的对象，都是要回收的对象，我们会维护一个空闲链表free_list来进行回收

假设 object.mark==false，将object.next=free_list，这里的free_list表示的是空闲链表的首地址，就是将object指向free_list，然后再free_list=object，也就是将原本指向free_list的指针指向object，这样，object就成为了free_list的首部，完成回收

清除完成后堆的状态

可以看到，所有未被根直接或者间接引用的对象，全部链入到空闲链表中（白色部分），标记清除法，完结撒花！！！

等一下，真的这么简单吗？？
NO!

还记得前置知识中对算法好坏评判的四大标准吗？，显然，这个算法将会带来以下问题

缺点

1. 碎片化，如上图，仅一次清理就出现三个地方的空闲分块，如果进行多次回收，那么空闲块将会以碎片的方式存在堆中，当mutator要申请一个大的内存时，即使堆中有足够的容积，也会因为分成了很多碎片而拿不出来
2. 速度慢，当需要分块时，每次都必须从头遍历空闲列表free_list，找到一块足够大的空间进行分配，比如下图，如果我要找到大小为4的块，需要走两步，如果要找到大小更大的，不知道需要多少步，最坏情况下，将遍历完整个空闲列表
   
3. 最大暂停时间长，由于标记清除法是统一标记统一清除的，假如一次性标记了过多的垃圾，那么清除起来将会导致程序过长时间暂停，具体就是用ide写java的时候，动不动IDE就无响应了，然后变成白色,鼠标转啊转…… 会把人逼疯！！！
4. 与写时复制不兼容，这个可能有点难懂，如果想详细了解写时复制，可以去搜搜看，简单说就是如果一个子进程想要修改父进程的内容，比如一个老师要修改教务系统中某位同学的成绩，那么最好是只将这位同学的成绩复制到本地，然后修改，对于进程来说，就是只复制需要修改的部分，在子进程中修改好后，再写回到父进程中。

但是标记清除法是一个全局的方法，他需要对整个空间中的对象进行标记才有作用，所以如果你是用了写时复制技术，那么标记清除法将失效

策略

你可能说，既然有那么多缺点，那我们干脆就不用了吧
但是鲁迅说过：兵来将挡，水来土掩。方法肯定是有滴

1. BiBop VS 碎片化 + 速度慢
   碎片化的成因在于，清除的对象有大有小，分布在堆中，那么我们只需要将对象大小相近的分类，放在堆中即可，这就是BiBop方法
   
   可以看到，我们将3个字的放在一起，2个字的放在一起，这样，就不会出现碎片
   同时，我们维护了一个空闲链表的数组，每一个空闲链表专门指向一个大小的字，这样如果你想要3个字大小的空间，直接找专门用于3个字大小的空闲链表即可
   一举两得哦

2. 延迟清除 VS 最大暂停时间长
   这个其实不算什么厉害的技术，简单说就是，标记完成后，我并不清除，只有当需要分配新的内存空间时，我才进行清除操作，而且我这个清除，不是之前那种全部清除。只要我清除出一个符合要求的空间分配即可
   这就是典型的拆东墙补西墙……
   不过有效，也许每次新建对象会慢那么0.00001秒，但是人毕竟是感受不出来的
   另外还有一个问题是会导致堆中总是有垃圾，所以这个方法不能全局用，需要配合其他清除算法使用

3. 位图标记 VS 写时复制
   对于写时复制，关键在于如何在只能操作一部分空间的情况下，对整个空间进行标记处理
   我想你猜到了，我们是如何只看几页就知道一本书在讲什么的呢？目录！
   
   我们维护一个位图表格，每一个子进程都保留一个这样的表格，在子进程中通过表格就知道那些对象是被标记过的了，然后可以对复制进来的对象们进行GC处理，修改位图表格，最后还到父进程，父进程同样更新这个表格即可，其他子进程保持同步更新
   同时还有一个好处，我们在执行清除操作的时候直接按表就行了，标志位0的直接删除，这种按图索骥的方法又快又准，事实上，这种思想在计算机中大量使用，比如hash

这样就可以实现一叶知秋的效果啦

小结

说了这么多，其实这个方法是落后的方法，以后还会有引用计数法，GC复制法，分代回收法（java目前就是使用这种方法）等极具智慧与哲学的方法，快来学习前人的智慧吧！