垃圾回收(GC)算法介绍(1)——GC标记-清除算法

编程语言

在编程领域，垃圾回收(Garbage Collection)，简称GC(简便起见，以下都把垃圾回收用GC代替)。GC负责把堆上不用的内存进行回收，以便之后可以再次进行分配。回忆一下C中对内存申请，一般来说malloc和free需要成对地出现，malloc为对象申请内存空间，free负责释放申请的内存空间。但如果只有malloc但却不free，就会造成堆上的内存无法回收，造成内存泄漏。

一些高级的语言中都内置了GC，比如Python、Java、Ruby等。编程语言内置GC对程序员来说是一个不小的福利，我们再也不用惦记申请内存后要释放了，没有了内存泄漏，应用程序更安全了。

目前流行的GC算法主要有以下三种：

1.标记-清除算法

2.引用计数法

3.GC复制算法

还有一些其他的GC算法，但基本上是上面三种算法的衍生算法。

GC标记-清除算法(Mark-Sweep)概述

标记-清除算法可以说是最古老的一种GC算法了，于1960年由Lisp之父John McCarthy在其论文中发布。顾名思义，标记-清除算法分为两个阶段：

1.标记

2.清除

标记阶段，将堆上所有的活动对象打上标记。清除阶段，将堆上没有活动标记的非活动对象所占用的内存放入一个空闲链表(free_list)中。当需要在堆上申请新内存时，遍历空闲链表，找到一个合适大小的内存块进行分配。

上面的描述是非常抽象的，只说明了一个大概过程，有很多细节被隐藏了。一个大致的标记-清除过程用伪代码来表示就是：

1
2
3
4
mark_sweep(){
  mark_phase()
  sweep_phase()
}

在说明标记-清除算法的详细过程之前，先来看看堆上的活动对象和非活动对象。

一个堆就是一块连续的内存空间，一个堆有一个根，从这个根出发，可以直接访问到所有的顶层活动对象，这些顶层活动对象可能还会引用活动的子对象，这样一层一层引用下去，就能找到堆上所有的活动对象，就可以对它们实施标记。那些没有被标记的对象自然就是非活动对象了，它们已经无法被访问到，对程序来说已无用处，可以说是“垃圾”了。

来看一下mark_phase，假设堆的根为$root：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
mark_phase(){
  for(obj in $root){
    mark(obj)
  }
}

mark(obj){
  if(!obj.mark){
    obj.mark = True
    for(child in obj.children){
      mark(child)
    }
  }
}

在mark_phase中，遍历了堆的根上的所有顶层对象，mark函数对传入的对象递归地进行标记。

再看看’sweep_phase’，假设空闲链表为$free_list，堆的首地址为$heap_start，堆的尾地址为$heap_end：

1
2
3
4
5
6
7
8
9
10
11
12
sweep_phase(){
  sweeping = $heap_start
  while(sweeping < $heap_end){
    if(sweeping.mark){
      sweeping.mark = False
    } else {
      sweeping.next = $free_list
      $free_list = sweeping
    }
    sweeping += sweeping.size
  }
}

在sweep_phase中，使用sweeping遍历了整个堆，对所有已被标记的活动对象，把它们的mark置为False，在下一次mark_phase的时候会再次对这些活动对象设置标记。对于非活动对象，就将这些对象链接到空闲链表$free_list的头部。

整个标记-清除过程之后，堆上所有被回收的内存块就都被空闲链表收集了，它们以一个链表的形式存在。当需要在堆上申请内存时，就遍历空闲链表，找到合适的内存块就返回它，如果遍历后没有找到可以分配的块，就返回NULL。

空闲块分配策略

在之前的描述中，当需要在堆上申请内存时，遍历空闲链表，找到合适的内存块就返回它。这里的“合适”一词说的很模糊，一般来说有三种情况：

1.First-Fit: 在空闲链表中第一个找到的大小够用的内存块
2.Best-Fit: 在空闲链表中最适合所申请块大小的内存块（大小够用的最小内存块）
3.Worst-Fit: 在空闲链表中的最大的那个内存块

Worst-Fit由于要找到空闲链表中的最大内存块进行分配，势必要进行分割，有可能会造成很多内存碎片。在申请内存时，考虑到应该尽可能快地返回，一般还是会选择First-Fit。

空闲空间合并

在清除阶段，如果发现两个紧邻的空闲内存块时，会将它们合并形成一个更大的内存块，这样做有助于减少空闲内存的碎片化。

优点和缺点

标记-清除算法的优点是实现简单。缺点是容易形成内存碎片，在极端情况下会发生堆上空闲内存的总空间比所申请的空间size大，但没有哪个单个空闲块的大小够用的情况。还有一个问题就是分配速度，由于采用空闲链表，标记-清除算法的空闲内存时不连续的，每次分配都需要遍历空闲链表，因此它的分配速度是不稳定的。在后面会介绍几种缓解这些缺点的方法。

优化方案

对于标记-清除算法的缺点，有一些优化措施，这些优化措施在一定程度上可以缓解这些缺点带来的问题，但无法彻底根除。

1. 使用多个空闲链表

使用First-Fit时，随着时间的推移，堆上的空闲内存必然会出现很多碎片，造成申请内存时效率降低。由于应用程序很少会一下申请很大的内存空间，所以我们可以维护多个空闲链表，比如第一个空闲链表里都是2字节，第二个都是2字节，以此类推。但我们不可能枚举所有情况，所以可以类似这样处理：对100以下的各个数字，都建立相应的空闲链表，第一个空闲链表里都保存1字节的内存块，第二个都保存2字节的内存块，一直到第100个都保存100字节的内存块。大于100字节的内存块都保存在第101个空闲链表中。在申请内存时，查看相应大小的空闲链表中是否有可用内存块，有就分配，没有就从第101个内存块按照First-Fit去找。

2. 位图标记法

之前我们都是在对象头部进行标记，这样就会改变对象的状态。对于Linux等使用写时复制的系统来说，这会导致很多不必要的复制开销。我们知道一个堆对应一块连续的内存空间，于是很容易想到可以使用位图的方式来记录对象的标记状态。对于堆上每个字节，使用1位来表示，直观上来说，我们可以想象有一个位数组，数组长度等于堆上内存的字节数。在标记阶段遍历堆寻找活动对象时，在相应的位图位置上进行标记，在清除阶段，我们遍历堆上的对象，每遍历一个对象，就在位图上查询该对象是否是活动对象，如果不是活动对象，就把这块内存加入空闲链表。遍历完堆后，直接把整个位图的所有位设为0，此时空闲链表也收集了所有空闲内存。使用位图标记法有个好处，它不会导致写时复制的问题，另外需要注意的是，一个应用程序可能有多个堆，有几个堆就要有几个相对应的位图。

3. 延迟清除法

普通情况下，标记-清除算法在清除阶段的开销和堆的大小成正比，堆越大，应用程序因的最大暂停时间就越长。延迟清除算法把标记和清除操作延后到申请内存时。具体来说就是，在申请内存时，首先进行一次lazy_sweep，lazy_sweep会遍历堆进行标记和清除操作，遇到活动对象就标记，遇到非活动对象就清除，如果某次清除出来的内存空间大于或等于申请的size，直接返回这块内存。如果这次lazy_sweep没有找到合适的内存块，就会进行一次标记过程，然后再次调用lazy_sweep，如果还是找不到合适的内存块，说明在堆上申请内存失败了。这里需要注意的是，延迟清除法每次进行lazy_sweep时，都是从上一次lazy_sweep结束的地方开始，这和之前我们看到的每次都从堆的起始处开始有所不同。

编程语言