运行存储分配策略
- 静态存储分配:在编译时刻就可以确定大小的数据对象,可以在编译时刻就为它们分配存储空间。
- 动态存储分配:编译时无法完全确定数据对象的大小,在运行时刻,再动态地分配数据对象的存储空间。主要有栈和堆式存储分配。
活动记录
使用编译器通常以过程(函数,方法)为单位分配存储空间,过程体的每次执行称为该过程的一个活动。
过程每执行一次,就为它分配一块连续存储区,用来管理过程一次执行所需的信息,这块连续存储区称为活动记录。活动记录的形式一般如下:
静态存储分配
在静态存储分配中,编译器为每个过程确定其活动记录在目标程序中的位置。这样,过程中每个名字的存储位置就确定了。
因此,这些名字的存储地址可以被编译到目标代码中。过程每次执行时,它的名字都绑定到同样的存储单元。
适合静态存储分配的语言必须满足以下条件:
- 数组上下界必须是常数
- 不允许过程的递归调用
- 不允许动态建立数据实体
满足这些条件的语言有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