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