垃圾回收 -- 复制算法

刺骨的言语ヽ痛彻心扉 2022-01-08 02:09 246阅读 0赞

GC 复制算法

GC 复制算法是利用From 空间进行分配的。当From 空间被完全占满时，GC 会将活动  
对象全部复制到To 空间。当复制完成后，该算法会把From 空间和To 空间互换，GC 也就结  
束了。From 空间和To 空间大小必须一致。这是为了保证能把From 空间中的所有活动对象  
都收纳到To 空间里

copying(){
    	$free = $to_start
    	for(r : $roots)
    		*r = copy(*r)
    	swap($from_start, $to_start)
    }

在GC 结束时，原空间的对象会作为垃圾被回收。因此，由根指向原空间对象的指针也会被重写成指向返回值的新对象的指针

在复制过程中，需要识别已经被复制的对象，这个是通过标识 obj.tag = COPIED 实现， 当GC扫描到该对象时，发现已经被复制，就会跳过该对象， 这样有多个指向该obj的指针也就不会被复制多次

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbXByZWw_size_16_color_FFFFFF_t_70]

copy() 函数会返回指向新空间的指针，所以会把指向子对象的引用重写为这个新  
的指针。这样一来，从To 空间指向From 空间的指针就全部指向To 空间

注意GC 完成后只有1 个分块的内存空间。在每次分配时，只要把所申请大小的内存空间从这个分块中分割出来给mutator 就行了. 意思就是GC复制算法每次都是从空闲的块起始位置开始分配的，即使之前分配的对象已经不再被使用，失效了， mutator分配内存的时候也会从上次内存分配的结束位置开始进行分配，如果发现内存不足， 那么就会启动回收机制，进行从from空间到to空间的整理

在复制算法搜索活动对象的时候，使用的深度优先搜索

特点：

1.  优秀的吞吐量

GC 标记- 清除算法消耗的吞吐量是搜索活动对象（标记阶段）所花费的时间和搜索整体堆（清除阶段）所花费的时间之和，GC 复制算法只搜索并复制活动对象，跟一般的GC 标记- 清除算法相比，它能在较短时间内完成GC

1.  可实现高速分配

GC 复制算法不使用空闲链表。这是因为分块是一个连续的内存空间， 只要这个分块大小不小于所申请的大小，那么移动$free 指针就可以进行分配

1.  不会发生碎片化

因为每次分配都是从堆得一端依次开始进行分配，不会存在中间分块的内存碎片

1.  与缓存兼容

GC 复制算法中有引用关系的对象会被安排在堆里离彼此较近的位置

1.  堆得使用率低下

因为需要将堆分配为两块大小一样的内存空间， 只有一块空间会在同一时间被使用

1.  不兼容保守式GC 算法 因为需要移动对象
2.  递归调用函数

复制某个对象时要递归复制它的子对象， 比起这种递归算法，迭代算  
法更能高速地执行

改进：

1.  Cheney 的GC复制算法

迭代地进行复制， 使用的是广度优先搜索

Cheney 的GC 复制算法中使用的是forwarding 指针，而不是之前obj.tag设置为

COPIED进行判断，该对象是否已经被复制。 原因是，如果对象已经被复制，那么它的子对象指向的是to空间的地址，而如果还没有被复制，指向的是原来的from空间地址

广度优先搜索需要先入先出（FIFO）结构的队列，即把该搜索的对象保持在队列中，一边取出一边进行搜索。

可以抑制调用函数的额外负担和栈的消耗， 但是由于使用了广度优先算法，因此对于缓存的使用优势没有兼容

1.  近似深度优先搜索方法

方法是将堆分割成一个个页面的数组， 然后将相邻引用的对象放入对应的页面中

这样就可以将对象缓存在相邻位置

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbXByZWw_size_16_color_FFFFFF_t_70 1]

算法采用的不是完整的广度优先搜索，而是在每个页面上分别进行广度优先搜索。

1.  多空间复制算法

GC 复制算法最大的缺点是只能利用半个堆

如果将堆分成10 份，其中需要拿出2 块空间分别作为From 空间和To 空间来执行GC 复制算法。必须空出1 块空间来当To 空间，这样浪费率差不多就是1/10了

对于剩余空间的管理，可以使用其他方法进行， 比如标记清除算法

多空间复制算法简短得说就是把堆N 等分，对其中2 块空间执行GC 复制算法，对剩下的（N-2）块空间执行GC 标记- 清除算法，也就是把这2 种算法组合起来

过程：

multi_space_copying(){
    	$free = $heap[$to_space_index]
    	for(r : $roots)
    		*r = mark_or_copy(*r)
    	for(index : 0..(N-1))
    		if(is_copying_index(index) == FALSE)
    			sweep_block(index)
    	$to_space_index = $from_space_index
    	$from_space_index = ($from_space_index + 1) % N
    }

这里将堆N 等分，开头分别是$heap\[0\], $heap\[1\], …,  h e a p \[ N − 1 \] 。 这 时 heap\[N-1\]。这时 heap\[N−1\]。这时heap\[ t o s p a c e i n d e x \] 表 示 的 是 T o 空 间 。 每 次 执 行 G C 时 ， T o 空 间 都 会 像 to\_space\_index\] 表示的是To 空间。每次执行GC 时，To 空间都会像 tospaceindex\]表示的是To空间。每次执行GC时，To空间都会像heap\[0\],  h e a p \[ 1 \] , … , heap\[1\], …, heap\[1\],…,heap\[N-1\],  h e a p \[ 0 \] 这 样 进 行 替 换 。 F r o m 空 间 在 T o 空 间 的 右 边 ， 也 就 是 heap\[0\] 这样进行替换。From 空间在To 空间的右边，也就是 heap\[0\]这样进行替换。From空间在To空间的右边，也就是heap\[1\],$heap\[2\], …, $heap\[N-2\],  h e a p \[ N − 1 \] 。 在 第 3 行 和 第 4 行 给 活 动 对 象 打 上 标 记 。 很 像 G C 标 记 − 清 除 算 法 中 的 标 记 阶 段 。 不 过 有 一 点 不 同 ， 就 是 该 算 法 考 虑 到 了 对 象 在 F r o m 空 间 （ heap\[N-1\]。 在第3 行和第4 行给活动对象打上标记。很像GC 标记- 清除算法中的标记阶段。 不过有一点不同，就是该算法考虑到了对象在From 空间（ heap\[N−1\]。在第3行和第4行给活动对象打上标记。很像GC标记−清除算法中的标记阶段。不过有一点不同，就是该算法考虑到了对象在From空间（heap\[$from\_space\_index\]）里的情况。当参数obj 在From 空间里时，mark\_or\_copy() 函数会将其复制到To空间，返回其复制完毕的对象。如果obj 在除From 空间以外的其他地方，mark\_or\_copy()函数会像通常的标记函数一样给对象打上标记，递归标记或者复制它的子对象。  
第6 行到第8 行是清除阶段。这里跟以往的GC 标记- 清除算法基本一致，位于From空间和To 空间以外的分块且没被标记的对象会被连接到空闲链表。  
最后将To 空间和From 空间往右移动一个位置，GC 结束

示意图：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbXByZWw_size_16_color_FFFFFF_t_70 2]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbXByZWw_size_16_color_FFFFFF_t_70 3]

多空间复制算法没有将堆二等分，而是分割成了更多块空间，从而更有效地利用了堆。而多空间复制算法仅仅需要空出一个分块，不能使用的只有1/N 个

对于剩下的（N-2）块空间执行的是GC标记- 清除算法。就出现了GC 标记- 清除算法固有的问题：分配耗费时间、分块碎片化

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbXByZWw_size_16_color_FFFFFF_t_70]: /images/20211220/da683df8c6b34ab8a7dbd611e199330c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbXByZWw_size_16_color_FFFFFF_t_70 1]: /images/20211220/8aed458ad4b549e29bd0aeea57ddc130.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbXByZWw_size_16_color_FFFFFF_t_70 2]: /images/20211220/f46881fe1490487d9c38595bf4d6bef2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NvbXByZWw_size_16_color_FFFFFF_t_70 3]: /images/20211220/2cb4bf0b31664fd1a84bb3e5a70a1b9d.png