九章节运行时存储空间组织.ppt

第九章 运行时存储空间的组织,本章内容 讨论一个活动记录中的数据安排 程序执行过程中，所有活动记录的组织方式 存储器的组织与存储分配的策略,9.1 目标程序运行时的活动,9.1.1 过程的活动 活动 过程的一次执行称为过程的一次活动。 活动记录 过程的活动需要可执行代码和存放所需信息 的存储空间,后者称为活动记录。 活动的生存期 过程P一个活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序，包括执行P时调用其它过程花费的时间。,9.1 目标程序运行时的活动,9.1.2 参数传递 传地址（call by reference） 把实在参数的地址传递给相应的形式参数。 传值（call by value） 把实在参数的值计算出来并存放在一个被调用段可以拿得到的地方。被调用段开始工作时，首先把这些值抄进自己的形式单元中，然后就好像使用局部名一样使用这些形式单元。,9.1 目标程序运行时的活动,传名（call by name）：也称为“换名” 过程调用的作用相当于把被调用段的过程体抄到调用出现的位置，把其中任一出现的形式参数都替换成相应的实在参数（文字替换）。,9.2 运行时存储器的划分,9.2.1 运行时存储器的划分 编译程序为了使它编译后得到的目标程序能够运行，要从操作系统中获得一块存储空间。 对这块提供运行的空间应该进行划分以便存放，其中包括生成的目标代码、数据对象和跟踪过程活动的控制栈。目标代码的大小在编译时可以确定，所以编译程序可以把它放在一个静态确定的区域。,运行时存储器的划分：,9.2.2 活动记录（Activation Record） 为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这样的一个连续存储块称为活动记录。 活动记录一般包含如下内容： 临时单元 内情向量 局部变量 形式单元 静态链 动态链 返回地址,9.2.3 存储分配策略 1 静态分配 静态分配策略在编译时对所有数据对象分配固定的存储单元，且在运行时始终保持不变。 2 动态分配 栈式动态分配策略在运行时把存储器作为一个栈进行管理，运行时，每当调用一个过程，它所需要的存储空间就动态地分配于栈顶，一旦退出，它所占空间就予以释放。 堆式动态分配策略在运行时把存储器组织成堆结构，以便用户关于存储空间的申请与归还（回收），凡申请者从堆中分给一块，凡释放者退回给堆。,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量 过程调用的参数传递方式,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量 过程调用的参数传递方式 过程能否作为参数被传递,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量 过程调用的参数传递方式 过程能否作为参数被传递 过程能否作为结果值传递,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量 过程调用的参数传递方式 过程能否作为参数被传递 过程能否作为结果值传递 存储块能否在程序控制下动态地分配,9.2 运行时存储器的划分,影响存储分配策略的语言特征 过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量 过程调用的参数传递方式 过程能否作为参数被传递 过程能否作为结果值传递 存储块能否在程序控制下动态地分配 存储块是否必须显式地释放,9.3 静态存储分配,静态分配 名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。,9.3 静态存储分配,静态分配 名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。 绑定的生存期是程序的整个运行时间。,9.3 静态存储分配,静态分配 名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。 绑定的生存期是程序的整个运行时间。 控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。,9.3 静态存储分配,静态分配 名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。 绑定的生存期是程序的整个运行时间。 控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。 每个活动记录的大小是固定的。,9.3 静态存储分配,静态分配 名字在程序被编译时绑定到存储单元，不需要运行时的任何支持。 绑定的生存期是程序的整个运行时间。 控制再次进入该过程时，局部变量的值和控制上一次离开时的一样。 每个活动记录的大小是固定的。 过程调用时保存信息的地址在编译时也是已知的。,9.3 静态存储分配,静态分配给语言带来限制 递归过程不被允许,9.3 静态存储分配,静态分配给语言带来限制 递归过程不被允许 数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的,9.3 静态存储分配,静态分配给语言带来限制 递归过程不被允许 数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的 数据结构不能动态建立,9.3 静态存储分配,如果在编译时就能够确定一个程序在运行时所需的存储空间的大小，则在编译时就能够安排好目标程序运行时的全部数据空间，并能确定每个数据项的单元地址。存储空间的这种分配方法叫做静态分配。 FORTRAN程序的特点是：不允许过程的递归性；每个数据名所需的存储空间大小都是常量（即不许含可变体积的数据，如可变数组）；并且所有数据名的性质是完全确定的（不允许那种需在运行时动态确定其性质的名字）。,9.4 简单的栈式存储分配,这种语言没有分程序结构，过程定义不许嵌套，但允许过程的递归调用。C就是这样的一种语言。,9.4.1 C的活动记录 C的活动记录有以下四个项目。 ·连接数据，有两个： （1）老SP值，即前一活动记录的地址； （2）返回地址。 ·参数个数。 ·形式单元（存放实在参数的值或地址）。 ·过程的局部变量、数组内情向量和临时工 作单元。 9.4.2 C的过程调用、过程进入、数组空间分配和过程返回,9.5 嵌套过程语言的栈式实现,嵌套层次： 如过程 Q是在层数为 i的过程 P内定义，并且 P是包围 Q的最小过程，那么Q的层数就为 i1。 sort readarray exchange quicksort partition,9.5 嵌套过程语言的栈式实现,过程嵌套深度 sort 1 readarray 2 exchange 2 quicksort 2 partition 3,9.5 嵌套过程语言的栈式实现,过程嵌套深度 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度,9.5 嵌套过程语言的栈式实现,栈式分配 栈式分配策略在下列情况下行不通： 过程活动停止后，局部名字的值还必须维持,9.5 嵌套过程语言的栈式实现,栈式分配 栈式分配策略在下列情况下行不通： 过程活动停止后，局部名字的值还必须维持 被调用者的活动比调用者的活动活得更长，此时活动树不能正确描绘程序的控制流,9.5 嵌套过程语言的栈式实现,栈式分配 栈式分配策略在下列情况下行不通： 过程活动停止后，局部名字的值还必须维持 被调用者的活动比调用者的活动活得更长，此时活动树不能正确描绘程序的控制流 不遵守栈式规则的有Pascal语言和C语言的动态变量 Java禁止程序员自己释放空间,9.6 堆式动态存储分配,堆式的动态存储 如果一个程序语言允许用户自由地申请数据空间和退还数据空间，或者不仅有过程而且有进程（process）的程序结构，那么，由于空间的使用未必服从“先请后还，后请先还”的原则，因此，栈式的动态分配方案就不适用了。在这种情况下通常使用一种称之为堆式的动态存储分配方案。,9.6 堆式动态存储分配,9.6.1堆式动态存储分配的实现 1.定长块管理 堆式存储分配最简单的实现是按定长块进行 。 初始化时，将堆存储空间分成长度相等的若干块，每块中指定一个链域，按照邻块的顺序把所有块链成一个链表,9.6 堆式动态存储分配,2.变长块管理 （1）首次满足法：只要在空闲块链表中找到满足需要的一块，就进行分配。 （2）最优满足法：将空闲块链表中一个不小于申请块且最接近于申请块的空闲块分配给用户，则系统在分配前首先要对空闲块链表从头至尾扫描一遍，然后从中找出一块不小于申请块且最接近于申请块的空闲块分配。 （3）最差满足法：将空闲块表中不小于申请块且是最大的空闲的一部分分配给用户。,9.6 堆式动态存储分配,9.6.2 隐式存储回收 隐式存储回收要求用户程序和支持运行的回收子程序并行工作，因为回收子程序需要知道分配给用户程序的存储块何时不再使用。,例 题 1,一个C语言程序及其在X86/Linux操作系统上的编译结 果如下。根据所生成的汇编程序来解释程序中四个变 量的存储分配、作用域、生存期和置初值方式等方面 的区别。 static long aa = 10; short bb = 20; func() static long cc = 30; short dd = 40; ,例 题 1,.data | .align 4 .align 4 | .type cc.2,object .type aa,object | .size cc.2,4 .size aa,4 | cc.2: aa: | .long 30 .long 10 | .text .globl bb | .align 4 .align 2 | .globl func .type bb,object | func: .size bb,2 | . . . bb: | movw $40,-2(%ebp) .value 20 | . . .,例 题 2,main() char *cp1, *cp2; cp1 = “12345“; cp2 = “abcdefghij“; strcpy(cp1,cp2); printf(“cp1 = %sncp2 = %sn“, cp1, cp2); 运行结果是： cp1 = abcdefghij cp2 = ghij 为什么cp2所指的串被修改了？,例 题 2,因为常量串“12345”和“abcdefghij”连续分配在常数区 执行前： 1 2 3 4 5 0 a b c d e f g h i j 0 cp1 cp2,例 题 2,因为常量串“12345”和“abcdefghij”连续分配在常数区 执行前： 1 2 3 4 5 0 a b c d e f g h i j 0 cp1 cp2 执行后： a b c d e f g h i j 0 f g h i j 0 cp1 cp2,例 题 2,因为常量串“12345”和“abcdefghij”连续分配在常数区 执行前： 1 2 3 4 5 0 a b c d e f g h i j 0 cp1 cp2 执行后： a b c d e f g h i j 0 f g h i j 0 cp1 cp2 现在的编译器大都把程序中的串常量单独存放在一个 只读的数据段中。,例 题 3,下面的程序运行时输出3个整数。试从运行环境和printf的实现来分析，为什么此程序会有3个整数输出？ main() printf(“%d, %d, %dn”); ,例 题 4,func(i,j,f,e) short i,j; float f,e; short i1,j1; float f1,e1; printf( Address of i,j,f,e = 36, 42, 44, 54（八进制数） Address of i1,j1,f1,e1 = 26, 24, 20, 14,例 题 4,func(i,j,f,e) Sizes of short, int, long, float, short i,j; float f,e; double = 2, 4, 4, 4, 8 short i1,j1; float f1,e1; printf( Address of i,j,f,e = 36, 42, 44, 54（八进制数） Address of i1,j1,f1,e1 = 26, 24, 20, 14,例 题 4,func(i,j,f,e) Sizes of short, int, long, float, short i,j; float f,e; double = 2, 4, 4, 4, 8 short i1,j1; float f1,e1; printf( Address of i,j,f,e = 36, 42, 44, 54（八进制数） Address of i1,j1,f1,e1 = 26, 24, 20, 14,例 题 4,C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。,例 题 4,C语言编译是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。 但是对于形式参数和实在参数是不同的整型，或者是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果，条件是，当需要把高级别类型数据向低级别类型数据转换时，不出现溢出。,例 题 4,C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。 但是对于形式参数和实在参数是不同的整型，或者是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果，条件是，当需要把高级别类型数据向低级别类型数据转换时，不出现溢出。 当整型或实型数据作为实在参数时，将它们分别提升到long和double类型的数据再传递到被调用函数,例 题 4,C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。 但是对于形式参数和实在参数是不同的整型，或者是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果，条件是，当需要把高级别类型数据向低级别类型数据转换时，不出现溢出。 当整型或实型数据作为实在参数时，将它们分别提升到long和double类型的数据再传递到被调用函数 被调用函数根据形式参数所声明的类型，决定是否要将实在参数向低级别类型转换。,例 题 4,例 题 4,例 题 5,main() func(); printf(“Return from funcn“); func() char s4; strcpy(s,“12345678“); printf(“%sn“,s); ,例 题 5,main() func(); printf(“Return from funcn“); func() char s4; strcpy(s,“12345678“); printf(“%sn“,s); 在X86/Linux操作系统上的运行结果如下： 12345678 Return from func Segmentation fault (core dumped),例 题 5,main() func(); printf(“Return from funcn“); func() char s4; strcpy(s,“12345678“); printf(“%sn“,s); ,例 题 5,main() func(); printf(“Return from funcn“); func() char s4; strcpy(s,“123456789“); printf(“%sn“,s); 123456789 Segmentation fault (core dumped),