资源预览内容
第1页 / 共109页
第2页 / 共109页
第3页 / 共109页
第4页 / 共109页
第5页 / 共109页
第6页 / 共109页
第7页 / 共109页
第8页 / 共109页
第9页 / 共109页
第10页 / 共109页
亲,该文档总共109页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
运行时存储空间的组织和管理,运行时的程序,过程的活动 过程的一次执行称为过程的一次活动 活动记录 过程的活动需要可执行代码和存放所需信息的存储空间,后者称为活动记录,本章内容,影响存储分配策略的语言特征 活动记录中各种数据域的安排(局部) 各种存储分配策略(全局) 静态分配、栈式分配、堆式分配 非局部数据访问的实现方法 各种参数传递方式及其实现 符号表管理,影响存储分配策略的语言特征,过程能否递归 当控制从过程的活动返回时,局部变量的值是否要保留 过程能否访问非局部变量 过程调用的参数传递方式 过程能否作为参数被传递 过程能否作为结果值传递 存储块能否在程序控制下动态地分配 存储块是否必须显式地释放,7.1 局部存储分配策略,7.1.1 过程 过程定义 过程声明:过程名过程体 过程调用 执行被调用过程的过程体 形式参数 过程定义中用于在主调和被调间传递数据的标识符 实在参数 过程调用时用于在主调和被调间传递数据的变元 活动的生存期 程序执行期间的连续的步序列(过程执行的第一到最后一步),名字的作用域和绑定,名字的作用域 一个声明起作用的那部分程序称为该声明的作用域。 即使一个名字在程序中只声明一次,该名字在程序运行时也可能表示不同的数据对象(即保存值的存储单元)。 符号表可用来寻找对一个名字的出现起作用的声明,名字的绑定,从名字到值的两步映射。 环境把名字映射到左值,而状态把左值映射到右值。 赋值改变状态,但不改变环境。 如果环境将名字x映射到存储单元s,我们就说x被绑定到s。,名字的绑定,静态概念和动态概念的对应,活动记录,过程一次执行所需的信息用一块连续的存储区来管理,称为活动记录。 一般的活动记录的布局:,指向调用者的 活动记录,用来访问存于其它活动记录中的非局部数据,局部数据的安排,字节是可编址内存的最小单位。 变量所需的存储空间可以根据其类型而静态确定。 一个过程所声明的局部变量,按这些变量声明时出现的次序,在局部数据域中依次分配空间。 局部数据的地址可以用相对于某个位置的地址来表示。 数据对象的存储安排还有一个对齐问题。 整数必须放在内存中特定的位置,如被2、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 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;,程序块,本身含有局部变量声明的语句 可以嵌套 最近嵌套作用域规则 并列程序块不会同时活跃 并列程序块的变量可以重叠分配,程序块,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.2.2 静态存储分配策略,名字在程序被编译时绑定到存储单元,不需要运行时的任何支持。 绑定的生存期是程序的整个运行时间。 控制再次进入该过程时,局部变量的值和控制上一次离开时的一样。 每个活动记录的大小是固定的。 过程调用时保存信息的地址在编译时也是已知的。,例:某分段式程序运行时刻的内存划分,数组区 临时工作单元区 简单变量区 形式单元区 寄存器保护区 返回地址,某程序段,静态存储分配策略,顺序分配算法(基于调用图) 按照程序段出现的先后顺序逐段分配,程序段 区域 021 2236 3754 5571 7294 95104 共需要105个存储单元,程序段号/所需数据空间,能用更少的空间么?,分层分配算法,允许程序段之间的覆盖(覆盖可能性分析),程序段 区域 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语言程序的外部变量和程序中出现的常量都可以静态分配。 声明在函数外面 外部变量 静态外部变量 声明在函数里面 静态局部变量 自动变量,7.2.3 栈式存储分配策略,如果过程允许递归 某一时刻过程A可能已被自己调用了若干次,但只有最近一次处于执行状态。其余各次等待返回被中断的那次调用 必须保存每次调用相应的数据区内容(活动记录) 引入一个运行栈 让过程的每次执行和过程的活动记录相对应。 每调用一次过程,就把该过程的活动记录压入栈中,返回时弹出。 假设寄存器top标记栈顶,局部名字x的相对地址为dx,则x的地址为top+dx 怎样刻画控制进入和离开活动的情况?,7.2.3 栈式存储分配策略,引入活动树 活动树:用树来描绘控制进入和离开活动的方式,7.2.3 栈式存储分配策略,活动树的特点 每个结点代表某过程的一个活动 根结点代表主程序的活动 结点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 栈式存储分配策略,运行栈:把控制栈中的信息拓广到包括过程活动所需的所有局部信息(即活动记录),7.2.3 栈式存储分配策略,运行栈:把控制栈中的信息拓广到包括过程活动所需的所有局部信息(即活动记录),7.2.3 栈式存储分配策略,运行栈:把控制栈中的信息拓广到包括过程活动所需的所有局部信息(即活动记录),7.2.3 栈式存储分配策略,过程调用和过程返回都需要执行一些代码来管理活动记录栈,保存或恢复机器状态等 过程调用序列 过程调用时执行的分配活动记录,把信息填入它的域中的代码 过程返回序列 过程返回时执行的恢复机器状态,释放活动记录,使调用过程能够继续执行的代码 调用序列和返回序列常常都分成两部分,分处于调用过程和被调用过程中,7.2.3 栈式存储分配策略,即使是同一种语言,过程调用序列、返回序列和活动记录中各域的排放次序,也会因实现而异 设计这些序列和活动记录的一些原则是 以活动记录中间的某个位置作为基地址 长度能较早确定的域放在活动记录的中间 一般把临时数据域放在局部数据域的后面 把参数域和可能有的返回值域放在紧靠调用者活动记录的地方 用同样的代码来执行各个活动的保存和恢复,7.2.3 栈式存储分配策略,调用者和被调用者之间的任务划分,7.2.3 栈式存储分配策略,过程p调用过程q的调用序列 p在栈上留出放返回值的空间,并计算实参,依次放入栈顶,同时改变top_sp的值 p把返回地址和当前base_sp的值存入q的活动记录中,建立q的访问链,增加base_sp的值 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 栈式存储分配策略,过程的参数个数可变的情况 函数返回值改成用寄存器传递 编译器产生将这些参数逆序进栈的代码 被调用函数能准确地知道第一个参数的位置 被调用函数根据第一个参数到栈中取第二、第三个参数等等 如C语言的printf,7.2.3 栈式存储分配策略,活动记录的长度在编译时不能确定的情况 局部数组的大小要等到过程激活时才能确定 在活动记录中为这样的数组分别存放数组指针的单元 运行时,这些指针指向分配在栈顶的存储空间,7.2.3 栈式存储分配策略,悬空引用,悬空引用:引用某个已被释放的存储单元 main() | int dangle ( ) | int p; | int i = 23; p = dangle ( ); | return | ,7.2.4 堆式存储分配策略,栈式分配策略在下列情况下行不通: 过程活动停止后,局部名字的值还必须维持 被调用者的活动比调用者的活动的生存期更长,此时活动树不能正确描绘程序的控制流 不遵守栈式规则的有Pascal语言和C语言的动态变量 Java禁止程序员自己释放空间,7.3 非局部名字的访问,本节内容 无过程嵌套的静态作用域(C语言) 有过程嵌套的静态作用域(Pascal语言) 动态作用域(Lisp语言),7.3.1 无过程嵌套的静态作用域,过程体中的非局部引用可以直接使用静态确定的地址 局部变量在栈顶的活动记录中,可以通过base_sp指针来访问 无须深入栈中取数据,无须访问链 过程可以作为参数来传递,也可以作为结果来返回,7.3.2 有过程嵌套的静态作用域,sort readarray exchange quicksort 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
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号