# 运行时管理

## 存储组织

1. 运行时环境：编译器为目标程序创建并管理一个运行时环境，目标程序运行在该环境中
   - 对象存储位置和空间的分配
   - 访问变量的机制
   - 过程间的连接
   - 参数传递机制

2. 运行时涉及的主要内容
   - 运行时存储空间组织管理
   - 活动树与栈式空间分配
   - 调用序列与返回序列
   - 非局部数据的访问

3. 运行时由编译器、操作系统、目标机器共同完成
   - 编译器视角：目标程序运行在逻辑地址空间
   - 操作系统视角：将逻辑地址转换为物理地址
   - 目标机器视角：真正执行指令，访问数据，同时限制了存储空间的组织和数据的访问

4. 存储分配的策略
   - 如果不能在编译时刻 **完全确定** 数据对象的大小，就要采用 **动态存储分配** 的策略，也就是在编译时刻仅产生各种必要的信息，而在运行时刻再动态地分配存储空间，这包括栈式和堆式
   - **静态** 和 **动态** 这两个概念分别对应 **编译时刻** 和 **运行时刻**

5. 影响分配策略的特征
   - 过程能否递归
   - 控制从过程返回时局部变量的值是否保留
   - 过程能否访问非局部变量
   - 过程调用参数传递方式
   - 过程能否作为参数被传递
   - 过程能否作为结果值传递
   - 存储块能否在程序控制下被动态分配
   - 存储块是否必须被显式释放

6. 过程的执行需要一些元数据，即活动记录 (过程运行所需的额外信息，如参数局部数据，返回地址等)

7. 名字的作用域
   - 一个声明起作用的程序部分称为该声明的 **作用域**
   - 即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象

8. 环境和状态
   - 环境把名字映射到左值，状态把左值映射到右值 (即名字到值有两步映射)
   - 赋值改变状态，但不改变环境
   - 过程调用改变环境
   - 如果环境将名字 $x$ 映射到存储单元 $s$，则称 $x$ 被绑定到 $s$

9. 活动记录
   - 使用过程 (函数、方法) 作为用户自定义动作的单元的语言，其编译器通常 **以过程为单位分配存储空间**
   - 过程体的每次执行成为一个活动
   - 编译器 **为每一个活动分配一个连续存储区域**，用来管理此次执行所需的信息，这片区域称为活动记录

10. 局部数据的布局
    - 字节是可编址内存的最小单位
    - 变量所需的存储空间可以根据其类型而静态确定
    - 一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配空间
    - 局部数据的地址可以用相对于活动记录中某个位置的地址来表示
    - 数据对象的存储布局还有对齐问题

11. 程序块
    - 本身具有局部变量声明的语句
    - 可以嵌套
    - 最接近嵌套作用域规则
    - 并列程序块不会同时活跃
    - 并列程序块的变量可以重叠分配

12. 静态分配
    - 名字在程序被编译时绑定到存储单元，不需要运行时的任何支持
    - 静态分配给语言带来限制
      - 递归过程不被允许
      - 数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的
      - 数据结构不能动态建立

13. 动态分配
    - 程序对数据区的需求在编译时是完全未知的，这是因为每个数据对象所需数据区的大小和数目在编译时是未知的

## 空间的栈式分配

1. 栈式存储分配
   - 对于支持过程、函数和方法的语言，编译器通常会用 **栈** 的形式来管理其运行时刻存储
   - 当一个过程被调用时，过程的活动记录被 *压入栈中*，过程结束时，记录 *被弹出*
   - 这种安排不仅允许活跃时段不交叠的多个过程调用 **共享空间**，而且可以使得过程的非局部变量的相对地址总是 **固定**，和 **调用序列无关**

2. 活动树
   - 用树来描述程序 *运行* 期间控制 *进入* 和 *离开* 各个活动情况的树
   - 树中每个 *节点* 对应一个 *活动*，*根节点* 是启动程序执行的 main 过程的活动
   - 对于一个过程，其 *子节点* 对应于被这个过程的这次活动调用的各个过程的活动，*按照调用次序*，自左向右显示它们，*一个子节点必须在其右兄弟节点的活动开始之前结束*

3. 活动树与运行栈
   - 当前活跃着的过程活动可以保存在一个栈中
   - 把控制栈中的信息拓广到包括过程活动所需的素有局部信息 (即活动记录)

4. 活动树与控制栈
   - 每个活跃的活动都有一个位于控制栈中的活动记录
   - 活动树的根节点的记录位于栈底
   - 程序控制所在的活动记录位于栈顶
   - 栈中全部活动记录的序列对应在活动树中到达当前控制所在活动节点的路径

5. 对运行栈的管理
   - 代码序列：过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态
   - 过程调用序列 (calling sequence)：过程调用时执行的分配活动记录，把信息填入它的域中，使被调用过程可以开始执行的代码
   - 过程返回序列 (return sequence)：被调用过程返回时执行的恢复机器状态、释放被调用过程活动记录，使调用过程能够继续执行的代码
   - 调用序列和返回序列常常都 **分成两部分**，分处于 **调用过程和被调用过程的活动记录中**

6. 即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异；设计这些序列和活动记录的一些原则
   - 调用者和被调用者之间交流的数据放在 *被调用者活动记录的开始处*，尽量靠近调用者的活动记录
     - **参数域** 紧邻调用者活动记录
     - **返回值** 在参数域之上
   - **固定长度的域** 放在活动记录中间
     - 控制链、访问链、机器状态
   - **不能编译时刻** 确定大小的数据一般放在活动记录的末端
     - 局部动态数组、临时数据
   - 以活动记录中间的某个位置作为基地址 (**控制链**)来记录其中的内容

7. 栈上可变长数据
   - 数据对象的长度在编译时不能确定的情况
   - 仅仅为该活动运行过程使用
   - 避免垃圾回收开销
   - 如何在栈上布局可边长数组
     - 先分配存放数组指针的单元，对数组的访问通过指针间接访问
     - 运行时，这些指针指向分配在栈顶的数组存储空间

8. 悬空引用：引用某个已被释放的存储单元

## 非局部名字的访问

1. 无过程嵌套的数据访问
   - 过程体中的非局部引用可以直接使用静态确定的地址 (非局部数据此时是全局数据)
   - 局部变量在栈顶的活动记录中，可以通过 `base_sp` 指针访问
   - 无须深入栈中取数据，无须访问链

2. 有过程嵌套的静态作用域
   - 一个过程的声明包含另一个过程的声明，嵌套的子过程可以使用父过程的局部变量
   - 子过程代码被激活执行，要找到父过程的活动记录，需要建立访问链

3. 嵌套深度
   - 过程嵌套深度：主程序为 1，进入一个被包围的过程加 1
   - 变量的嵌套深度：声明所在过程的嵌套深度为该名字的嵌套深度

4. 过程嵌套的静态作用域在活动记录中增加访问指针形成访问链
   - 用来寻找非局部名字的存储单元
   - 假设 p 直接嵌套在 q 中，则 p 活动记录的访问链指针指向最靠近的 q 的活动记录

5. 两个关键问题需要解决
   - 通过访问链访问非局部引用
   - 访问链的建立

6. 过程 p 的嵌套深度 $n_p$，引用嵌套深度为 $n_a$ 的变量 a
   - 追踪访问链 $n_p-n_a$ 次
   - 到达 a 所在的活动记录
   - 访问链的追踪可以间接操作完成

7. 过程 p 的嵌套深度 $n_p$，调用嵌套深度为 $n_x$ 的过程 x
   - $n_p<n_x$，x 在 p 中，被调用过程的访问链必须hi想调用过程的活动记录的访问链
   - $n_p\geqslant n_x$，找到公共祖先，也就是过程 x 的最近的 $n_x-1$ 深度的过程，沿着访问呢连追踪 $n_p-n_x+1$ 次

8. 参数传递
   - 形参，存储单元 (左值)，引用调用
   - 实参，存储内容 (右值)，传值调用

9. 堆管理
   - 堆用于存放生命周期不确定、或生存到明确删除为止的数据对象
   - `new` 生成的对象可以生存到被 `delete` 为止
   - `malloc` 申请的空间生存到被 `free` 为止

10. 分配/回收堆空间的子系统
    - 分配：为内存请求分配一段连续、适当大小的堆空间
      - 首先从空闲的堆空间选择
      - 若内存紧张，可以回收一部分内存 (C/C++ 需要手动回收，Java 可以自动回收空间)
    - 评价指标：空间效率、程序效率、管理效率