GC:标记清除算法 £神魔★判官ぃ 2022-03-27 11:52 311阅读 0赞 > 本文主要介绍标准的标记-清除算法的过程,优缺点,以及做的一些优化过程。 ### GC Mark-Sweep Algorithm ### * 1.GC标记清除算法 * * 1.1 标记阶段 * 1.2 标记阶段算法 * 1.3 清除阶段算法 * 1.4 已回收空闲内存空间再分配 * 1.5 合并(内存碎片整理) * 2.GC标记清除算法的优缺点 * 3. GC标记清除算法的优化 * * 3.1 multi-size空闲链表优化分配速度 * 3.2 延迟清理 # 1.GC标记清除算法 # 标记清除算法主要分为两个阶段:标记、清除。 标记阶段:将所有的活动对象做上标记; 清除阶段:把内存里面没有打上标记的对象回收掉。 通过这两个阶段,就可以把不需要的空间重复利用。 下面详细介绍一下标记阶段和清除阶段是怎么做的。 假设现在执行GC前有一块分块堆状态如下图: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70] ## 1.1 标记阶段 ## 标记阶段的伪代码如下: mark_phase(){ for(r : $roots) { mark(*r) } } collector从遍历所有的根节点出发,标记所有的活动对象。然后通过调用递归函数mark()函数,mark函数伪代码如下: mark(obj){ if(obj.mark == FALSE){ //对象没有被标记 //设置对象是活动对象 obj.mark = TRUE for(child : children(obj)){ // 递归对象的子节点 mark(*child) } } 第二行判断 `if(obj.mark == FALSE)` 主要是针对循环引用的场景,避免循环引用时候会循环调用mark函数,避免重复进行标记处理。 这个标记obj.mark 肯定是需要保存到对象的头里面。 标记完所有活动对象后,标记阶段就结束了。标记阶段结束后堆的状态如下图: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 1] 由上面标记阶段可知,标记阶段会遍历堆中所有对象,所以标记阶段耗时是与“活动对象的总数”成正比的。 ## 1.2 标记阶段算法 ## 前面已经说了,标记阶段需要遍历所有的对象,那么怎么遍历呢?常见的是基于深度优先遍历搜索或则是广度优先遍历搜索。 针对这两种场景来说,一般深度优先遍历会比广度优先遍历搜索使用的内存量会更少,所以一般通过深度优先去做搜索。 ## 1.3 清除阶段算法 ## 清除阶段,collector也会遍历整个堆,然后回收释放所有没有打标的内存对象。 伪代码如下: sweep_phase(){ sweeping = $heap_start //起始指针 while(sweeping < $heap_end){ if(sweeping.mark == TRUE){ sweeping.mark = FALSE } else{ sweeping.next = $free_list $free_list = sweeping } sweeping += sweeping.size } } } 在此出现了叫作 size 的域,这是存储对象大小(字节数)的域。跟 mark 域一样,我们事先在各对象的头中定义它们。 清除阶段,通过变量 sweeping 遍历堆,具体来说就是从堆首地址 $heap\_start 开始,按顺序一个个遍历对象的标志位。 遍历回收过程中,我们用free\_list空闲链表来链接所有被回收的空闲内存块。 经过清除阶段之后内存堆的状态如下图: ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 2] 清除阶段,程序会遍历所有堆,进行垃圾回收所花费时间与堆大小成正比。堆越大,清除阶段所花费的时间就会越长。 ## 1.4 已回收空闲内存空间再分配 ## 当我们程序需要申请新的内存空间时,GC怎么做分配才能利用空闲列表呢? 前面我们在清除阶段已经把垃圾对象连接到空闲链表了。搜索空闲链表并寻找 大小合适的分块,这项操作就叫作分配。执行分配的函数 new\_obj() 伪代码如下: new_obj(size){ chunk = pickup_chunk(size, $free_list) if(chunk != NULL) return chunk else allocation_fail() } 上面的逻辑很简单,主要依赖于pickup\_chunk函数从空闲链表取出合适的内存空间。 pickup\_chunk() 函数用于遍历 $free\_list,寻找大于等于 size 的分块。它 不光会返回和 size 大小相同的分块,还会返回比 size 大的分块。如果它找到和 size 大小 相同的分块,则会直接返回该分块;如果它找到比 size 大的分块,则会将其分割成 size 大 小的分块和去掉 size 后剩余大小的分块,并把剩余的分块返回空闲链表。 如果此函数没有找到合适的分块,则会返回 NULL。返回 NULL 时分配是不会进行的。针对这种情况,有专门的allocation\_fail() 函数处理。 这里从free\_list搜索空闲合适内存时候,会有一些策略的不同优化。主要有First -fit、Best -fit、Worst -fit这些策略,具体的过程也比较简单,感兴趣的可以自行Google。 ## 1.5 合并(内存碎片整理) ## 经过一定次数的分配之后,肯定会产生很多的内存碎片。但如果它们是连续的, 我们就能把所有的小分块连在一起形成一个大分块。这种“连接连续分块”的操作就叫作合 并(coalescing),合并是在清除阶段进行的。具体的过程这里就不说明了。 # 2.GC标记清除算法的优缺点 # 优点: 1)首先就是简单,整个算法过程看上去还是比较easy的。 缺点: 1)很明显,这种方式会造成大量的内存碎片,对碎片化的合并也会大大增加GC的负担。 2)分配速度:遍历空闲列表来分配导致的效率肯定是不高的。 # 3. GC标记清除算法的优化 # 针对标记-清楚算法的缺点也会有一些优化。 ## 3.1 multi-size空闲链表优化分配速度 ## 前面讲了分配操作时候需要遍历空闲链表直到找到合适的内存大小,时间复杂度很明显的O(n)。 我们有一种方法,就是利用分块大小不同的空闲链表,即创建只连接大分块的空闲链表和只连接小分块的空闲链表。这样一来,只要按照 程序 所申请的分块大小选择空闲链表,就能在短时间内找到符合条件的分块了。 我们用一个空闲链表数组保存不同大小的空闲链表首地址。主要策略是: 1)针对小字节的碎片,一个size一个空闲列表; 2)针对大size的块,单独一个列表。 ## 3.2 延迟清理 ## 我们知道清理阶段耗费的时间与堆的大小有关系,为了降低STW的时间,标记阶段之后并不做及时的清理,而是在分配时候做检测然后清理,这样就可以减少STW的时间。 [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70]: /images/20220327/2d1a7605ef6c4ffca9582c4aad65cf5f.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 1]: /images/20220327/0988690287324a0e9151383f36915cbb.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTA4NTMyNjE_size_16_color_FFFFFF_t_70 2]: /images/20220327/8b9801c1dc72431a843d9135211ca164.png
还没有评论,来说两句吧...