GC学习读书笔记（二） GC标记 -清除算法

首先了解下标记清除算法的概念：GC 标记 - 清除算法由标记阶段和清除阶段构成。标记阶段是
把所有活动对象都做上标记的阶段。清除阶段是把那些没有标记的对象，也就是非活动对象
回收的阶段。下面我们带着问题去看 既然是标记清除算法那么是如何标记的呢
1.是如何标记的其中涉及的问题
（1）标记过程中如何确定引用的对象是都为垃圾对象？
可达性分析
（2）在过程中使用的是什么数据结构？
一GCRoot为起点以引用为指向一被引用为执行的有向图
（3）标记的是什么地方
在对象的头部有一个判断是否被标记的变量
（4）标记过程搜索中是如何遍历的
使用深度优先遍历 ，他比广度优先遍历需要存储对象更少
深度搜索图

image.png

广度搜索图

image.png
标记说完了那说一下如何清除的吧
在回收过程中会有一个空闲的链表来保存回收分块，在清除的时候会遍历整个堆 找到头部没有被标记的分块，是它指向空闲的链表。

为什么会有空闲链表 空闲链表的作用是什么？
1.在垃圾回收记录垃圾回收的分块大小
2.在需要内存是对内存进行重新分配

空闲链表的重新分配策略有什么？
First -fit：最初发现大于等于size 的分块时就会立即返回该分块
Best -fit：遍历空闲链表，返回大于等于 size 的最小分块
Worst -fit：即找出空闲链表中最大的分块，将其分割成 mutator 申请的大小和分割后剩余的大小，目的是将分割后剩余的分块最大化。但因为 Worst -fit 很容易生成大量小的分块，所以不推荐大家使用此方法

说了那么多标记清除算法他有什么优缺点呢？
优点
1、实现简单
2、不移动对象，与保守式GC算法兼容。在保守式GC算法中对象是不能移动的。
算法的缺点：
1、内存碎片化。因为对象不移动，所以导致块是不连续的，容易出现空闲内存很多，但分配大对象时找不到合适的块。
2、分配速度慢。即使是First-fit，但其操作仍是一个O(n)的操作，最坏情况是每次都要遍历到最后。同时因为碎片化，大对象的分配效率会更慢。
有什么可以优化的地方吗？
（1）优化分配速度：使用多条空闲链表
利用不同分块大小的分块分别放在不同的大小里面，为了防止分块过多设置一个阈值，超过某个阈值的分块全部放到这个分块里面，这样在分配的时候就不用遍历整个空闲链表去取了，这直接到所需要的的分块大小对应的分块链表中去取就行了，这个可以优化分配速度.
（2）内存碎片化优化：使用BiBOP，就是将大小相近的对象整理成固定大小的块进行管理的做法，我们使用这个方法把堆分割成固定大小的块，让每个块只能配置同样大小的对象，

图解 image.png
（3）使用位图标记
我们单独做一个位图表格来存储，在当前堆里面当前区块是否被标记的信息，是清除是只需要遍历当前位图表格就行了