堆式存储分配方法在编译原理与实践中的应用

对于一个允许用户自由地申请和释放数据空间的程序设计语言来说，空间的使用不一定遵循先申请后释放或后申请先释放的原则，因此，栈式的动态存储分配方案就变得不再适用，此时，需要使用一种称为堆式的动态存储分配方案。

所谓堆，是指一片连续的、足够大的专用全局存储区，其存储空间的分配与释放不再遵循后进先出的原则，需要时就分配一块存储区，当某空间不再使用时就把它归还给堆。例如，Pascal语言使用new和dispose来申请和释放空间，C语言则使用malloc和free来申请和释放空间。

就堆而言，由于空间的借、还时间先后不一，经一段运行时间之后，堆必定会被分割成许多块状单元，有些有用、有些无用（空闲），如图7-22所示。

图7-22　堆空间的存储映像(www.xing528.com)

堆式存储分配方式甚为复杂，需要考虑的因素很多，尤其表现在以下两个方面。

一是当运行程序申请一块体积为N的空间时，究竟该如何分配？理论上讲，应从比N稍大一点的一个空闲块中取出N个单元，以便使大的空闲块派上更大的用场。但是这种做法比较麻烦。通常的做法是，先碰上哪块比N大就从其中分出N个单元。无论采用什么原则，堆在一定时间之后必然会零碎不堪，最终会出现这样的问题：运行程序要求一块体积为N的空间，但发现没有比N大的空闲块了，然而所有空闲块的总和却要比N大得多。解决办法其实很简单，只需把所有空闲块连接在一起，形成一片可分配的连续空间即可，但是，这样做必须要调整运行程序对各占用块的全部引用点。

二是当运行程序申请一块体积为N的空间时，所有空闲块的总和小于N，又该如何处理？一种可行的解决方案是废品回收，即寻找那些运行程序业已无用但尚未释放的占用块，或者那些运行程序目前很少使用的占用块，把它们收回来重新分配。然而，如何知道哪些块运行时在使用或者目前很少使用？即使知道了，一经收回后运行程序在某个时候又要用它时该怎么办？因此，废品回收技术的实现，除了在语言上要有明确的具体限制外，还需要有特别的硬件措施予以保障才行。