垃圾回收--标记清除算法

缺乏、安全感 2021-12-23 00:17 362阅读 0赞

标记-清除算法

第一个GC算法

标记清除算法有两个阶段： 标记阶段和清除阶段 。标记是将活动对象做标志， 也就是识别非活动对象。清除就是非活动对象回收的过程

标记时候，会去标志所有的对象，因此，耗时与对象的总数是成正比的

因为会遍历所有对象，一般会用到两种搜索算法：

1.  深度优先搜索
2.  广度优先搜索

深度优先比广度优先搜索更能压低内存使用量， 二是可以将有关系的对象，放入到邻近的位置上

1.  标记：
    
    通过根 递归地标记能访问到的对象， 这样根及其子对象都会被扫描到，并被标识

mark(obj){
     if(obj.mark == FALSE)
       obj.mark = TRUE
       for(child : children(obj))
          mark(*child)
    }

1.  清除
    
    在清除阶段中，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
        }
        #heap_start堆开始位置 heap_end 堆尾   free_list 空闲链表
2.  分配空间
    
    当mutator 申请分块时， 搜索空闲链表并寻找大小合适的分块，清除阶段已经把垃圾对象连接到空闲链表.
3.  合并
    
    在内存分配及回收这些过程中，堆内存中可能产生大量的碎片，有些是连续的内存空间，可以整合，合并为更大的空闲空间

标记清除法的优缺点：

1.  实现简单
2.  保守式算法兼容（对象位置不会发生变化）， 标志清除算法经常跟其他算法一起使用
3.  碎片化 在使用分配回收这些过程中，进行内存分块， 很容易产生内存碎片
4.  分配算法 分配最差的情况，需要遍历空闲链表的最后
5.  与写时复制不兼容

优化改进：

1.  多个空闲链表
    
    一个空闲链表，对大的分块和小的分块进行同样的处理。每次分配的时候都要遍历一次空闲链表来寻找合适大小的分块。如果利用分块大小不同的空闲链表，只要按照mutator 所申请的分块大小选择合适的空闲链表，就能在短时间内找到符合条件的分块了， 但是如果为每个大小分配一个链表，明显是不合适的，因此一般维护大小块在一定范围的链表
2.  bibop

BiBOP 是Big Bag Of Pages 的缩写。将大小相近的对象整理成固定大小的块进行管理， 目的是消除碎片化，但是并不能完全消除碎片化

1.  位图标记

在标记清除算法中标记的位是在到各个对象的头中， 这与写时复制技术不兼容。

收集各个对象的标志位并表格化，不跟对象一起管理，散列表和树形结构等实现这个表格

这就与写时复制技术兼容，并且清除操作更加高效，只需要找到表格中对应对象的标志进行操作即可， 但是需要维护这个表格，对象位置是需要进行计算的， 如果堆有多个，对象地址不连续的情况下，我们无法用单纯的位运算求出标志位的位置。

1.  延迟清除法

标记清除算法，清除操作所花费的时间是与堆大小成正比的， 堆越大花费的时间越长。

延迟清除法（Lazy Sweep）是缩减因清除操作而导致的mutator 最大暂停时间的方法， 延迟清除法不是一下遍历整个堆，它只在分配时执行必要的遍历，所以可以压缩因清除操作而导致的mutator 的暂停时间， 但是也不能够完全消除最坏的情况。