GC：标记清除算法

￡神魔★判官ぃ 2022-03-27 11:52 308阅读 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