7 运行存储分配

约 3190 个字 95 行代码预计阅读时间 12 分钟

所谓的 “静态” 与 “动态” 分别对应了编译时刻与运行时刻
静态存储分配

对于在 编辑时刻 就可以确定大小的数据对象，我们可以在编译时就为其分配存储空间
动态存储分配

若在 编译时刻 不能确定数据对象的大小，我们只存储必要信息，在 运行时刻 为数据对象分配空间

一般分为栈式存储分配 & 堆式存储分配

运行时内存划分

┌-------------┐----- low
| 静态 code 区 |
├-------------┤
| 静态 data 区 |
├-------------┤-----
| Stack 区  ↓ |    ｜
├-------------┤    |
|   空闲内存   |  动态数据区
├-------------┤    |
| Heap 区   ↑ |    |
└-------------┘----- high

活动记录 Activation Record
- 使用过程（函数）作为用户自定义动作单位的语言，其编译器通常 以过程为单位 分配存储空间
- 我们将过程体的每一次执行都称为该过程的一个 “活动 Activation“，并为其分配一块连续的存储区域，用于管理本次执行所需的信息 -> 这块连续区域被称为 “活动记录”
- 活动记录的一般内容如下：
  
  实参
  
  返回值
  
  控制链（调用者活动记录）
  
  访问链（用于访问其他活动记录中的非局部数据）
  
  保存的机器状态
  
  局部数据
  
  临时变量

1 静态存储分配

在 静态存储分配 中：
- 编译器为每个过程确定其活动记录在目标程序中的位置
- 因此，每个名字的存储位置是确定的，可以被直接编译到目标代码中
- 每次执行时，名字被绑定到 固定的存储单元
使用静态存储分配的语言必须满足以下条件
- Array 的上下界为常数（数组大小确定）
- 不允许 function 的递归调用（无法确定同时生成多少个活动记录）
- 不允许动态建立数据实体（运行时不分配存储空间）

1.1 顺序分配法

在满足静态分配条件的程序里，调用函数的总量和顺序是确定的
- 我们可以按照 function 在程序中出现的先后顺序对其进行标号，并计算每一个 function 需要的存储空间长度
- 随后，按照出现顺序（标号顺序）逐段为其分配连续的存储空间（互不相交）
  
  类似于 OS 中的「段表」
分配结果的一个例子

过程编号存储区域

1 0-21

2 22-36

3 37-54

1.2 层次分配法

“顺序分配法”显然不能充分利用空间：

通过观察调用关系图，我们可以知道某几个函数之间不存在相互调用关系 => 他们不可能同时活跃！
这几个互不相干的函数可以共用同一块存储空间！

在 ”层次分析法“ 中，我们尽量使无相互调用关系过程的局部数据 共享存储空间

因为不允许嵌套调用，依赖关系中不存在环 -> 可以使用 Bottom-Up 的方法遍历
对同一 depth 上、不存在相互调用关系的几个 function，我们可以从「同一起点」开始分配
对于存在内部调用的函数，需要从 max( child[i].endAddr ) + 1 开始

层次分配算法
- 使用 ”关系调用矩阵“ B[i][j] 来表示函数间的调用关系，B[i][j] == 1 表示 \(func_i\) 调用了 \(func_j\)
- 数组 Units[n] 存放每个 function 需要的内存单元数量
- 数组 base[n] 表示局部数据区基地址
- 数组 allocated[n] 表示该局部数据是否已经分配

void allocate(int* Units, int* base, int nBlock) {
    int i, j, k, sum;
    // initialization
    int* allocated = (int*)malloc(sizeof(int) * nBlock);
    for(i=0 ; i<nBlock ; i++) {
        base[i] = 0;
        allocated[i] = 0;
    }
    // allocate
    for(j=0 ; i<nBlocks ; j++) {
        for(i=0 ; i<nBlocks; i++) {
            sum = 0;
            for(k=0 ; k<nBlocks ; k++) sum += B[i][k];
            if(!sum && !allocated[i]) {
                allocated[i] = i;
                print(i, base[i], base[i]+Units[i]-1);
                for(k=0 ; k<nBlocks ; k++) {
                    if(B[k][i]) {
                        if(base[k] < base[i]+Units[i]) {
                            base[k] = base[i]-Units[i];
                            B[k][i] = 0;
                        }
                    }
                }
            }
        }
    }
    free(allocated);
}

2 栈式存储分配

当函数被调用时，对应的活动记录被压入 Stack；结束时被弹出
这种安排允许 活跃时间不重叠 的多个过程调用之间共享过程，并且允许 非局部变量 的 相对地址固定（与调用序列无关）

活动树

用于描述程序 运行期间 进入&离开各个活动的情况

树中的每一个 node 都对应了一个活动，root 代表启动时执行的 main() 函数
对于非叶节点 p，其 childs 对应该 p 在此次活动中调用的各过程活动
- 这些被调用活动按照 调用顺序，自左向右排列
- 一个 child 必须在其 rightBrother 开始前结束

控制栈

每一个活跃的 function 都有一个位于 控制栈 中的活动记录
- 栈底：活动树的根活动记录 main()
- 栈顶：当前正在执行的函数
栈中所有的活动记录序列 == 活动树中从 root 到达当前节点的路径

活动记录

  | ┌-------------┐----- bottom of Stack ↓ 
  | | 参数 & 返回值 |   ｜
  | ├-------------┤   ｜
  └-| 控制链，访问链｜  Record of
  ┌>| 机器状态     ｜  Caller
  | ├-------------┤   ｜
  | | 局部/临时数据 |   ｜
  | ├-------------┤-----
  | | 参数 & 返回值 |   ｜
  | ├-------------┤   ｜
  └-| 控制链，访问链｜  Record of
    | 机器状态     ｜  Callee
sp->├-------------┤   ｜
    | 局部/临时数据 |   ｜
    ├-------------┤----- 
    |             |

在 Caller & Callee 之间传递的值一般放在 Callee 的开始位置（两边都比较近）
长度固定的数据被放在中间位置（控制链，访问链，机器状态）
在早起实现中，不知道大小的项放在尾部
栈顶指针 sp 实际指向的是 curFunc 中 局部数据的起始地址

3 调用/返回序列

在过程调用 / 返回阶段都需要操作活动记录栈，对机器状态进行保存/恢复
- 「调用序列」
  
  过程调用时需要执行的代码段，它在栈中为活动记录分配相应空间，并在相关字段中填写信息
- 「返回序列」
  
  过程结束时需要执行的代码段，对机器状态进行恢复，使得后续代码能够正常执行
调用 / 返回序列所包含的代码往往被分成两部分，分别塞到 Caller & Callee 中

下面是 Caller & Callee 合作的例子：

「调用序列」
1. Caller
  - 计算实参的值，并将其放在 Callee 活动记录中的指定位置
  - 将 返回地址（程序计数器值）放到 Callee 的 机器状态 字段中
  - 将原来的 sp 值放到 Callee 的 控制链 中
  - 修改 sp 的值，使其指向 Callee 局部数据开始位置
2. Callee
  - 保存 寄存器值 及其他状态信息
  - 初始化局部数据，并开始执行
「返回序列」
1. Callee
  - 将 返回值 保存到与 参数相邻 的位置
  - 使用状态链&机器状态信息，恢复 sp & 寄存器值
    
    尽管此时 sp 已经被减小了（指向 Caller）且 返回值 保存在 Callee 的记录中，但由于 Caller 知道其相对于当前sp 的偏移量，因此仍然可以正常访问
  - 跳转到机器状态中记录的返回地址（ Caller 在调用时写入的）
  - 小结
    - sp 指针由 Caller 更新，Callee 恢复
    - Callee 中的字段
  - Caller 填写：参数、控制链、机器状态（返回值）
  - Callee 填写：返回值、机器状态（寄存器及其他）

4 变长数据存储分配

在现代程序设计语言中，编译时刻 不能确定大小的对象通常被放在 Heap 中
但 函数的局部对象 （出了该函数就不可访问）可以被放在 Stack 中（运行时刻栈）

将对象放在 Stack 中可以避免对空间进行 垃圾回收 ，从而降低 overhead

以「动态数组」存储分配为例：

在编译时刻，数组长度不能确定，活动记录中指存储了指向 数组起始位置 的指针

数组本身所占空间并不是本函数活动记录的一部分，而是在本记录与下一记录之间
在运行时刻，数组指针关于 sp 的偏移量已知，可以通过指针正常访问数组

5 非局部数据访问

使用在本过程外调用的数据

我们首先将语言分为两种类型：

支持 过程嵌套声明（类 SASS）

允许在一个 function 内部声明另一个 function，如 \(Pascal\)

下面是一个 \(Pascal\) 编写的排序函数：

program sort(input, output);
    var a:array[0..10] of integer;
        x:integer;
    procedure readarray;
        var i:integer;
        begin ... a ... end {readarray};
    procedure exchange(i, j:integer);
        begin x=a[i];a[i]=a[j];a[j]=x; end {exchange};
    procedure quicksort(m, n:integer);
        var k, v:integer;
        function partition(y, z:integer):integer;
            var i, j:integer;
                begin ... a ... v ... exchange(i,j) ... end {partition};
        begin ... a ... v ... partition ... quicksort ... end {quicksort};
    begin ... a ... readarray ... quicksort ... end {sort};

在这种支持嵌套定义的语言中，过程不仅可以访问 自身定义 的局部数据、全局数据，还可以使用 外围过程 中声明的对象。
在这个例子中：
- 过程 readarray , exchange, quicksort 均可以访问由 sort 定义的 \(a, x\)
- 过程 partition 可以访问由外围过程 quicksort 定义的变量 \(v\)

不支持 过程嵌套声明（类 CSS），如 \(C\)

下面也是一个用 \(C\) 编写的排序例程：

int a[11];

void readArray() {
    int i;
    for(i=1;i<10;i++) scanf("%d", &a[i]);
}

int partition(int m, int n) {}

void quickSort(int m, int n) {
    int i;
    if(n>m) {
        i = partition(m, n);
        quicksort(m, i-1);
        quicksort(i+1, n);
    }
}

void main() {
    readArray();
    a[0] = -9999;
    a[10] = 9999;
    qicksort(1, 9);
}

在这种情况下，function 只能使用 自身定义 的局部数据和全局数据

5.1 无嵌套声明数据访问

全局变量

分配至 静态区，使用 静态确定 的地址进行访问
其他变量
- 一定是 栈顶活动 的 局部变量
- 通过运行时刻栈的 sp 指针进行访问

5.2 嵌套声明数据访问

嵌套深度

过程嵌套深度
- 不嵌套在任意过程中的过程，\(depth = 1\)
- 若过程在 \(depth=i\) 的过程中被嵌套定义，则 \(depth_p =i+1\)
变量嵌套深度

即为定义该变量的嵌套深度

访问链 Access Links

静态作用域原则

只要过程 \(b\) 的声明嵌套在过程 \(a\) 的声明中，\(b\) 就可以访问 \(a\) 中声明的变量

嵌套定义的函数只能在其父函数中被调用（其他祖先不行）
我们可以在互相嵌套的活动记录之间建立 Access Link（指针），使得内嵌过程可以访问外层过程中声明的对象
若 \(b\) 直接嵌套在 \(a\) 中被声明（\(depth_b=depth_a+1\)），则 \(b\) 的 任何活动 的 Access Link 均指向 最近的 · \(a\) 的 活动记录

当前的 \(b\) 函数一定是被尚未结束的 \(a\) 函数进程调用的（而且可以调用多次）
访问链的建立（调用序列）
- 假设过程 \(x\) 调用了过程 \(y\) ，两者的嵌套深度分别为 \(n_x,n_y\)
  - \(n_x < n_y\) 外层调内层
    
    \(y\) 一定是在 \(x\) 中直接定义的(\(n_y=n_x+1\)) => 在讲 \(y\) 的访问链指向 \(x\)
  - \(n_x == n_y\) 平级调用
    
    一定是递归调用 \(x \rightarrow x\)，直接复制
  - \(n_x > n_y\) 内层调外层
    
    过程 \(x\) 被嵌套在过程 \(z\) 中（后代过程），而 \(z\) 中直接定义了 \(y\)
    
    我们从 \(x\) 的访问链开始回溯 \(n_x-n_y+1\) 层以获取最新的 \(z\) 记录，并将 \(y\) 的访问链指向它

6 符号表

我们需要为每一个 作用域（程序块） 建立单独的符号表

符号表内容
- 本符号表中 所有变量 需要的总存储空间大小
- 定义的变量及其起始地址
- 直接嵌套声明的 函数名 及指向对应符号表的指针
为每个过程/作用域建立的符号表与编译时的活动记录是对应的，

过程中 非局部变量 的 id 信息可以通过扫描其 外围过程符号表 得到。

6.1 根据符号表构造访问链

\(n_x < n_y\)

通过直接扫描 Caller \(x\) 的符号表，可以得知 \(y\) 在 \(x\) 中被声明。

=> \(y\) 的访问链指向 \(x\)
\(n_x == n_y\) 直接复制
\(n_x > n_y\)

首先在 Caller \(x\) 的符号表中查找 \(y\) （肯定找不到），回溯至上一级；

在当前符号表中查找 \(y\)，找不到就继续回溯；

若在当前层级的符号表中找到 \(y\) => \(y\) 的访问链指向当前层级函数的活动记录

6.2 identifier 基本处理方法

在某一函数的 声明语句 中识别出了一个 \(id\) => 查找本函数的符号表
- 能查到 => Error：\(id\) 重复声明
- 查不到 => 为符号表添加新的表项，并填写相关信息
在 可执行语句 中识别出 \(id\) 时 => 从本函数开始递归回溯查询
- 能查到 => 取出相关信息进行处理
- 查不到 => Error：\(id\) 未声明

6.3 建立符号表

在 允许嵌套声明 的语言中，看到 嵌套过程 时，应暂时挂起对 外围过程声明语句 的处理

在调用一个 function 时
- 使用 makeTable(previous) 建立新的符号表，记录指向符号表的指针
  
  previous 是指向外围过程符号表的指针（最外层函数传 null 就行）
- 将新的符号表指针 tablePtr 与此时的符号表总长 offset = 0 入栈
  
  offset 记录的是关于本活动记录的相对偏移，所以初始化都是 0
识别到(单个)变量声明时
- 调用 enter(tablePtr, idName, type, offset) 在符号表中为该变量新建一条记录
- offset += curId.width
完成嵌套过程声明时
- 使用 addwidth(top(offset)) 更新当前符号表表头中记录的变量总宽度
  
  该表的变量总宽度就是此时栈顶的 offset 数值
- 将 tablePtr, offset 出栈 => 漏出外围过程的相关数据
- 调用 enterProc(top(tablePtr), subProcName, subProcPtr) 在外围过程的符号表中为嵌套过程的函数名建立记录
完成对 完整程序 的识别时
- 更新最外层函数 main() 符号表表头中记录的 totWidth
- 将最外层函数的 tablePtr, offset 出栈

实参
返回值
控制链（调用者活动记录）
访问链（用于访问其他活动记录中的非局部数据）
保存的机器状态
局部数据
临时变量

过程编号	存储区域
1	0-21
2	22-36
3	37-54