垃圾回收的算法与实现 笔记 Part1

• 基本概念
• 底层算法
• TODO状态

基本概念

对象/头/域

• 对象
  • OOP – 具有属性和行为的事物
  • GC – 通过应用程序利用的数据的集合
  • GC根据情况将配置好的对象进行移动或销毁，因此对象是GC的基本单位
  • 对象一般由 头 (header) 和 域 (field) 组成
  • 一个对象存在至少1个域
• 头 (header)
  • 对象的大小
  • 对象的种类
• 域 (field)
  • 指针 – 内存空间中某块区域的值
  • 非指针 – 直接使用值本身

指针

• GC根据指针搜索对象，GC对非指针对象不进行操作
• 大多数语言中，指针都默认指向对象的首地址 （详情见笔记数据结构 Data Structure | swzxsyh）

mutator

• GC在mutator这个程序内工作
• 实际会进行的操作
  • 生成对象
  • 更新指针

堆

• 执行程序时存放对象的内存空间。mutator会从这个堆中申请内存空间
• 当堆占满时，就会启动GC进行可用空间分配。如果不能分配足够空间，需要扩大堆

活动对象/非活动对象

• 能通过mutator引用的对象称为 活动对象 （GC时会保留）
• 在堆中不能通过mutator引用的是 非活动对象（即Garbage，GC时销毁，并释放空间）

分配(allocation)

• 即在内存空间中分配对象
• 当mutator需要新对象时，会向分配器 (allocator) 申请一个合适的空间，分配器寻找空间并返回
• 当空间被活动对象占满时
  • 销毁所有计算结果并销毁
  • 扩大堆（推荐）

分块(chunk)

• 为利用对象而事先准备出来的空间，初始状态下被一个大分块占据
• 根据mutator进行分割作为活动对象使用，非活动后被回收再成为 分块

根

• 指向对象的指针的 起点 部分
• 可以直接或间接从全局变量中引用的对象视为 活动对象
• 可以通过mutator直接引用 调用栈(call stack) 和 寄存器。即 调用栈、寄存器、全局变量空间都是根

评价标准

• 吞吐量
  • 单位时间内的处理能力（处理每一块非活动对象时间总和）
• 最大暂停时间
  • GC过程中会令mutator暂停，最大暂停时即 因GC暂停mutator的最长时间
• 堆使用效率 – 头大小/堆的用法 影响
  • 堆中存放的信息越多，GC效率越高，吞吐量随之改善。为了执行GC，需要把在头中存放的信息控制在最小限度
  • 根据堆的用法，使用效率也会出现巨大差异
  • 可用的堆越大，GC越快。相反越想有效利用有限的堆，GC时间越长
• 访问的局部性
  • 具有引用关系的对象之间通常很可能存在连续访问的情况，称为访问的局限性
  • 把具有引用关系的对象放在相近的位置，能提高利用率，提高mutator效率

基础算法

标记-清除算法

概念

标记阶段

• 把遍历所有对象并对活动对象打上标记
• 搜索对象算法DFS，BFS，推荐BFS，内存占用更小

清除阶段

• 清除没有标记的对象，即回收非活动对象

分配

合并

优点

缺点

引用计数法

复制算法

压缩算法

Source

https://www.amazon.co.jp/ガベージコレクションのアルゴリズムと実装-中村-成洋/dp/4798025623