斯坦福cs231(编译原理)の 11 Automatic Memory Management

引出

自动内存管理也称之为垃圾回收(garbage collection)

手动管理内存有很多出乎意料的bug：

• 忘记释放没有被使用的内存
• 忘记去掉一些无用引用，或者是野指针
• 偶然的内存覆盖
• ...

内存相关bug很难发现(比如内存溢出，就需要排查很长时间)

🌰：

某个对象没有被引用了，但是对应的指针还在；突然后面该对象被覆盖了，但是指针仍然引用这块内存，这个时候使用这个指针的读写还是按照原来的类型进行读写，就很容易出现错误(原类型是8bit大小，现在的类型是16bit大小这种情况)

如何自动管理内存呢？

思路：当一个对象被创建的时候就会同时分配空间；但是当没有足够的空间可用的时候，是否可以复用那些没有被使用(引用)的对象的空间呢？

我们如何得知一个对象"没有被再次使用呢"

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

上面的代码里new A生成的A对象后面被覆盖了，这个A对象就是没有被再次使用的对象(这里不考虑其他代码，仅考虑本行代码)，x和y共同引用一个对象。这个A对象被称作为不可达对象

不可达对象定义，当且仅当：

• 存在寄存器指向了对象x，或者
• 存在某一个可达对象y指向这个x

考虑如下代码：if分支始终为True

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

假设在x <- y 之后，y是非活跃变量，这里：

• A是不可达的
• B是可达的，通过x，但是B之后再也没有被使用过；

所以，判断可达和不可达只是一种近似手段；

可以通过以寄存器为起点遍历引用链，寻找所有可达对象(为什么以寄存器为起点，因为只有保存在寄存器的变量才说明是参与计算的活跃的对象)，总的来说，有以下几种比较常见的垃圾回收算法：

• 标记清除(mark and sweep)
• 复制转移(stop and copy)
• 引用计数(reference count)

前两种都是内存耗尽的时候，才垃圾回收；引用计数不是等待内存耗尽的才开始进行，在没有指针指向该对象时尝试收集该对象

mark and sweep(标记清除)

标记清除有两个步骤：

• the mark phase: 找到可达对象(rearchable objects)
• the sweep phase: 收集可回收对象

实现方式：

每个对象有一个额外的标记是否可回收的bit位

• 该bit位初始化为0
• 在mark phase期间，对于所有的可达对象设置为1

mark phase:

let todo = {all roots}
while todo != 空集 do
	pick v 属于 todo
	todo <- todo - {v}
	if mark(v) == 0 then
		mark(v) <- 1
		let v1, v2, ..., vn be the pointers contained in v
		todo <- todo 并集 {v1, v2, ..., vn}
	fi
od

sweep phase:

清除阶段扫描堆空间里可以清除的对象(也就是比特标记仍为0的对象)，这些对象是不可达的，可以被视作"垃圾"。这些垃圾对象可以在清除阶段形成一段链表(可以避免堆内存碎片)

清除阶段过后，之前被设置为1的对象应该重置为0，方便下一次垃圾回收。

siseof(p) is the size of block starting at p，sizeof(p)表示p对象所占据的大小，这里默认大部分情况下对象的内存布局是连续的

p <- bottom of heap
while p < top of heap fp
	if mark(p) == 1 then
		mark(p) <- 0
	else
		add block p...(p + sizeof(p) - 1) to freelist
	fi
	p <- p + sizeof(p)
od

这一段代码的大概意思就是从堆的起点开始出发，直到堆的终点，如果发现p为1，则重置为0；否则，说明是垃圾对象，把[start, start + sizeof(p)]的内存串到freelist链表里，在每一轮结束后，别忘了对p增加本次对象的偏移量

🌰：这里假设只有一个寄存器，初始的时候寄存器指向A对象

root -> A(0) -> B(0) -> C(0) -> D(0) -> E(0) -> F(0)

标记阶段后:
root -> A(1) -> B(0) -> C(1) -> D(0) -> E(1) -> F(0)

清除阶段后:
root -> A(0) -> B(0) -> C(0) -> D(0) -> E(0) -> F(0)

以上普通标记-清除的缺点：

由于一旦使用该算法的时候，已经是内存不够用了，然而在标记阶段还要借用内存去维护todo这样一个数据结构，并且这个结构的大小是不受控制的，有可能有许多垃圾需要回收，这是和垃圾回收的目的相悖的

改进：

todo这样的数结构可否不开辟新的空间？

todo这个数据结构是为了寻找可达对象，那么可否直接遍历对象引用图，把可达对象的bit标志位设置为呢？

对图dfs遍历，但是引用是大部分情况下是单向的，如何在图里回溯(在遍历的同时反转链表，这样回溯的时候沿着反转指针即可)，这里实际操作的时候需要注意借用临时变量(寄存器)去存储当前遍历节点，以便下一个节点使用

cur.next = tmp(反转) // 连接上一个节点
tmp = cur; // 现在tmp是当前节点，给下一个节点使用
cur = cur.next;

对象在被分配的时候一般按如下规则进行分配：

• 挑选尽量大的空间块
• 按需分配
• 顺序且连续分配，比如有100个bit大小的自左向右的连续内存空间，现在要分配50bit给某个对象，那么分配的就是前50bit

标记—清除的优势：

• 碎片化内存，更多的使用内存碎片，减少空间利用率
• 对象在垃圾回收的时候不需要移动，也就是对应的指针也不会变化(这在一些允许自己手动管理内存的语言很重要，如C，C++，不会引起歧义)

stop and copy

内存被划分为两块：

• old space: 用于分配内存
• new space: 为垃圾回收备用

另外有一个heap pointer, 总是指向old space的下一个可用空间，所以，分配内存仅仅在增加heap pointer

image-20230520103417917

stop and copy的特点：

• 仅仅从old space copy可达对象到new space(所以当垃圾很多的时候，这种算法效率很高)
• 垃圾被留在了old space
• 在copy之后，new space比垃圾回收之前的old space占用的空间更少
• 在copy结束之后，old space和new space交换
• 由于需要移动scan pointer和alloc pointer，和标记-清除一样，需要知道对象的大小
• 由于对象被移动了，函数堆栈里的相关指针必须更新

每次copy之后，需要更新被copy对象内部的指针，因为其指向后续也会发生copy才对，如何让其指针引用的对象指向最新的已经copy的对象？可以在每个对象增加一个关于转移指针的字，如果对象发生了copy，那么转移指针有值且指向最新的地址，

总结：转移指针就是存在于旧对象里指向新拷贝对象的一个指针，作用是方便后续引用该对象的指针能够根据转移指针正确更新，另外就是标记旧的对象已经被拷贝了

所以stop and copy的目标是寻找到所有的可达对象并copy至new space，对于当前copy对象，还需要更新其内部的所有指针

image-20230520111956200

while scan <> alloc do
	let O be the object at scan pointer
	for each pointer p contained in O do
		find O' that p points to
		if O' is without a forwarding pointer
			copy O' to new space (update alloc pointer)
			set a word of old O' to point the new copy (这一步就是标记旧的对象已经被拷贝了)
			change p to point to the new copy of O'
		else
			set p in O equal to the forwarding pointer
	end for
	increment scan pointer to the next object
od

优点：

• 相对比较快，尤其垃圾比较多的时候，因为只需要处理可达对象
• 分配内存是简单且快速的，因为只需要增加heap pointer

缺点：

• 一些语言，如C和C++不允许对象拷贝，以及指针转移，因为指针作为对象语义的一部分在程序中公开

针对C和C++不允许对象拷贝，以及指针转移，有一些Conservative collection技术

引用计数

在没有耗尽内存的时候就开始对对象的引用数（每个分配操作都会引起引用计数），进行计数，一旦计数为0，说明该对象需要被回收了。

rp(x)为x的引用计数

每个赋值x <- y ，这里假设x,y对象分别指向o和p：

rc(p) <- rc(p) + 1
rc(o) <- rc(o) + 1
if (rc(o) == 0) then free o
x <- y

优点：

• 易于实现
• 增量收集垃圾，而不会在执行过程中出现大量的停顿，因为它在没有耗尽内存的时候就开始对对象的引用数，每次赋值语句都可能会引起垃圾回收，但是每次的垃圾都是增量变化的，并不会占据很多时间。

缺点：

• 无法处理循环引用

x -> A => B =>A
x = null

上面语句里，x是一个指针引用了A，而A又引用了B，当x不再指向A的时候，由于A和B的引用计数始终不为0，所以没有办法回收A和B

• 在每次分配时处理引用计数有的时候比较慢，如果一个赋值一句牵连到了很多对象，那么引用计数就会计算这些对象，可以在编译的时候优化这些赋值语句，比如如果有一个对象的两次更新，可以优化成一次，这样就会计算一次引用计数了。

总结

自动内存管理可防止严重的存储错误

But，也减少了程序员对内存的控制：

• 例如，内存中的数据布局
• 例如，何时重新分配内存

常见的自动内存管理问题：

• 实时应用里可能由于垃圾回收时间过长出现短暂的程序停止
• 内存泄漏，一般多是程序员没有及时回收"野"对象

有一些更高级的垃圾回收算法：

• concurrent: 垃圾回收的同时允许程序运行
• generational：不会扫描长期存活对象（v8里就有）
• real time: 减少因为垃圾回收引起的程序停止的下界
• parallel: 允许多个垃圾回收器同时运行；