Compilers Chaper 7 总结

这一章讲解的是运行时环境。前面一半讲的是原来的套路。MemoryLayout，Stack，Heap，Activation Record，静态链、动态链等。
另外，这一章居然用了一半的篇幅讲解自动垃圾回收，可见，这个技术已经变得相当重要了。

1、运行时环境。为了准确实现源语言中定义的各种抽象，编译器通过与操作系统以及目标机器相配合，创建并维护一个程序的运行时环境。运行时的存储布局包括静态的代码区、静态数据区、堆、栈。后两者中的数据存储区是在运行时分配的。
2、控制栈。过程的调用和返回通常使用一个栈来维护。我们可以用栈，是因为过程的活动时间是嵌套的。即，如果p调用q，那么q的活动时间一定嵌套在p中。
3、栈空间分配。对于有类似于c的局部变量的语言，这些变量的存储空间分配在运行时栈上。对于这类语言，每一个过程的活动都在栈上对应着一个活动记录。活动树的根对应的活动记录在栈底。在栈上的活动记录的序列对应着活动树上从根到当前过程活动的路径。
4、访问非局部变量。对于类似于c的不允许过程嵌套定义的语言，变量或者是局部的，或者是全局的。局部变量在当前的活动记录中，通过偏移量访问。全局变量分配在静态数据区中，有编译时已知的地址。对于允许过程嵌套的语言，访问非局部、非全局的变量时，通过活动记录中的access link或是display来访问。
5、堆管理。堆中的存储区可以存活任意长的时间，直到程序显式地删除它。堆管理器分配和释放堆中的空间。垃圾收集器自动的寻找程序不再使用的对象并将它释放。对于某些语言，垃圾收集器是重要的一个子系统。
6、局部性。通过更有效地利用存储层次结构，堆管理器可以让程序运行得更快。大部分的程序有时间局部性和空间局部性。程序对数据的访问的模式比较多变，更需要仔细地探索局部性。
7、减少堆中的碎片。随着程序的运行，堆中可能存在大量的碎片。最佳适应策略通常可以很好的工作。尽管最佳适应改善了空间的利用率，但是，却没有改善，甚至影响了数据的空间局部性。通过将回收到的相邻的存储片段组成更大的空闲空间也可以减少碎片。
8、手工释放空间。常常导致两种错误：存储泄漏和访问悬挂指针。
9、可达性。垃圾指不会再被程序引用（不可达）的已分配存储区。找不可达的存储区有两种基本方法：一，每当一个可达的存储区变成不可达的时候，记录下它；二、周期性的找出所有可达的存储区，其它的为不可达的。
10、引用计数垃圾收集器。为每一个对象维护一个引用计数，当计数变成0时，该对象不再可达。这种收集器为每一个改变引用计数的操作引入了额外开销，总开销比较大，并且不能找出循环引用的垃圾组。
11、基于踪迹的垃圾收集。周期性的从根集合开始，递归地找出所有的可达对象，将其它不可达对象收回。根集合指程序不需要任何解引用操作的，可以直接访问的对象。
12、Mark-and-Sweep。该收集器首先访问并标记出所有可达对象，然后释放所有不可达对象。
13、Mark-and-Compact。在12的基础上，将所有可达对象在堆中重新排放，消除碎片。
14、Copying Collector。打破了13中“找出所有可达对象”和“为可达对象重新分配空间”两个操作之间的依赖关系。它将堆分成两个部分，A和B。所有的分配请求都从一个部分满足，例如A，直到它没有空间了。此时，在A中运行垃圾收集，将所有的可达对象拷贝到B，然后交换A和B的角色。
15、递增式的收集器。简单的垃圾收集在进行时需要停下来用户的程序。增量式的则把垃圾收集的执行和用户程序的执行交错起来。用户程序会影响垃圾收集的可达性分析。于是，增量式的垃圾收集器每次运行一般是保守的而不是精确的，在本次运行中的浮动垃圾在下一次运行中可以保证被收集。
16、部分收集器同样也用于减少垃圾收集的暂停时间。他们每次只对一部分垃圾进行收集。最著名的一个是分代的垃圾收集器。它根据对象已经被分配的时间的长短将对象分为若干组。最新分配的对象更可能很快被释放，所以对这些组的垃圾收集比较频繁。另外一个可选的算法是火车算法。它使用固定长度的分区，称为car，若干个car会组成一个train，当一个car被垃圾收集的时候，其中的可达对象被移动到其它的car中，所以这个car可以被完全释放并从所在的train中删除。上述两个算法可以组合起来使用，对于不成熟的对象使用分代的策略，对于成熟的对象使用火车策略。