运行时环境

编译器的工作不止于"翻译代码"——源语言中的各种抽象(变量、函数调用、作用域、对象)在运行时需要一套协议和数据结构来支撑。这套协议就是运行时环境(Runtime Environment)。 具体来说,运行时环境负责回答以…

📖 阅读指南

知识依赖链(建议按此顺序阅读):

1
2
3
4
5
第四章:中间代码生成(三地址码、类型系统)
    └─ 理解"变量"、"过程调用"的编译期表示
            └─ 本章:运行时环境(这些抽象在运行时如何落地)
                    ├─ 5.2 存储管理(核心:栈帧结构与堆分配)
                    └─ 5.3 垃圾回收(核心:可达性与四种 GC 算法)

阅读重点提示:

  • 5.2.2 节的活动记录结构和调用/返回序列是核心,务必结合 5.5 的图解理解
  • 5.2.3 节的访问链 vs 显示表是嵌套语言(Pascal/ML)的特有难点
  • 5.3 节四种 GC 算法需要横向对比,关注各自解决的问题和引入的新问题
  • 5.4 节 Java 四种引用类型是工程考点

5.1 运行时刻环境概述

问题动机

编译器的工作不止于”翻译代码”——源语言中的各种抽象(变量、函数调用、作用域、对象)在运行时需要一套协议和数据结构来支撑。这套协议就是运行时环境(Runtime Environment)。

具体来说,运行时环境负责回答以下问题:

问题 对应机制
变量在哪里?(局部 / 全局 / 嵌套) 存储分配策略 + 访问机制
函数调用/返回如何工作? 调用序列 + 活动记录
参数如何传递? 参数传递协议(值传递/引用传递)
动态分配的内存怎么管理? 堆管理 + 垃圾回收
如何与操作系统交互? ABI(Application Binary Interface)

关键洞察:编译器生成的代码要正确运行,前端(语义分析)和后端(代码生成)必须就运行时环境的结构达成共识。运行时环境是两者之间的隐性契约。


5.2 存储管理

5.2.1 存储分配基础

内存的三大区域

程序运行时的内存(虚拟地址空间)分为三个区域,各有不同的生命期管理策略:

1
2
3
4
5
6
7
8
9
10
11
12
13
高地址
┌──────────────────┐
│      堆(Heap)   │  ← 向高地址增长(malloc/new)
│        ↓         │
│   (空闲区域)    │
│        ↑         │
│      栈(Stack)  │  ← 向低地址增长(函数调用)
├──────────────────┤
│   静态/全局区     │  ← 编译时分配,程序全生命期
├──────────────────┤
│      代码区       │  ← 只读,存放可执行指令
└──────────────────┘
低地址
区域 内容 大小确定时机 生命期
代码区 可执行目标代码 编译时 程序全生命期
静态区 全局变量、常量、编译器辅助数据(如 GC 信息表) 编译时 程序全生命期
栈 函数调用的局部变量、参数、返回地址 运行时(LIFO 管理) 函数调用期间
堆 动态分配的对象(new/malloc) 运行时(显式/GC 管理) 不定(直到回收)

三种分配策略

① 静态分配:大小编译时已知,分配在固定地址(静态区)。C 语言的全局变量、static 局部变量均属此类。

② 栈式动态分配:与过程调用/返回同步管理(LIFO)。局部变量的生命期 = 过程的生命期。优点:分配/释放代价极低(仅移动栈指针)。

③ 堆动态分配:数据生命期不确定,可能超过创建它的过程。需要显式管理(C/C++)或垃圾回收(Java/Python/Go)。

内存对齐与补白(Padding)

1
2
3
4
5
6
7
8
struct S {
    char  a;   // 1 字节,offset = 0
    // [3字节补白]  ← 因为 int 需要 4 字节对齐
    int   b;   // 4 字节,offset = 4
    char  c;   // 1 字节,offset = 8
    // [7字节补白]  ← 因为 double 需要 8 字节对齐
    double d;  // 8 字节,offset = 16
};             // 总大小 = 24 字节(非 1+4+1+8=14)

工程影响:结构体字段顺序影响内存占用。将大字段放前面可以减少补白(如 double, int, char 只需 16 字节)。


5.2.2 栈式分配

5.2.2.1 活动树

为什么用栈管理过程调用?

过程调用天然具有时间嵌套性:后调用的过程必然先返回(LIFO)。这与栈的语义完全吻合。

活动树(Activation Tree):用树结构表示程序运行期间所有过程活动的调用关系:

  • 每个节点 = 一次过程活动(注意:同一过程的递归调用是不同的活动)
  • 根节点 = main 的活动
  • 子节点从左到右 = 被调用顺序
  • 关键约束:子节点必须在其右兄弟开始前结束(LIFO 保证)
1
2
3
4
5
6
7
8
9
10
11
示例程序:main 调用 p,p 调用 q,p 还调用 r

活动树:
        main
        /
       p
      / \
     q   r       ← q 必须在 r 开始前结束

调用序列(前序遍历):main → p → q → r
返回序列(后序遍历):q → r → p → main

关键洞察:任意时刻,控制栈中所有活动记录的序列 = 活动树中从根到当前活动节点的路径。这是栈正确性的直观证明。

5.2.2.2 活动记录(栈帧)

每个活跃的过程活动在栈中对应一个活动记录(Activation Record / Stack Frame):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
一个完整的活动记录布局(从低地址到高地址):

  ┌─────────────────────┐ ← 调用者的 top_sp 处
  │   实在参数          │  调用者传入的参数值
  ├─────────────────────┤
  │   返回值            │  被调用者将结果放这里
  ├─────────────────────┤
  │   控制链            │  → 指向调用者的活动记录(用于恢复栈帧)
  ├─────────────────────┤
  │   访问链            │  → 指向外层过程的活动记录(嵌套语言需要)
  ├─────────────────────┤
  │   机器状态          │  保存的寄存器 + 返回地址(eip/PC)
  ├─────────────────────┤  ← top_sp 指向此处(定长字段末端)
  │   局部数据          │  本次活动的局部变量(大小编译期已知)
  ├─────────────────────┤
  │   临时值            │  表达式求值的中间结果
  └─────────────────────┘
  │   变长数据          │  变长数组等(top 指向此区域末端)

两个关键指针:

指针 含义 用途
top_sp 指向定长字段末端 以固定偏移访问定长数据(局部变量、参数等)
top 指向实际栈顶 标识下一个活动记录起始位置

为什么需要两个指针? 当活动记录中存在变长数据(如 C99 VLA)时,top_sp 固定不变(定长部分),top 随变长数据移动。定长数据的访问始终用 top_sp + 编译期已知偏移,保证高效。

各字段放置原则:

  • 传递的参数靠近调用者记录(便于调用者在自己的帧中准备参数)
  • 固定长度字段(控制链、访问链、寄存器状态)在中间
  • 大小未知的字段(变长数组)放末尾,在 top_sp 以外

5.2.2.3 调用/返回代码序列

调用一个过程涉及调用者(Caller)和被调用者(Callee)双方的协作。

调用代码序列(Calling Sequence):

1
2
3
4
5
6
7
8
9
10
11
12
调用者负责:
  1. 计算所有实在参数的值
  2. 在被调用者的活动记录区域写入:
     - 实在参数
     - 返回地址(调用指令的下一条指令地址)
     - 保存当前 top_sp(控制链)
  3. 增加 top_sp,跳转到被调用者代码

被调用者负责:
  4. 保存调用者的寄存器状态(机器状态字段)
  5. 初始化局部变量
  6. 开始执行函数体

返回代码序列(Return Sequence):

1
2
3
4
5
6
7
8
被调用者负责:
  1. 将返回值写入指定位置
  2. 从机器状态字段恢复 top_sp 和寄存器
  3. 跳转到返回地址

调用者负责:
  4. 从返回值位置取出结果(若有)
  5. 继续执行调用点后的代码

工程原则:尽量把代码放在被调用者中,而非调用者中。原因:同一函数可能在 n 个调用点被调用,若代码在调用者,则每个调用点都生成一份,代码膨胀 n 倍;被调用者的代码只有一份。

这也是为什么 ABI 通常规定”被调用者保存寄存器”(callee-saved registers)——由被调用者统一保存/恢复,节省调用者代码量。

5.2.2.4 栈中的变长数据

场景:C99 的变长数组(Variable Length Array, VLA)——大小在运行时确定。

1
2
3
4
void f(int n) {
    int a[n];   // VLA:大小运行时才知道
    ...
}

处理方式:VLA 生命期局限于函数活动期 → 可以放在栈上,但不属于活动记录的固定部分,位于 top_sp 以外(top 指针以内)。

1
2
3
4
5
6
7
8
函数 f 的栈布局:

  ┌─────────────────────┐
  │  固定部分(参数n、  │ ← top_sp 在此
  │  控制链、局部变量等)│
  ├─────────────────────┤
  │  int a[n](VLA)    │ ← 运行时确定大小,紧跟固定部分之上
  └─────────────────────┘ ← top 在此

访问 VLA 中的元素:需要先通过指针(存放在固定部分)间接寻址,不能用常数偏移。


5.2.3 非局部数据的访问

无嵌套过程(C 语言模型)

C 语言不允许函数嵌套定义,因此只有两种变量:

  • 局部变量:在本函数的活动记录中,top_sp + 编译期已知偏移 直接访问
  • 全局变量:在静态区,地址编译时已知,直接访问

函数作为参数传递时,只需传入代码起始地址(函数指针),无需额外的环境信息。

嵌套声明过程(Pascal / ML / Ada 模型)

当语言允许函数嵌套定义,内层函数需要访问外层函数的局部变量。

1
2
3
4
5
6
7
8
9
procedure outer;
    var x: integer;
    procedure inner;
    begin
        x := x + 1;   (* inner 访问 outer 的局部变量 x *)
    end;
begin
    inner;
end;

问题:inner 执行时,outer 的活动记录在栈中的哪里?

⚠️ 反直觉点:inner 的访问链不一定指向调用者的活动记录(控制链),而是指向词法上的外层过程的活动记录。两者在递归等场景下不同!

嵌套深度(Nesting Depth):编译时静态确定的概念。

1
2
不嵌套在任何过程中的顶层过程:深度 = 1
嵌套在深度 i 的过程中定义的过程:深度 = i + 1

每个活动记录中增加一个”访问链”指针,指向词法上直接外层过程的最近一次活动记录。

访问外层变量的步骤:

设当前过程深度为 np,被访问变量 x 声明在深度 nq 的过程中(nq < np):

  1. 从当前活动记录出发,沿访问链走 np - nq 步,到达深度 nq 的活动记录
  2. 以 x 的编译期已知偏移访问 x
1
2
3
4
5
6
7
8
9
10
示例(深度差 = 2):

当前记录(深度3)
    │ 访问链
    ↓
中间记录(深度2)
    │ 访问链
    ↓
目标记录(深度1)
    └─ x 在此处(偏移量编译期已知)

访问链的维护规则:

场景 如何设置被调用者的访问链
p 直接定义在 q 内(深度 p = 深度 q + 1) → 指向当前(q 的)活动记录
递归调用(p 调用自身) → 等于当前活动记录的访问链(指向同一外层)
p 定义在 r 中,通过 q(嵌套在 r 中)传递调用 → 指向栈中最顶部的 r 的活动记录

传递过程指针参数时:参数必须是(代码地址, 访问链)的二元组——即闭包(Closure)的雏形。

访问链的代价:访问深度差为 k 的变量需要 k 次指针跳转,代价为 O(k)。

方案二:显示表(Display)

问题动机:访问链方案在深度差大时开销线性增长,能否做到 O(1)?

核心思想:用一个全局数组 d[],d[i] 始终指向栈中最近一次活动的深度为 i 的过程的活动记录。

访问深度 i 的变量:直接取 d[i],再加变量偏移,一次间接寻址,O(1)。

维护方式:

1
2
3
4
5
6
调用深度为 np 的过程 p 时:
  1. 在 p 的活动记录中保存 d[np] 的旧值
  2. 将 d[np] 设为当前(p 的)活动记录地址

从 p 返回时:
  3. 从 p 的活动记录中恢复 d[np] 的旧值

访问链 vs 显示表对比:

方案 访问深度差为 k 的变量 维护开销(每次调用/返回) 内存开销
访问链 O(k)(k 次指针跳转) O(1)(设置一个指针) 每帧一个指针
显示表 O(1)(直接查数组) O(1)(保存/恢复一个槽) 全局数组(最大深度大小)

工程现实:现代语言(Go、Rust、Python)对闭包的实现通常用堆上分配的环境(Environment),而非显示表。显示表是编译器教材中的经典方案,工业上更多见于静态作用域的嵌套语言(Pascal 时代)。


5.2.4 堆管理

为什么需要堆?

栈上的数据生命期与函数调用绑定——函数返回时栈帧消失。但有些数据需要活得比创建它的函数更长:

1
2
3
4
5
int* create_array(int n) {
    int* arr = malloc(n * sizeof(int));  // 必须放堆上!
    return arr;                           // 函数返回后 arr 仍然有效
}
// 若 arr 在栈上,函数返回后栈帧销毁,返回的指针成悬空指针!

堆分配的评价维度

  • 空间效率:减少碎片(Fragmentation),提高内存利用率
  • 时间效率:分配/释放操作要快
  • 程序局部性:相关数据在内存中靠近,减少缓存/TLB 缺失

堆碎片问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
初始堆(32字节):
[||||||||||||||||||||||||||||||||]  全部空闲

分配 8、4、8 字节后:
[AAAAAAAA BBBB CCCCCCCC         ]
 ↑8字节   ↑4字节 ↑8字节   ↑12字节空闲

释放 B(4字节)后:
[AAAAAAAA #### CCCCCCCC         ]
 ↑8字节   ↑4字节空洞 ↑8字节  ↑12字节空闲

现在申请 8 字节:
  - 中间 4 字节洞太小
  - 右边 12 字节空闲可满足
  - 但如果右边没有12字节,虽然总空闲=16,也无法满足8字节请求
                 ↑ 这就是外部碎片(External Fragmentation)

两种基本分配策略

策略 思想 优点 缺点
Best-Fit 选能容纳请求的最小空闲块 保留大块供大请求使用 搜索慢;产生大量极小碎片
First-Fit 选第一个能容纳的空闲块 分配快;大块保留在后端 前端碎片化严重

容器化堆管理(GNU C 方案)

按尺寸分档,同规格的空闲块放同一个”容器(bin)”:

1
2
3
4
5
6
7
8
9
10
容器分档:
  16B 容器: [□□□□□...]
  24B 容器: [□□□□□...]
  32B 容器: [□□□□□...]
  ...
  512B 容器: [□□□...]
  >512B: 按对数划分

分配时:找对应容器取一个空闲块
不足时:从"荒野块(Wilderness Chunk)"中分割

优点:分配常数时间;同规格块组合良好,减少内部碎片。

空闲块接合(Coalescing)

回收时将相邻空闲块合并成更大块,防止堆越来越碎。

关键技术:边界标记(Boundary Tag)

每个存储块的头部和尾部都存放该块的元数据:

1
2
3
4
5
块结构:
┌──────────────┬────────────────────────────────┬──────────────┐
│ 头(Header) │         有效数据区             │ 尾(Footer) │
│  size | free │                                │  size | free │
└──────────────┴────────────────────────────────┴──────────────┘

检查邻块是否空闲(O(1)):

  • 检查左邻块:读取当前块头部地址 - 4(上一块的尾部)
  • 检查右邻块:读取当前块头部地址 + size(下一块的头部)

双向链接的空闲列表:在每个空闲块的有效数据区内嵌入前向/后向指针,维护所有空闲块的双链表,O(1) 插入删除。

手工内存管理的两大危险

① 内存泄漏(Memory Leak):分配了堆内存,但在不再使用后忘记释放。

1
2
3
4
5
void leak() {
    char* buf = malloc(1024);
    if (error) return;  // 忘记 free(buf)!
    free(buf);
}

长期运行的程序(服务器等)因持续泄漏最终 OOM(Out of Memory)。

② 悬空指针(Dangling Pointer):释放内存后仍然持有指向该内存的指针。

1
2
3
int* p = malloc(sizeof(int));
free(p);
*p = 42;   // 未定义行为!该内存可能已被重新分配给别人

手工管理的缓解模式

  • 对象所有权(Object Ownership):每个对象只有一个所有者,只有所有者能删除;Rust 语言将此作为编译期强制规则
  • 引用计数(Reference Counting):计数归 0 时自动释放;C++ shared_ptr 的实现思路
  • 基于区域的分配(Region-based Allocation):同生命期的对象放同一区域,整块一起释放;Apache HTTP Server 的 apr_pool 即此思路

5.3 垃圾回收

5.3.1 基础概念:可达性与根集

什么是垃圾?

严格定义:程序无法再访问到的对象(不可达对象)。

广义定义:程序不会再使用的对象(但这在一般情况下不可计算——相当于停机问题)。

工程折中:GC 只能回收不可达的对象,而不是”不再需要”的对象。这意味着即使在 GC 语言中,也可能发生”逻辑内存泄漏”(对象可达但永远不会使用,如全局 HashMap 中积累的僵尸条目)。

根集(Root Set)

定义:不需要通过任何指针解引用就能直接访问的对象集合。

典型的根集来源:

  • 全局变量(静态区中的引用类型字段)
  • 当前栈上的局部变量和参数
  • CPU 寄存器中的引用

可达性的传播:

1
2
3
4
5
根集对象都是可达的
    ↓ 若可达对象 A 的某字段存放了对象 B 的引用
B 也是可达的
    ↓ 递归传播
所有通过引用链从根集可到达的对象都是可达的

关键性质:一旦不可达,永远不会再变成可达(在正确的程序中)。

改变可达对象集合的三类操作

操作 效果
对象分配 新对象出现,加入可达集(通常初始分配在根集可达处)
引用赋值 u = v u 原来指向的对象可能失去一个引用,v 指向的对象多一个引用
过程返回 局部变量从根集消失,被局部变量唯一引用的对象变不可达

GC 的前提条件

GC 要求语言类型安全(Type-Safe):运行时能判断任意内存位置是否存放的是指针。

为什么 C/C++ 不能做精确 GC? C 中可以将指针转换为整数再转回来,GC 无法区分”恰好等于某对象地址的整数”和”真正的指针”,因此只能做保守 GC(Conservative GC)——把所有看起来像指针的值都当指针处理,可能导致垃圾无法被回收。


5.3.2 引用计数

机制

每个堆对象附带一个引用计数字段,记录当前有多少个指针指向该对象:

操作 计数变化
对象被分配 计数 = 1
新引用指向该对象(赋值、参数传递等) 计数 + 1
引用消失(赋值覆盖、局部变量出作用域等) 计数 - 1
计数变为 0 立即删除对象,并递归减少其所有字段指向对象的计数

引用赋值 u = v 的完整操作

1
2
3
4
5
旧对象 = u 指向的对象
1. 旧对象.count -= 1
2. 若 旧对象.count == 0:递归删除旧对象
3. u = v(更新指针)
4. v 指向的对象.count += 1

注意:必须先减再赋值,否则若 u == v,会先把计数减到 0 导致误删。

优缺点分析

优点:

  • 对象变垃圾时立即回收,内存利用率高
  • 无需停顿(Stop-the-World),适合实时性要求高的场景
  • 回收工作均摊到每次引用操作,避免 GC 长暂停

缺点:

① 无法回收循环引用(致命缺陷):

1
2
3
4
5
6
7
8
9
对象 A 和 B 互相引用,形成环:
  A.ref = B
  B.ref = A
  
当程序不再持有 A、B 时,根集中指向 A/B 的引用消失,但:
  A.count = 1(B 还引用 A)
  B.count = 1(A 还引用 B)
  
计数永远不为 0 → 永远不会被回收 → 内存泄漏!

CPython 解决方案:主要用引用计数,同时有一个循环检测器(gc 模块)处理循环引用。

② 运行时开销大:每次指针操作(赋值、函数调用传参、返回)都需要更新计数,对引用密集型代码性能影响显著。

③ 多线程问题:计数的增减必须是原子操作(CAS),开销进一步增加。


5.3.3 基于跟踪的回收

基本思路:不在垃圾产生时立即回收,而是周期性运行(通常在堆空间不足时触发),从根集出发遍历所有可达对象,回收其余的不可达对象。

对象的四种状态

状态 含义
空闲(Free) 不含活跃对象,可被分配
未被访问(Unreached) 当前 GC 轮次尚未访问(默认假设不可达)
待扫描(Scanned) 已确认可达,但其内部的引用字段尚未追踪
已扫描(Unscanned) 已确认可达,且内部所有引用都已追踪完毕

GC 结束后:所有对象要么是已扫描(可达,保留),要么是空闲(不可达,回收)。

5.3.3.1 标记-清扫(Mark-Sweep GC)

两个阶段:

Phase 1:标记(Mark)

从根集出发,做图遍历(BFS 或 DFS),将所有可达对象标记:

1
2
3
4
5
6
7
8
初始化:将所有对象状态设为 Unreached
将根集中的所有对象加入工作队列(状态→Scanned)

while 工作队列非空:
    取出一个对象 o(Scanned → Unscanned)
    for o 的每个引用字段 p:
        if p 指向的对象是 Unreached:
            将 p 指向的对象状态设为 Scanned,加入工作队列

Phase 2:清扫(Sweep)

遍历整个堆,处理每个对象:

  • Unscanned(已标记,可达)→ 清除标记,保留
  • Unreached(未标记,不可达)→ 回收,加入空闲列表
1
2
3
4
5
6
7
8
9
10
代价分析(堆大小 H 字节,可达数据 R 字节):
  标记代价 ∝ R(只遍历可达对象)
  清扫代价 ∝ H(遍历整个堆)
  单次 GC 总代价:C(GC) = a·R + b·H

  每回收一个字节的代价:
  C(per_byte) = (a·R + b·H) / (H - R)

  当 H >> R 时(堆很大,垃圾很多):C(per_byte) ≈ b
  当 H ≈ R 时(堆几乎满),代价急剧升高 → 需要扩堆

Baker 优化:维护 Unreached 链表,清扫时只扫描该列表而非整个堆,减少清扫代价。

缺点:

  • Stop-the-World:GC 期间整个应用暂停(对延迟敏感的应用不可接受)
  • 堆碎片:存活对象位置不变,碎片依然存在
  • 清扫代价与堆大小成正比,堆越大停顿越长

5.3.3.2 标记-压缩(Mark-Compact GC)

动机:Mark-Sweep 不移动对象,碎片问题无法解决。

三个阶段:

1
2
3
4
5
6
7
8
9
10
Phase 1:标记(同 Mark-Sweep)

Phase 2:计算新位置
  从堆最低地址开始,依次为每个"存活对象"计算新地址
  (想象把所有存活对象从左到右紧密排列)
  用哈希表 NewLocation[old_addr] = new_addr 记录映射

Phase 3:移动对象并更新所有引用
  将每个存活对象从 old_addr 拷贝到 new_addr
  遍历所有存活对象的引用字段,用 NewLocation 更新指针

效果:

1
2
3
4
5
6
7
GC 前(碎片化):
  [AAAA #### BBBB #### #### CCCC ####]
       空洞       空洞  空洞       空洞

GC 后(压缩):
  [AAAA BBBB CCCC                    ]
                   ↑ 单一连续空闲区域

优点:消除所有碎片,空闲空间成为单一连续块,分配变为 O(1) 的指针碰撞(bump pointer)。

缺点:需要三遍扫描堆;更新所有引用意味着 GC 期间所有指针临时失效,实现复杂。

5.3.3.3 拷贝回收(Copying GC / Semispace GC)

核心思想:用空间换时间——将堆分为两个等大的半空间(From / To),GC 时只拷贝存活对象。

流程图:

1
2
3
4
5
6
7
8
9
10
11
12
13
正常分配:
  程序在 From 空间中用"指针碰撞"顺序分配对象
  From_ptr ──→ 对象A 对象B 对象C ... 对象N │ 空闲空间

From 空间满,触发 GC:
  1. 从根集出发,遍历所有可达对象
  2. 将每个可达对象拷贝到 To 空间(按遍历顺序,消除碎片)
  3. 在原对象位置留下"转发指针(Forwarding Pointer)"指向新地址
  4. 更新根集中的所有引用

GC 完成,交换角色:
  原 From 空间:全部视为空闲(所有对象已复制走或是垃圾)
  原 To 空间:成为新的 From 空间,继续分配

Cheney 算法(拷贝 GC 的经典实现,无需递归栈):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
在 To 空间维护两个指针:
  scan:指向下一个待扫描(追踪其引用字段)的对象
  free:指向下一个空闲位置(新对象拷贝到此处)

初始化:将根集对象拷贝到 To 空间,设 scan = To 开始,free = 根集拷贝结束后的位置

while scan < free:
    取出 scan 处的对象 o
    for o 的每个引用字段 r:
        if r 指向的 From 空间对象没有转发指针:
            将该对象拷贝到 free 处,free += 对象大小
            在原处设转发指针
        r = 转发指针指向的 To 空间新地址
    scan += o 的大小

完成:scan == free,所有可达对象都在 To 空间

优点:

  • 无碎片(分配始终是指针碰撞,O(1))
  • 遍历可达对象时直接移动,兼具标记和压缩
  • 改善程序局部性(相关对象按访问顺序排列在 To 空间)

缺点:

  • 内存利用率只有 50%(一半空间永远闲置)
  • 每轮 GC 需遍历所有存活对象(即使垃圾极少)

5.3.3.4 分代回收(Generational GC)

动机(弱代假设,Weak Generational Hypothesis):

1
2
3
4
5
实验观测:大多数对象"朝生暮死"——
  > 80% 的对象在分配后极短时间内变垃圾
  < 20% 的对象活得较长(老年对象)

推论:对年轻代频繁做 GC,每次 GC 的代价小且回收量大,效率高

结构:

1
2
3
4
5
6
7
8
9
10
11
堆分为多个"代(Generation)":

  新生代(Young Generation):对象新生,GC 频繁
  ┌──────────────────────────────────────┐
  │  Eden Space  │  S0(Survivor 0)  │  S1(Survivor 1)  │
  └──────────────────────────────────────┘
  
  老年代(Old / Tenured Generation):存活多轮的老对象,GC 不频繁
  ┌──────────────────────────────────────┐
  │                                      │
  └──────────────────────────────────────┘

执行流程(以 JVM G1/HotSpot 为例):

1
2
3
4
5
6
7
1. 新对象在 Eden 空间分配
2. Eden 满 → Minor GC(只回收新生代):
   - 存活对象从 Eden + S0 拷贝到 S1
   - 清空 Eden 和 S0
   - S0/S1 角色互换
3. 多次 Minor GC 后仍存活的对象"晋升"到老年代(age 阈值,默认 15)
4. 老年代满 → Major GC / Full GC(回收整个堆,代价高)

关键问题:老年代引用新生代怎么处理?

Minor GC 只扫描新生代,但老年代中的对象可能引用新生代对象——若忽略这些引用,存活对象会被误回收。

解决方案:记忆集(Remembered Set)

记录老年代中所有指向新生代的引用。Minor GC 时,记忆集中的引用也作为根集的一部分处理。

1
2
3
4
5
老年代对象 O.field = 新生代对象 Y

记忆集 remembered_set = { O.field 的地址 }

Minor GC 根集 = 正常根集 ∪ { O.field 指向的对象 Y }

维护记忆集的方式:写屏障(Write Barrier)——每次引用赋值时,检查是否是从老年代到新生代的跨代引用,如是则更新记忆集。


5.4 Java GC 设计(引用类型)

Java 通过四种引用强度精细控制对象的生命周期与 GC 行为:

引用类型 类 GC 时机 典型用途
强引用(Strong Reference) 普通 Object obj = new ... 有强引用存在时永不回收 所有普通对象
软引用(Soft Reference) SoftReference<T> 内存不足时才回收 缓存(允许 GC 降级)
弱引用(Weak Reference) WeakReference<T> 正常 GC 时即回收(不论内存是否充足) 短期缓存、WeakHashMap
虚引用(Phantom Reference) PhantomReference<T> 正常 GC 时回收,但回收前加入 ReferenceQueue 跟踪 GC 时机、资源清理

生存时间排序:强引用 » 软引用 > 弱引用 ≈ 虚引用

软引用使用场景:图片缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
Map<String, SoftReference<Image>> imageCache = new HashMap<>();

Image getImage(String url) {
    SoftReference<Image> ref = imageCache.get(url);
    if (ref != null) {
        Image img = ref.get();   // 可能返回 null(已被 GC 回收)
        if (img != null) return img;
    }
    // 缓存失效,重新加载
    Image img = loadFromNetwork(url);
    imageCache.put(url, new SoftReference<>(img));
    return img;
}

内存充足时图片驻留缓存;内存不足时 GC 自动回收,避免 OOM。

虚引用的特殊性

虚引用对对象的生命周期没有任何影响(持有虚引用等于没有引用),但对象被 GC 回收之前,JVM 会将该虚引用加入关联的 ReferenceQueue。

1
2
3
4
5
6
7
8
9
10
11
12
ReferenceQueue<Resource> queue = new ReferenceQueue<>();
PhantomReference<Resource> phantomRef = 
    new PhantomReference<>(new Resource(), queue);

// 在另一个线程中监听队列
Thread cleaner = new Thread(() -> {
    while (true) {
        Reference<?> ref = queue.remove();   // 阻塞等待
        // 收到通知:对应的 Resource 对象即将/已被 GC 回收
        // 在此执行清理工作(如关闭文件句柄、释放 native 资源)
    }
});

Java 9+ 的 Cleaner API:基于虚引用封装,是 finalize() 的现代替代品。finalize() 因执行时机不确定、性能差、安全问题已在 Java 18 中弃用。


5.5 运行时环境图解(完整示例)

以 main 调用 fun(a, b) 为例,追踪完整的栈帧生命周期。

三个关键寄存器(x86 模型):

寄存器 全称 作用
eip Instruction Pointer 当前执行指令的地址
ebp Base Pointer 当前栈帧的底部(基址)
esp Stack Pointer 当前栈顶(最新压栈位置)

完整执行流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
初始状态:
  代码区:main 代码、fun 代码
  静态区:全局变量 m = 10
  动态区(栈):空

Step 1:main 建立自己的栈帧
  push ebp        // 保存调用者(OS)的 ebp
  mov ebp, esp    // ebp 指向 main 栈底
  sub esp, 8      // 为局部变量 i, j 分配空间

  局部变量初始化:i = 4, j = 5

Step 2:调用 fun(i, j) 前的准备
  C 调用约定:参数**逆序**入栈
  push j          // 先压 j=5
  push i          // 再压 i=4
  call fun        // ① 将返回地址(call 下一条指令)push 入栈
                  // ② eip 跳转到 fun 代码

Step 3:fun 建立自己的栈帧
  push ebp        // 保存 main 的 ebp
  mov ebp, esp    // ebp 指向 fun 栈底
  sub esp, 4      // 为局部变量 c 分配空间

此时栈(从高到低):
  ┌──────────────┐
  │    j = 5     │  ebp + 12(main 传入的第二个参数)
  ├──────────────┤
  │    i = 4     │  ebp + 8 (main 传入的第一个参数)
  ├──────────────┤
  │  返回地址    │  ebp + 4
  ├──────────────┤
  │  main 的 ebp │  ebp + 0  ← fun 的 ebp 指向此处
  ├──────────────┤
  │    c = ?     │  ebp - 4  ← fun 的局部变量
  └──────────────┘  ← esp

Step 4:fun 执行计算
  mov eax, [ebp+8]    // 读取参数 i(= a)
  add eax, [ebp+12]   // 加上参数 j(= b)
  mov [ebp-4], eax    // 结果存入 c
  mov eax, [ebp-4]    // 返回值放 eax(C 调用约定)

Step 5:fun 返回
  mov esp, ebp        // 恢复 esp(释放局部变量)
  pop ebp             // 恢复 main 的 ebp
  ret                 // pop 返回地址 → eip,跳回 main

Step 6:main 获取返回值
  add esp, 8          // 清除压栈的两个参数(调用者清栈,cdecl 约定)
  mov [m], eax        // 将 fun 的返回值(eax)存入全局变量 m

参数逆序入栈的原因:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
C 支持可变参数(如 printf)。最左边的参数(格式字符串)必须在最高地址
(最先被弹出/访问),所以最后一个压栈,因此参数逆序入栈。

  printf("%d %d", a, b)
  
  栈(从高到低):
  ┌──────────────┐
  │    b         │  ebp + 16
  ├──────────────┤
  │    a         │  ebp + 12
  ├──────────────┤
  │  "%d %d"    │  ebp + 8   ← 格式字符串,第一个参数,最靠近调用者帧
  ├──────────────┤
  │  返回地址    │  ebp + 4
  └──────────────┘

附录

常见误区对照表

误区 正确理解
“活动树的子节点从左到右是调用顺序,说明右边的孩子更早执行” 相反:左边先执行(先调用),右边后执行
“控制链和访问链一样,都指向调用者” 控制链指向调用者(动态),访问链指向词法外层(静态),两者在递归等场景下不同
“显示表比访问链一定更快” 显示表访问变量是 O(1),但维护时每次调用/返回要保存恢复一个槽;访问链维护 O(1) 但访问 O(k)。深度差小时差异不大
“引用计数能回收所有垃圾” 引用计数无法回收循环引用形成的垃圾孤岛,这是其根本缺陷
“Mark-Sweep 的标记代价与堆大小成正比” 标记只遍历可达对象,代价 ∝ R(可达数据量);清扫才与堆大小 H 成正比
“拷贝 GC 内存浪费,所以比 Mark-Sweep 差” 拷贝 GC 消除碎片、分配极快(指针碰撞),GC 时间只与存活对象相关,垃圾多时反而高效
“分代 GC 只扫描年轻代,所以不需要考虑老年代的引用” 老年代对年轻代的引用必须通过记忆集纳入 Minor GC 的根集,否则会误回收存活对象
“软引用在内存充足时永远不会被回收” JVM 规范没有严格定义,不同 JVM 实现可能不同;实践上 HotSpot 用 -XX:SoftRefLRUPolicyMSPerMB 控制软引用存活时间
“虚引用可以用来延迟对象的 GC” 虚引用对对象生命周期没有任何保护作用,GC 不受其影响

关键概念速查表

概念 一句话定义 所在章节
活动记录(栈帧) 一次过程调用在栈中的数据结构,含参数/返回地址/局部变量等 5.2.2.2
活动树 表示程序运行期间所有过程活动调用关系的树,前序=调用序 5.2.2.1
控制链 活动记录中指向调用者活动记录的指针(动态链接) 5.2.2.2
访问链 活动记录中指向词法外层过程最近活动记录的指针(静态链接) 5.2.3
top_sp 指向顶层活动记录定长字段末端,用固定偏移访问定长数据 5.2.2.2
top 指向实际栈顶(下一个活动记录起始位置) 5.2.2.4
显示表 数组 d[],d[i] 指向深度 i 最顶层活动记录,O(1) 非局部变量访问 5.2.3
嵌套深度 编译时静态确定的过程嵌套层次 5.2.3
边界标记 每个存储块两端存放 size 和 free/used 位,支持 O(1) 邻块接合 5.2.4
Best-Fit 选最小能容纳的空闲块,保留大块但搜索慢 5.2.4
First-Fit 选第一个能容纳的空闲块,分配快但前端碎片多 5.2.4
根集 无需指针解引用可直接访问的对象集合(全局变量、栈变量等) 5.3.1
可达性 从根集出发通过引用链可访问到的对象属性 5.3.1
引用计数 每对象附带引用数,为 0 时立即回收;缺陷:循环引用 5.3.2
Mark-Sweep 标记可达对象,清扫不可达;简单但有碎片,Stop-the-World 5.3.3.1
Mark-Compact 标记后压缩存活对象,消除碎片;需更新所有引用 5.3.3.2
Copying GC 堆分两半,GC 时拷贝存活对象到另一半;无碎片,内存利用率 50% 5.3.3.3
Generational GC 按年龄分代,年轻代频繁 GC;依赖”大多数对象短命”假设 5.3.3.4
记忆集 记录老年代到年轻代的跨代引用,供 Minor GC 使用 5.3.3.4
写屏障 引用赋值时的 hook,用于维护记忆集等 GC 数据结构 5.3.3.4
强引用 有引用存在时对象永不回收(Java 普通引用) 5.4
软引用 内存不足时才回收,适合缓存(Java SoftReference) 5.4
弱引用 正常 GC 时即回收(Java WeakReference) 5.4
虚引用 最弱引用,用于监听 GC 事件(Java PhantomReference + ReferenceQueue) 5.4

本章知识依赖图(ASCII 树)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
前置知识
├── 过程调用语义(函数如何传参/返回)
├── 作用域规则(词法作用域 vs 动态作用域)
└── 内存模型基础(地址空间、字节寻址)

本章内容
├── 5.2 存储管理
│   ├── 5.2.1 三大区域(代码/静态/动态)
│   │   ├── 静态分配(全局变量)
│   │   ├── 栈式分配(过程调用)
│   │   └── 堆分配(动态对象)
│   │
│   ├── 5.2.2 栈式分配
│   │   ├── 活动树(调用关系的树状表示)
│   │   ├── 活动记录(栈帧结构,7个字段)
│   │   ├── 调用/返回代码序列(调用者+被调用者分工)
│   │   └── 变长数据(top vs top_sp 双指针)
│   │
│   ├── 5.2.3 非局部数据访问
│   │   ├── 无嵌套(C):静态区 + 偏移
│   │   └── 嵌套过程(Pascal):
│   │       ├── 访问链(O(深度差),维护简单)
│   │       └── 显示表(O(1),维护略复杂)
│   │
│   └── 5.2.4 堆管理
│       ├── Best-Fit / First-Fit 分配策略
│       ├── 容器化管理(GNU C)
│       ├── 边界标记 + 双链表(O(1) 接合)
│       └── 手工管理问题(泄露/悬空指针)
│           └── 缓解:所有权 / 引用计数 / 区域分配
│
└── 5.3 垃圾回收
    ├── 5.3.1 基础:根集 + 可达性
    ├── 5.3.2 引用计数(即时回收,循环引用缺陷)
    └── 5.3.3 基于跟踪(四种算法)
        ├── Mark-Sweep(简单,有碎片,Stop-the-World)
        ├── Mark-Compact(无碎片,更新引用开销大)
        ├── Copying GC(无碎片,50%内存利用率)
        └── Generational GC(优化短命对象,记忆集+写屏障)

工程连接
├── JVM:G1/ZGC/Shenandoah(并发分代 GC)
├── Python:引用计数 + 循环检测器
├── Go:三色标记-清扫(并发,低停顿)
├── Rust:所有权 + 借用检查(编译期解决,无 GC)
└── Linux/glibc:ptmalloc(容器化堆,per-thread arena)
编译原理

聊一聊