运行存储分配策略
- 静态存储分配：在编译时刻就可以确定大小的数据对象，可以在编译时刻就为它们分配存储空间。
- 动态存储分配：编译时无法完全确定数据对象的大小，在运行时刻，再动态地分配数据对象的存储空间。主要有栈和堆式存储分配。
活动记录
使用编译器通常以过程（函数，方法）为单位分配存储空间，过程体的每次执行称为该过程的一个活动。
过程每执行一次，就为它分配一块连续存储区，用来管理过程一次执行所需的信息，这块连续存储区称为活动记录。活动记录的形式一般如下：
静态存储分配
在静态存储分配中，编译器为每个过程确定其活动记录在目标程序中的位置。这样，过程中每个名字的存储位置就确定了。
因此，这些名字的存储地址可以被编译到目标代码中。过程每次执行时，它的名字都绑定到同样的存储单元。
适合静态存储分配的语言必须满足以下条件：
- 数组上下界必须是常数
- 不允许过程的递归调用
- 不允许动态建立数据实体
满足这些条件的语言有BASIC和FORTRAN等。分配方法主要有顺序分配法和层次分配法。
顺序分配法
按照过程出现的先后顺序逐段分配存储空间 各过程的活动记录占用互不相交的存储空间。
层次分配法
通过对过程间的调用关系进行分析，凡属无相互调用关系的并列过程，尽量使其局部数据共享存储空间
动态存储分配
栈式存储分配
当一个过程被调用时，该过程的活动记录被压入栈；当过程结束时，该活动记录被弹出栈。
活动树
用来描述程序运行期间控制进入和离开各个活动的情况的树。
例：下面是一个快速排序的活动树：
下面是当执行到 q(2,3) 的控制栈，注意，这个栈是从上向下的。
一般来说，控制栈的设计如下：
- 临时变量：编译产生的，用于暂存值的变量
- 保存机器状态：调用过程的活动在调用点的机器状态，包括计数器，各种寄存器的值
- 静态链：指向本活动要访问的非局部数据所在的活动记录。
- 控制链：指向主调过程的活动记录的首地址
调用序列和返回序列
调用序列
调用者计算实际参数的值，将返回地址放到被调用者的机器状态字段中。将原来的top-sp（栈顶指针寄存器，指向局部数据开始的位置）值放到被调用者的控制链中。 然后，增加top-sp的值，使其指向被调用者局部数据开始的位置。
被调用者保存寄存器值和其它状态信息，初始化其局部数据并开始执行。
返回序列
被调用者将返回值放到与参数相邻的位置，然后恢复top-sp和其它寄存器，最后跳转到由调用者放在机器状态字段中的返回地址。
变长数据的存储分配
在现在的高级语言中，在编译时刻不能确定大小的对象将被分配在堆区。但是，如果它们是过程的局部对象，也可以将它们分配在运行时刻栈中。尽量将对象放置在栈区的原因：可以避免对它们的空间进行垃圾回收，也就减少了相应的开销。
非局部数据的访问
语言可以分为两种类型：
- 支持过程嵌套声明的语言，即可以在一个过程中声明另一个过程，如 Pascal
- 不支持过程嵌套声明的语言，不可以在一个过程中声明另一个过程。如 C 系列
无过程嵌套声明时的数据访问
- 全局变量被分配在静态区，使用静态确定的地址访问它们
- 其它变量一定是栈顶活动的局部变量。可以通过运行时刻栈的top_sp指针访问它们
有过程嵌套声明时的数据访问
访问链：可以在相互嵌套的过程的活动记录之间建立访问链，使得内嵌的过程可以访问外层过程中声明的对象。
访问链的建立：实质上就是指向自己的父亲的活动记录。
堆式存储分配
堆式存储分配是把连续存储区域分成块，当活动记录或其它对象需要时就分配。
申请
设当前自由块总长为M，欲申请长度为n
如果存在若干个长度大于或等于n的存储块，可按以下策略之一进行存储分配。
- 取长度m满足需求的第1个自由块，将长度为m-n的剩余部分仍放在自由链中（首次优先）
- 取长度m满足需求的最小的自由块（最佳优先）
- 取长度m满足需求的最大的自由块（最大优先）
如果不存在长度大于或等于n的存储块
- 如果M≥n，将自由块在堆中进行移位和重组
- 如果M<n，则应采用更复杂的策略来解决堆的管理问题
释放
只需将被释放的存储块作为新的自由块插入自由链中， 并删除已占块记录表中相应的记录即可
符号表
为每个程序块建立一个独立的符号表。
首先看一下主过程，首先，符号表有一个头部，其中第三行是主过程所需要的存储空间。
对于变量，第一列是变量名，第二列是变量类型，第三列是变量的相对地址。对于所定义的函数，有一个指针指向所定义函数的符号表，相应的，对应的函数的头部有一个指针指向主函数。
当我们需要某个符号的时候，就会跟着访问链向上访问，直到找到某个符号。（可以根据这个判断局部变量的传递）
def foo():
a = 3
def bar():
print(a)
bar()
foo()
上面的代码执行就是 3
