Memory Management（内存管理）

（以下内容，译自Category:Tutorials中的Memory Management。更多内容可以参看Category:Chinese。）

本教程介绍Visual Prolog（Vip）中是如何管理内存的，将学习运行栈、堆及垃圾收集等内容。

内存(Memory)

Vip程序有三种存放数据的地方：

• 运行栈（Run Stack）

• 堆（Heap）

• 系统内存（System Memory）

它们各有自己的维护机制与用途。

运行栈(Run Stack)

运行栈用于参数与局部变量。无论什么时候，只要调用一个谓词，就会首先把它的参数压入运行栈，而后就调用该谓词。返回地址也放在这个栈里。

参数及返回地址的顺序与（用language关键字声明的）调用协议有关。

谓词进入后，它就会在这个栈中为局部变量及簿记数据分配空间。

参数、返回地址、局部变量等内容的整体，称为一个栈帧（stack frame）。

谓词执行完了，它的栈帧也会被消去。

上面说的这些，与大多数据编程语言的内存处理是一样的。但是当遇到所谓“非确定性”谓词时，情况就不同了。

当一个谓词带有激活的回溯点返回时，若要回溯，还需要再次使用该谓词的栈帧，这样一来，只要谓词是带有激活回溯点返回的，栈帧就不能消去。

回溯点是在嵌套的调用中时，这个栈帧也不能消去。因此，单一一个回溯点就会要保存一整套有效栈帧的“链”。

如果由于截断而消去了回溯点，则相应的栈帧也就消去。可以认为要消去的栈帧总是在栈帧链最顶上的，这样，一个截断就会消去链最上面一个栈帧（当然也会消去回溯点）。

运行栈也常常简称为栈，有时也叫它调用栈（尤其是对没有回溯的其它语言，在控制返回到调用程序时它们没有栈帧这个问题）。

最终调用优化(Last Call Optimization)

递归谓词（也就是自己调用自己的谓词）是很常见的。谓词每调用一次自身，就会创建一个新的栈帧，反复如此，创建起来的栈帧可就不小了。

由于栈（创建之后）大小是固定的，这就对栈帧有个限制要求。

Vip6（以及更早版本的Visual Prolog）会进行一种通常称为 最终调用优化 的工作，其主要 思路是：如果当前栈帧在谓词里的最后一个调用之后不再需要了，那最好就在最终谓词调用之前消去它。

具体实现上还有很多细节，最重要的是最终调用要比其它调用的栈效能高得多。当然，再说一次，如果谓词中有回溯点的话，这个栈帧还是需要的。

栈帧耗尽(Exhausting the Run Stack)

能耗尽运行栈的，多半是递归谓词（或递归谓词链），其中递归不是最后的调用。还可能的是，由于回溯点必须要保留栈帧。

堆和垃圾收集(Heap and Garbage Collection)

简单的（或是说少量的）数据如数值等会直接拷贝到运行栈帧中，不过长表之类的数据结构在当作参数传递或结果返回时，要拷贝它们可就代价太大了。因此，大的数据如表等，处理办法是不同的。

大的数据存放在堆中，它们是由指向数据本身的一个指针来表示的。这个指针会如上面说的拷贝到栈帧中，但是实际的数据还是原地不动。

表及函子值一经创建，它们就存放在堆中，也还是在这里它们最终由垃圾收集器回收。

必须保存的回溯点也使用堆来保存，还有不能移走（下面还要说）的数据（基本上也就是事实数据库及对象）也要用到堆，还有一些下面要说的原因，可能其它数据也会使用堆。

堆是用垃圾收集机制管理的。程序员分配（隐式多于显式）堆中的内存片，但他决不会（无论隐式还是显式）做 释放 内存的事。这个事情是由垃圾收集器（它是一种算法）来做的，它时时对堆进行分析，释放那些再也不需要使用的存储区。就是说，它回收垃圾。

这就是堆的管理原理。当需要堆中的内存时，会发生下面三种情况之一：

• 垃圾收集器有合适的堆的内存片可用，就提供它

• 从操作系统中分配得到新的内存

• 回收堆中的垃圾，再进行分配

<A name=Garbage_Collection></A>

垃圾收集

Visual Prolog使用Boehm-Demers-Weiser保守式的垃圾收集器。

我们先看一下程序总是分配内存，但永远不做释放工作的情况。

某个时刻程序有了一些分配，但并非所有这些分配都是可达的。程序只能直接或间接访问那些有索引的内存，而程序从子程序中返回后，子程序的局部变量及参数也就不存在了，相应的索引也就没有了。

程序可以访问的内存/数据称之为活 的数据，其它的就是死数据或垃圾 。

垃圾收集器就是要定位垃圾并使其可以为（活的数据）重新利用。

为要定位垃圾，收集器首先定位和 标记 所有活数据，在这个过程中所有没标记的已分配内存就是垃圾。

垃圾收集器标记活数据从所谓根集（root set）开始，根集是全局变量加上当前存在的局部变量及参数。所有指向来自根集的内存标记了，同样所有指向来自已标记内存的内存也标记了，剩下没有标记的就是垃圾。

垃圾收集器回收垃圾前，会对所有垃圾运行 终结器 程序。所谓终结器是一个可选的用户定义例程，它是在一片内存回收之前执行的。运行了相应的终结器后，垃圾就被回收，内存就可以重新使用了。

终结器(Finalizers)

Visual Prolog支持对象的终结器：这个终结器只需要在对象构造类里给谓词finalize/0写些子句。这个谓词是隐含声明的，不能做显式声明。

要注意，垃圾收集器算法有一个特点：回收内存是波动进行的，一段时间里没有什么回收而接着一段时间里又有很多回收，如此反复。因此，终结器也是波动式地执行的。

要记住，当某一片内存不再是活的时候，终结器并不是马上就执行的。只是在垃圾收集期间垃圾收集器回收内存时才会先执行终结器程序。

数据在哪儿(Where is Data Allocated)

上面说运行栈保存了参数和局部变量，但只是部分如此。实际上运行栈只保存数值、字符及指针。所有不是数值也不是字符的数据是由指向该数据的一个指针来表示的，而实际数据则是存放在堆中。

堆里的数据(Data on Heap)

对象总是放在堆中的，它并不只是一个值，它还带有易变的状态。如果复制了一个对象，就会有该对象的两个版本存在，更新了其中一个在另一个中间是看不到的。在最开始的时候，对象就是放在堆里的。

串放在堆中一个特殊的部分，这个特殊部分被叫做原子堆（atomic Heap）。堆的这部分效能更高，但它只能存放不含任何指针的数据。它之所以效能更高，正是因为在垃圾收集时不用扫瞄指针。

还有，已经说过，事实中的数据也是存放在堆中的。

多线程与内存(Multi-Threading and Memory)

多线程程序中的各线程对谓词的调用及回溯是相互独立的。因此，各线程有自己的运行栈。而另一方面，所有的线程共享唯一的一个堆。

对各运行栈，只有一个线程可以访问，所以不需要进一步的同步机制。而所有的线程都可以访问堆中的数据，但Visual Prolog并没有提供的访问同步，这需要由程序编写者自己确保对数据访问的方法正确。

除了事实数据库（包括对象中的事实数据库），Visual Prolog的数据都是非易变的。非易变数据没有任何同步问题：可以有任意数量的线程同时读数据。

在两个（或更多个）线程同时更新一片内存中的数据时，才会出现问题。比如两个或多个线程同时对一个事实数据库插入或撤消事实时，就可能有问题。

插入（assert）及撤消（retract）例程实现可以保证事实数据库总是完好的（就是说，可以保证它俩对事实数据库的并发使用不会导致访问违例及类似的情况）。

不过，如果两个线程同时更新同一个数据库时，可能有的更新会 丢失 。例如，同时插入两个事实，可能会出现一个插入了而另一个丢失了的情况。

在数据库更新时读该数据库是不会有问题的。

PFC提供了同步的方法，可以用来同步事实的更新。主要方法是semaphore（信号）和mutex（互斥），可以参看多线程包。

系统内存(System Memory)

Visual Prolog程序使用某些工具时，例如GDI+或COM，它会接收到来自系统内存的数据。把这些数据拷贝到Visual Prolog的堆并释放外部的内存是有益的。各个情况下,数据的分配内存及释放内存应该根据所用工具提供的帮助来完成。