笔记仓库

正常人的正常笔记集

垃圾回收

在前面的寄存机器模型的基础上,Storage Allocation and Garbage Collection简单描述了数据在存储中的分配表示,以及不断分配空间给新数据必然带来的问题:存储耗尽,因此需要一个垃圾收集机制维护整个存储系统正常运转。这部分内容不是很多也不难理解,但文字内容比较密集叙述有点乏味,因此我另外简单写一篇重点看算法的代码实现。此外,可能因为原文一直都是在假设已经知道内存中哪些部分放的数据是需要被清理的垃圾,而哪些是还需要继续使用的数据,所以只需要在空间耗尽前通过一定的算法清理掉垃圾释放空间,但并没有解释怎样去区分垃圾和有用的数据,所以看着会有些困惑。这里同样不再讨论这个问题,有兴趣的自己找相关文本材料阅读。

序对和其他数据的向量表示

传统的计算机内存可以被想象成一些排列规划好的格子,用于存放数据,而每个格子都有一个唯一的名字或者说序号,可以通过它来访问和更改格子里的内容。而这个唯一的标识符就是它的地址/位置,地址也可以被当作普通的数据来对待,进行一些算术运算得到新的地址,再通过新的地址去访问其他数据,这也令诸如pair,list这样的树状数据结构可以在线性的内存中很好的被表达。

对这种存储结构的建模可以用向量来模拟,和C++ STL的vector相似,把它当成一种像数组一样可以直接用索引访问的容器,通过下面两个基本操作对向量中的元素进行访问和修改:

  • (vector-ref <vector> <n>): 读取向量<vector>的第n个元素并返回
  • (vector-set! <vector> <n> <value>): 把向量<vector>的第n个元素的值设置为<value>

而这些操作的效率都是与n本身大小无关的,可以认为是$o(1)$,通过对n参数的算术运算可以连续取值。索引计数默认从0开始。

列表

我们用两个向量来存储所有的序对(pair)结构,the-cars向量表示用来存放所有序对的car部分,the-cdrs用来存放所有序对的cdr部分。指向一个序对的指针表示可以暂时想象成某个索引值nthe-cars的第n个元素是这个序对的car部分,the-cdrs的第n个元素是这个序对的cdr部分。

放在向量中的元素实际上都可以被看成指针,有些是指向其他序对(即索引值),有些则指向数值或symbol等常量。指针的内涵可以被扩展为类型指针(typed pointer),除了它指向什么的数据地址外,还需要在标识出它指向的东西的类型,一般实现这种结构的方法是在把指针的固定长度的前几位作为类型域(type field),在此不再多作讨论。

当指针指向不同类型的数据时,假设它的第一个部分用来标识数据的类型,如整数4被标识为n4,指向nil被标识为e0,指向另一个序对时,标识类型为p而后面的表示符表示那个序对在向量中对应的索引。

列表((1 2) 3 4)可以表示为

每个序对左下角的数字表示在向量中的索引

在寄存机器语言中,可以用两个同名寄存器the-carsthe-cdrs来表示这两个向量,利用前面提到的向量操作vector-refvector-set!把序对相关操作转换成对于寄存器的操作。

比如carcdr

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

可以写为

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

reg2即该序对在向量中对应的索引值

更改操作

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

可以写为

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

free是一个特殊的寄存器,指向下一个可用索引。使用cons来构造一个新的序对

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

可以用这样的实现:

1
2
3
4
5
6
(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))

栈*

用上述写法展开一些栈操作,比如对the-stack的压栈(save <reg>)操作可以实现为:

1
(assign the-stack (op cons) (reg <reg>) (reg the-stack))

同样弹栈操作(restore <reg>)实现为:

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

初始化命令(perform (op initialize-stack))实现为:

1
(assign the-stack (const ()))

这些内容也没什么可细说的,之前把栈作为list来实现,现在了解了list如何实现后再从底层重新写一遍而已。

垃圾收集

程序运行中会产生一些临时数据,使用过一次或几次后不需要再被使用。如果在内存中始终为它们保留这些空间,可能会导致内存耗尽,因为我们暂时做不到物理上的无限大小的内存。因此需要一个合适的垃圾收集(garbage collection)来回收处理这些对未来的计算不会产生任何影响(即不会有后续的car cdr等针对它的读写操作),给其他有用的数据让出更多的空间。

一种经典的,被用于Scheme的高速垃圾收集方法名为stop-and-copy算法,也就是通常所说的Minsky-Fenichel-Yochelson算法,接下来主要描述这种算法。另一种常见的方法mark-sweep方法可以见MIT6.001相关课程材料中给出的实现和讨论,或直接阅读Allen原文1的完整讨论。

Stop-and-copy

基本思想是先把内存划分成两半:一半被称为工作内存(working memory),另一半为空闲内存(free memory)。

我们首先从当前的工作内存中分配空间来构造新的序对,这个过程中通过free指针的自增操作不断指引下一个可用的空间位置。当工作内存满了的时候,会混杂着垃圾和有用的数据。

这时都该进行垃圾收集了。

垃圾收集过程中我们定位所有在工作内存中有用的数据,并把它们复制到空闲内存中的连续空间中。这里寻找有用的数据(序对)是通过追踪机器寄存器中的所有carcdr指针,能通过它们访问到的数据就是有用的。因为我们没有复制垃圾,所以空闲内存被使用的空间是小于原工作内存的,那么空闲区域可以继续分配空间给新的序对。而工作内存现在的数据都已经没有继续保留的价值了,反正有用的数据也已经被复制了。所以,现在可以直接交换这两部分内存的角色,让原来的空闲内存从此成为当前的工作内存,而原来的工作内存也成了现在的空闲内存。至此,本次垃圾收集完成。

当工作内存再次用完时,再进行如上操作并交替。

实现细节

接下来试图用寄存机器语言指令实现一个垃圾收集器(garbage collector),首先假设存在一个root寄存器,相当于其他树形数据结构的根结点的角色,通过它开始的遍历可以访问到所有机器中可访问的数据,维护root可以通过在垃圾收集前,把所有机器中的寄存器的内容存放到root指向的list。

当调用cons时发现free指针指向一个超出当前工作内存的位置,就说明内存已经耗尽,可以开始进行垃圾收集了。收集的过程中除了原来的free,还需要一个scan作为指针记录在工作空间中扫描到的位置。算法中,root用于指示新内存的起点,序对被复制过来后,root也会调整到新的位置,free也会相应增加。

旧位置的序对被复制完成后,内容会被更改为相应的标记来指示这个位置的内容已经转移了。这种标记表示为:在car位置放置一个特殊的标签(传统上我们叫它broken heart标签),在cdr位置放置指向这个数据被复制到新内存的位置的转发地址(forwarding address),可以直接通过这个地址达到它在新内存的位置进行取值访问。

首先来看最后交换工作内存和空闲内存的gc-flip部分,new-carsnew-cdrs是垃圾收集完成前的空闲内存,the-carsthe-cdrs是垃圾收集完成前的工作内存。简单的进行交换内容即可:


1
2
3
4
5
6
7
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))

核心操作relocate-old-result-in-new可以看成一个函数,以工作内存中被扫描到的内容old作为参数,返回它在空闲内存中被复制到的内容new

如果old不是指向序对结构的指针,也就是说它指向数值符号等常量,这里假设常量被存储在另外一片不可更改只能被引用的空间,那么不需要另外开辟空间来存储它,new只需要沿用old的值。

如果old指向了一个已经被复制转移到新内存的序对(通过检查old指向的序对的car是否有broken heart标签),那么只需要从cdr读取原序对的新位置,就可以作为new的内容。

如果old指向的序对还没有被转移,那就需要我们来对它完成复制转移。先把它们复制到新内存的第一个可用位置(free指向的内容)记为new,增加free使之指向下一个可用位置,再在原来的car部分打上broken heart标签,并在原来的cdr位置设置new为转发地址。


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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))
(assign new (reg free)) ; new location for pair
;; 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))

中间寄存器oldcr用于分别在不同时间存放old指向的序对的car内容和cdr内容。

整个垃圾收集的过程开始时,先初始化freescan,并找到旧内存的root迁移到新内存后的位置作为新的root

1
2
3
4
5
6
7
8
9
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))

然后开启gc-loop的循环。

在这个主循环中,如果freescan指针相遇,则说明已经扫描完了新内存中所有数据,没有还需要复制转移的,那么直接跳转到最后的gc-flip即可。

而如果还有没扫描完的数据,说明有些指针的内容在第一次被遇到后就复制到了,这些内容包含指向旧内存的指针,因此需要通过relocate-old-result-in-new把这些被指向的旧内存内容复制转移到新内存,或者对于已经转移过来的,直接指向新内存。对每个scan指向的new-carsnew-cdrs两个部分都需要进行一次这样重新定位内容的操作。

所以主循环是这样的:

1
2
3
4
5
6
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))

先对scan扫描到的car部分进行重定位,并修改car部分内容。再对scan指向的cdr部分重新定位并修改内容,完成后对scan进行自增操作扫描下一个位置重复入手操作,直至scanfree相遇为止。

1
2
3
4
5
6
7
8
9
10
11
12
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))

小结

这篇算是我写过的比较短的内容了,介绍了一个至今还在服役的算法的基本思想。垃圾收集器无法被调试,且必须保证很高的效率,因此又必须写的小巧精致。后来有人把这个算法改进成了不用停下程序计算也能同时完成垃圾收集的实时垃圾回收机制2,如果对垃圾回收很感兴趣,不妨可以先从大一统理论3开始看起来(笑)。

上面介绍的算法实现上可能会有时想不过来为什么需要复制后不断扫描修改和分配新地址,这也算不上什么巧妙高端的技术,你写二叉树复制或者更宽泛的深拷贝场景的时候肯定遇到过相似的问题,多回去写写自然会明白。


  1. 1.Allen, John. 1978. Anatomy of Lisp. New York: McGraw-Hill
  2. 2.Baker Jr, Henry G. "List processing in real time on a serial computer." Communications of the ACM 21.4 (1978): 280-294.
  3. 3.Bacon, David F., Perry Cheng, and V. T. Rajan. "A unified theory of garbage collection." ACM SIGPLAN Notices 39.10 (2004): 50-68.