第7章 运行时环境

运行时环境负责管理目标计算机的寄存器和存储器，为程序执行提供内存分配、变量访问和过程调用机制。

7.1 程序执行时的存储器组织

存储器布局

程序运行时，存储器通常分为代码段、静态数据区、栈区和堆区。

三种运行时环境

类型 特点 典型语言 分配方式
完全静态 无递归、无动态分配、无指针 FORTRAN 77 全部预分配
基于栈 递归、局部变量动态分配 C、Pascal、Ada 栈式分配活动记录
完全动态 自动内存管理、垃圾回收 LISP、Smalltalk 堆分配为主

7.2 完全静态运行时环境

特点

  • 所有变量（全局和局部）均为静态分配
  • 每个过程只有一个活动记录，执行前分配
  • 通过固定地址直接访问所有变量

调用序列

调用者：
1. 计算自变量 → 保存到被调用过程的参数位置
2. 保存返回地址
3. 跳转到被调用过程

被调用者：
1. 执行代码
2. 将返回值放入指定位置
3. 跳转回返回地址

7.3 基于栈的运行时环境

活动记录（Activation Record / Stack Frame）

活动记录典型布局：
┌──────────────┐
│  实参（参数）   │
├──────────────┤
│  返回值地址    │
├──────────────┤
│  控制链（old FP）│  ← 帧指针 fp
├──────────────┤
│  访问链       │
├──────────────┤
│  保存的寄存器  │
├──────────────┤
│  局部变量      │
├──────────────┤
│  临时变量      │
└──────────────┘
                     ← 栈指针 sp

调用序列（Calling Sequence）

调用者：
1. 计算实参并压入栈
2. 将返回地址压入栈
3. 跳转到被调用过程

被调用者：
1. 保存旧 fp（控制链）
2. 将 sp 复制到 fp（建立新的帧指针）
3. 增加 sp（为局部变量和临时变量分配空间）
4. 保存需要的寄存器
5. 执行过程体
6. 恢复寄存器
7. 恢复 fp 和 sp
8. 跳转到返回地址

嵌套过程和访问链（Access Link）

  • 问题：嵌套过程如何访问外层过程的变量？
  • 解决方案：
    • 访问链（静态链）：每个活动记录中保存指向直接外层活动记录的指针
    • Display 表：从栈外数组保存每层嵌套的最新活动记录指针
  • 访问链的长度 = 嵌套深度差

7.4 动态存储

堆（Heap）分配

  • 用于动态创建的数据结构（链表、树、对象等）
  • 手动管理：malloc/free（C）、new/delete（C++）
  • 自动管理：垃圾回收

垃圾回收（Garbage Collection）

标记-清扫（Mark-and-Sweep）

第1遍（标记）：从根集出发，标记所有可达对象
第2遍（清扫）：遍历堆，回收所有未标记的对象

引用计数（Reference Counting）

  • 每个对象维护引用计数
  • 计数归零时立即回收
  • 缺点：无法处理循环引用

停止-复制（Stop-and-Copy）

  • 将堆分成两半
  • 只使用一半，满了后将存活对象复制到另一半
  • 自动压缩内存（消除碎片）

7.5 参数传递机制

机制 含义 典型语言
传值（call by value） 传递实参的值（副本） C（默认）、Pascal（val）
传引用（call by reference） 传递实参的地址 C++（&）、Pascal（var）
传结果（call by result） 返回时复制值到实参 Ada（out）
传值-结果（call by value-result） 进入时复制值，返回时复制回 Ada（in out）
传名（call by name） 文本替换（thunk） Algol 60

传值 vs 传引用对比

void swap_val(int x, int y) {
    int t = x; x = y; y = t;  // 不影响实参
}

void swap_ref(int &x, int &y) {
    int t = x; x = y; y = t;  // 交换实参
}

7.6 TINY 语言的运行时环境

  • TINY 无递归、无嵌套过程 → 可用完全静态环境
  • 但 TM 机使用基于栈的环境（为 C-Minus 准备）
  • TINY 环境简单：变量固定位置、无活动记录管理

考试重点

★★★ 第一梯队

考点 典型题型
活动记录的布局图 标出各字段（参数、控制链、返回地址、局部变量等）

★★☆ 第二梯队

考点 典型题型
三种运行时环境的对比 静态 vs 栈式 vs 动态
调用序列 调用者和被调用者的职责划分
访问链 嵌套过程中的变量访问路径
参数传递机制 传值 vs 传引用经典对比题
垃圾回收的标记-清扫算法 算法步骤

★☆☆ 第三梯队

考点 典型题型
引用计数 vs 停止-复制 对比
TINY 运行时环境 简答