垃圾回收算法总结

最近研读了《垃圾回收的算法与实现》这本书, 对来垃圾回收(GC)的来龙去脉及理论和实践有了一个概括性,深入性的了解,这里分多篇进行总结。首先本文先对GC的理论来一个总览性的回顾.

什么是垃圾回收

我们知道一台服务器的内存是有限的,而程序的运行需要占用内存空间,一个程序内部可能有些内存空间使用后不再使用,这部分不再使用的内从空间就被视为垃圾。而GC就是要

  1. 找到内存空间里的垃圾
  2. 回收垃圾,让程序员能够再次利用这部分空间

如果没有GC的情况下需要程序员自己手动管理内存,例如C/C++等程序。这个过程将会非常麻烦,如果管理不当就会照成内存泄露引起系统崩溃,引发各种恶性bug和安全问题。有了GC就会省去很大一部分精力,降低了开发的难度。

垃圾回收基本概念

要深入了解垃圾回收的理论知识,下面这些关键件信息比必要掌握:

  • 对象/头/域: 这里对象是由头(heder)和域(field)构成的。头是指保持对象本身信息的部分,主要包括对象的大小对象的种类;域是对象使用者可以访问的部分,域的数据类型主要分为指针和非指针两种。
  • 指针: GC根据对象的指针指向去搜寻其他对象,对于非指针不进行任何操作。
  • mutator: 程序运行过程中关系的改变,主要包括生成对象更新指针等操作。
  • 堆: 用于动态存放对象的内存空间。当mutator申请存放对象时,所需的内从空间就是从这个堆中被分配给mutator的。
  • 活动对象/非活动对象: 内存空间中可以通过mutator引用的对象是”活动对象”, 不能通过程序引用的称为”非活动对象”。非活动对象无法重新被引用,所以就是”垃圾”。
  • 分配: 内存空间中分配(allocatio)对象。当mutator需要新对象时,就会向分配器(allocator)申请一个大小合适的空间。
  • 分块: 未利用对象而事先准备的空间。初始状态堆就是一个大分块,根据mutator的需求而分割成合适的大小。
  • 根: 跟是指向对象的指针的起点,通过mutator可以直接调用的调用栈(call stack),寄存器和全局变量都是根。但是调用栈和寄存器中的值是不是指针,需要再做判断。
  • 评价标准: GC算法的性能评价标准主要有
    1. 吞吐量: 单位时间内的处理能力。
    2. 最大暂停时间: 因执行GC和停止mutator的最长时间。
    3. 堆使用效率
    4. 访问的局部性: 局部性原理,数据离得越近越好处理。

垃圾回收算法总览

首先先上一张垃圾回收算法的总概括图:
垃圾回收算法总览
上面列举和好多算法及对应的细节。其实GC最基本的思想就是三种算法(GC标记-清除法, 引用计数法, GC复制算法), 其他算法都算是这几个算法的延伸和组合。