07 编译原理--运行时刻环境

这一节是南京大学计算机系许畅所讲述的编译原理中的运行时刻环境。这一节的主要内容有:为数据分配安排存储位置,确定访问变量时使用的机制, 过程之间的连接、参数传递, 和操作系统、输入输出设备相关的其它接口,存储管理:栈分配、堆管理、垃圾回收以及对变量、数据的访问。
展开查看详情

1.第七章 运行时刻环境 许畅 南京大学计算机系 2018年春季

2.运行时刻环境 • 运行时刻环境 – 为数据分配安排存储位置 – 确定访问变量时使用的机制 – 过程之间的连接、参数传递 – 和操作系统、输入输出设备相关的其它接口 • 主题 – 存储管理:栈分配、堆管理、垃圾回收 – 对变量、数据的访问 2

3.存储分配的典型方式  目标程序的代码放置在代码区  静态区、堆区、栈区分别放置不同类型生命期的 数据值 3

4.静态和动态存储分配 • 静态分配 – 编译器在编译时刻就可以做出存储分配决定,不需要 考虑程序运行时刻的情形 – 全局常量、全局变量 • 动态分配 – 栈式存储:和过程的调用/返回同步进行分配和回收, 值的生命期与过程生命期相同 – 堆存储:数据对象比创建它的过程调用更长寿 • 手工进行回收 • 垃圾回收机制 4

5.栈式分配  内容  活动树  活动记录  调用代码序列  栈中的变长数据 5

6.活动树 • 过程调用 (过程活动) 在时间上总是嵌套的 – 后调用的先返回 – 因此用栈来分配过程活动所需内存空间 • 程序运行的所有过程活动可以用树表示 – 每个结点对应于一个过程活动 – 根结点对应于main过程的活动 – 过程p的某次活动对应的结点的所有子结点 – 表示此次活动所调用的各个过程活动 – 从左向右,表示调用的先后顺序 6

7.活动树的例子 • 快速排序程序 • 过程调用 (返回) 序列和活动 树的前序 (后序) 遍历对应 • 假定当前活动对应结点N, 那么所有尚未结束的活动对 应于N及其祖先结点 7

8.活动记录  过程调用和返回由控制栈 进行管理  每个活跃的活动对应于栈 中的一个活动记录  活动记录按照活动的开始 时间,从栈底到栈顶排列 8

9.运行时刻栈的例子  说明  a[11]为全局变量  main无局部变量 r  r有局部变量i  q有局部变量i, 和参数m, n r 9

10.调用代码序列 • 调用代码序列 (Calling sequence) 为活动记录分配 空间,填写记录中的信息 • 返回代码序列 (Return sequence) 恢复机器状态, 使调用者继续运行 • 调用代码序列会分割到调用者和被调用者中 – 根据源语言、目标机器、操作系统的限制,可以有不 同的分割方案 – 把代码尽可能放在被调用者中 10

11.调用/返回代码序列的要求  数据方面  能够把参数正确地传递给被调用者  能够把返回值传递给调用者  控制方面  能够正确转到被调用过程的代码开始位置  能够正确转回调用者的调用位置 (的下一条指令)  调用代码序列和活动记录的布局相关 11

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

13.调用代码序列的例子 • Calling sequence – 调用者计算实在参数的值 – 将返回地址和原top_sp存放到被调用者的活动记录中; 调用者增加top_sp的值 (越过了调用者的局部数据、临 时变量、被调用者的参数、机器状态字段) – 被调用者保存寄存器值和其他状态字段 – 被调用者初始化局部数据、开始运行 • Return sequence – 被调用者将返回值放到和参数相邻的位置 – 恢复top_sp和寄存器,跳转到返回地址 13

14.调用者/被调用者的活动记录 1 2 3 14

15.栈中的变长数据 • 如果数据对象的生命 期局限于过程活动的 生命期,就可以分配 在运行时刻栈中 – 变长数组也可以 • top指向实际栈顶 • top_sp用于寻找顶层 记录的定长字段 15

16.非局部数据的访问 (无嵌套过程)  没有嵌套过程时的数据访问  C语言中,每个函数能访问的变量  函数的局部变量:相对地址已知,且存放在当前活动记录内, top_sp指针加上相对地址即可访问  全局变量:在静态区,地址在编译时刻可知  很容易将C语言的函数作为参数进行传递  参数中只需包括函数代码的开始地址  在函数中访问非局部变量的模式很简单,不需要考虑过程是如 何激活的 16

17.非局部数据的访问 (有嵌套过程) • PASCAL中,如果过程A的声明中包含了过程B的 声明,那么B可以使用在A中声明的变量 • 当B的代码运行时,如果它使用的是A中的变量, 必须通过访问链访问 当A调用C,C又调用B时: void A() { int x, y; A的活动记录 void B() { C的活动记录 int b; B的活动记录 x = b + y; } void C() { B(); } 当A直接调用B时: C(); A的活动记录 B(); B的活动记录 } 17

18.嵌套深度 深度2:readArray, • 嵌套深度可根 深度1:sort exchange, quicksort 据源程序静态 确定 – 不内嵌于任何 其它过程的过 程,深度为1 – 嵌套于深度为i 深度3:partition 的过程的过程, 深度为i + 1 18

19.访问链和访问链的使用 • 访问链被用于访问非局部的数据 • 如果过程p在声明时 (直接) 嵌套在过程q中,那么p活 动记录中的访问链指向上层最近的q的活动记录 • 从栈顶活动记录开始,访问链形成了一个链路,嵌套 深度沿着链路逐一递减 • 设深度为np的过程p访问变量x,而变量x在深度为 nq的过程q中声明 – np – nq在编译时刻已知;从当前活动记录出发,沿访 问链前进np – nq次找到活动记录 – x相对于这个活动记录的偏移量在编译时刻已知 19

20.访问链的维护 • 当过程q调用过程p时 – p的深度大于q:根据作用域规则,p必然在q中直接定 义;那么p的访问链指向当前活动记录 (即q) • 例如:sort调用quicksort(1, 9) – 递归调用p = q:新活动记录的访问链等于当前记录的 访问链 (即和前一个q指向同一目标) • 例如:quicksort(1, 9)调用quicksort(1, 3) – p的深度小于等于q的深度:必然有过程r,p直接在r中 定义,而q嵌套在r中;p的访问链指向栈中r的活动记 录 • 例如:partition调用exchange 20

21.访问链的例子 21

22.访问链的维护 (过程指针型参数)  在传递过程指针参数时,过程型参数中不仅包含 过程的代码指针 (开始地址),还包括正确的访问 链 22

23.显示表 • 用访问链访问数据,访问开销和嵌套深度差有关 • 使用显示表可以提高效率,访问开销为常量 • 显示表:数组d为每个嵌套深度保留一个指针 – 指针d[i]指向栈中最近的、嵌套深度为i的活动记录 – 如果过程p访问嵌套深度为i的过程q中声明的变量x, 那么d[i]直接指向相应的活动记录 (i在编译时刻已知) • 显示表的维护 – 调用过程p时,在p的活动记录中保存d[np]的值,并将 d[np]设置为当前活动记录 (即p) – 从p返回时,恢复d[np]的值 23

24.显示表的例子 q(1, 9)调用q(1, 3) 时,q的深度为2 p调用e,e 的深度为2 q(1, 3)调用p,p 的深度为3 24

25.堆管理 • 堆空间 – 用于存放生命周期不确定、或生存到被明确删除为止 的数据对象 – 例如:new生成的对象可以生存到被delete为止, malloc申请的空间生存到被free为止 • 存储管理器 – 分配/回收堆区空间的子系统 – 根据语言而定 • C、C++需要手动回收空间 • Java可以自动回收空间 (垃圾收集) 25

26.存储管理器 • 基本功能 – 分配:为内存请求分配一段连续、适当大小的堆空间 • 首先从空闲的堆空间分配 • 如果不行则从操作系统中获取内存、增加堆空间 – 回收:把被回收的空间返回空闲空间缓冲池,以满足 其它内存需求 • 评价存储管理器的特性 – 空间效率:使程序需要的堆空间最小,即减小碎片 – 程序效率:运用内存系统的层次,使程序运行更快 – 低开销:使分配/收回内存的操作尽可能高效 26

27.计算机的存储层次结构 27

28.程序中的局部性  程序具有高度的局部性 (Locality)  时间局部性:一个程序访问的存储位置很可能将在一 个很短的时间段内被再次访问  空间局部性:被访问过的存储位置的临近位置很可能 在一个很短的时间段内被访问  90%的时间用来执行10%的代码  局部性这一特性恰好可以充分利用计算机的层次 存储结构 28

29.堆空间的碎片问题 • 随着程序分配/回收内存,堆区逐渐被割裂成为若 干空闲存储块 (窗口) 和已用存储块的交错 • 分配一块内存时,通常是把一个窗口的一部分分 配出去,其余部分成为更小的块 • 回收时,被释放的存储块被放回缓冲池;通常要 把连续的窗口接合成为更大的窗口 碎片 已分配空间 29