《编译原理第六章运行时存储空间的组织和管理课件》由会员分享，可在线阅读，更多相关《编译原理第六章运行时存储空间的组织和管理课件（110页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 术语术语过程的过程的活动活动过程的一次执行称为过程的一次活动过程的一次执行称为过程的一次活动活动记录活动记录过程的活动需要可执行代码和存放所需信息的存储空间过程的活动需要可执行代码和存放所需信息的存储空间, ,后者称为活动记录后者称为活动记录本章内容本章内容讨论一个活动记录中的数据布局讨论一个活动记录中的数据布局程序执行过程中，所有活动记录的组织方式程序执行过程中，所有活动记录的组织方式第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征过程能否递归过程能否递
2、归当控制从过程的活动返回时，局部变量的值是否要保留当控制从过程的活动返回时，局部变量的值是否要保留过程能否访问非局部变量过程能否访问非局部变量过程调用的参数传递方式过程调用的参数传递方式过程能否作为参数被传递过程能否作为参数被传递过程能否作为结果值传递过程能否作为结果值传递存储块能否在程序控制下动态地分配存储块能否在程序控制下动态地分配存储块是否必须显式地释放存储块是否必须显式地释放6.1 局部存储分配局部存储分配6.1.1过程过程语言概念：语言概念：过程定义、过程定义、过程过程调用、形式参数、实在参调用、形式参数、实在参数、数、活动的活动的生存期生存期6.1 局部存储分配局部存储分配6.1.
3、2名字的作用域和绑定名字的作用域和绑定1、名字的作用域、名字的作用域一个声明起作用的程序部分称为该声明的一个声明起作用的程序部分称为该声明的作作用域用域6.1 局部存储分配局部存储分配2、环境和状态、环境和状态环境把名字映射到左值，而状态把左值映射环境把名字映射到左值，而状态把左值映射到右值（即到右值（即名字到值有两步映射名字到值有两步映射）赋值改变状态，但不改变环境赋值改变状态，但不改变环境过程调用改变环境过程调用改变环境如果环境将名字如果环境将名字x映射到存储单元映射到存储单元s，则说则说x被被绑定绑定到到s名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配3、静
4、态概念和动态概念的对应、静态概念和动态概念的对应 静静态态概概念念 动动态态对对应应 过程的定义过程的定义 过程的活动过程的活动 6.1 局部存储分配局部存储分配3、静态概念和动态概念的对应、静态概念和动态概念的对应 静静态态概概念念 动动态态对对应应 过程的定义过程的定义 过程的活动过程的活动 名字的声明名字的声明名字的绑定名字的绑定6.1 局部存储分配局部存储分配3、静态概念和动态概念的对应、静态概念和动态概念的对应 静静态态概概念念 动动态态对对应应 过程的定义过程的定义 过程的活动过程的活动 名字的声明名字的声明名字的绑定名字的绑定声明的作用域声明的作用域 绑定的生存期绑定的生存期6.
5、1 局部存储分配局部存储分配6.1.3活动记录活动记录活动记录的常见布局活动记录的常见布局返返回回值值临临时时数数据据参参数数控控制制链链访访问问链链机机器器状状态态局局部部数数据据6.1 局部存储分配局部存储分配6.1.4局部数据的布局局部数据的布局字节是可编址内存的最小单位字节是可编址内存的最小单位一一个个过过程程所所声声明明的的局局部部变变量量，按按这这些些变变量量声声明明时时出出现的次序，在局部数据域中依次分配空间现的次序，在局部数据域中依次分配空间局局部部数数据据的的地地址址可可以以用用相相对对于于某某个个位位置置的的地地址址来来表表示示数据对象的存储布局还有一个数据对象的存储布局还
6、有一个对齐问题对齐问题6.1 局部存储分配局部存储分配例例 在在SPARC/Solaris工工作作站站上上下下面面两两个个结结构构体体的的size分别是分别是24和和16，为什么不一样？，为什么不一样？typedefstruct_atypedefstruct_bchar c1;charc1;long i;char c2;char c2;longi;doublef;doublef;a;b;对齐：对齐：char:1,long:4,double:86.1 局部存储分配局部存储分配例例 在在SPARC/Solaris工工作作站站上上下下面面两两个个结结构构体体的的size分别是分别是24和和16，为什
7、么不一样？，为什么不一样？typedefstruct_atypedefstruct_bchar c1;0charc1;0long i;4char c2;1char c2;8longi;4doublef;16doublef;8a;b;对齐：对齐：char:1,long:4,double:86.1 局部存储分配局部存储分配例例 在在X86/Linux机机器器的的结结果果和和SPARC/Solaris工工作作站不一样，是站不一样，是20和和16。typedefstruct_atypedefstruct_bchar c1;0charc1;0long i;4char c2;1char c2;8longi
8、;4doublef;12doublef;8a;b;对齐：对齐：char:1,long:4,double:46.1 局部存储分配局部存储分配 程序块程序块本身含有局部变量声明的语句本身含有局部变量声明的语句可以嵌套可以嵌套最接近的嵌套最接近的嵌套作用域规则作用域规则并列程序块不会同时活跃并列程序块不会同时活跃并列程序块的变量可以重叠分配并列程序块的变量可以重叠分配6.1 局部存储分配局部存储分配main()/ 例例 / beginofB0 /inta=0;intb=0;/ beginofB1 /intb=1;/ beginofB2 /inta=2;/ endofB2 / beginofB3 /i
9、ntb=3;/ endofB3 / endofB1 / endofB0 /声声明明作作用用域域inta=0;B0 B2intb=0;B0 B1intb=1;B1 B3inta=2;B2intb=3;B3a0b0b1a2,b3重叠分配存储单元重叠分配存储单元6.2 全局栈式存储分配全局栈式存储分配本节介绍本节介绍描描述述过过程程的的目目标标代代码码怎怎样样访访问问绑绑定定到到局局部部名名字字的的存存储单元储单元介绍三种分配策略介绍三种分配策略静态分配策略静态分配策略栈式分配策略栈式分配策略堆式分配策略堆式分配策略6.2 全局栈式存储分配全局栈式存储分配 运行时内存的划分运行时内存的划分代代码码静
10、静态态数数据据堆堆栈栈6.2 全局栈式存储分配全局栈式存储分配1、静态分配、静态分配名名字字在在程程序序被被编编译译时时绑绑定定到到存存储储单单元元，不不需需要运行时的任何支持要运行时的任何支持绑定的生存期是程序的整个运行期间绑定的生存期是程序的整个运行期间6.2 全局栈式存储分配全局栈式存储分配2、静态分配给语言带来限制、静态分配给语言带来限制递归过程不被允许递归过程不被允许数数据据对对象象的的长长度度和和它它在在内内存存中中位位置置的的限限制制，必须是在编译时可以知道的必须是在编译时可以知道的数据结构不能动态建立数据结构不能动态建立6.2 全局栈式存储分配全局栈式存储分配例例 C程程序序的
11、的外外部部变变量量、静静态态局局部部变变量量以以及及程程序中出现的常量都可以静态分配序中出现的常量都可以静态分配声明在函数外面声明在函数外面外部变量外部变量 静态分配静态分配静态外部变量静态外部变量 静态分配静态分配声明在函数里面声明在函数里面静态局部变量静态局部变量 也是静态分配也是静态分配自动变量自动变量 不能静态分配不能静态分配6.2 全局栈式存储分配全局栈式存储分配 活动树和运行栈活动树和运行栈1、活动树、活动树用树来描绘控制进入和离开活动的方式用树来描绘控制进入和离开活动的方式mq(1,9)rp(1,9)q(1,3)q(1,0)p(1,3)q(2,3)q(2,1)q(3,3)p(2,
12、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的生存期的生存期6.2 全局栈式存储分配全局栈式存储分配当前活跃着的过程活动可以保存在一个栈中当前活跃着的过程活动可以保存在一个栈中例例控制栈的内容：控
13、制栈的内容：m,q(1,9),q(1,3),q(2,3) mq(1,9)rp(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、运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活
14、动所需的所有局部信息（即活动记录）ma:arraym6.2 全局栈式存储分配全局栈式存储分配2、运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mintira:arraymr6.2 全局栈式存储分配全局栈式存储分配2、运运行行栈栈：把把控控制制栈栈中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mq(1,9)rmintiq(1,9)a:arrayintm,n6.2 全局栈式存储分配全局栈式存储分配2、运运行行栈栈：把把控控制制栈栈
15、中中的的信信息息拓拓广广到到包包括括过过程程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mq(1,9)rp(1,9) q(1,3)q(1,0)p(1,3)q(1,9)mintia:arrayintm,nintm,nintiq(1,3)6.2 全局栈式存储分配全局栈式存储分配 调用序列调用序列过程调用序列过程调用序列过程调用时执行的分配活动记录、把信息填入域中的代码过程调用时执行的分配活动记录、把信息填入域中的代码过程返回序列过程返回序列过过程程返返回回时时执执行行的的恢恢复复机机器器状状态态，释释放放活活动动记记录录，使使调调用用过过程能够继续执行的代码程能够继续执
16、行的代码6.2 全局栈式存储分配全局栈式存储分配即即使使是是同同一一种种语语言言，过过程程调调用用序序列列、返返回回序序列列和和活活动记录中各域的排放次序，也会因实现而异动记录中各域的排放次序，也会因实现而异设计这些序列和活动记录的原则设计这些序列和活动记录的原则调用者和被调用者交流的数据放在调用者和被调用者交流的数据放在活动记录开始处，并尽可能靠近调用活动记录开始处，并尽可能靠近调用者的活动记录者的活动记录固定长度的项放在活动记录中间。固定长度的项放在活动记录中间。在编译时不能及时知道大小的项目在编译时不能及时知道大小的项目放在活动记录末端放在活动记录末端返返回回值值临临时时数数据据参参数数
17、控控制制链链访访问问链链机机器器状状态态局局部部数数据据6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列(1)p计算实参，依计算实参，依次放入栈顶，并在次放入栈顶，并在栈顶留出放返回值栈顶留出放返回值的空间。的空间。top_sp的的值在此过程中被改值在此过程中被改变变返回值和参数返回值和参数top_sp base_sp 临时数
18、据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 返回值和参数返回值和参数6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列(2)p把返回地址和把返回地址和当前当前base_sp的值的值存入存入q的活动记录的活动记录中，建立中，建立q的访问的访问链，增加链，增加base_sp的值的值返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 返回值和参数返回值和参数控制链和返回地址控制链和返回地址6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过
19、程调用过程q的调用序列的调用序列(3)q保存寄存器的保存寄存器的值和其它机器状态值和其它机器状态信息信息返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 返回值和参数返回值和参数控制链控制链和保存的机器状态和保存的机器状态6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列(4)q根据局部数据根据局部数据域和临时数据域的域和临时数据域的大小增加大小增加top_sp的的值，初始化它的局值，初始化它的局部数据，并开始执部数据，并开始执行过程体行过程体临时数据局部数据临时数据局
20、部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配调用者调用者p和被调用者和被调用者q之间的任务划分之间的任务划分被调用者被调用者q的责任的责任调用者调用者p的责任的责任调用者调用者p的的活动记录活动记录被被调用者调用者q的活动记录的活动记录临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈
21、增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列临时数据局部数据临时数据局部数据返回值返回值和参数和参数返回值和
22、参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 (1)q把返回值置入邻把返回值置入邻近近p的活动记录存放的活动记录存放返回值的地方返回值的地方6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列(2)q对应调用序列对应调用序列的步骤的步骤(4)，减小，减小top_sp的值的值返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 返回值和
23、参数返回值和参数控制链控制链和保存的机器状态和保存的机器状态6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列(3)q恢复寄存器恢复寄存器(包包括括base_sp)和机器和机器状态，返回状态，返回p返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 返回值和参数返回值和参数6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链和保存的机
24、器状态和保存的机器状态 (4)p根据参数个数根据参数个数与类型和返回值类与类型和返回值类型调整型调整top_sp，然然后取出返回值后取出返回值6.2 全局栈式存储分配全局栈式存储分配6.2.4栈上可变长数据栈上可变长数据活动记录的长度在编译时不能确定的情况活动记录的长度在编译时不能确定的情况例例：局局部部数数组组的的大大小小要要等等到到过过程程激激活活时时才才能能确定确定备注：备注： Java语言的实现是将它们分配在堆上语言的实现是将它们分配在堆上6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组控制链控制链数组数组A的指针的指针数组数组B的指针的指针top_sp b
25、ase_sp .栈栈(1)编译时，在活编译时，在活动记录中为这样动记录中为这样的数组分别存放的数组分别存放数组指针的单元数组指针的单元6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组(2)运行时，运行时，这些指针指向这些指针指向分配在栈顶的分配在栈顶的存储空间存储空间控制链控制链数组数组A的指针的指针数组数组B的指针的指针top_sp base_sp .栈栈数组数组A数组数组B6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组(3)运行时，运行时，对数组对数组A和和B的访问都要通的访问都要通过相应指针来过相应指针来间接访问间接访问控制链控制
26、链数组数组A的指针的指针数组数组B的指针的指针top_sp base_sp .栈栈数组数组A数组数组B6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组q的数组的数组q的活动记录的活动记录p的数组的数组p的活动记录的活动记录控制链控制链top_sp base_sp 数组数组A的指针的指针数组数组B的指针的指针数组数组A数组数组B控制链控制链.栈栈6.2 全局栈式存储分配全局栈式存储分配6.2.5悬空引用悬空引用悬空引用：悬空引用：引用某个已被释放的存储单元引用某个已被释放的存储单元6.2 全局栈式存储分配全局栈式存储分配6.2.5悬空引用悬空引用悬空引用：悬空引用：引
27、用某个已被释放的存储单元引用某个已被释放的存储单元main()|int dangle()|int q;|intj=20;q=dangle(); |return&j;|*6.3 非局部名字的访问非局部名字的访问本节介绍本节介绍无过程嵌套的静态作用域（无过程嵌套的静态作用域（C语言）语言）有过程嵌套的静态作用域有过程嵌套的静态作用域（Pascal语言）语言）动态作用域动态作用域（Lisp语言）语言）*6.3 非局部名字的访问非局部名字的访问 无过程嵌套的静态作用域无过程嵌套的静态作用域过过程程体体中中的的非非局局部部引引用用可可以以直直接接使使用用静静态态确确定的地址定的地址局局部部变变量量在在栈
28、栈顶顶的的活活动动记记录录中中，可可以以通通过过base_sp指针来访问指针来访问无须深入栈中取数据，无须访问链无须深入栈中取数据，无须访问链过过程程可可以以作作为为参参数数来来传传递递，也也可可以以作作为为结结果果来返回来返回*6.3 非局部名字的访问非局部名字的访问 有过程嵌套的静态作用域有过程嵌套的静态作用域sortreadarrayexchangequicksortpartition*6.3 非局部名字的访问非局部名字的访问 有过程嵌套的静态作用域有过程嵌套的静态作用域过程过程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition3变量的
29、嵌套深度：它的声明所在过程的嵌套变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度深度作为该名字的嵌套深度访问链访问链用来寻找非局部用来寻找非局部名字的存储单元名字的存储单元sa,xq(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链e(1,3)访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链*6.3非局部名字的访问非局部名字的访问*6.3 非局部名字的访问非局部名字的访问访问非
30、局部名字的存储单元访问非局部名字的存储单元假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度为它引用嵌套深度为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单元sort1readarray2exchange2quicksort2partition3*6.3 非局部名字的访问非局部名字的访问访问非局部名字的存储单元访问非局部名字的存储单元假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度为它引用嵌套深度为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单元从栈顶的活动记录开始，追踪访问链从栈顶的活动记录开始，追踪访问链np na次次到
31、达到达a的声明所在过程的活动记录的声明所在过程的活动记录访问链的追踪用间接操作就可完成访问链的追踪用间接操作就可完成sort1readarray2exchange2quicksort2partition3访问非局部名字的存储单元访问非局部名字的存储单元 sortreadarrayexchangequicksortpartitionsa,xq(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链sa,xq(1,3)k,v访问链访问链q(1,9)k,v访问链访问链p(1,3)i,j访问链访问链e(1,3)访问链访问链sa,xq(1,3)k,v访问链访问链q
32、(1,9)k,v访问链访问链p(1,3)i,j访问链访问链*6.3非局部名字的访问非局部名字的访问*6.3 非局部名字的访问非局部名字的访问C语语言言的的函函数数声声明明不不能能嵌嵌套套，函函数数不不论论在在什什么么情况下激活，要访问的数据分成两种情况情况下激活，要访问的数据分成两种情况非非静静态态局局部部变变量量（包包括括形形式式参参数数），它它们们分分配配在在活动记录栈顶的那个活动记录中活动记录栈顶的那个活动记录中外外部部变变量量（包包括括定定义义在在其其它它源源文文件件之之中中的的外外部部变变量量）和和静静态态的的局局部部变变量量，它它们们都都分分配配在在静静态态数数据据区区6.4 参参
33、 数数 传传 递递6.4.1值调用值调用实参的右值传给被调用过程实参的右值传给被调用过程值调用可以如下实现值调用可以如下实现把把形形参参当当作作所所在在过过程程的的局局部部名名看看待待，形形参参的的存存储储单元在该过程的活动记录中单元在该过程的活动记录中调调用用过过程程计计算算实实参参，并并把把其其右右值值放放入入形形参参的的存存储储单元中单元中6.4 参参 数数 传传 递递6.4.2引用调用引用调用实参的左值传给被调用过程实参的左值传给被调用过程引用调用可以如下实现：引用调用可以如下实现：把把形形参参当当作作所所在在过过程程的的局局部部名名看看待待，形形参参的的存存储储单元在该过程的活动记录
34、中单元在该过程的活动记录中调调用用过过程程计计算算实实参参，把把实实参参的的左左值值放放入入形形参参的的存存储单元储单元在在被被调调用用过过程程的的目目标标代代码码中中，任任何何对对形形参参的的引引用用都是通过传给该过程的指针来间接引用实参都是通过传给该过程的指针来间接引用实参6.4 参参 数数 传传 递递6.4.3换名调用换名调用从概念上说，每次调用时，用实参表达式对从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行形参进行正文替换，然后再执行procedureswap(varx,y:integer);vartemp:integer;begintemp:=x;x:=y;y:=
35、tempend6.4 参参 数数 传传 递递6.4.3换名调用换名调用从概念上说，每次调用时，用实参表达式对从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行形参进行正文替换，然后再执行procedureswap(varx,y:integer);vartemp:integer;例如：例如：调用调用swap(i,ai)begintemp:=x;x:=y;y:=tempend6.4 参参 数数 传传 递递6.4.3换名调用换名调用从概念上说，每次调用时，用实参表达式对从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行形参进行正文替换，然后再执行proceduresw
36、ap(varx,y:integer);vartemp:integer;例如：例如：调用调用swap(i,ai)begin替换结果：替换结果：temp:=i;temp:=x;i:=ai;x:=y;ai:=tempy:=tempend6.4 参参 数数 传传 递递6.4.3换名调用换名调用从概念上说，每次调用时，用实参表达式对从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行形参进行正文替换，然后再执行procedureswap(varx,y:integer);vartemp:integer;例如：例如：调用调用swap(i,ai)begin替换结果：替换结果：temp:=i;te
37、mp:=x;i:=ai;x:=y;ai:=tempy:=temp交换两个数据的程序交换两个数据的程序end并非总是正确并非总是正确栈式存储分配策略在下列情况下不能使用：栈式存储分配策略在下列情况下不能使用：活动结束时必须保持局部名字的值活动结束时必须保持局部名字的值被调用者的活动比调用者的活动的生存期长。被调用者的活动比调用者的活动的生存期长。堆式存储器的策略：（堆管理器管理堆空间）堆式存储器的策略：（堆管理器管理堆空间）把连续存储区域分成块，当活动记录或其他对象需把连续存储区域分成块，当活动记录或其他对象需要时就分配。要时就分配。块的释放可以按任意次序进行，所以经过一段时间块的释放可以按任意
38、次序进行，所以经过一段时间后，堆可能包含交错的正在使用的和已经释放的区后，堆可能包含交错的正在使用的和已经释放的区域域6.5堆堆管管理理6.5 堆堆管管理理堆式分配堆式分配堆用来存放生存期不确定的数据堆用来存放生存期不确定的数据C+和和Java允允许许程程序序员员用用new创创建建对对象象，它它们们的的生生存存期期没没有被约束在创建它们的过程活动的生成期之内有被约束在创建它们的过程活动的生成期之内实现内存回收是内存管理器的责任实现内存回收是内存管理器的责任堆空间的回收有两种不同方式堆空间的回收有两种不同方式程序显式释放空间：程序显式释放空间：free（C）或）或delete（C+）垃圾收集器自
39、动收集（垃圾收集器自动收集（Java）。）。6.5 堆堆管管理理6.5.1内存管理器内存管理器内存管理器把握的基本信息是堆中空闲空间内存管理器把握的基本信息是堆中空闲空间分配函数分配函数回收函数回收函数内存管理器应具有下列性质内存管理器应具有下列性质空间有效性：极小化程序需要的堆空间总量空间有效性：极小化程序需要的堆空间总量程程序序有有效效性性：较较好好地地利利用用内内存存子子系系统统，使使得得程程序序能能运运行行得得快一些快一些低低开开销销：分分配配和和回回收收操操作作所所花花时时间间在在整整个个程程序序执执行行时时间间中中的比例尽量小的比例尽量小6.5 堆堆管管理理6.5.2 计算机内存分
40、层计算机内存分层虚拟内存虚拟内存(磁盘磁盘)物理内存物理内存2级缓存级缓存1级缓存级缓存寄存器寄存器(处理器处理器)典型大小典型大小2千兆字节千兆字节256兆兆 2千兆字节千兆字节128千千 4兆字节兆字节16 64千字节千字节32字字典型访问时间典型访问时间3 15微秒微秒100 150纳秒纳秒40 60纳秒纳秒5 10纳秒纳秒1纳秒纳秒6.5 堆堆管管理理6.5.2 计算机内存分层计算机内存分层现现代代计计算算机机都都设设计计成成程程序序员员不不用用关关心心内内存存子子系系统统的的细细节节就就可以写出正确的程序可以写出正确的程序程程序序的的效效率率不不仅仅取取决决于于被被执执行行的的指指令
41、令数数，还还取取决决于于执执行行每每条指令需要多长时间条指令需要多长时间执行一条指令的时间区别非常可观执行一条指令的时间区别非常可观差差异异源源于于硬硬件件技技术术的的基基本本局局限限：构构造造不不了了大大容容量量的的高高速速存存储器储器数据以块（缓存行、页）为单位在相邻层次之间进行传送数据以块（缓存行、页）为单位在相邻层次之间进行传送数据密集型程序可从恰当利用内存子系统中获益数据密集型程序可从恰当利用内存子系统中获益6.5 堆堆管管理理6.5.3程序局部性程序局部性大大多多数数程程序序的的大大部部分分时时间间在在执执行行一一小小部部分分代代码码，并并且仅涉及一小部分数据且仅涉及一小部分数据时
42、间局部性时间局部性程序访问的内存单元在很短的时间内可能再次被程序访问程序访问的内存单元在很短的时间内可能再次被程序访问空间局部性空间局部性毗邻被访问单元的内存单元在很短的时间内可能被访问毗邻被访问单元的内存单元在很短的时间内可能被访问6.5 堆堆管管理理6.5.3程序局部性程序局部性从从代代码码本本身身很很难难看看出出哪哪部部分分代代码码会会被被频频繁繁使使用用,必必须动态调整最快缓存的内容须动态调整最快缓存的内容把把最最近近使使用用的的指指令令保保存存在在缓缓存存是是一一种种较较好好的的最最优优化利用内存分层的策略化利用内存分层的策略改改变变数数据据布布局局或或计计算算次次序序也也可可以以改
43、改进进程程序序数数据据访访问的时间和空间局部性问的时间和空间局部性6.5 堆堆管管理理6.5.4手工回收请求手工回收请求程程序序员员在在程程序序中中显显式式释释放放堆堆块块来来达达到到回回收收堆堆块块的的目目的的内存泄漏：没有释放已经引用不到的堆块内存泄漏：没有释放已经引用不到的堆块只要内存没有用尽，它就不影响程序的正确性只要内存没有用尽，它就不影响程序的正确性 自自动动无无用用单单元元收收集集通通过过回回收收所所有有无无用用单单元元来来摆摆脱脱内内存存泄漏泄漏悬空引用：引用已经被释放的堆块悬空引用：引用已经被释放的堆块 过分热心地释放数据对象而引起过分热心地释放数据对象而引起悬空引用容易导致
44、不会被捕获的错误悬空引用容易导致不会被捕获的错误 本本章章要要点点影响存储分配策略的语言特征影响存储分配策略的语言特征各各种种存存储储分分配配策策略略，主主要要了了解解静静态态分分配配和和动动态栈式分配态栈式分配活动记录中各种数据域的作用和布局活动记录中各种数据域的作用和布局非局部数据访问的实现方法非局部数据访问的实现方法各种参数传递方式及其实现各种参数传递方式及其实现堆管理堆管理例例题题1一个一个C语言程序及其在语言程序及其在X86/Linux操作系统上的编译结操作系统上的编译结果如下。根据所生成的汇编程序来解释程序中四个变果如下。根据所生成的汇编程序来解释程序中四个变量的存储分配、作用域、
45、生存期和置初值方式等方面量的存储分配、作用域、生存期和置初值方式等方面的区别的区别staticlongaa=10;shortbb=20;func() staticlongcc=30;shortdd=40;例例题题1.data|.align4.align4|.typecc.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).valu
46、e20|.例例题题1.data|.align4.align4|.typecc.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|.例例题题1.data|.align4.align4|.typecc.2,object.typeaa,object|.size cc.2,4.sizeaa,4|cc.2:aa:|.lon
47、g30.long10|.text.globlbb|.align4.align2|.globlfunc.typebb,object|func:.sizebb,2|.bb:|movw$40,-2(%ebp).value20|.例例题题1.data|.align4.align4|.typecc.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(%
48、ebp).value20|.例例题题2func(i)longi;longj;j=i-1;func(j);例例题题2func(i)func:longi;pushl%ebp老的基地址指针压栈老的基地址指针压栈movl%esp,%ebp修改修改基地址指针基地址指针longj;subl$4,%esp为为j分配空间分配空间j=i-1;movl8(%ebp),%edx取取i到到寄存器寄存器func(j);decl%edxi1movl%edx,-4(%ebp)i1jmovl-4(%ebp),%eaxpushl%eax把实参把实参j的值压栈的值压栈callfunc函数调用函数调用addl$4,%esp恢恢复复
49、栈栈顶顶指指针针L1:leave即即movebp,esp;popebpret即即popeip(下条指令地址）下条指令地址）. . .参数参数i返址返址控制链控制链变量变量j.ebp esp 栈栈低低高高例例题题2func(i)func:longi;pushl%ebp老的基地址指针压栈老的基地址指针压栈movl%esp,%ebp修改修改基地址指针基地址指针longj;subl$4,%esp为为j分配空间分配空间j=i-1;movl8(%ebp),%edx取取i到到寄存器寄存器func(j);decl%edxi1movl%edx,-4(%ebp)i1jmovl-4(%ebp),%eaxpushl%
50、eax把实参把实参j的值压栈的值压栈callfunc函数调用函数调用addl$4,%esp恢恢复复栈栈顶顶指指针针L1:leave即即movebp,esp;popebpret即即popeip(下条指令地址）下条指令地址）. . .ebp esp 例例题题2func(i)func:longi;pushl%ebp老的基地址指针压栈老的基地址指针压栈movl%esp,%ebp修改修改基地址指针基地址指针longj;subl$4,%esp为为j分配空间分配空间j=i-1;movl8(%ebp),%edx取取i到到寄存器寄存器func(j);decl%edxi1movl%edx,-4(%ebp)i1jm
51、ovl-4(%ebp),%eaxpushl%eax把实参把实参j的值压栈的值压栈callfunc函数调用函数调用addl$4,%esp恢恢复复栈栈顶顶指指针针L1:leave即即movebp,esp;popebpret即即popeip(下条指令地址）下条指令地址）. . .ebp esp 参数参数i例例题题2func(i)func:longi;pushl%ebp老的基地址指针压栈老的基地址指针压栈movl%esp,%ebp修改修改基地址指针基地址指针longj;subl$4,%esp为为j分配空间分配空间j=i-1;movl8(%ebp),%edx取取i到到寄存器寄存器func(j);decl
52、%edxi1movl%edx,-4(%ebp)i1jmovl-4(%ebp),%eaxpushl%eax把实参把实参j的值压栈的值压栈callfunc函数调用函数调用addl$4,%esp恢恢复复栈栈顶顶指指针针L1:leave即即movebp,esp;popebpret即即popeip(下条指令地址）下条指令地址）. . .ebp esp 参数参数i返址返址例例题题2func(i)func:longi;pushl%ebp老的基地址指针压栈老的基地址指针压栈movl%esp,%ebp修改修改基地址指针基地址指针longj;subl$4,%esp为为j分配空间分配空间j=i-1;movl8(%e
53、bp),%edx取取i到到寄存器寄存器func(j);decl%edxi1movl%edx,-4(%ebp)i1jmovl-4(%ebp),%eaxpushl%eax把实参把实参j的值压栈的值压栈callfunc函数调用函数调用addl$4,%esp恢恢复复栈栈顶顶指指针针L1:leave即即movebp,esp;popebpret即即popeip(下条指令地址）下条指令地址）. . .ebp esp 参数参数i返址返址控制链控制链例例题题2func(i)func:longi;pushl%ebp老的基地址指针压栈老的基地址指针压栈movl%esp,%ebp修改修改基地址指针基地址指针longj
54、;subl$4,%esp为为j分配空间分配空间j=i-1;movl8(%ebp),%edx取取i到到寄存器寄存器func(j);decl%edxi1movl%edx,-4(%ebp)i1jmovl-4(%ebp),%eaxpushl%eax把实参把实参j的值压栈的值压栈callfunc函数调用函数调用addl$4,%esp恢恢复复栈栈顶顶指指针针L1:leave即即movebp,esp;popebpret即即popeip(下条指令地址）下条指令地址）. . .ebp esp 参数参数i返址返址控制链控制链例例题题2func(i)func:longi;pushl%ebp老的基地址指针压栈老的基地
55、址指针压栈movl%esp,%ebp修改修改基地址指针基地址指针longj;subl$4,%esp为为j分配空间分配空间j=i-1;movl8(%ebp),%edx取取i到到寄存器寄存器func(j);decl%edxi1movl%edx,-4(%ebp)i1jmovl-4(%ebp),%eaxpushl%eax把实参把实参j的值压栈的值压栈callfunc函数调用函数调用addl$4,%esp恢恢复复栈栈顶顶指指针针L1:leave即即movebp,esp;popebpret即即popeip(下条指令地址）下条指令地址）. . .参数参数i返址返址控制链控制链变量变量j.ebp esp 栈栈
56、低低高高例例题题2func(i)func:longi;pushl%ebp老的基地址指针压栈老的基地址指针压栈movl%esp,%ebp修改修改基地址指针基地址指针longj;subl$4,%esp为为j分配空间分配空间j=i-1;movl8(%ebp),%edx取取i到到寄存器寄存器func(j);decl%edxi1movl%edx,-4(%ebp)i1jmovl-4(%ebp),%eaxpushl%eax把实参把实参j的值压栈的值压栈callfunc函数调用函数调用addl$4,%esp恢恢复复栈栈顶顶指指针针L1:leave即即movebp,esp;popebpret即即popeip(下
57、条指令地址）下条指令地址）. . .参数参数i返址返址控制链控制链变量变量j.ebp esp 栈栈低低高高调用序列之一调用序列之一调用序列之二调用序列之二例例题题2func(i)func:longi;pushl%ebp老的基地址指针压栈老的基地址指针压栈movl%esp,%ebp修改修改基地址指针基地址指针longj;subl$4,%esp为为j分配空间分配空间j=i-1;movl8(%ebp),%edx取取i到到寄存器寄存器func(j);decl%edxi1movl%edx,-4(%ebp)i1jmovl-4(%ebp),%eaxpushl%eax把实参把实参j的值压栈的值压栈callfu
58、nc函数调用函数调用addl$4,%esp恢恢复复栈栈顶顶指指针针L1:leave即即movebp,esp;popebpret即即popeip(下条指令地址）下条指令地址）. . .参数参数i返址返址控制链控制链变量变量j.ebp esp 栈栈低低高高返回序列之一返回序列之一返回序列之二返回序列之二例例题题3main()char*cp1,*cp2;cp1=12345;cp2=abcdefghij;strcpy(cp1,cp2);printf(cp1=%sncp2=%sn,cp1,cp2);在某些系统上的运行结果是：在某些系统上的运行结果是：cp1=abcdefghijcp2=ghij为什么为什
59、么cp2所指的串被修改了？所指的串被修改了？例例题题3因因为为常常量量串串“12345”和和“abcdefghij”连连续续分分配配在在常常数区数区执行前：执行前：123450abcdefghij0 cp1cp2例例题题3因因为为常常量量串串“12345”和和“abcdefghij”连连续续分分配配在在常常数区数区执行前：执行前：123450abcdefghij0 cp1cp2执行后执行后：abcdefghij0fghij0 cp1cp2例例题题3因因为为常常量量串串“12345”和和“abcdefghij”连连续续分分配配在在常常数区数区执行前：执行前：123450abcdefghij0 c
60、p1cp2执行后执行后：abcdefghij0fghij0 cp1cp2现在的编译器大都把程序中的串常量单独存放在只读现在的编译器大都把程序中的串常量单独存放在只读数据段中，因此运行时会报错数据段中，因此运行时会报错例例题题4下面的程序运行时输出下面的程序运行时输出3个整数。试从运行环个整数。试从运行环境和境和printf的实现来分析，为什么此程序会有的实现来分析，为什么此程序会有3个整数输出？个整数输出？main()printf(“%d,%d,%dn”);. . .参数参数返址返址控制链控制链.ebp esp 栈栈低低高高例例题题5func(shorti,shortj,floatf,floa
61、te)shorti1,j1;floatf1,e1;printf(“Adressofijfe=%o%o%o%on”,&i,&j,&f,&e);printf(“Adressofi1j1f1e1=%o%o%o%on”,&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例例题题5func(shorti,shortj,floatf,floate)Sizesofshort,int,long,float,do
62、uble=2,4,4,4,8（在在SPARC/SUN工作站上）工作站上）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例例题题5func(shorti,shortj,floatf,floate)Sizesofshort,int,long,float,double=2,4,4,4,8（在在SPAR
63、C/SUN工作站上）工作站上）shorti1,j1;floatf1,e1;printf(&i,&j,&f,&e);printf(&i1,&j1,&f1,&e1);main()为什么为什么4 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例例题题5当当用用传传统统的的参参数数声声明明方方式式时时，C语语言言编编译译器器是是不不做做实实在在参
64、参数数和和形形式式参参数数的的个个数数和和类类型型是是否否一一致致的的检检查查的的，由由程程序序员员自自己己保证它们的一致性保证它们的一致性对对于于形形式式参参数数和和实实在在参参数数是是不不同同的的整整型型，或或者者是是不不同同的的实实型型，编编译译器器则则试试图图保保证证目目标标代代码码运运行行时时能能得得到到正正确确的的结结果果，条条件件是是，当当需需要要把把高高级级别别类类型型数数据据向向低低级级别别类类型型数数据据转转换换时时，不不出现溢出出现溢出当当整整型型或或实实型型数数据据作作为为实实在在参参数数时时，将将它它们们分分别别提提升升到到long和和double类型的数据再传递到被
65、调用函数类型的数据再传递到被调用函数被被调调用用函函数数根根据据形形式式参参数数所所声声明明的的类类型型，决决定定是是否否要要将将实实在在参数向低级别类型转换参数向低级别类型转换例例题题5低地址低地址放高位放高位高地址高地址放低位放低位shortlong长整型和短整型长整型和短整型floatdouble双精度型和浮点型双精度型和浮点型例例题题5e，8个字节个字节在在main函函数数中中参参数数压压栈栈时的观点时的观点在在func函函数数中中存存取取形形式式参参数数时的观点时的观点4个字节，起始地址个字节，起始地址544个字节，起始地址个字节，起始地址442个字节，起始地址个字节，起始地址422
66、个字节，起始地址个字节，起始地址36f，8个字节个字节j，4个字节个字节i，4个字节个字节栈栈的的增增长长方向方向参数在栈中的情况参数在栈中的情况例例题题6下面程序为什么死循环（在下面程序为什么死循环（在SPARC/SUN工作站上工作站上)？long*p;loop()longi,j; j=0;for(i=0;i10;i+)(*p)-;j+;addr()longk;k=0;p=&k;main()addr();loop();例例题题6将将long*p改成改成short*p，longk改成改成shortk后，循环体执行一次便停止，为什么？后，循环体执行一次便停止，为什么？short*p;loop()
67、longi,j; j=0;for(i=0;i10;i+)(*p)-;j+;addr()shortk;k=0;p=&k;main()addr();loop();例例题题6将将long*p改成改成short*p，longk改成改成shortk后，循环体执行一次便停止，为什么？后，循环体执行一次便停止，为什么？short*p; 活动记录栈是从高向低方向增长活动记录栈是从高向低方向增长loop()longi,j; j=0;for(i=0;i10;i+) (*p)-;j+;addr()shortk;k=0;p=&k;main()addr();loop();低地址低地址放高位放高位高地址高地址放低位放低位
68、shortklongi例例题题7main() func(); printf(Returnfromfuncn);func() chars4;strcpy(s,12345678);printf(%sn,s);在在X86/Linux操作系统上的运行结果如下：操作系统上的运行结果如下：12345678ReturnfromfuncSegmentationfault(coredumped)例例题题7main() func(); printf(Returnfromfuncn);func() chars4;strcpy(s,12345678);printf(%sn,s);. . .返址返址控制链控制链变量变量
69、sebp esp 栈栈低低高高例例题题7main() func(); printf(Returnfromfuncn);func() chars4;strcpy(s,123456789);printf(%sn,s);123456789Segmentationfault(coredumped). . .返址返址控制链控制链变量变量sebp esp 栈栈低低高高例例题题8intfact(i)|main()inti;|printf(%dn,fact(5);if(i=0)|printf(%dn,fact(5,10,15);return1;|printf(%dn,fact(5.0);else|printf
70、(%dn,fact();returni*fact(i-1);|该程序在该程序在X86/Linux机器上的运行结果如下：机器上的运行结果如下：1201201Segmentationfault(coredumped)例例题题8请解释下面问题：请解释下面问题：第第二二个个fact调调用用：结结果果为为什什么么没没有有受受参参数数过过多多的的影响？影响？第第三三个个fact调调用用：为为什什么么用用浮浮点点数数5.0作作为为参参数数时时结果变成结果变成1?第第四四个个fact调调用用：为为什什么么没没有有提提供供参参数数时时会会出出现现Segmentationfault？例例题题8请解释下面问题：请解
71、释下面问题：第第二二个个fact调调用用：结结果果为为什什么么没没有有受受参参数数过过多多的的影响？影响？解解答答：参参数数表表达达式式逆逆序序计计算算并并进进栈栈，fact能能够够取取到到第一个参数第一个参数例例题题8请解释下面问题：请解释下面问题：第第三三个个fact调调用用：为为什什么么用用浮浮点点数数5.0作作为为参参数数时时结果变成结果变成1?解答：解答：参数参数5.0转换成双精转换成双精度数进栈，占度数进栈，占8个字节个字节它低地址的它低地址的4个字节看成整个字节看成整数时正好是数时正好是0. . .参数参数返址返址控制链控制链局部变量局部变量ebp esp 栈栈低低高高例例题题8
72、请解释下面问题：请解释下面问题：第第四四个个fact调调用用：为为什什么么没没有有提提供供参参数数时时会会出出现现Segmentationfault？解答：由于没有提供参数，解答：由于没有提供参数，而而main函数又无局部变量，函数又无局部变量，fact把老把老ebp（控制链）控制链）（main的活动记录中保存的活动记录中保存的的ebp）当成参数，它一定当成参数，它一定是一个很大的整数，使得活是一个很大的整数，使得活动记录栈溢出动记录栈溢出. . .控制链控制链返址返址控制链控制链局部变量局部变量ebp esp 栈栈低低高高习习题题第一次：第一次：6.3,6.5，6.9第二次：第二次：6.12,6.18,6.23
