存储分配

计算机科学领域术语

编译程序的整个编译过程大体分成五部分：词法分析、语法分析、代码优化、存储分配和代码生成。在代码生成之前还必须先确定程序、变量以及常数在内存中存放的地址，这些工作，统称为存储分配，也就是把程序或数据块分配到指定的存储单元的过程。存储分配策略包括：静态存储分配、栈和堆式存储分配；存储分配算法包括：最佳适应算法、最先适应算法、循环最先适应算法。

定义

编译程序的整个编译过程大体分成五部分：词法分析、语法分析、代码优化、存储分配和代码生成。在代码生成之前还必须先确定程序、变量以及常数在内存中存放的地址，这些工作，统称为存储分配，也就是把程序或数据块分配到指定的存储单元的过程。

数据区可以分为静态数据区（全局数据区）和动态数据区，后者又可分为堆区和栈区。之所以这样划分，是因为它们存放的数据和对应的管理方法不同。静态数据区、栈区和堆区的存储空间分别遵循3种不同的规则：静态存储分配、栈式存储分配和堆式存储分配。后两种分配方式皆称为“动态存储分配”，因为这两种方式中存储空间并不是在编译的时候静态分配好的，而是在运行时才进行的。

某些编程语言，如早期的FORTRAN语言及COBOL语言等，其存储分配是完全静态的，程序的数据对象与其存储的绑定是在编译期间进行的，称为静态语言。而对于另一些语言，所有数据对象与其存储的绑定只能发生在运行期间，此类语言称为动态语言，如Lisp、ML、Perl等。多数语言（如C/C++、Java、Pascal等）采取的存储分配策略是介于二者之间的。

静态存储分配

所谓的静态存储分配，即在编译期间为数据对象分配存储空间。这要求在编译期间就可以确定数据对象的大小，同时还可以确定数据对象的数目。

现状

多数（现代）语言只实施部分静态存储分配。可静态分配的数据对象包括大小固定且在程序执行期间可全称访问的全局变量、静态变量、程序中的常量以及class的虚函数表等，如C语言中的static和extern变量，以及C++中的static变量，这些数据对象的存储将被分配在静态数据区。

常见做法

从道理上讲，或许可以将静态数据对象与某个绝对存储地址绑定，然而，通常的做法是将静态数据对象的存取地址对应到偶对（DataArerStart，Offset）。Offset是在编译时刻确定的固定偏移量，而DataArerStart则可以推迟到链接或运行时刻才确定。有时，DataArerStart的地址也可以装入某个基地址寄存器Register，此时数据对象的存取地址对应到偶对（DataArerStart，Offset），即所谓的寄存器偏址寻址方式。

优点

采用这种方式，存储分配极其简单。

缺点

（1）采用这种方式会带来存储空间的浪费。为解决存储空间浪费问题，人们设计了变量的重叠布局机制，如FORTRAN语言的equivalence语句。重叠布局带来的问题是使得程序难写难读。

（2）完全静态分配的语言还有另外一个缺陷，就是无法支持递归过程或函数。

（3）对于一些动态的数据结构，例如动态数据（C++中使用new关键字来分配内存）以及递归函数的局部变量等最终空间大小必须在运行时才能确定的场合，静态存储分配就无能为力了。

栈式存储分配

栈区是作为“栈”这样的一种数据结构来使用的动态存储区，称为运行栈。运行栈数据空间的存储和管理方式称为栈式存储分配，它将数据对象的运行时存储按照栈的方式来管理，常用于实现可动态嵌套的程序结构，如过程、函数以及嵌套程序块（分程序）等。

特点

与静态存储分配方式不同，栈式存储分配是动态的，也就是说必须是在运行的时候才能确定数据对象的存储分配结果。例如，对如下的C代码片段：

int factorial (int n)

{

int tmp;

if (n<=1)

return 1;

else

{

temp=n-1;

tmp=n*factorial(tmp);

return tmp;

}

随着n的不同，这段代码运行时所需要的总内存空间大小是不同的，而且每次递归的时候tmp对应的内存单元都不同。

活动记录

在过程/函数的实现中，参与栈式存储分配的存储单位拟是活动记录，运行时每当进入一个过程/函数，就在栈顶为该过程/函数分配存放活动记录的数据空间。当一个过程/函数工作完毕返回时，它在栈顶的活动记录数据空间也随机释放。

在过程/函数的某一次执行中，其活动记录中会存放生存期在该过程/函数本次执行中的数据对象以及必要的控制信息单元。一般来说，运行栈中的数据通常都是属于某个过程/函数的活动记录。

必要条件

在编译期间，过程、函数以及嵌套程序块的活动记录大小（最大值）应该是可以确定的（以便进入的时候动态地分配活动记录的空间），这是进行栈式存储分配的必要条件，如果不满足则应该使用堆式存储管理。

堆式存储管理

当数据对象的生存期与创建它的过程/函数的执行期无关时，例如，某些数据对象可能在该过程/函数结束之后仍然长期存在，就不适合进行栈式存储分配。一种灵活但是较昂贵的存储分配方式是堆式存储分配。在堆式存储分配中，可以在任意时刻以任意次序从数据段的堆区分配和释放数据对象的运行时存储空间。通常，分配和释放数据对象的操作是应用程序通过向操作系统提出申请来实现的，因此要占用相当的时间。

两种方式

堆式存储空间的分配和释放可以是显式的，也可以是隐式的。

（1）显式的是指由程序员来负责应用程序的（堆）存储空间管理，可借助编译器和运行时系统所提供的默认存储管理机制。

（2）隐式的是指（堆）存储空间的分配或释放不需要程序员负责，而是由编译器和运行时系统自动完成。

某些语言有显式的存储空间分配和释放命令，如Pascal中的new/deposit，C++中的new/delete。在C语言中没有显式的存储空间分配和释放语句，但程序员可以使用标准库中的函数malloc()和free()来实现显式的分配和释放。

某些语言支持隐式的堆区士的堆区存储空间释放，这需要借助垃圾回收站机制。例如，Java程序员不需要考虑对象的析构，堆区存储空间的释放是由垃圾回收程序自动完成的。

3种方案的利弊

对于堆区存储空间的释放，下面简单讨论一下不释放、显式释放以及隐式释放3种方案的利弊。

（1）不释放堆区存储空间的方法。这种方法只分配空间，不释放空间，待空间耗尽时停止。如果多数堆数据对象为一旦分配后永久使用，或者在虚存很大而无用数据对象不致带来大零乱的情形下，那么这种方案有可能是合适的。这种方案的存储管理机制很简单，开销很小，但应用面很窄，不是一种通用的解决方案。

（2）显式释放堆区存储空间的方法。这种方法是由用户通过执行释放命令来清空无用的数据空间，存储管理机制比较简单，开销较小，堆管理程序只维护可提供分配命令使用的空闲空间。然而，这种方案的问题是对程序员要求过高，程序的逻辑错误有可能导致灾难性的后果，例如指针悬挂问题。

（3）隐式释放堆区存储空间的方法。该方法的优点是程序员不必考虑存储空间的释放，不会发生指针悬挂之类的问题，但缺点是对存储管理机制要去较高，需要堆区存储空间管理程序具备垃圾回收的能力。

常见存储分配算法

由于在堆式存储分配中可以在任意时刻以任意次序分配和释放数据对象的存储空间，因此程序运行一段时间之后，堆区存储空间可能被划分成许多块，有些被占用，有些空闲。对于堆区存储空间的管理，通常需要好的存储分配算法，使得在面对多个可用的空闲存储块时，根据某些优化原则选择最合适的一个分配给当前数据对象。以下是几类常见的存储分配算法：

最佳适应算法

最佳适应算法，即选择空间浪费最少的存储块。

最先适应算法

最先适应算法，即选择最先找到的足够大的存储块。

循环最先适应算法

循环最先适应算法，，即起始点不同的最先适应算法。

另外，由于每次分配后一般不会用尽空闲存储块的全部空间，而这些剩余的空间又不适于分配给其他数据对象，因而在程序运行一段时间之后，堆区存储空间可能出现许多“碎片”。这样，堆区存储空间的管理中通常需要用到碎片整理算法，用于压缩合并小的存储块，使其更可用。

全国各地天气预报查询

上海市

市辖区

云南省

临沧市