5.3 Storage Allocation and Garbage Collection - CloneableX/SICP-learning GitHub Wiki

在下一节我们将讲解如何通过寄存器机器实现 Scheme 求值器。为了简化下一章讨论的内容，需要提前为寄存器机器装载 列表结构存储器（list-structured memory），我们能够通过一些基础操作维护该存储器。存储器这种抽象概念极其有用，尤其是大家都将精力集中于 Scheme 解释器的控制机制时，不过它并不能完全反映现代计算机中关于数据操作的真实情况。要获得更加完备的 Lisp 系统运转细节，必须通过对列表结构如何与现代计算机存储相互兼容的研究得出。

在实现列表结构的话题上有两个待讨论的问题。首先是关于列表结构的表现形式问题，在只使用经典计算机存储的存储和寻址功能的基础上，如何才能表示 Lisp 序对中的盒子与指针结构。其次是关于将存储像计算过程一样管理的方法。Lisp 系统的操作紧密依赖连续创建新数据对象的能力。这些数据对象也包括由被解释器解释的 Lisp 程式创建的对象，以及解释器本身创建的结构，例如环境和参数列表。尽管常量数据对象的创建不会在拥有无限快速寻址存储的计算机中出现问题，但真实的计算机存储却大小有限。因此 Lisp 系统会提供 自动存储分配（automatic storage allocation） 的功能，通过该功能能够制造无限存储的假象。当某个数据对象不再被使用时，分配给它的存储会自动回收，然后该存储将用于构建新数据对象。有许多不同种类的技术都能实现自动存储分配功能。而我们在本节讨论的相关技术称为 垃圾回收（garbage collection）。

现代计算机的存储通常被看作一组房间，每个房间中都储存一段信息。并且每个房间都有独一无二的名称，这些名称被称为 地址（address） 或 位置（location）。通常存储系统都需要提供两个基础操作，一个操作能够从指定地址获取其中存储的数据，另一个操作能够向指定地址存入数据。可以向存储地址使用加法，通过这种方式能够访问连续的存储房间。通常来说，许多重要的数据操作都会将存储地址视为数据，这样便能够将存储地址保存起来，并在寄存器中操作。列表结构的呈现形式就是 地址算术运算（address arithmetic） 的一种应用。

在计算机存储器的建模上，我们需要使用另一种数据结构 向量（vector）。简而言之，向量是一种复合数据对象，其中的每个元素都能够通过整数索引访问，这种访问的时间消耗与索引无关。我们打算通过两个维护向量的 Scheme 基础程式描述存储操作。

• (vector-ref <vector> <n>) 将返回向量的第 n 个元素。
• (vector-set! <vector> <n> <value>) 将向量的第 n 个元素设置为指定值。

例如，如果 v 是一个向量，(vector-ref v 5) 将获取向量 v 中的第 5 个元素值，(vector-set! v 5 7) 会将向量 v 中的第 5 个元素值修改为 7。对于计算机存储器而言，这种存储访问可以通过存储地址算术运算结合基础存储地址实现，首先指定向量在存储中的首个地址下标，然后根据访问的元素进行偏移量计算即可。

现在我们可以使用向量实现基础的序对结构以供列表结构存储使用。首先我们将计算机存储想象为两个独立的向量，一个为 the-cars，另一个为 the-cdrs。接着我们可以通过下列方式实现列表结构，序对的指针实际是两个向量中的一个下标。序对的 car 值就是 the-cars 中对应索引元素中存储的数据，而序对的 cdr 值是 the-cdrs 中对应索引元素中存储的数据。同时，除了序对之外，我们还需要表示对象（例如数字和标识），并且需要通过某种方式区分不同种类的数据。实现上述功能的方式有很多，但它们本质上都是使用了 类型指针（typed pointer），这种指针即保留指针原有的功能，同时还包含数据类型的相关信息。类型指针中的数据类型信息使系统能够区分该指针是指向序对（指向序对的类型指针由「pair」数据类型信息和向量索引组成）还是其他类型的数据（指向其他类型数据的类型指针由对应的数据类型信息与该类型数据的具体呈现内容组成）。如果两个数据对象的指针相同，则两个数据对象相同（通过 eq? 判断）。下图展示了通过这种方法表示列表 ((1 2) 3 4)。我们通过前缀字符表示数据类型。因此，指向下标为 5 的序对指针应表示为 p5，空列表指针应表示为 e0，数字 4 的指针应表示为 n4。在盒子-指针图中，我们能够通过序对中向量索引的大小判断哪个元素存储着 car 值，哪个元素存储着 cdr 值。the-cars 和 the-cdrs 中的空白地址可能会用于存储其他的列表结构。

指向数字的指针由指向的数字类型和实际的数值构成，例如 n4。不过要表示占用固定数量空间的较大数字需要使用 bignum 数字类型，该数字的指针将指向一个存放该数字的存储列表。

使用类型指针表示标识时由标识的打印结果的字符序列构成。在这些字符串输入时会由 Lisp 读取器构建相应的字符序列。我们希望通过 eq? 判断两个标识是否相同时只要对比它们的指针即可，所以在读取器再次读入相同的字符串时会对该字符串应用相同的指针。要实现该功能，读取器需要维护一个表，该表通常称为 对象表（obarray），此表中包含了读取器读入的所有标识。当读取器发现一个标识字符串时，它将检查对象表以确认该字符串是否已经出现过。如果没有出现过，便用该字符串构建新的标识（其实是一个指向新字符序列的类型指针），并将该指针记录在对象表中。如果该字符串已经出现过，读取器会将对象表中储存的字符序列指针返回。这种通过唯一指针替换字符串的过程称为 互换（interning） 标识。

按照之前讨论的数据对象呈现形式，我们可以通过几个向量基础操作实现基础版列表寄存器机器。首先需要使用到两个寄存器 the-cars 和 thd-cdrs，分别指代存储向量，然后假定 vector-ref 和 vector-set! 已经存在。然后关于类型指针我们能够对索引部分进行算术运算（例如可以增加一个指针的下标，或者用一对指针索引一个向量，或者将两个数值相加）。

例如，我们可以制作一台支持下列指令的寄存器机器。

(assign <reg1> (op car) (reg <reg2>))
(assign <reg1> (op cdr) (reg <reg2>))

上述指令可以如下实现。

(assign <reg1> (op vector-ref) (reg the-cars) (reg <reg2>))
(assign <reg1> (op vector-ref) (reg the-cdrs) (reg <reg2>))

下列指令

(perform (op set-car!) (reg <reg1>) (reg <reg2>))
(perform (op set-cdr!) (reg <reg1>) (reg <reg2>))

可以如下实现。

(perform
 (op vector-set!) (reg the-cars) (reg <reg1>) (reg <reg2>))
(perform
 (op vector-set!) (reg the-cdrs) (reg <reg1>) (reg <reg2>))

cons 执行时会为其分配尚未使用的索引，并将 the-cars 和 the-cdrs 中对应的向量索引存储于 cons 中。此处我们需要一个特殊的寄存器 free，它将持有一个包含着下一个可用索引的序对指针，并且可以不断递增该指针的索引部分以查找尚未使用的存储地址。例如，下列指令。

(assign <reg1> (op cons) (reg <reg2>) (reg <reg3>))

可以通过下列一系列指令实现。

(perform
 (op vector-set!) (reg the-cars) (reg free) (reg <reg2>))
(perform
 (op vector-set!) (reg the-cdrs) (reg free) (reg <reg3>))
(assign <reg1> (reg free))
(assign free (op +) (reg free) (const 1))

对于 eq? 操作而言，(op eq?) (reg <reg1>) (reg <reg2>) 需要检测寄存器中的所有内容，而像 pair?、null?、symbol? 和 number? 只需要检测其中的类型部分即可。

虽然我们在之前已经实现了使用堆栈的寄存器机器，但因为堆栈使用的是列表实现，所以我们需要重新实现堆栈的操作。堆栈是一个能够存储数值的列表，同时由寄存器 the-stack 指向。因此 (save <reg>) 可实现为 (assign the-stack (op cons) (reg <reg>) (reg the-stack))。

与之类似，(restore <reg>) 需要实现为下列指令。

(assign <reg> (op car) (reg the-stack))
(assign the-stack (op cdr) (reg the-stack))

并且指令 (perform (op initialize-stack)) 应该被实现为 (assign the-stack (const ()))。

这些操作都是由之前提供的向量操作扩展而来。不过在常规计算机架构中，将堆栈实现为单独的向量更加合理。因为这样只需要通过增减向量索引便能实现堆栈的存储和取值操作。

前面的内容解决了列表结构实现的问题，接下来我们需要实现一个无限大小的存储器。在现实的计算机器我们始终都是通过空闲空间构建新序对。不过常规计算中使用的大量序对只是作为中间值使用。在这些序对数值被访问后它们将不再被需要，于是它们便成了 垃圾（garbage）。例如，进行 (accumulate + 0 (filter odd? (enumerate-interval 0 n))) 计算时会生成两个列表，一个列表是枚举结果，另一个列表收集过滤后的枚举结果。当累积计算完成时，这些列表都不再被需要，所以它们对应的存储空间都会被回收。如果我们定期进行垃圾回收，那么这些存储空间便能够以同样的频率被循环利用，通过这种手段便能制造无限存储空间的假象。

要实现序对的循环利用，我们必须能够判断哪些序对不再被使用（也就是说这些序对的内容不再影响后面的计算）。这种检测方法称为 垃圾回收（garbage collection）。垃圾回收的原理基于一个现象，任何时刻在 Lisp 解释器中，那些能够影响未来运算的对象必然是能够通过当前寄存器的指针指向，并不断通过 car 或 cdr 能够访问到的对象。如果某个存储单元不能通过这种方式访问到，则该存储单元便能够回收。

我们有许多方式能够执行垃圾回收。我们在本节要讲解的方式叫做 停止并拷贝（stop-and-copy）。在此概念中将存储空间分为两半，分别是「工作空间」和「空闲空间」。当通过 cons 构建序对时，该序对会被分配至工作空间。在工作空间被填满后，我们将执行垃圾回收将定位工作空间中所有有用的序对，并将它们拷贝互相连续地存储至空闲空间。有用的序对通过寄存器中的指针不断使用 car 或 cdr 访问确认。在我们没有拷贝垃圾对象时，空闲空间可以用于存储新序对。并且当工作空间中的所有有用序对都被拷贝到空闲空间后，工作空间中的所有内容都不再被需要。所以，如果此时我们交换工作空间和空闲空间的角色，整个流程依然可以顺畅运行。新的序对将被分配至新工作空间中（也就是原来的空闲空间）。当新工作空间被填满后，我们又会将有用的序对从工作空间拷贝到空闲空间（也就是原来的工作空间）。

现在需要用寄存器机器语言描述停止拷贝算法的细节。首先假设存在寄存器 root，它存储着一个指针，该指针指向一个能够指向所有可访问数据的结构。该结构会在开始垃圾回收前将所有寄存器的内容存储于 root 指向的预分配列表。其实这就是此时的工作空间，除此之外我们还需要一个空闲空间。当前的工作空间由 the-cars 和 the-cdrs 的寄存器中的基础地址向量构成，而空闲空间由 new-cars 和 new-cdrs 寄存器的基础地址向量构成。

当工作空间中的所有存储单元都被占用时垃圾回收将被触发，此时的 cons 操作在递增 free 指针时将溢出工作空间的向量。当垃圾回收完成时，root 指针将指向新的存储空间，并且通过 root 可以访问的所有对象都被转移至新的存储空间，free 指针将指向新存储空间的下一可用存储单元，并为新的序对分配该存储单元。并且工作空间的角色将和新的存储空间进行互换，新的序对将在新存储空间中构建，也就是 free 指针指向的存储单元，而之前的工作空间将作为下一轮垃圾回收的新存储空间存在。下图展示了存储空间在垃圾回收前后的变化。

垃圾回收过程的状态由 free 和 scan 指针控制。它们初始时都指向新存储空间的起始位置。垃圾回收算法以将 root 指向的序对重新分配至新存储空间的起始位置开始。然后开始拷贝序对，接着将 root 指针指向新存储空间，最后 free 指针递增。并且原有地址的序对会被标记为序对内容已经迁移。这些标记按如下步骤操作，在 car 部分 使用一个特殊标识表示该对象已经被迁移（这种对象被称为 破碎之心（broken heart）。在 cdr 部分存入一个地址，该地址指向对象被迁移的地方。

在重新定位 root 指针后，垃圾回收器将开始它的回收环节。在算法的每一步，scan 指针都指向一个序对，该序对已经被迁移至新的存储空间，不过它的 car 和 cdr 指针还指向旧存储空间的对象。这些对象每一个都需要重新分配存储空间，并且 scan 指针会不断递增。为了给该对象重新分配存储空间我们需要检测该对象是否已经迁移（可以通过破碎之心对象中的 car 部分的标识判断）。如果对象没有被迁移了，我们只需要将它拷贝到 free 指向的空间，并更新 free 指针，然后将该对象的原有存储地址更新为破碎之心对象，并将破碎之心对象的指针指向该对象的新地址（在本例中，我们扫描的是序对中的 car 指针）。如果对象已经被迁移，则指向此对象的地址会被更新为破碎之心对象的指针地址。最终，所有的可访问对象都将被迁移和扫描，而每次 scan 指针指向的位置超过 free 指针指向的位置时该运算过程将被停止。

我们可以将停止拷贝算法编写为一个寄存器机器指令序列。重新分配对象的基础步骤由 relocate-old-result-in-new 子程序完成。该子程序的参数包括一个指向被重新分配的对象的指针，该指针存储于寄存器 old 中。在重新分配指定对象时，先将指向该对象的指针存入寄存器 new 中，然后通过跳转至储存于 relocate-continue 寄存器中的入口节点。在初始化 free 和 scan 之后，我们通过调用该子程序重新分配 root 指针。当 root 的重新分配完成时，我们将使用新的指针作为 root 指针，并开启垃圾回收的主循环。

begin-garbage-collection
  (assign free (const 0))
  (assign scan (const 0))
  (assign old (reg root))
  (assign relocate-continue (label reassign-root))
  (goto (label relocate-old-result-in-new))
reassign-root
  (assign root (reg new))
  (goto (label gc-loop))

在垃圾回收的主循环中，我们必须判断是否有对象需要被扫描。同时还需要检测 scan 指针是否与 free 指针相遇。如果两个指针相等，那么所有的可访问对象都需要被重新分配空间，此时跳转至 gc-flip 节点，该节点能够清空存储空间并让中断的计算得以继续。如果有一个序对需要扫描，便需要调用重新分配空间的子程序为下一个序对的 car 值重新分配空间（使用 old 替换 car 中的指针）。relocate-continue 寄存器需要重新设置，以方便子程序能够返回更新 car 指针。

gc-loop
  (test (op =) (reg scan) (reg free))
  (branch (label gc-flip))
  (assign old (op vector-ref) (reg new-cars) (reg scan))
  (assign relocate-continue (label update-car))
  (goto (label relocate-old-result-in-new))

在 update-car 节点中我们将修改被扫描到的 car 指针，然后继续为该序对的 cdr 重新分配空间。当重新分配空间的工作完成后，程序会回到 update-cdr 节点。在完成 cdr 的重新分配空间和更新后，便完成了对序对的扫描，接着继续回到主循环。

update-car
  (perform (op vector-set!)
           (reg new-cars)
           (reg scan)
           (reg new))
  (assign old (op vector-ref) (reg new-cdrs) (reg scan))
  (assign relocate-continue (label update-cdr))
  (goto (label relocate-old-result-in-new))
update-cdr
  (perform (op vector-set!)
           (reg new-cdrs)
           (reg scan)
           (reg new))
  (assign scan (op +) (reg scan) (const 1))
  (goto (label gc-loop))

relocate-old-result-in-new 将按如下步骤为对象重新分配空间。如果被重新分配空间的对象（由 old 指针指向的对象）不是序对，则返回指向该对象的未做修改的指针（存储于 new 中）。例如，我们可能会扫描到一个序对，它的 car 值是数字 4。如果我们通过 n4 表示 car，则我们希望重新分配后的 car 指针应为 n4。如果被重新分配空间的对象是序对，则必须执行重新分配空间的操作。如果该序对的 car 值包含破碎之心的标识，那么该序对已经被迁移了，所以我们要取得该对象的新地址（从破碎之心的 cdr 部分取得）并储存在 new 中。如果 old 中的旧指针指向尚未迁移的序对，则将该序对迁移至新存储空间的首个空闲存储单元中（也就是由 free 指向的存储单元），并将原先的存储单元设置为一个由该序对新地址构成的破碎之心对象。relocate-old-result-in-new 通过寄存器 oldcr 持有 old 指向的对象的 car 或 cdr 对象。

relocate-old-result-in-new
  (test (op pointer-to-pair?) (reg old))
  (branch (label pair))
  (assign new (reg old))
  (goto (reg relocate-continue))
pair
  (assign oldcr (op vector-ref) (reg the-cars) (reg old))
  (test (op broken-heart?) (reg oldcr))
  (branch (label already-moved))
  ;; Update free pointer
  (assign free (op +) (reg free) (const 1))
  ;; Copy the car and cdr to new memory
  (perform (op vector-set!)
           (reg new-cars) (reg new) (reg oldcr))
  (assign oldcr (op vector-ref) (reg the-cdrs) (reg old))
  (perform (op vector-set!)
           (reg new-cdrs) (reg new) (reg oldcr))
  ;; Construct the broken heart
  (perform (op vector-set!)
           (reg the-cars) (reg old) (const broken-heart))
  (perform
   (op vector-set!) (reg the-cdrs) (reg old) (reg new))
  (goto (reg relocate-continue))
already-moved
  (assign new (op vector-ref) (reg the-cdrs) (reg old))
  (goto (reg relocate-continue))

在每次垃圾回收运算结束时，我们都要交换新旧两个存储空间的指针，也就是交换 the-cars 和 new-cars、the-cdrs 和 new-cdrs 的指针。然后在下次存储空间溢出时将再次触发垃圾回收过程。

gc-flip
  (assign temp (reg the-cdrs))
  (assign the-cdrs (reg new-cdrs))
  (assign new-cdrs (reg temp))
  (assign temp (reg the-cars))
  (assign the-cars (reg new-cars))
  (assign new-cars (reg temp))