编译原理

第七章 运行时刻环境

2020-04-23 10:00 CST
2020-04-30 16:19 CST
CC BY-NC 4.0

7.1 存储组织

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

  • 对齐和补白(padding)
  • 堆区向正方向增长,栈区向负方向增长
  • 人工分配和释放数据对象(mallocfree

静态和动态存储分配

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

动态分配:

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

7.2 空间的栈式分配

7.2.1 活动树

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

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

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

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

7.2.2 活动记录

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

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

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

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

7.2.3 调用代码序列

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

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

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

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

活动记录的布局原则:

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

7.2.4 栈中的变长数据

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

  • 在分配数组的位置分配一个指针,指向数组存放的位置。
  • 两个指针toptop_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 拷贝垃圾回收

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

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

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