运行时存储空间的组织和管理研讨.ppt

《运行时存储空间的组织和管理研讨.ppt》由会员分享，可在线阅读，更多相关《运行时存储空间的组织和管理研讨.ppt（109页珍藏版）》请在金锄头文库上搜索。

1、运行时存储空间的组织和管理,运行时的程序,过程的活动 过程的一次执行称为过程的一次活动 活动记录 过程的活动需要可执行代码和存放所需信息的存储空间,后者称为活动记录,本章内容,影响存储分配策略的语言特征 活动记录中各种数据域的安排(局部) 各种存储分配策略（全局） 静态分配、栈式分配、堆式分配 非局部数据访问的实现方法 各种参数传递方式及其实现 符号表管理,影响存储分配策略的语言特征,过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量 过程调用的参数传递方式 过程能否作为参数被传递 过程能否作为结果值传递 存储块能否在程序控制下动态地分配 存储块是否必须显式

2、地释放,7.1 局部存储分配策略,7.1.1 过程 过程定义 过程声明：过程名过程体 过程调用 执行被调用过程的过程体 形式参数 过程定义中用于在主调和被调间传递数据的标识符 实在参数 过程调用时用于在主调和被调间传递数据的变元 活动的生存期 程序执行期间的连续的步序列（过程执行的第一到最后一步）,名字的作用域和绑定,名字的作用域 一个声明起作用的那部分程序称为该声明的作用域。 即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象（即保存值的存储单元）。 符号表可用来寻找对一个名字的出现起作用的声明,名字的绑定,从名字到值的两步映射。 环境把名字映射到左值，而状态把左值映

3、射到右值。 赋值改变状态，但不改变环境。 如果环境将名字x映射到存储单元s，我们就说x被绑定到s。,名字的绑定,静态概念和动态概念的对应,活动记录,过程一次执行所需的信息用一块连续的存储区来管理，称为活动记录。 一般的活动记录的布局：,指向调用者的 活动记录,用来访问存于其它活动记录中的非局部数据,局部数据的安排,字节是可编址内存的最小单位。 变量所需的存储空间可以根据其类型而静态确定。 一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配空间。 局部数据的地址可以用相对于某个位置的地址来表示。 数据对象的存储安排还有一个对齐问题。 整数必须放在内存中特定的位置，如被2

4、、4、8整除的地址,局部数据的安排,在SPARC/Solaris工作站上下面两个结构的size分别是24和16，为什么不一样？ typedef struct _a typedef struct _b char c1; char c1; long i; char c2; char c2; long i; double f; double f; a; b;,局部数据的安排,在SPARC/Solaris工作站上下面两个结构的size分别是24和16，为什么不一样？ typedef struct _a typedef struct _b char c1; 0 char c1; 0 long i; 4

5、char c2; 1 char c2; 8 long i; 4 double f; 16 double f;8 a; b;,局部数据的安排,在X86/Linux机器的结果和SPARC/Solaris工作站不一样，是20和16。 typedef struct _a typedef struct _b char c1; 0 char c1; 0 long i; 4 char c2; 1 char c2; 8 long i; 4 double f; 12 double f;8 a; b;,程序块,本身含有局部变量声明的语句 可以嵌套 最近嵌套作用域规则 并列程序块不会同时活跃 并列程序块的变量可以重

6、叠分配,程序块,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 /,7.2 全局存储分配策略,介绍程序运行时所需的各个活动记录在存储空间的分配策略 描述过程的目标代码怎样访问绑定到局部名字的存储单元 介绍三种分配策略 静态分配策略 栈式分配策略 堆式分配策略,7.2.1 运行时内存的划分

7、,7.2.2 静态存储分配策略,名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。 绑定的生存期是程序的整个运行时间。 控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。 每个活动记录的大小是固定的。 过程调用时保存信息的地址在编译时也是已知的。,例：某分段式程序运行时刻的内存划分,数组区 临时工作单元区 简单变量区 形式单元区 寄存器保护区 返回地址,某程序段,静态存储分配策略,顺序分配算法（基于调用图） 按照程序段出现的先后顺序逐段分配,程序段 区域 021 2236 3754 5571 7294 95104 共需要105个存储单元,程序段号/所需数据空间,能用更少的空间

8、么？,分层分配算法,允许程序段之间的覆盖（覆盖可能性分析）,程序段 区域 6 09 5 022 4 016 3 2340 2 1731 1 4162 共需要63个存储单元,思考：如何设计分配算法？,7/80,7.2.2 静态存储分配策略,静态分配给语言带来的限制 不允许递归过程 数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的 数据结构不能动态建立,7.2.2 静态存储分配策略,Fortran语言被设计成允许静态存储分配,7.2.2 静态存储分配策略,C语言程序的外部变量和程序中出现的常量都可以静态分配。 声明在函数外面 外部变量 静态外部变量 声明在函数里面 静态局部变量 自动

9、变量,7.2.3 栈式存储分配策略,如果过程允许递归 某一时刻过程A可能已被自己调用了若干次，但只有最近一次处于执行状态。其余各次等待返回被中断的那次调用 必须保存每次调用相应的数据区内容（活动记录） 引入一个运行栈 让过程的每次执行和过程的活动记录相对应。 每调用一次过程，就把该过程的活动记录压入栈中，返回时弹出。 假设寄存器top标记栈顶，局部名字x的相对地址为dx，则x的地址为top+dx 怎样刻画控制进入和离开活动的情况？,7.2.3 栈式存储分配策略,引入活动树 活动树:用树来描绘控制进入和离开活动的方式,7.2.3 栈式存储分配策略,活动树的特点 每个结点代表某过程的一个活动 根结

10、点代表主程序的活动 结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动 结点a处于结点b的左边，当且仅当a的生存期先于b的生存期,7.2.3 栈式全局存储分配策略,当前活跃着的过程活动保存在栈中 控制栈的内容：s, q (1, 9), q (1, 3), q (2, 3),7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,s,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记

11、录）,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,7.2.3 栈式存储分配策略,运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）,7.2.3 栈式存储分配策略,过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等 过程调用序列 过程调用时执行的分配活动记录，把信息填入它的域中的代码 过程返回序列 过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够继续执行的代码 调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中,7.2.3 栈式存储分配策略,即使是同一种语言，过程

12、调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异 设计这些序列和活动记录的一些原则是 以活动记录中间的某个位置作为基地址 长度能较早确定的域放在活动记录的中间 一般把临时数据域放在局部数据域的后面 把参数域和可能有的返回值域放在紧靠调用者活动记录的地方 用同样的代码来执行各个活动的保存和恢复,7.2.3 栈式存储分配策略,调用者和被调用者之间的任务划分,7.2.3 栈式存储分配策略,过程p调用过程q的调用序列 p在栈上留出放返回值的空间，并计算实参，依次放入栈顶，同时改变top_sp的值 p把返回地址和当前base_sp的值存入q的活动记录中，建立q的访问链，增加base_sp的值

13、 q保存寄存器的值和其它机器状态信息 q根据局部数据域和临时数据域的大小增加top_sp的值，初始化它的局部数据，并开始执行过程体,7.2.3 栈式存储分配策略,过程p调用过程q的返回序列 q把返回值置入邻近p的活动记录的地方 q对应调用序列的步骤（4），减小top_sp的值 q恢复寄存器（包括base_sp）和机器状态，返回p p根据参数个数与类型和返回值类型调整top_sp，然后取出返回值,7.2.3 栈式存储分配策略,过程的参数个数可变的情况 函数返回值改成用寄存器传递 编译器产生将这些参数逆序进栈的代码 被调用函数能准确地知道第一个参数的位置 被调用函数根据第一个参数到栈中取第二、第三

14、个参数等等 如C语言的printf,7.2.3 栈式存储分配策略,活动记录的长度在编译时不能确定的情况 局部数组的大小要等到过程激活时才能确定 在活动记录中为这样的数组分别存放数组指针的单元 运行时，这些指针指向分配在栈顶的存储空间,7.2.3 栈式存储分配策略,悬空引用,悬空引用：引用某个已被释放的存储单元 main() | int dangle ( ) | int p; | int i = 23; p = dangle ( ); | return | ,7.2.4 堆式存储分配策略,栈式分配策略在下列情况下行不通： 过程活动停止后，局部名字的值还必须维持 被调用者的活动比调用者的活动的生存

15、期更长，此时活动树不能正确描绘程序的控制流 不遵守栈式规则的有Pascal语言和C语言的动态变量 Java禁止程序员自己释放空间,7.3 非局部名字的访问,本节内容 无过程嵌套的静态作用域（C语言） 有过程嵌套的静态作用域（Pascal语言） 动态作用域（Lisp语言）,7.3.1 无过程嵌套的静态作用域,过程体中的非局部引用可以直接使用静态确定的地址 局部变量在栈顶的活动记录中，可以通过base_sp指针来访问 无须深入栈中取数据，无须访问链 过程可以作为参数来传递，也可以作为结果来返回,7.3.2 有过程嵌套的静态作用域,sort readarray exchange quicksort

16、partition,7.3.2 有过程嵌套的静态作用域,过程嵌套深度 sort 1 readarray 2 exchange 2 quicksort 2 partition 3,7.3.2 有过程嵌套的静态作用域,过程嵌套深度 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度,7.3.2 有过程嵌套的静态作用域,寻找非局部名字存储单元的访问链,s,a, x,q (1, 9),k, v,访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,s,a, x,q (1, 3),k, v,访问链,q (1, 9),k, v,访问链,p (1