第七章运行时刻环境 许畅 南京大学计算机系 2022年春季 版权所有南京大学计算机科学与技术系许畅2022春季版
许畅 南京大学计算机系 2022年春季 第七章 运行时刻环境 版权所有 南京大学计算机科学与技术系 许畅 2022春季版 南大编译许畅
运行时刻环境 运行时刻环境 为数据分配安排存储位置 确定访问变量时使用的机制 过程之间的连接、参数传递 和操作系统、输入输出设备相关的其它接口 。主题 存储管理：栈分配、堆管理、垃圾回收 对变量、数据的访问 2
运行时刻环境 • 运行时刻环境 – 为数据分配安排存储位置 – 确定访问变量时使用的机制 – 过程之间的连接、参数传递 – 和操作系统、输入输出设备相关的其它接口 • 主题 – 存储管理：栈分配、堆管理、垃圾回收 – 对变量、数据的访问 2 南大编译许畅
存储分配的典型方式 目标程序的代码放置在代码区 静态区、堆区、栈区分别放置不同类型生命期的 数据值 代码区 静态区 堆区 空闲内存 栈区 3
存储分配的典型方式 • 目标程序的代码放置在代码区 • 静态区、堆区、栈区分别放置不同类型生命期的 数据值 3 南大编译许畅
静态和动态存储分配 静态分配 编译器在编译时刻就可以做出存储分配决定，不需要 考虑程序运行时刻的情形 全局常量、全局变量 动态分配 栈式存储：和过程的调用/返回同步进行分配和回收， 值的生命期与过程生命期相同 堆存储：数据对象比创建它的过程调用更长寿 手工进行回收 垃圾回收机制 4
静态和动态存储分配 • 静态分配 – 编译器在编译时刻就可以做出存储分配决定，不需要 考虑程序运行时刻的情形 – 全局常量、全局变量 • 动态分配 – 栈式存储：和过程的调用/返回同步进行分配和回收， 值的生命期与过程生命期相同 – 堆存储：数据对象比创建它的过程调用更长寿 • 手工进行回收 • 垃圾回收机制 4 南大编译许畅
栈式分配 。内容 活动树 活动记录 调用代码序列 栈中的变长数据 大编译许畅 5
栈式分配 • 内容 – 活动树 – 活动记录 – 调用代码序列 – 栈中的变长数据 5 南大编译许畅
活动树 过程调用（过程活动）在时间上总是嵌套的 后调用的先返回 因此用栈来分配过程活动所需内存空间 ·程序运行的所有过程活动可以用树表示 每个结点对应于一个过程活动 根结点对应于main过程的活动 过程p的某次活动对应的结点的所有子结点 表示此次活动所调用的各个过程活动 从左向右，表示调用的先后顺序 6
活动树 • 过程调用 (过程活动) 在时间上总是嵌套的 – 后调用的先返回 – 因此用栈来分配过程活动所需内存空间 • 程序运行的所有过程活动可以用树表示 – 每个结点对应于一个过程活动 – 根结点对应于main过程的活动 – 过程p的某次活动对应的结点的所有子结点 • 表示此次活动所调用的各个过程活动 • 从左向右，表示调用的先后顺序 6 南大编译许畅
活动树的例子 enter main() 快速排序程序 enter readArray() 过程调用（返回）序列和活动 leave readArray() enter quicksort(1,9) 树的前序（后序）遍历对应 enter partition(1,9) leave partition(1,9) 假定当前活动对应结点N, enter quicksort(1,3) 那么所有尚未结束的活动对 leave quicksort(1,3) 应于N及其祖先结点 enter quicksort(5,9) leave quicksort(5,9) leave quicksort(1,9) 9(1,9) leave main() p(1,9) q(1,3) q(5,9) 图7-2中程序的可能的活动序列 p(1,3)q(1,0)q(2,3) p(5,9)q(5,5)q(7,9 p(2,3)q(2,1)q(3,3) p(7,9)q(7,7)g(9,9) 7
活动树的例子 • 快速排序程序 – 过程调用 (返回) 序列和活动 树的前序 (后序) 遍历对应 – 假定当前活动对应结点N， 那么所有尚未结束的活动对 应于N及其祖先结点 7 南大编译许畅
活动记录 过程调用和返回由控制栈 实在参数 进行管理 返回值 。 每个活跃的活动对应于栈 中的一个活动记录 控制链 访问链 ·活动记录按照活动的开始 时间，从栈底到栈顶排列 保存的机器状态 局部数据 临时变量 8
活动记录 • 过程调用和返回由控制栈 进行管理 • 每个活跃的活动对应于栈 中的一个活动记录 • 活动记录按照活动的开始 时间，从栈底到栈顶排列 8 南大编译许畅
运行时刻栈的例子 integer a11] integer a11 。说明 main main main main [11]为全局变量 main无局部变量 integer i b)r被激活 r有局部变量i g有局部变量i, integer all] integer a11] main main main main 和参数m,n integer m,n integer m:n q(1,9) q1,9) q(1,9) q(1,9) integer i integer t p(1,9)q(1,3) integer m,n p(1,3)q(1,0) q(1,3) integer i c)Y被弹出栈，q(1,9)被压栈 d)控制返回到q1,3) 9
运行时刻栈的例子 • 说明 – a[11]为全局变量 – main无局部变量 – r有局部变量i – q有局部变量i， 和参数m, n 9 r r 南大编译许畅
调用代码序列 调用代码序列(Calling sequence)为活动记录分配 空间，填写记录中的信息 返回代码序列(Return sequence)恢复机器状态， 使调用者继续运行 调用代码序列会分割到调用者和被调用者中 根据源语言、目标机器和操作系统的限制，可以有不 同的分割方案 把代码尽可能放在被调用者中 10
调用代码序列 • 调用代码序列 (Calling sequence) 为活动记录分配 空间，填写记录中的信息 • 返回代码序列 (Return sequence) 恢复机器状态， 使调用者继续运行 • 调用代码序列会分割到调用者和被调用者中 – 根据源语言、目标机器和操作系统的限制，可以有不 同的分割方案 – 把代码尽可能放在被调用者中 10 南大编译许畅