六章运行时存储空间的组织和管理.ppt
《六章运行时存储空间的组织和管理.ppt》由会员分享,可在线阅读,更多相关《六章运行时存储空间的组织和管理.ppt(150页珍藏版)》请在三一文库上搜索。
1、第六章 运行时存储空间的组织和管理 术语 过程的活动 过程的一次执行称为过程的一次活动 活动记录 过程的活动需要可执行代码和存放所需信息的存 储空间,后者称为活动记录 本章内容 讨论一个活动记录中的数据布局 程序执行过程中,所有活动记录的组织方式 第六章 运行时存储空间的组织和管理 影响存储分配策略的语言特征 过程能否递归 当控制从过程的活动返回时,局部变量的值是否 要保留 过程能否访问非局部变量 过程调用的参数传递方式 过程能否作为参数被传递 过程能否作为结果值传递 存储块能否在程序控制下动态地分配 存储块是否必须显式地释放 6.1 局部存储分配 6.1.1 过程 语言概念: 过程定义、过程
2、调用、形式参数、实在参 数、活动的生存期 6.1 局部存储分配 6.1.2 名字的作用域和绑定 1、名字的作用域 一个声明起作用的程序部分称为该声明的作 用域 即使一个名字在程序中只声明一次,该名字 在程序运行时也可能表示不同的数据对象 6.1 局部存储分配 2、环境和状态 环境把名字映射到左值,而状态把左值映射 到右值(即名字到值有两步映射) 赋值改变状态,但不改变环境 过程调用改变环境 如果环境将名字x映射到存储单元s,则说x被 绑定到s 名字存储单元 状态 值 环境 6.1 局部存储分配 3、静态概念和动态概念的对应 静 态 概 念 动 态 对 应 过程的定义 过程的活动 6.1 局部存
3、储分配 3、静态概念和动态概念的对应 静 态 概 念 动 态 对 应 过程的定义 过程的活动 名字的声明 名字的绑定 6.1 局部存储分配 3、静态概念和动态概念的对应 静 态 概 念 动 态 对 应 过程的定义 过程的活动 名字的声明 名字的绑定 声明的作用域 绑定的生存期 6.1 局部存储分配 6.1.3 活动记录 活动记录的常见布局 临 时 数 据 参 数 局 部 数 据 机 器 状 态 访 问 链 控 制 链 返 回 值 6.1 局部存储分配 6.1.4 局部数据的布局 字节是可编址内存的最小单位 变量所需的存储空间可以根据其类型而静态 确定 一个过程所声明的局部变量,按这些变量声 明
4、时出现的次序,在局部数据域中依次分配 空间 局部数据的地址可以用相对于活动记录中某 个位置的地址来表示 数据对象的存储布局还有一个对齐问题 6.1 局部存储分配 例 在SPARC/Solaris工作站上下面两个结构 体的size分别是24和16,为什么不一样? typedef struct _atypedef struct _b char c1; char c1; long i; char c2; char c2; long i; double f; double f; a; b; 对齐:char : 1, long : 4, double : 8 6.1 局部存储分配 例 在SPARC/So
5、laris工作站上下面两个结构 体的size分别是24和16,为什么不一样? typedef struct _atypedef struct _b char c1;0 char c1; 0 long i;4 char c2; 1 char c2;8 long i; 4 double f; 16 double f; 8 a; b; 对齐:char : 1, long : 4, double : 8 6.1 局部存储分配 例 在X86/Linux机器的结果和SPARC/Solaris 工作站不一样,是20和16。 typedef struct _atypedef struct _b char c1
6、;0 char c1; 0 long i;4 char c2; 1 char c2;8 long i; 4 double f; 12 double f; 8 a; b; 对齐:char : 1, long : 4, double : 4 6.1 局部存储分配 6.1.5 程序块 本身含有局部变量声明的语句 可以嵌套 最接近的嵌套作用域规则 并列程序块不会同时活跃 并列程序块的变量可以重叠分配 6.1 局部存储分配 main() / 例 / / begin of B0 / int a = 0; int b = 0; / begin of B1 / int b = 1; / begin of B2
7、 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / / end of B1 / / end of B0 / 6.1 局部存储分配 main() / 例 / / begin of B0 / int a = 0; int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / / end of B1 / / end of B0 / 声 明
8、作 用 域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2 int b = 3; B3 a0 b0 b1 a2, b3 重叠分配存储单元 6.2 全局栈式存储分配 本节介绍 介绍程序运行时所需的各个活动记录在存储 空间的分配策略 描述过程的目标代码怎样访问绑定到局部名 字的存储单元 介绍三种分配策略 静态分配策略 栈式分配策略 堆式分配策略 6.2 全局栈式存储分配 6.2.1 运行时内存的划分 代 码 静 态 数 据 堆 栈 6.2 全局栈式存储分配 1、静态分配 名字在程序被编译时绑定到存储单元,不需 要运行时
9、的任何支持 绑定的生存期是程序的整个运行期间 6.2 全局栈式存储分配 2、静态分配给语言带来限制 递归过程不被允许 数据对象的长度和它在内存中位置的限制, 必须是在编译时可以知道的 数据结构不能动态建立 6.2 全局栈式存储分配 例 C程序的外部变量、静态局部变量以及程 序中出现的常量都可以静态分配 声明在函数外面 外部变量- 静态分配 静态外部变量- 静态分配 声明在函数里面 静态局部变量- 也是静态分配 自动变量- 不能静态分配 6.2 全局栈式存储分配 6.2.2 活动树和运行栈 1、活动树 用树来描绘控制进入和离开活动的方式 m q(1,9)r p(1,9) q(1,3) q(1,0
10、) p(1,3)q(2,3) q(2,1) q(3,3)p(2,3) q(5,9) q(5,5) p(5,9)q(7,9) q(7,7) q(9,9)p(7,9) 6.2 全局栈式存储分配 活动树的特点 每个结点代表某过程的一个活动 根结点代表主程序的活动 结点a是结点b的父结点,当且仅当控制流从a的 活动进入b的活动 结点a处于结点b的左边,当且仅当a的生存期先 于b的生存期 m q(1,9)r p(1,9) q(1,3) . . . . q(5,9) . . . . 6.2 全局栈式存储分配 当前活跃着的过程活动可以保存在一个栈中 例 控制栈的内容:m, q (1, 9), q (1, 3
11、), q (2, 3) m q(1,9)r p(1,9) q(1,3) q(1,0) p(1,3)q(2,3) q(2,1) q(3,3)p(2,3) q(5,9) q(5,5) p(5,9)q(7,9) q(7,7) q(9,9)p(7,9) 6.2 全局栈式存储分配 2、运行栈:把控制栈中的信息拓广到包括过程 活动所需的所有局部信息(即活动记录) 6.2 全局栈式存储分配 2、运行栈:把控制栈中的信息拓广到包括过程 活动所需的所有局部信息(即活动记录) main 栈 main 函数调用关系树 6.2 全局栈式存储分配 2、运行栈:把控制栈中的信息拓广到包括过程 活动所需的所有局部信息(即活
12、动记录) main r 函数调用关系树 main int i r ( ) 栈 6.2 全局栈式存储分配 2、运行栈:把控制栈中的信息拓广到包括过程 活动所需的所有局部信息(即活动记录) main q(1,9)r 函数调用关系树 main int i q (1, 9) int m, n 栈 6.2 全局栈式存储分配 2、运行栈:把控制栈中的信息拓广到包括过程 活动所需的所有局部信息(即活动记录) main q(1,9)r p(1,9)q(1,3) main int i q (1, 9) int m, n int i q (1, 3) int m, n 栈 函数调用关系树 6.2 全局栈式存储分配
13、 2、运行栈:把控制栈中的信息拓广到包括过程 活动所需的所有局部信息(即活动记录) main q(1,9)r p(1,9)q(1,3) q(1,0) p(1,3) main int i q (1, 9) int m, n int i q (1, 3) int m, n int i q (1, 0) int m, n 栈 函数调用关系树 6.2 全局栈式存储分配 6.2.3 调用序列 过程调用和过程返回都需要执行一些代码来 管理活动记录栈,保存或恢复机器状态等 过程调用序列 过程调用时执行的分配活动记录,把信息填入它的 域中,使被调用过程可以开始执行的代码 过程返回序列 被调用过程返回时执行的恢
14、复机器状态,释放被调 用过程活动记录,使调用过程能够继续执行的代码 调用序列和返回序列常常都分成两部分,分 处于调用过程和被调用过程中 6.2 全局栈式存储分配 即使是同一种语言,过程调用序列、返回序 列和活动记录中各域的排放次序,也会因实 现而异 设计这些序列和活动记录 的一些原则 以活动记录中间的某个 位置作为基地址 长度能较早确定的域放在 活动记录的中间 临 时 数 据 参 数 局 部 数 据 机 器 状 态 访 问 链 控 制 链 返 回 值 6.2 全局栈式存储分配 即使是同一种语言,过程调用序列、返回序 列和活动记录中各域的排放次序,也会因实 现而异 设计这些序列和活动记录 的一些
15、原则 一般把临时数据域放在 局部数据域的后面 把参数域和可能有的返回 值域放在紧靠调用者活动 记录的地方 临 时 数 据 参 数 局 部 数 据 机 器 状 态 访 问 链 控 制 链 返 回 值 6.2 全局栈式存储分配 即使是同一种语言,过程调用序列、返回序 列和活动记录中各域的排放次序,也会因实 现而异 设计这些序列和活动记录 的一些原则 用同样的代码来执行各个 活动的保存和恢复 临 时 数 据 参 数 局 部 数 据 机 器 状 态 访 问 链 控 制 链 返 回 值 6.2 全局栈式存储分配 1、过程p调用过程q的调用序列 返回值和参数 top_sp base_sp 临时数据局部数据
16、 控制链 和保存的机器状态 6.2 全局栈式存储分配 1、过程p调用过程q的调用序列 (1) p计算实参,依 次放入栈顶,并在 栈顶留出放返回值 的空间。top_sp的 值在此过程中被改 变 返回值和参数 top_sp base_sp 临时数据局部数据 控制链 和保存的机器状态 返回值和参数 top_sp 6.2 全局栈式存储分配 1、过程p调用过程q的调用序列 (2) p把返回地址和 当前base_sp的值 存入q的活动记录 中,建立q的访问 链,增加base_sp 的值 返回值和参数 top_sp base_sp 临时数据局部数据 控制链 和保存的机器状态 返回值和参数 控制链和返回地址
17、base_sp top_sp 6.2 全局栈式存储分配 1、过程p调用过程q的调用序列 (3) q保存寄存器的 值和其它机器状态 信息 返回值和参数 top_sp base_sp 临时数据局部数据 控制链 和保存的机器状态 返回值和参数 控制链 和保存的机器状态 6.2 全局栈式存储分配 1、过程p调用过程q的调用序列 (4) q根据局部数据 域和临时数据域的 大小增加top_sp的 值,初始化它的局 部数据,并开始执 行过程体 临时数据局部数据 返回值和参数 返回值和参数 控制链 和保存的机器状态 top_sp base_sp 临时数据局部数据 控制链 和保存的机器状态 6.2 全局栈式存储
18、分配 调用者p和被调用者q之间的任务划分 被调用者q的责任 调用者p的责任 调用者p的 活动记录 被调用者q 的活动记录 临时数据局部数据 返回值和参数 返回值和参数 控制链 和保存的机器状态 top_sp base_sp 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 6.2 全局栈式存储分配 2、过程p调用过程q的返回序列 临时数据局部数据 返回值和参数 返回值和参数 控制链 和保存的机器状态 top_sp base_sp 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 6.2 全局栈式存储分配 2、过程p调用过程q的返回序列 临时数据局部数据 返回值和参数
19、 返回值和参数 控制链 和保存的机器状态 top_sp base_sp 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 (1) q把返回值置入 邻近p的活动记录 的地方 参数个数可变场 合难以确定存放返 回值的位置,因此 通常用寄存器传递 返回值 6.2 全局栈式存储分配 2、过程p调用过程q的返回序列 (2) q对应调用序列 的步骤(4),减小 top_sp的值 返回值和参数 top_sp base_sp 临时数据局部数据 控制链 和保存的机器状态 返回值和参数 控制链 和保存的机器状态 6.2 全局栈式存储分配 2、过程p调用过程q的返回序列 (3) q恢复寄存器(包 括b
20、ase_sp)和机器 状态,返回p 返回值和参数 top_sp base_sp 临时数据局部数据 控制链 和保存的机器状态 返回值和参数 6.2 全局栈式存储分配 2、过程p调用过程q的返回序列 返回值和参数 top_sp base_sp 临时数据局部数据 控制链 和保存的机器状态 (4) p根据参数个数 与类型和返回值类 型调整top_sp,然 后取出返回值 6.2 全局栈式存储分配 3、过程的参数个数可变的情况 临时数据局部数据 参 数 参 数 控制链 和保存的机器状态 top_sp base_sp 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 (1) 函数返回值改 成用
21、寄存器传递 6.2 全局栈式存储分配 3、过程的参数个数可变的情况 临时数据局部数据 参数1, , 参数n 参数1, ,参数m 控制链 和保存的机器状态 top_sp base_sp 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 (2) 编译器产生将 实参表达式逆序计 算并将结果进栈的 代码 自上而下依次 是参数1, , 参数 n 6.2 全局栈式存储分配 3、过程的参数个数可变的情况 临时数据局部数据 参数1, , 参数n 参数1, ,参数m 控制链 和保存的机器状态 top_sp base_sp 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 (3) 被调
22、用函数能 准确地知道第一个 参数的位置 6.2 全局栈式存储分配 3、过程的参数个数可变的情况 临时数据局部数据 参数1, , 参数n 参数1, ,参数m 控制链 和保存的机器状态 top_sp base_sp 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 (4) 被调用函数根 据第一个参数到栈 中取第二、第三个 参数等等 6.2 全局栈式存储分配 3、过程的参数个数可变的情况 临时数据局部数据 参数1, , 参数n 参数1, ,参数m 控制链 和保存的机器状态 top_sp base_sp 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 C语言的printf
23、函 数就是按此方式, 用C语言编写的 下面语句的输出? printf(“%d, %d, %dn”); 6.2 全局栈式存储分配 6.2.4 栈上可变长数据 活动记录的长度在编译时不能确定的情况 例:局部数组的大小要等到过程激活时才能 确定 备注: Java语言的实现是将它们分配在堆上 6.2 全局栈式存储分配 访问动态分配的数组 控制链 数组A的指针 数组B的指针 top_sp base_sp . . . . . . . . . 栈 (1) 编译时, 在活动记录中 为这样的数组 分配存放数组 指针的单元 6.2 全局栈式存储分配 访问动态分配的数组 (2) 运行时, 这些指针指向 分配在栈顶的
24、 数组存储空间 控制链 数组A的指针 数组B的指针 top_sp base_sp . . . . . . . . . 栈 数组A 数组B 6.2 全局栈式存储分配 访问动态分配的数组 (3) 运行时, 对数组A和B 的访问都要通 过相应指针来 间接访问 控制链 数组A的指针 数组B的指针 top_sp base_sp . . . . . . . . . 栈 数组A 数组B 6.2 全局栈式存储分配 访问动态分配的数组 q的数组 q的活动记录 p的数组 p的活动记录 控制链 top_sp base_sp 数组A的指针 数组B的指针 数组A 数组B 控制链 . . . . . . . . . 栈
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运行 存储空间 组织 管理
链接地址:https://www.31doc.com/p-2338208.html