运行时存储空间的组织与管理

域	用途
临时数据	保存临时值，比如寄存器不足时，将计算的中间结果存放在这
局部数据	保存本过程内部定义的局部变量
保存的机器状态	用于保存本过程调用前的机器状态
访问链	通过访问链访问非局部数据
控制链	指向调用者的活动记录
返回值	存放本过程返回给调用过程的值
参数	存放调用过程提供的实在参数

#局部数据的布局

字节是可编址内存的最小单位。

一个过程所声明的局部变量，按这些变量声明时出现的次序，在活动记录的局部数据区中依次分配空间。

局部数据的地址可以用相对于某个位置（本过程对应的活动记录的起始位置）的偏移来表示。

数据对象的存储安排深受目标机器寻址方式的影响，存在对齐问题。例如，要求整数（int，long）的相对地址可以被 4 整除。

由于对齐而引起的无用空间称为衬垫空白区。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


// 对于以下两个结构体，因为衬垫区的存在，其size不同
struct s1{
    char   c1;
    char   c2;
    int    i1;
    double d1;
};
struct s2{
    char   c1;
    int    i1;
    double d1;
    char   c2;
};

#全局栈式存储分配

#运行时内存空间的划分

区	用途
代码	存放目标代码（.exe）
静态区	全局变量，静态变量等
堆	动态分配的内存
空闲内存	为堆和栈提供动态支持
栈	活动记录

堆和栈是动态的，在它们占用的存储空间不断变化时，相向增长。在实际机器中，堆向高地址增长，栈向低地址增长。

#内存分配策略

#静态分配策略

名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。

绑定的生存期是程序的整个运行时间。

控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。

每个活动记录的大小是固定的。

过程调用时保存信息的地址在编译时也是已知的。

#栈式分配策略——活动树和运行栈

栈式分配主要用于管理过程的活动记录。

局部变量的生存期是过程活动的时间。

控制进入该过程时，局部变量绑定到存储单元，过程活动结束后，局部变量的空间释放。

#活动树

每个结点代表某过程的一个活动
根结点代表主程序的活动
结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动
结点a 处于结点b 的左边，当且仅当a的生存期先于b的生存期

活动的执行顺序（程序的控制流）对应活动树的后根遍历（深度优先）。

#运行栈

把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）。不要把静态的数据画在运行栈里。

#栈上可变长数据

活动记录的长度在编译时不能确定的情况。🌰局部数组的大小要等到过程激活时才能确定。

解决方案：

编译时，在活动记录中为这样的数组分配存放数组指针的单元。

运行时，这些指针指向分配在栈顶的数组存储空间。

运行时，对数组的访问都要通过相应指针来间接访问。

#悬空引用

引用某个已被释放的存储单元

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


int* dangle(){
    int i = 20;
    return &i;  // return之后，i的存储单元被释放掉了
}

int main(){
    int* p;
    p = dangle();
    return 0;
}

#堆式分配策略

内存分配与释放按照任意次序进行。

堆中可能包含交错的正在使用的和已经释放的区域。

#三种分配策略的比较

\	静态分配	栈式分配	堆式分配
使用范围	外部变量、静态局部变量、常量	局部变量、形参	动态变量
分配时间	程序开始前	进入过程前	用户决定
释放时间	程序结束后	过程结束	用户决定
地址计算时间	编译时	运行时	运行时
存取速度	快	慢	慢

#非局部名字的访问

#静态作用域

#无过程嵌套的静态作用域

由于没有过程嵌套，声明在过程外的所有变量都可以分配在静态区。过程体中的非局部引用可以直接使用静态确定的地址（非局部数据此时就是全局数据）。

#有过程嵌套的静态作用域

#过程嵌套深度

设主程序的嵌套深度为 1，从一个过程进入一个被包围的过程时，嵌套深度加 1。

变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度。

#访问链（静态链）

如果过程 p 直接嵌在过程 q 中，那么过程 p 的活动记录的访问链直接指向最靠近的属于过程 q 的活动记录的访问链。

假定过程 p 的嵌套深度为 $n_p$，它调用嵌套深度为 $n_x$ 的过程 x:

(1) $n_p < n_x$。表明被调用过程比 p 嵌的更深，而且过程 x 肯定嵌在过程 p 里，否则无法调用。这种情况下需要追踪访问链 $n_x-n_p$ 次。

(1) $n_p \geq n_x$。追踪访问链 $n _ { p } - n _ { x } + 1$ 次到达了静态包围 x 和 p 的且离它们最近的那个过程的最新活动记录。所到达的访问链就是 x 的活动记录中的访问链应该指向的那个访问链。

#动态作用域

被调用过程的非局部名字a和它在调用过程中引用的是同样的存储单元。

新的绑定仅为被调用过程的局部名字建立，这些名字在被调用过程的活动记录中占用存储单元。

总结的说，动态作用域就是谁调用的找谁。

#参数传递

#值调用

实参的右值传给被调用过程。把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中。调用过程计算实参，并把右值放入形参的存储单元中。

对形参的任何操作不会影响调用者实参的值。

#引用调用

实参的左值传给被调用过程。把实参的左值放入形参的存储单元。在被调用过程的目标代码中，任何对形参的引用都是通过传给该过程的指针来间接引用实参的。

对形参的任何赋值都会影响调用者实参的值。

#换名调用

用实参表达式对形参进行正文替换。

program main(input,output);
    var a,b: integer;
    procedure p(x,y,z: integer);
        begin
        y:＝y+1;
        z:＝z+x;
        end;
    begin
        a:＝2;
        b:＝3;
        p(a+b, a, a);
        print a;
    end．
{值调用结果为2，不改变实参值}
{引用调用结果为8，a+b的结果5放在临时变量中，传参时将临时变量地址传过去}
{换名调用可以看作是执行a=a+1;a=a+(a+b);注意在第二条语句中右边的每一个a都等于3}

运行时存储空间的组织与管理

相关文章：