第7章运行环境

导读

程序的生命周期不仅包括编译阶段，还包括运行阶段。运行环境是程序执行的舞台，它决定了程序如何被加载到内存中、如何分配和管理存储空间、如何访问变量和过程、如何与其他程序交互。

理解运行环境对于编写高效、正确的程序至关重要。作为编译器设计者，你需要为目标语言设计合适的运行模型；作为程序员，你需要理解运行环境的约束来编写更好的代码。

本章将系统地介绍程序运行环境的各个方面。我们将从源程序的静态结构和动态执行的区别开始，讨论存储分配策略（静态分配、栈分配、堆分配），然后深入探讨名字到存储地址的绑定机制（活动树、活动记录、调用序列），最后讨论参数传递方式和程序访问非局部名字的机制。

通过本章的学习，你将理解为什么局部变量分配在栈上而全局变量分配在静态区，你将理解函数调用时栈帧的结构和变化过程，你将理解递归函数是如何工作的，你也将理解为什么有些语言支持指针而有些不支持。

核心概念详解

7.1 源程序的静态结构与动态执行

源程序的静态结构是指程序的文本组织——函数定义、变量声明、控制流结构等。这些结构在编译时就能确定。

程序的动态执行是指程序运行时的实际行为——函数调用序列、变量值的改变、控制流的转移等。这些行为只有在运行时才能观察到。

关键区别：

// 静态结构：函数f调用函数g
void f() {
    g();  // 静态调用关系
}

// 动态执行：实际调用序列可能不同
int main() {
    f();  // 调用序列: main → f → g
    f();  // 调用序列: main → f → g
    // 每次调用f时，g都被调用
}

过程的递归性：

非递归过程：在任意时刻，一个过程最多只有一个活动（执行实例）
递归过程：一个过程可能有多个同时活跃的活动
间接递归：过程A调用过程B，过程B又调用过程A

7.2 存储分配策略

程序运行时需要存储空间来存放代码和数据。存储分配策略决定了程序的各个部分在内存中的位置。

代码与数据分离：

高地址
┌──────────────────────┐
│     栈（Stack）       │  ← 向下增长
│        ↓             │
│                      │
│        ↑             │
│     堆（Heap）        │  ← 向上增长
├──────────────────────┤
│     BSS段            │  未初始化的全局/静态变量
├──────────────────────┤
│     数据段            │  已初始化的全局/静态变量
├──────────────────────┤
│     文本段            │  程序代码（只读）
└──────────────────────┘
低地址

三种主要的存储分配策略：

静态分配（Static Allocation）

- 所有数据对象在编译时分配固定的地址

- 优点：简单、高效

- 缺点：不支持递归、不支持动态数据结构

- 适用：FORTRAN 77、早期BASIC

栈分配（Stack Allocation）

- 局部数据在栈上分配

- 过程调用时分配活动记录，返回时释放

- 优点：支持递归、自动管理内存

- 缺点：不支持返回局部变量的引用

- 适用：C、C++、Java（局部变量）

堆分配（Heap Allocation）

- 数据在堆上动态分配

- 由程序员或垃圾回收器管理

- 优点：灵活、支持动态数据结构

- 缺点：管理复杂、可能有内存泄漏

- 适用：Java（对象）、Python、C（malloc）

7.3 活动树与活动记录

活动（Activation）是过程的一次执行实例。过程的一次调用对应一个活动的创建，过程的返回对应一个活动的终止。

活动树（Activation Tree）描述程序运行时活动的嵌套关系：

根节点是主程序的活动
每个节点是一个活动
如果活动A在执行过程中调用了过程B，则B的活动是A的子节点

示例：

int main() {
    f();
    g();
    f();
}
void f() { h(); }
void g() { }
void h() { }

活动树：

main
├── f₁
│   └── h₁
├── g₁
└── f₂
    └── h₂

活动记录（Activation Record）是栈上为每个活动分配的存储块，包含该活动所需的所有信息。

活动记录的结构（从高地址到低地址）：

┌──────────────────────┐  高地址
│   实际参数            │
├──────────────────────┤
│   返回值              │
├──────────────────────┤
│   控制链接            │  ← 调用者的活动记录地址
├──────────────────────┤
│   访问链接            │  ← 非局部变量的访问信息
├──────────────────────┤
│   保存的机器状态       │  ← 寄存器、程序计数器等
├──────────────────────┤
│   局部变量            │
├──────────────────────┤
│   临时变量            │
├──────────────────────┤
│   临时变量            │
└──────────────────────┘  低地址（栈顶）

7.4 调用序列与返回序列

调用序列（Calling Sequence）是过程调用时执行的代码，负责分配活动记录并初始化。

调用序列的工作：

调用者执行:
1. 将参数传递给被调用者
2. 保存调用者的返回地址
3. 保存调用者的栈顶指针（帧指针）
4. 跳转到被调用者的代码

被调用者执行:
5. 更新栈顶指针
6. 为局部变量分配空间
7. 保存需要保留的寄存器
8. 执行过程体

返回序列（Return Sequence）是过程返回时执行的代码，负责恢复调用者的状态。

被调用者执行:
1. 将返回值放到约定位置
2. 恢复保存的寄存器
3. 恢复栈顶指针（释放活动记录）
4. 跳转到调用者的返回地址

调用者执行:
5. 恢复帧指针
6. 继续执行

7.5 变量的访问

局部变量的访问通过帧指针（Frame Pointer, FP）偏移量来实现。

活动记录布局:
┌──────────────────────┐  FP + 12
│   参数 n             │
├──────────────────────┤  FP + 8
│   参数 x             │
├──────────────────────┤  FP + 4
│   返回地址            │
├──────────────────────┤  FP
│   旧帧指针            │  ← FP指向这里
├──────────────────────┤  FP - 4
│   局部变量 a          │
├──────────────────────┤  FP - 8
│   局部变量 b          │
├──────────────────────┤  FP - 12
│   临时变量 t1         │
└──────────────────────┘

访问局部变量 a：FP - 4

访问参数 x：FP + 8

非局部变量的访问更复杂，需要额外的机制：

7.6 访问链接（Display/Access Link）

访问链接是一种访问非局部变量的机制，主要用于嵌套过程语言（如Pascal、Ada）。

嵌套深度（Nesting Depth）：过程的嵌套层次。主程序的嵌套深度为0，直接嵌套在主程序中的过程嵌套深度为1，以此类推。

访问链接的工作原理：

每个活动记录包含一个访问链接，指向词法上直接外层过程的最近活动记录。

过程嵌套:
program P (depth 0)
    procedure A (depth 1)
        procedure B (depth 2)
            procedure C (depth 3)

当C活动时，访问链接链：

C的活动记录 → B的活动记录 → A的活动记录 → P的活动记录

访问非局部变量：

如果过程X在嵌套深度 nx 中定义，要访问嵌套深度 ny（ny < nx）中的变量：

沿访问链接走 nx - ny 步
然后用偏移量访问变量

7.7 块结构与作用域

块（Block）是允许在内部声明变量的语句组。C语言的块结构：

{
    int x = 1;
    {
        int y = 2;
        // 这里可以访问 x 和 y
    }
    // 这里只能访问 x
}

作用域规则：

词法作用域（静态作用域）：变量的可见性由程序的文本结构决定
动态作用域：变量的可见性由运行时的调用关系决定

词法作用域示例：

python

x = 10
def f():
    print(x)  # 访问全局的x，输出10

def g():
    x = 20
    f()  # 仍然输出10（词法作用域）

g()

动态作用域示例：

x = 10
def f():
    print(x)  # 访问调用者环境中的x

def g():
    x = 20
    f()  # 输出20（动态作用域）

g()

大多数现代语言使用词法作用域，因为它更可预测、更易于推理。

7.8 参数传递方式

过程调用时，实际参数（实参）到形式参数（形参）的传递有多种方式：

1. 传值（Call by Value）

将实参的值复制给形参
形参的修改不影响实参
C、Java（基本类型）使用这种方式

void swap(int a, int b) {
    int t = a; a = b; b = t;
    // 不影响调用者的变量
}

2. 传引用（Call by Reference）

将实参的地址传给形参
形参的修改会影响实参
C++的引用参数、Pascal的var参数

cpp

void swap(int &a, int &b) {
    int t = a; a = b; b = t;
    // 影响调用者的变量
}

3. 传值-结果（Call by Value-Result）

调用时复制实参的值给形参
返回时复制形参的值回实参
也称为"复制-恢复"（copy-restore）
Ada的in out参数

4. 传名（Call by Name）

形参被实参的文本替换
每次访问形参都重新计算实参
Scala的按名参数

scala

def loop(body: => Unit): Unit = {
    while (true) body  // body每次都被重新求值
}

7.9 别名问题

别名（Aliasing）是指两个或多个名字引用同一个存储位置。别名会增加程序分析的难度，可能导致意外的副作用。

别名的来源：

指针：

int x = 10;
int *p = &x;
int *q = &x;
// p和q是x的别名

传引用：

cpp

void f(int &a, int &b) {
    a = b;  // 如果a和b是同一变量，则无效果
}
int x = 10;
f(x, x);  // x是a和b的别名

数组与指针：

void f(int a[], int *p) {
    a[0] = 1;
    *p = 2;  // 可能修改a[0]
}

别名的影响：

优化困难：编译器无法确定两个指针是否指向同一位置
正确性问题：意外的副作用
分析困难：数据流分析需要考虑别名

7.10 堆存储管理

堆（Heap）是用于动态存储分配的内存区域。堆管理需要解决两个核心问题：

如何分配内存块

如何回收不再使用的内存块

内存分配策略：

首次适配（First Fit）：从堆顶开始搜索，找到第一个足够大的空闲块

- 优点：简单、快速

- 缺点：可能在低地址端积累小碎片

最佳适配（Best Fit）：找到最小的足够大的空闲块

- 优点：减少浪费

- 缺点：搜索慢，可能产生无用的小碎片

下次适配（Next Fit）：从上次分配的位置开始搜索

- 优点：均匀分布分配

- 缺点：可能产生更多碎片

垃圾回收（Garbage Collection, GC）：

自动回收不再使用的内存。核心问题是判断哪些对象是"垃圾"（不再被引用）。

引用计数（Reference Counting）：

每个对象维护一个引用计数
当引用增加时计数加1，引用减少时计数减1
计数为0时回收
优点：实时回收
缺点：无法处理循环引用，计数操作有开销

标记-清除（Mark-and-Sweep）：

从根对象出发，标记所有可达对象

扫描堆，回收所有未标记的对象

优点：能处理循环引用
缺点：产生内存碎片，需要暂停程序（Stop-the-World）

复制回收（Copying GC）：

将堆分为两个区域（From和To）

将存活对象从From复制到To

交换From和To的角色

优点：无碎片，分配快
缺点：需要双倍空间，复制开销

分代回收（Generational GC）：

基于"弱代假说"：大多数对象存活时间很短
将对象分为新生代和老年代
新生代频繁回收，老年代较少回收
Java的HotSpot JVM使用这种策略

重要知识点

7.11 栈分配的实现细节

帧指针（FP）与栈指针（SP）：

SP指向栈顶（最后分配的位置）
FP指向当前活动记录的固定位置
使用FP可以方便地访问局部变量和参数

可变大小活动记录：

当局部变量包含变长数组时，活动记录的大小在编译时无法确定。

void f(int n) {
    int a[n];  // C99变长数组
    // 活动记录大小依赖于n
}

处理方法：

在栈上动态分配变长部分
使用显示栈（explicit stack）管理

7.12 过程间的数据流

全局数据流分析需要考虑过程间的调用关系：

过程内分析：分析单个过程内的数据流
过程间分析：分析跨过程的数据流
上下文敏感分析：考虑调用上下文
上下文无关分析：不考虑调用上下文（更保守）

7.13 非局部变量的访问机制比较

机制	适用语言	优点	缺点
访问链接	Pascal, Ada	实现简单	嵌套深时访问慢
Display表	PL/I, Ada	访问速度快	维护开销大
全局变量	C, Java	简单直接	命名空间污染
闭包	ML, Haskell	灵活	需要堆分配

常见误区

误区一：栈上的数据总是安全的

栈上的数据在函数返回后就会被释放。如果返回了指向栈上数据的指针，将导致未定义行为：

int* bad_function() {
    int x = 10;
    return &x;  // 危险！x在函数返回后被释放
}

误区二：垃圾回收可以回收所有内存

垃圾回收只能回收堆上的内存，不能回收：

操作系统资源（文件描述符、网络连接等）
栈上的内存
外部资源（数据库连接等）

这些资源需要显式释放或使用RAII等机制管理。

误区三：传值总是比传引用安全

虽然传值避免了别名问题，但也有缺点：

大对象的复制开销大
无法修改调用者的数据
某些设计模式需要传引用

误区四：静态分配比动态分配总是更快

静态分配在编译时完成，运行时没有分配开销，但：

不支持递归
不支持动态数据结构
可能浪费内存（按最大需求分配）

实践应用

7.14 实际系统中的运行环境

C/C++运行时：

栈分配局部变量
malloc/free管理堆内存
程序员负责内存管理

Java运行时（JVM）：

栈分配局部变量和基本类型
堆分配对象
自动垃圾回收（分代GC）

Rust运行时：

栈分配为主
所有权系统管理内存
无垃圾回收
借用检查器在编译时防止别名问题

Go运行时：

栈分配局部变量
堆分配逃逸变量
并发垃圾回收
协程（goroutine）的栈管理

7.15 运行环境的调试

调试运行环境相关问题的方法：

内存调试工具：Valgrind、AddressSanitizer

栈跟踪：分析调用栈和函数调用序列

内存分析：分析堆内存的使用情况

泄漏检测：检测内存泄漏

本章小结

本章系统介绍了程序运行环境的各个方面。核心内容包括：

存储分配策略：静态分配、栈分配、堆分配各有适用场景。

活动树与活动记录：描述程序运行时的动态行为，活动记录是栈上的存储结构。

调用与返回序列：过程调用和返回时的状态保存与恢复机制。

变量访问：局部变量通过帧指针偏移访问，非局部变量通过访问链接或Display表访问。

参数传递：传值、传引用、传值-结果、传名各有特点。

堆管理：内存分配策略和垃圾回收算法。

理解运行环境对于编写高效、正确的程序至关重要，也是编译器设计的基础知识。

第7章 运行环境

导读