内存管理

二十四课

回顾 register machine

(图1)

在前几课介绍的 register machine 如上图所示,它主要由三个部分组成:

  • registers: 用来存储各种 procedures 执行时所需要的参数、环境及输出的结果等数据

  • stack: 用来临时存储将被修改的 register 中的数据以便在 subroutine 执行完后恢复环境继续执行

  • heap: 用来存储各种各样的具体数据结构的地方。对于 scheme 来说就是存储所有 list 的地方,无论是表达式还是数据都是 list。

本节介绍的就是 heap 及其所依赖的技术。

Abstraction

Vector

内存支持数据的随机存取,即可以在常数级别的时间复杂度内存取内存中任意位置上的数据,这可以被抽象为 Vector 模型,如下图所示:

(图2)

其中在 Scheme、Register Machine 中相应的操作也如上图所示。

Stack

我们也很容易使用 Vector 来实现 Stack:用一个 stack pointer (SP) 指向当前 stack 的顶部,每当 save 的时候就往 vector 增大的方向移动 SP;每当 restore 的时候就往 vector 减小的方向移动 SP:

(save <reg>)
; becomes
(assign sp (op +) (reg sp) (cons 1))
(perform (op vector-set!) (reg stack)
(reg sp) (reg <reg>))
(restore <reg>)
; becomes
(assign <reg> (op vector-ref) (reg stack) (reg sp))
(assign sp (op - ) (reg sp) (cons 1))

Heap

在 register machine 中,heap 就是一堆 cons,它们分别由 car 和 cdr 构成。为了支持 cons,我们可以使用两个平行等长的 vector 来模拟,第一个 vector 叫作 the-cars,第二个 vector 叫作 the-cdrs,它们共用 base index,如下图所示:

(图3)

car & cdr

cons 的 selectors 操作,即 car 和 cdr 如下文所示:

; CAR
(assign <reg> (op car) <pair>)
; becomes
(assign <reg> (op vector-ref)
(reg the-cars) <pair>))
; CDR
(assign <reg> (op cdr) <pair>)
; becomes
(assign <reg> (op vector-ref)
(reg the-cdrs) <pair>)
; where <pair> is a cell offset into the-cars & the-cdrs vectors

cons

heap 不仅要支持 cons 数据的获取,还需要支持 cons 的分配与回收,即 heap 的内存管理。首先我们需要新增一个 register --- free,它指向当前尚未分配的最近一个 cell,当分配操作被执行时,free 指针指向的 cell 被分配出去,free 指针则指向下一个尚未分配的 cell,整个过程示意图如下所示:

(图4)

cons 的执行过程如下所示:

; CONS
(assign <rename> (op cons) <val-1> <val-2>)
; becomes
(perform (op vector-set!)
(reg the-cars) (reg free) <val-1>)
(perform (op vector-set!)
(reg the-cdrs) (reg free) <val-2>)
(assign <regname> (reg free))
(assign free (op +) (reg free) (const 1))

那么我们如何区别 cons cell 中储存的不同类型的数据呢?比如 null、integer、boolean、指向其它 cell 的指针等等。我们可以拿出 (car cell)、(cdr cell) 中数据的一部分 bits 来存储数据的类型,剩下的 bits 用于存取具体的数据内容,如下图所示:

(图5)

举例:

(define a (list 4 7 6))
(cons a a)

利用刚才的 vector 抽象,我们足以支持以上语句中的 list 数据创建,如下图所示:

(图6)

cell 的回收:Garbage Collection

如果内存足够大,我们可以不断地分配 cells,但我们知道内存空间无论再怎么大也是有限度的,当空间不足时,我们就需要把不用的 heap 空间回收,即所谓垃圾回收 (Garbage Collection)。

垃圾生成 (Creation of Garbage)

垃圾就是在当下之前分配的、直到程序运行结束时都不可能再被使用到的内存空间。一个简单的垃圾生成的例子如下图所示:

(图7)

垃圾检测 (Detection of Garbage)

与程序之后运行有关的数据都存储在 registers、stack 以及 global environment 中,因此只要把它们中指向的 heap cons cells,以及这些 cells 指向的其它 cells 保留,剩下的没有被引用到的 cells 就是垃圾。

垃圾回收法1 --- Mark/Sweep Garbage Collection

Mark & Sweep 顾名思义,分为 Mark 和 Sweep 两个阶段。Mark 阶段 Garbage Collector 会顺着 registers、stack 和 global environment 出发,把所有被直接或间接引用到的 cells 都 mark 成 1;Sweep 阶段在 Mark 阶段完成后,遍历一遍被分配的 cells,把所有没有被 mark 成 1 的 cells 全部回收。接着刚才的 the-cars 和 the-cdrs 模型,我们新增一个 the-marks vector,就可以分别完成 mark 和 sweep,举例如下图所示:

(图8)

Mark 阶段:从 registers、stack 和 global environment 中的 c 出发,找到直接引用 4 以及间接引用 0、1,于是它们被 mark 成 1。

Sweep 阶段:将没有被 mark 成 1 的 2、3 回收。

Mark/Sweep 的示例代码如下:

; Mark Phase
(define (mark object)
(cond ((not (pair? object)) #f)
((not (= 1 (vector-ref the-marks object)))
(vector-set! the-marks object 1)
(mark (car object))
(mark (cdr object)))))
; For a pair, "object" is an integer offset denoting the cell location
; Sweep Phase
(define (sweep i)
(cond ((not (= i size))
(cond ((= 1 (vector-ref the-marks i))
(vector-set! the-marks i 0))
(else (set-cdr! (int-to-pointer i) free)
(set! free (int-to-pointer i))))
(sweep (+ i 1)))))
(define (gc)
(mark root)
(sweep 0))

垃圾回收法2 --- Stop & Copy Garbage Collection

使用 Stop & Copy 策略时,Garbage Collector 将可支配内存空间分为两半,只将一半用于分配。当用于分配的一半分配完后,同样从 registers、stack 和 global environment 出发遍历所有直接引用和间接引用的空间,将其中的信息复制到另一半未分配的空间中去,并保持它们之间的引用关系。相较于 Mark & Sweep 策略,Stop & Copy 需要两倍内存空间,但后者可以利用复制的过程来做碎片整理。

小结

垃圾回收最早需要程序员手动完成,但由于这个过程即使是素质过硬的程序员也在所难免会出现错误,这种错误难以检查、发现,将它交给程序管理,确实是一种进步。但作为站在巨人肩上的程序员,了解一下你为什么能站在巨人的肩膀上,为什么能写着在天上飞的语言还是很有必要的。

参考