7.1 存储组织

内存可以分为代码区、静态区、堆区、栈区等。

• 对齐和补白（padding）
• 堆区向正方向增长，栈区向负方向增长
• 人工分配和释放数据对象（malloc和free）

静态和动态存储分配

静态分配：编译器在编译时刻就可以做出存储分配决定，不需要考虑程序运行时刻的情形。适用于全局常量、全局变量。

动态分配：

• 栈式存储：和过程的调用/返回同步进行分配和回收，值的生命期和过程的生命期相同；
• 堆存储：数据对象比创建他的过程调用更长寿，需要手工进行回收、建立垃圾回收机制。

7.2 空间的栈式分配

7.2.1 活动树

过程调用（活动）在时间上总是嵌套的。

• 后调用的先返回
• 适合用栈来分配活动过程中所需的内存空间

程序运行的所有过程活动可以用活动树来表示：

• 每个节点对应于一个过程活动
• 根节点对应于main过程的活动
• 过程$p$的（某次活动对应的节点的所有子节点）表示（此次活动所调用的各个过程活动），顺序为从左到右先后调用

7.2.2 活动记录

• 过程调用和返回由控制栈进行管理
• 每个活跃的活动对应于栈中的一个活动记录

活动记录按照活动的开始时间，从栈底到栈顶排列。

一个概括性的活动记录包括：

• 实在参数（实参）
• 返回值
• 控制链：指向调用者的活动记录
• 访问链：当被调用过程需要其他地方的某个数据时需要使用访问链进行定位
• 保存的机器状态：保存的现场（寄存器）、返回地址
• 局部数据
• 临时变量

7.2.3 调用代码序列

• 调用代码序列（calling sequence）：为活动记录分配空间，天蝎记录中的信息
• 返回代码序列（return sequence）：恢复机器状态，使调用者继续运行

调用代码序列会分割到调用者和被调用者中，根据源语言、目标机器和操作系统的限制，可以有不同的分割方案；把代码尽可能放在被调用者中。

调用/返回代码序列的要求：

• 数据方面：
  • 能够把参数正确的传递给被调用者
  • 能够把返回值传递给调用者
• 控制方面：
  • 能够正确转到被调用过程的开始位置
  • 能够正确转回调用者的调用位置（的下一条指令）

活动记录的布局原则：

• 调用者和被调用者之间传递的值在被调用者活动记录的开始位置
• 固定长度的项（控制链、访问链、机器状态）放在中间位置
• 早期不知道大小的项`放在活动记录尾部
• 栈顶指针（top\_sp）通常指向固定长度字段的末端（机器状态后）

7.2.4 栈中的变长数据

如果数据对象的生命局限于过程活动的生命期，就可以把数据分配在运行时刻栈中。

• 在分配数组的位置分配一个指针，指向数组存放的位置。
• 两个指针top和top_sp，前者指向下一个活动记录降压开始的位置，后者用来找到顶层活动记录的局部定长字段。

7.3 栈中非局部数据的访问

7.3.1 没有嵌套过程时的数据访问

不支持嵌套过程：某个变量要么在函数内定义，要么在全局定义。

• 函数的局部变量：相对地址已知，且存放在当前活动记录内，使用top_sp指针加上相对地址即可访问
• 全局变量：在静态区，地址在编译时刻可知

7.3.2 和嵌套过程相关的问题

一个过程可以访问另一个过程的变量，只要后一个过程的声明包含了前一个过程的声明即可。如A的声明包含了过程B的说明，那么B可以使用在A中声明的变量。

当B的代码运行时，如果它使用的是A中的变量，必须通过访问链访问，而不能通过控制链来访问调用者获得变量：

• 间接调用：A -> C -> B
• 直接调用：A -> B

7.3.4 嵌套深度

对于不内嵌在任何其他过程中的过程，定义其嵌套深度为$1$；如果一个过程$p$在深度为$i$的过程中定义，则$p$的嵌套深度为$i + 1$。

7.3.5 访问链

访问链（access link）被用于访问非局部的数据：

• 如果过程$p$在声明时（直接）嵌套在过程$q$中，那么$p$的活动记录中访问链指向上层最近的$q$的活动记录
• 从栈顶活动开始，访问链形成了一个链路，嵌套深度沿着链路逐一递减

设深度为$n_p$的过程$p$访问变量$x$，而变量$x$在深度为$n_q$的过程$q$中声明：

• 从当前活动记录触发，沿访问链前进$n_p - n_q$（编译时刻已知）找到活动记录
• $x$相对于这个活动记录的偏移量在编译时刻已知

7.4 堆管理

7.4.4 碎片整理

堆空间分配方法：

• Best-fit：总是讲请求的内存分配在满足请求的最小窗口中
  • 好处：可以将大的窗口保留下来，应对更大的请求
• First-fit：总是将对象放置在第一个能够容纳请求的窗口中
  • 放置对象花费时间较少，但是总体性能较差
  • 经常具有良好的数据局部性，同一时间段内生成的对象经常被分配在连续的空间内

使用容器机制的堆管理方法：

• 设定不同大小的块规格，相同的块放入同一容器
• 较小的（常用的）尺寸设置较多的容器
• 小尺寸直接在容器中找，大尺寸寻找适当的空闲块或进行分割

管理和接合空闲空间：

• 当回收一个块时，可以把这个块和相邻的块接合起来，形成更大的块
• 数据结构：
  • 边界标记
  • 双向链表

7.4.5 人工回收请求

人工回收带来的问题：

• 内存泄漏：未能删除不可能再被引用的数据
• 悬空指针引用：引用已被删除的数据

其他问题：空指针访问/数组越界访问

7.5 垃圾回收概述

垃圾：（广义）不需要再被引用的数据，（狭义）不能被引用（不可达）的数据。

垃圾回收：自动回收不可达数据的机制，解除了程序员的负担。

7.5.1 垃圾回收器的设计目标

基本要求：

• 语言必须是类型安全的，保证回收器能够知道数据元素是否为一个指向某内存块的指针
• 类型不安全的语言：如C/C++，无法确定数据的类型

性能目标：

• 总体运行时间：不显著增加应用程序的总运行时间
• 空间使用：最大限度地利用可用内存
• 停顿时间：当垃圾回收机制启动时，可能引起应用程序的停顿，这个停顿应该比较短
• 程序局部性：改善空间局部性和时间局部性

7.5.2 可达性

可达性：一个存储块可以被程序访问到

根集：不需要指针解引用就可以直接访问的数据，如静态成员和栈中变量

• 根集的成员都是可达的
• 对于任意一个对象，如果指向它的一个指针被保存在可达对象的某字段或数组元素中，那么这个对象也是可达的

可达性的性质：一旦一个对象变得不可达，它就不会再变成可达的。

改变可达对象集合的操作：

• 对象分配
• 参数传递、返回值
• 引用赋值
• 过程返回（出栈）

垃圾回收方法：

• 关注不可达：变为不可达的时候回收内存
• 关注可达：在需要时标出所有可达对象，回收其他对象

7.5.3 引用计数垃圾回收器

每个对象有一个用于存放引用计数的字段，并按如下方式维护：

• 对象分配：引用计数设为1
• 参数传递：引用计数加1
• 引用赋值：$u=v$，$u$指向的对象引用减1，$v$指向的对象引用加1
• 过程返回：局部变量指向对象的引用减1

如果一个对象的引用计数为0，在删除对象前，此对象各个指针成员所指对象的引用计数减1。

引用计数进行垃圾回收的方式开销较大，但不会引起停顿。

循环垃圾：多个对象相互引用，没有来自外部的指针，又不是根集成员，但都是垃圾，却无法被基于引用的垃圾回收机制回收。

7.6 基于跟踪的垃圾回收

7.6.1 标记-清扫式垃圾回收

一种直接的、全面停顿的算法。

分成两个阶段：

• 标记：从根集开始，跟踪并标记出所有的可达对象；
• 清扫：遍历整个堆区，释放不可达对象。

7.6.2 基本抽象

基本抽象分类：

• 每个存储块处于四种状态之一：空闲、未被访问（未知）、待扫描、已扫描
• 对存储块的操作会改变存储块的状态：应用程序分配、垃圾回收器扫描、回收

7.6.4 标记并压缩垃圾回收

对可达对象进行重定位可以消除存储碎片

• 堆区的一端是可达对象，另一端是空闲空间
• 空闲空间合并成单一块，提高分配内存时的效率

整个过程分成三个步骤：

• 标记
• 计算新位置
• 移动并设置新的引用

7.6.5 拷贝垃圾回收

堆空间被分成两个半空间：

• 应用程序在某个半空间分配存储
• 垃圾回收时可达对象被拷贝到另一个半空间
• 回收完成后两个半空间角色对调

优点：不涉及任何不可达对象