课程主页：

https://www.edx.org/course/compilers

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

备注：

图片均来自于课件。

这次回顾垃圾回收。

自动内存管理

  • 在现代编程中，存储管理仍然是一个难题
  • C和C++程序有很多存储错误
    • 忘记释放未使用的内存
    • 取消引用悬空指针（dereferencing a dangling pointer）
    • 意外覆盖部分数据结构
    • 等等…
  • 很难找到存储错误
    • 但错误可能会导致明显的影响。

历史

  • 这是一个老问题：
    • 自1950年代开始对LISP进行研究。
  • 有众所周知的全自动内存管理技术；
  • 随着Java的流行而成为主流。

内存管理动机

  • 创建对象时，将自动分配未使用的空间。

    • 在Cool中，新的对象由new创建。

  • 一段时间后，不再有未使用的空间。

  • 一些空间将被不再使用的对象占据。

    • 此空间可以释放以供以后重用。

  • 我们如何知道某个对象将“不再使用”？

  • 观察：程序只能使用可以找到的对象：

    let x : A <- new A in { x <- y; ... }

    赋值后，y无法被找到。

  • 当且仅当满足以下条件时，对象x才可达：

    • 一个寄存器包含指向x的指针；
    • 另一个可达对象y包含一个指向x的指针。

  • 您可以通过从寄存器开始并跟随所有指针来找到所有可访问的对象。

  • 无法到达的对象永远不会被使用

    • 这样的对象是垃圾（garbage）

例子

  • 考虑程序

    x <- new A;
y <- new B;
x <- y;
if alwaysTrue() then x <- new A else x.foo() fi

    y是dead。

  • 在x <- y之后（假设y在此处死亡）

    • 第一个对象A不可到达；
    • 对象B可到达（通过x）；
    • 因此，B不是垃圾也不会被回收
      • 但永远不会使用对象B，根据判断分支
    • 可达是一种近似。

Cool中的内存管理

Coolc使用

  • 累加器
    • 它指向一个对象；
    • 并且此对象可能指向其他对象，等等。

  • 和堆栈指针

    • 每个堆栈帧都包含指针

      • 例如方法参数

    • 每个堆栈帧还包含非指针

      • 例如返回地址

    • 如果我们知道栈帧的布局，则可以在其中找到指针

acc和SP

  • 在coolc中，我们开始从acc和堆栈进行跟踪
    • 这些是roots
  • 注释B和D无法通过acc和堆栈访问
    • 因此，我们可以复用它们的存储

小结

  • 每个垃圾回收方案都有以下步骤
    • 1.根据需要为新对象分配空间
    • 2.当空间用完时：
      • a）计算可能再次使用的对象（通常是通过跟踪一组“root”寄存器可访问的对象）；
      • b）释放（a）中找不到的对象使用的空间。
  • 一些策略会在空间实际用完之前执行垃圾回收

标记和清除

  • 当内存用完时，GC执行两个阶段
    • 标记阶段：跟踪可到达的对象；
    • 清除阶段：收集垃圾对象。
  • 每个对象都有一个额外的位：标记位
    • 保留用于内存管理；
    • 最初的标记位为0；
    • 在标记阶段将可达对象的标记为设置为1。

标记阶段伪代码

  • $\mathrm{//\text{mark phase}}$
  • $\text{let todo = {all roots}}$
  • $\mathrm{while\ todo\neq \varnothing\ do}$
    • $\mathrm{pick\ v \in todo}$
    • $\mathrm{todo \to todo - \{ v \} }$
    • $\text{if mark(v) = 0 then}\quad \text{// v is unmarked yet}$
      • $\mathrm{mark(v)\leftarrow 1}$
      • $\mathrm{let\ v_1,…,v_n\ be\ the\ pointers\ contained\ in\ v}$
      • $\mathrm{todo \leftarrow todo \cup \{v_1,…,v_n\}} $
    • $\mathrm{fi}$
  • $\mathrm{od}$

扫描阶段

  • 扫描阶段扫描堆以查找标记位为0的对象
    • 在标记阶段未访问这些对象；
    • 所以他们是垃圾。
  • 任何此类对象均已添加到free列表中；
  • 标记位为1的对象将其标记位重置为0。

伪代码

  • $\text{// sweep phase}$
  • $\text{// sizeof(p) is the size of block starting at p}$
  • $\mathrm{p\leftarrow bottom\ of\ heap}$
  • $\text{while p < top of heap do}$
    • $\text{if mark(p) = 1 then}$
      • $\mathrm{mark(p) \leftarrow 0}$
    • $\text{else}$
      • $\text{add block p…(p+sizeof(p)-1) to freelist}$
    • $ \text{fi}$
    • $\mathrm {p\leftarrow p + sizeof(p)}$
  • $\text{od}$

例子

习题

选择第三项。

小结

  • 虽然从概念上讲很简单，但是该算法具有许多棘手的细节

    • 这是GC算法的典型特点。

  • 标记阶段存在严重问题

    • 当我们空间不足时调用该函数；
    • 但是它需要空间来构造todo list；
    • todo list的大小不受限制，因此我们无法为它预留空间。

  • todo list用作辅助数据结构以执行可达性分析

  • 有一个技巧可以将辅助数据存储在对象本身中

    • 指针反转：反转指针以指向其父对象

  • 类似的，free列表存储在空闲对象本身中

  • 从free列表中分配了新对象的空间

    • 选择一个足够大的块
    • 从中分配了必要大小的区域
    • 剩下的被放回free列表中

  • 标记和清除会碎片化内存

    • 合并可能的空闲块

  • 优点：GC期间不移动对象

    • 无需更新指向对象的指针
    • 适用于C和C ++等语言

停止和复制

  • 内存分为两个区域

    • 旧空间：用于分配

    • 新空间：用作GC的保留空间

  • 堆指针指向旧空间中的下一个空闲字

  • 分配只会使堆指针前进

流程

  • CG在旧空间已满时开始
  • 将所有可到达的对象从旧空间复制到新空间
    • 留下垃圾
    • 复制阶段之后，新空间使用的空间比垃圾收集之前的旧空间要少
  • 复制后，旧空间和新空间的作用相反，程序恢复

例子

操作细节

  • 我们需要找到所有到达的对象，就像标记和清除
  • 找到可到达的对象后，将其复制到新空间中
    • 而且我们必须修复所有指向它的指针！
  • 当我们复制一个对象时，我们在旧副本中存储一个指向新副本的前向指针
    • 当我们稍后到达一个带有前向指针的对象时，我们知道它已经被复制了

问题

  • 我们仍然存在如何在不使用额外空间的情况下实现遍历的问题
  • 以下技巧解决了该问题：
    • 将新空间划分为三个连续的区域

  • 第一部分为指针字段已跟踪的被复制对象
  • 第二部分指针字段尚未跟踪的被复制对象

例子

  • 步骤1：复制由根指向的对象并设置前向指针

  • 步骤2：跟随下一个未扫描对象（A）中的指针
    • 复制指向的对象（本例中为C）
    • 修正A中指针
    • 设置前向指针

  • 跟随下一个未扫描对象中的指针（C）
    • 复制指向的对象（在这种情况下为F）

  • 跟随下一个未扫描对象（OF）中的指针
    • 被指向的对象（A）已被复制。 将指针设置为与前向指针相同

  • 既然扫描赶上了alloc，我们就完成了
  • 交换空间的角色并恢复程序

代码
  • $\text{while scan <> alloc do}$
    • $\text{let O be the object at scan pointer}$
    • $\text{for each pointer p contained in O do}$
      • $\text{find O’ that p points to}$
      • $\text{if O’ is without a forwarding pointer}$
        • $\text{copy O’ to new space (update alloc pointer)}$
        • $\text{set 1st word of old O’ to point to the new copy}$
        • $\text{change p to point to the new copy of O’}$
      • $\text{else}$
        • $\text{set p in O equal to the forwarding pointer}$
      • $\text{f}$i
    • $\text{end for}$
    • $\text{increment scan pointer to the next object}$
  • $\text{od}$

习题

选择第三项。

问题

  • 与标记和清除一样，当我们扫描对象时，我们必须能够分辨出对象的大小
    • 并且我们还必须知道指针在对象内部的位置
  • 我们还必须复制堆栈指向的所有对象并更新堆栈中的指针
    • 这可能是一个昂贵的操作

小结

  • 通常认为停止和复制是最快的GC技术
  • 分配代价很低
    • 只需增加堆指针
    • 时间复杂度为$\text{O(|live objects|)}$
  • 回收代价相当低
    • 特别是在有很多垃圾的情况下
    • 仅触摸可到达的对象
    • 不接触垃圾
  • 但是某些语言不允许复制
    • C，C++

保守回收

  • 垃圾收集依赖于能够找到所有可到达的物体
    • 它需要找到一个对象中的所有指针
  • 在C或C++中，无法识别内存中对象的内容
    • 例如，两个内存字的序列可能是
      • 列表（包含数据和下一个字段）
      • 二叉树节点（具有左右字段）
    • 因此，我们无法判断所有指针在哪里
  • 但是可以保守一点：
    • 如果一段内存字看起来像一个指针，则它被认为是一个指针
      • 必须对齐
      • 它必须指向数据段中的有效地址
    • 跟踪所有此类指针，我们高估了可到达对象的集合
  • 但是我们仍然无法移动对象，因为我们无法更新指向它们的指针
    • 如果我们认为的指针实际上是一个帐号怎么办？

引用计数

  • 另一个方法不是等待内存耗尽，在没有指针指向该对象时尝试收集该对象
  • 在每个对象中存储指向该对象的指针数
    • 这是引用计数
  • 每个分配操作都会操纵引用计数

细节

  • new返回引用计数为1的对象

  • 令rc(x)为x的引用计数

  • 假设x，y指向对象o，p

  • 每个赋值$\mathrm{x\leftarrow y}$变成：

优缺点

  • 优点：
    • 易于实现
    • 增量收集垃圾，而不会在执行过程中出现大量的停顿
  • 缺点：
    • 无法收集循环结构
    • 在每次分配时处理引用计数非常慢

习题

$B$的引用计数变为$0$，所以free，从而$C$的引用计数也变为$0$，因此选择第三项。

小结

  • 自动内存管理可防止严重的存储错误
  • 但是减少了程序员的控制
    • 例如，内存中的数据布局
    • 例如，何时重新分配内存
  • 问题
    • 实时应用程序中有问题的暂停
    • 内存可能泄漏
  • 总体来说，垃圾依然收集很重要
  • 有更多高级垃圾收集算法：
    • 并发：在收集发生时允许程序运行
    • generational：不要在每个集合中扫描寿命长的对象
    • 实时：限制停顿的时间
    • 并行：几个收集器同时工作