第九章 运行时存储空间的组织

第九章运行时存储空间的组织本章内容讨论一个活动记录中的数据安排程序执行过程中，所有活动记录的组织方式存储器的组织与存储分配的策略

名字存储单元状态值环境9.1目标程序运行时的活动9.1.1过程的活动活动

过程的一次执行称为过程的一次活动。活动记录 过程的活动需要可执行代码和存放所需信息的存储空间,后者称为活动记录。活动的生存期过程P一个活动的生存期，指的是从执行该过程体第一步操作到最后一步操作之间的操作序，包括执行P时调用其它过程花费的时间。9.1目标程序运行时的活动9.1.2参数传递传地址（callbyreference）把实在参数的地址传递给相应的形式参数。传值（callbyvalue）把实在参数的值计算出来并存放在一个被调用段可以拿得到的地方。被调用段开始工作时，首先把这些值抄进自己的形式单元中，然后就好像使用局部名一样使用这些形式单元。9.1目标程序运行时的活动传名（callbyname）：也称为“换名”过程调用的作用相当于把被调用段的过程体抄到调用出现的位置，把其中任一出现的形式参数都替换成相应的实在参数（文字替换）。9.2运行时存储器的划分9.2.1运行时存储器的划分编译程序为了使它编译后得到的目标程序能够运行，要从操作系统中获得一块存储空间。对这块提供运行的空间应该进行划分以便存放，其中包括生成的目标代码、数据对象和跟踪过程活动的控制栈。目标代码的大小在编译时可以确定，所以编译程序可以把它放在一个静态确定的区域。

运行时存储器的划分：目标代码静态数据栈堆9.2.2活动记录（ActivationRecord）为了管理过程在一次执行中所需要的信息，使用一个连续的存储块，这样的一个连续存储块称为活动记录。活动记录一般包含如下内容：临时单元内情向量局部变量形式单元静态链动态链返回地址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.1C的活动记录C的活动记录有以下四个项目。·连接数据，有两个：（1）老SP值，即前一活动记录的地址；（2）返回地址。·参数个数。·形式单元（存放实在参数的值或地址）。·过程的局部变量、数组内情向量和临时工作单元。9.4.2C的过程调用、过程进入、数组空间分配和过程返回9.5嵌套过程语言的栈式实现嵌套层次：如过程Q是在层数为i的过程P内定义，并且P是包围Q的最小过程，那么Q的层数就为i＋1。sort readarray exchange quicksort partition 9.5嵌套过程语言的栈式实现过程嵌套深度sort 1 readarray 2 exchange 2 quicksort 2 partition 39.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操作系统上的编译结果如下。根据所生成的汇编程序来解释程序中四个变量的存储分配、作用域、生存期和置初值方式等方面的区别。staticlongaa=10;shortbb=20;func(){ staticlongcc=30;shortdd=40;}例题1.data | .align4.align4 | .type cc.2,@object .typeaa,@object | .size cc.2,4 .sizeaa,4 |cc.2:aa: | .long30 .long10 |.text.globlbb | .align4 .align2 |.globlfunc

.typebb,@object |func: .sizebb,2 | ...bb: | movw$40,-2(%ebp) .value20 | ...例题2main(){ char*cp1,*cp2;

cp1="12345"; cp2="abcdefghij"; strcpy(cp1,cp2); printf("cp1=%s\ncp2=%s\n",cp1,cp2);}运行结果是： cp1=abcdefghij cp2=ghij为什么cp2所指的串被修改了？例题2因为常量串“12345”和“abcdefghij”连续分配在常数区执行前： 12345\0abcdefghij\0

cp1 cp2例题2因为常量串“12345”和“abcdefghij”连续分配在常数区执行前： 12345\0abcdefghij\0

cp1 cp2执行后：

abcdefghij\0fghij\0

cp1 cp2例题2因为常量串“12345”和“abcdefghij”连续分配在常数区执行前： 12345\0abcdefghij\0

cp1 cp2执行后：

abcdefghij\0fghij\0

cp1 cp2现在的编译器大都把程序中的串常量单独存放在一个只读的数据段中。例题3 下面的程序运行时输出3个整数。试从运行环境和printf的实现来分析，为什么此程序会有3个整数输出？

main(){

printf(“%d,%d,%d\n”);}例题4func(i,j,f,e)shorti,j;floatf,e;{shorti1,j1;floatf1,e1; printf(&i,&j,&f,&e);

printf(&i1,&j1,&f1,&e1);

}main(){shorti,j;floatf,e;func(i,j,f,e);}Addressofi,j,f,e=…36,…42,…44,…54（八进制数）Addressofi1,j1,f1,e1=…26,…24,…20,…14

例题4func(i,j,f,e) Sizesofshort,int,long,float,

shorti,j;floatf,e; double=2,4,4,4,8

{shorti1,j1;floatf1,e1; printf(&i,&j,&f,&e);

printf(&i1,&j1,&f1,&e1);

}main(){ shorti,j;floatf,e;func(i,j,f,e);}Addressofi,j,f,e=…36,…42,…44,…54（八进制数）Addressofi1,j1,f1,e1=…26,…24,…20,…14例题4func(i,j,f,e) Sizesofshort,int,long,float,

shorti,j;floatf,e; double=2,4,4,4,8

{shorti1,j1;floatf1,e1; printf(&i,&j,&f,&e);

printf(&i1,&j1,&f1,&e1);

}main() 为什么4个形式参数i,j,f,e的地址{ 间隔和它们类型的大小不一致

shorti,j;floatf,e;func(i,j,f,e);}Addressofi,j,f,e=…36,…42,…44,…54（八进制数）Addressofi1,j1,f1,e1=…26,…24,…20,…14例题4C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。

例题4C语言编译是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。

但是对于形式参数和实在参数是不同的整型，或者是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果，条件是，当需要把高级别类型数据向低级别类型数据转换时，不出现溢出。

例题4C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。

但是对于形式参数和实在参数是不同的整型，或者是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果，条件是，当需要把高级别类型数据向低级别类型数据转换时，不出现溢出。

当整型或实型数据作为实在参数时，将它们分别提升到long和double类型的数据再传递到被调用函数例题4C语言编译器是不做实在参数和形式参数的个数和类型是否一致的检查的，由程序员自己保证它们的一致性。

但是对于形式参数和实在参数是不同的整型，或者是不同的实型，编译器则试图保证目标代码运行时能得到正确的结果，条件是，当需要把高级别类型数据向低级别类型数据转换时，不出现溢出。

当整型或实型数据作为实在参数时，将它们分别提升到long和double类型的数据再传递到被调用函数被调用函数根据形式参数所声明的类型，决定是否要将实在参数向低级别类型转换。例题4低地址放高位高地址放低位shortlong长整型和短整型floatdoublee双精度型和浮点型例题4e，8个字节在main函数中参数压栈时的观点在fun