前言

参考课上PPT内容。 该学习笔记目前仅打算个人使用。

后续会进一步整理，包括添加笔记内容，标明参考资料。


更新中。。。

跳过目录
目录
一、动态存储分配
思路
二、活动记录（AR）
1、局部数据区
2、参数区
3、display区
1. 变量二元地址
BL
ON
2. 运行栈的部分追踪
活动记录基指针abp
运行过程
3. 不同语言中display区的效果
4. 建造display区的规则
5. 运行时的地址计算



一、动态存储分配

在编译时生成相应的目标程序，在目标程序运行时才进行分配
编译时要生成进行动态分配的目标指令

常使用栈式动态存储分配
思路
程序对数据区的需求在编译时是完全未知的，这是因为每个数据对象所需数据区的大小和数目在编译时是未知的。
但是，当它们在运行中进入一个程序模块时，该模块所需的数据区大小必须是已知的。
类似地，数据对象的多次出现也是允许的，只要在运行时，每当进入一个程序模块就为其分配一个新的数据区。
正如前面的讨论所指出的，动态存储分配在很大程度上是一种面向模块的方法，因此，可用于像C、C++、Java、Pascal、PL/1、ALGOL这样的分程序结构的语言。
分程序的嵌套性质
使用一个类似于栈的数据区（通常称为运行栈）来实现：

程序内的每个程序模块都有自己的数据区
在程序运行中，当模块被调用时，可从总的数据区中（即从运行栈中）请求一个空间作为它的数据区，并保留该空间直到执行完整个模块时为止
待模块执行完毕以后，就释放它占用的数据空间（即从运行栈中弹出）
从模块被调用到它运行结束之间，还可以通过过程调用或程序块入口"BEGIN"进入其他模块，那么也可按刚才所介绍的方法将这些模块的数据区压入运行栈
当程序运行返回到开始调用模块的地方时，运行中的格局和内容也就立即恢复到调用之前的情况

对于分程序结构，而且允许递归调用的语言，，即使用一个类似于堆栈的“运行栈”来实现数据区的分配。
分配策略：整个数据区为一个堆栈

(1) 当进入一个过程时，在栈顶为其分配一个数据区。

(2) 当退出一个过程时，撤消该过程的数据区。
例1：通过图对运行栈的追踪来说明活动记录的作用。




当进入该程序模块时，在运行栈上就为第一个 BBLOCK 创建一个活动记录，如(a)所示。
在 BBLOCK 中调用名为 M1 的PBLOCK，于是将标志为AR2 的 M1 的活动记录压入栈中，如(b)所示。
在执行M1的过程中，调用名为M2 的 PBLOCK，此时活动记录 AR3 入栈，如 (c) 所示。
假如再进入M2之内的BBLOCK，则又一个新的活动记录 AR4 将压入栈内，如(d)所示。
当编号为4的BBLOCK一执行完，活动记录AR4即从运行栈中弹出，因为出该模块以后，该模块的变量已不再可以访问了。
随着程序的继续运行和其余模块的运行结束，相应的活动记录AR3，AR2和AR1也将以与AR4相同的方式相继从栈中弹出。
二、活动记录（AR）
由图可知，运行栈上的动作与一个普通的堆栈上的动作相同。
当进入一个程序模块时，譬如说进入模块i，就在运行栈的栈顶创建一个专用数据区，该数据区通常称为活动记录（Activation Record，用ARi表示），它包含保存局部于该程序模块的变量的值所必需的存储空间。
活动记录基：一个活动记录的开始位置称为活动记录的基。
当该模块执行结束时（即到达模块的出口），则其相应的活动记录从运行栈的栈顶除去，因为在模块 i 中所定义的变量在该模块的外部是不能进行访问的。
一个典型的活动记录可以分为三部分：

局部数据区
参数区
display区



1、局部数据区
存放模块中定义的各个局部变量。
2、参数区
用于存放隐式参数和显式参数。
分为：

隐式参数区
显式参数区



形参数据区：每一形参都要分配数据空间，形参单元中存放实参值或者实参地址。
ret addr：返回地址，即调用语句的下一条执行指令地址。
prev abp：指向前个活动记录基的指针（previous active record base pointer，）
ret value：返回值（无值则空）

3、display区

虽然在C、C++、Java等语言中已经不再需要利用display区访问外层变量，因为它们对嵌套程序之间的相互调用做了更严格的限制甚至禁止，但是在Pascal等语言中， display区是一种巧妙且快速访问外部变量的重要机制。

为了访问到对当前模块来说是全局变量的每个变量，需要在display区保留一些必要的信息
它由一系列指针组成，每一个指针指向一个模块的活动记录的开始位置，而这个模块对于当前正在执行的模块来说是全局的。
例：


当执行编号为4的模块时，在模块1和模块3中所声明的变量可以作为全局变量访问。
所以，当模块4被激活时所建立的display区应包括两个指针：

一个指向模块1的活动记录的开始位置
另一个指向模块3的活动记录的开始位置

1. 变量二元地址
对于分程序结构语言，通常采用一个包含有分程序的层次（BL）域和（ON）域的二元编址方案。
使用二元地址和display区可在运行栈中找到变量的值。
变量二元地址：(BL, ON)
BL

变量声明所在的层次。
模块的层次号
可以用它找到该层数据区开始地址。
注意为嵌套层次
并列过程具有相同层次

ON

变量出现的顺序号
相当于显示参数区开始位置的位移（相对地址）。

例：



程序块1（最外层BBLOCK）

X：(1, 0)
Y：(1, 1)
NAME：(1, 2)

过程块M1

IND：(2, 0)
X：(2, 1)

注：

模块的层次号（BL）取2是因为M1的嵌套深度为2
从0开始来计算变量的序号（ON）。

高层（内层）模块可以引用低层（外层）模块中的变量

包含该变量单元的活动记录能够间接通过当前活动记录中display区中的相应指针来引用。

例：在M1中可引用外层模块中定义的变量 Y。

在 M1 中引用Y时，可通过其 display 区找到程序块 1 的活动记录基地址，加上 Y 在该数据区的相对地址就可以求得 Y 的绝对地址。
例：最外层所声明的变量X被处在内部的编号为4的模块引用


X：(1, 0)
X的模块层次号（1）将小于当前模块的层次号（4）。
变量X的地址可以通过对BL=1和display区第一个元素的引用，并使用该活动记录的基指针值加上用于确定在最外层的变量X在活动记录中的位置的序号0求得。
2. 运行栈的部分追踪
活动记录基指针abp
活动记录基指针abp记录当前执行模块的活动记录的开始位置
运行过程
1、进入模块1
程序的运行将从编号为1的BBLOCK开始。



指针abp记录当前执行模块的活动记录的开始位置

注：

该块的活动记录中并不包括display区

因为对该模块来说并不存在外层的全局变量
也没有参数区

因为没有其他模块来调用它
实际上也可以有一个参数区：

在该区中保存返回到操作系统的返回地址
同时，外部参数也可以通过该参数区传递给该程序。



2、M1被调用
当过程块M1被调用时，就建立一个单元素的display区



指针abp(1)：称为活动记录基指针，指向编号为1的模块的活动记录的开始位置（基）。


该display元素方便了全局变量X、Y和NAME的引用。


ret addr(1) ：标识返回地址，表示在执行M1以后控制要返回的地址。


prevabp：前一个活动记录基指针，存放到参数区中。指向其调用模块，即编号为1模块的活动记录（AR1）的开始位置。


IND：要赋给形式参数IND的值，存放到参数区中。


3、调用过程块M2



display区：单元素，与前一个display区一样（abp(1)）

因为过程块M2的全局变量与过程块M1的相同，也就是在编号为1的模块中所声明的那些变量。

至于在进入一个模块时如何建立该模块的display区将在随后介绍。
prevabp：前一个活动记录基指针，存放在参数区。指向其调用模块，即过程块M1的活动记录（AR2）的开始位置。

4、进入内模块4（BBLOCK）

创建的display区将包含：

abp(1)：指向模块1（BBLOCK）的活动记录的开始位置
abp(3)：指向过程M2（编号为3）的活动记录的开始位置

所以，变量X、Y、NAME和J这些全局于编号为4的基本块的所有变量都可通过相应的display区进行访问。
5、内模块4（BBLOCK）执行完以后，控制转向过程块M2
已执行完的基本块的活动记录从逻辑上必须从运行栈中除去，以便使运行栈恢复到该基本块执行以前的状况。
为此，要把活动记录基指针abp值重新设置为"prevabp"，使abp指向过程块M2的活动记录AR3的开始位置

重新设置活动记录基指针的过程必须在模块的执行结束和控制转到前一个活动模块前进行。



3. 不同语言中display区的效果
display区对于Pascal，ALGOL等具有分程序结构的语言而言，在程序运行时访问其他模块中定义的变量具有显著的加速效果。
而当前常用的其他语言，例如C、C++、Java等，如果语言本身不支持或者限制嵌套分程序之间的相互调用，编译器在编译时能够对被访问变量的存储地址进行定位，那么display区的存在就没有必要了。
存放各外层模块活动记录的基地址。
4. 建造display区的规则
从 i 层模块进入（调用）第 j 层模块：
1、若 j = i + 1

即进入一个BEGIN类型的模块或调用当前模块局部声明的过程块


复制 i 层模块的display区，然后增加一个指向 i 层模块活动记录基的指针abp。

2、若 j ≤ i

即调用外层模块或同层模块


来自 i 层模块活动记录中的display区前面 j - 1 个入口将组成 j 层模块的display区。

5. 运行时的地址计算
给定一个要访问的变量，具有地址 (BL, ON) ，该变量是在LEV层的一个模块中。
该变量的地址ADDR计算公式：
if (BL == LEV)
    ADDR = abp + (BL - 1) + nip + ON;
else if (BL < LEV)
    ADDR = display[BL] + (BL - 1) + nip + ON;
else
	printf("地址错，不合法的模块层次");



abp：指当前活动记录基指针值


display[BL]：指当前活动记录display区中第BL个元素，nip指隐式参数的数目


(BL - 1) ：display区的大小（即在BL层上的一个程序块必有BL-1大小的display区）


nip：隐式参数区大小


由于 (BL - 1) 和 nip 在编译时是已知的，因此，某些编译程序是先计算出 (BL-1) + nip，然后将它们加到ON中去。这种方法降低了运行时地址计算的复杂性。

局部变量可按 abp + ON 计算
全局变量按 display[BL] + ON 计算