第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 过程的过程的活动活动过程的一次执行称为过程的一次活动过程的一次执行称为过程的一次活动第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 过程的过程的活动活动过程的一次执行称为过程的一次活动过程的一次执行称为过程的一次活动活动记录活动记录过程的活动需要可执行代码和存放所需信息过程的活动需要可执行代码和存放所需信息的存储空间的存储空间, ,后者称为活动记录后者称为活动记录第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 过程的过程的活动活动过程的一次执行称为过程的一次活动过程的一次执行称为过程的一次活动活动记录活动记录过程的活动需要可执行代码和存放所需信息过程的活动需要可执行代码和存放所需信息的存储空间的存储空间, ,后者称为活动记录后者称为活动记录本章内容本章内容讨论一个活动记录中的数据安排讨论一个活动记录中的数据安排第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 过程的过程的活动活动过程的一次执行称为过程的一次活动过程的一次执行称为过程的一次活动活动记录活动记录过程的活动需要可执行代码和存放所需信息过程的活动需要可执行代码和存放所需信息的存储空间的存储空间, ,后者称为活动记录后者称为活动记录本章内容本章内容讨论一个活动记录中的数据安排讨论一个活动记录中的数据安排程序执行过程中，所有活动记录的组织方式程序执行过程中，所有活动记录的组织方式第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征过程能否递归过程能否递归第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征过程能否递归过程能否递归当当控控制制从从过过程程的的活活动动返返回回时时，局局部部变变量量的的值值是否要保留是否要保留第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征过程能否递归过程能否递归当当控控制制从从过过程程的的活活动动返返回回时时，局局部部变变量量的的值值是否要保留是否要保留过程能否访问非局部变量过程能否访问非局部变量第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征过程能否递归过程能否递归当当控控制制从从过过程程的的活活动动返返回回时时，局局部部变变量量的的值值是否要保留是否要保留过程能否访问非局部变量过程能否访问非局部变量过程调用的参数传递方式过程调用的参数传递方式第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征过程能否递归过程能否递归当当控控制制从从过过程程的的活活动动返返回回时时，局局部部变变量量的的值值是否要保留是否要保留过程能否访问非局部变量过程能否访问非局部变量过程调用的参数传递方式过程调用的参数传递方式过程能否作为参数被传递过程能否作为参数被传递第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征过程能否递归过程能否递归当当控控制制从从过过程程的的活活动动返返回回时时，局局部部变变量量的的值值是否要保留是否要保留过程能否访问非局部变量过程能否访问非局部变量过程调用的参数传递方式过程调用的参数传递方式过程能否作为参数被传递过程能否作为参数被传递过程能否作为结果值传递过程能否作为结果值传递第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征过程能否递归过程能否递归当当控控制制从从过过程程的的活活动动返返回回时时，局局部部变变量量的的值值是否要保留是否要保留过程能否访问非局部变量过程能否访问非局部变量过程调用的参数传递方式过程调用的参数传递方式过程能否作为参数被传递过程能否作为参数被传递过程能否作为结果值传递过程能否作为结果值传递存储块能否在程序控制下动态地分配存储块能否在程序控制下动态地分配第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征过程能否递归过程能否递归当当控控制制从从过过程程的的活活动动返返回回时时，局局部部变变量量的的值值是否要保留是否要保留过程能否访问非局部变量过程能否访问非局部变量过程调用的参数传递方式过程调用的参数传递方式过程能否作为参数被传递过程能否作为参数被传递过程能否作为结果值传递过程能否作为结果值传递存储块能否在程序控制下动态地分配存储块能否在程序控制下动态地分配存储块是否必须显式地释放存储块是否必须显式地释放6.1 局部存储分配局部存储分配6.1.1过程过程过程定义、过程定义、过程过程调用、形式参数、实在参数、调用、形式参数、实在参数、活动的活动的生存期生存期6.1 局部存储分配局部存储分配6.1.2名字的作用域和绑定名字的作用域和绑定名字的作用域名字的作用域一个声明起作用的程序部分称为该声明的一个声明起作用的程序部分称为该声明的作作用域用域即使一个名字在程序中只声明一次，该名字即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象在程序运行时也可能表示不同的数据对象6.1 局部存储分配局部存储分配从名字到值的两步映射从名字到值的两步映射 名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配从名字到值的两步映射从名字到值的两步映射环境把名字映射到左值，而状态把左值映射环境把名字映射到左值，而状态把左值映射到右值到右值 名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配从名字到值的两步映射从名字到值的两步映射环境把名字映射到左值，而状态把左值映射环境把名字映射到左值，而状态把左值映射到右值到右值赋值改变状态，但不改变环境赋值改变状态，但不改变环境 名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配从名字到值的两步映射从名字到值的两步映射环境把名字映射到左值，而状态把左值映射环境把名字映射到左值，而状态把左值映射到右值到右值赋值改变状态，但不改变环境赋值改变状态，但不改变环境过程调用改变环境过程调用改变环境名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配从名字到值的两步映射从名字到值的两步映射环境把名字映射到左值，而状态把左值映射环境把名字映射到左值，而状态把左值映射到右值到右值赋值改变状态，但不改变环境赋值改变状态，但不改变环境过程调用改变环境过程调用改变环境如果环境将名字如果环境将名字x映射到存储单元映射到存储单元s，我们就我们就说说x被被绑定绑定到到s名字名字存储单元存储单元状态状态值值环境环境6.1 局部存储分配局部存储分配静态概念和动态概念的对应静态概念和动态概念的对应 静静态态概概念念 动动态态对对应应 过程的定义过程的定义 过程的活动过程的活动 6.1 局部存储分配局部存储分配静态概念和动态概念的对应静态概念和动态概念的对应 静静态态概概念念 动动态态对对应应 过程的定义过程的定义 过程的活动过程的活动 名字的声明名字的声明名字的绑定名字的绑定6.1 局部存储分配局部存储分配静态概念和动态概念的对应静态概念和动态概念的对应 静静态态概概念念 动动态态对对应应 过程的定义过程的定义 过程的活动过程的活动 名字的声明名字的声明名字的绑定名字的绑定声明的作用域声明的作用域 绑定的生存期绑定的生存期6.1 局部存储分配局部存储分配6.1.3活动记录活动记录一般的活动记录的布局一般的活动记录的布局返返回回值值临临时时数数据据参参数数控控制制链链访访问问链链机机器器状状态态局局部部数数据据6.1 局部存储分配局部存储分配6.1.4局部数据的安排局部数据的安排字节是可编址内存的最小单位字节是可编址内存的最小单位6.1 局部存储分配局部存储分配6.1.4局部数据的安排局部数据的安排字节是可编址内存的最小单位字节是可编址内存的最小单位变变量量所所需需的的存存储储空空间间可可以以根根据据其其类类型型而而静静态态确定确定6.1 局部存储分配局部存储分配6.1.4局部数据的安排局部数据的安排字节是可编址内存的最小单位字节是可编址内存的最小单位变变量量所所需需的的存存储储空空间间可可以以根根据据其其类类型型而而静静态态确定确定一一个个过过程程所所声声明明的的局局部部变变量量，按按这这些些变变量量声声明明时时出出现现的的次次序序，在在局局部部数数据据域域中中依依次次分分配配空间空间6.1 局部存储分配局部存储分配6.1.4局部数据的安排局部数据的安排字节是可编址内存的最小单位字节是可编址内存的最小单位变变量量所所需需的的存存储储空空间间可可以以根根据据其其类类型型而而静静态态确定确定一一个个过过程程所所声声明明的的局局部部变变量量，按按这这些些变变量量声声明明时时出出现现的的次次序序，在在局局部部数数据据域域中中依依次次分分配配空间空间局局部部数数据据的的地地址址可可以以用用相相对对于于某某个个位位置置的的地地址来表示址来表示6.1 局部存储分配局部存储分配6.1.4局部数据的安排局部数据的安排字节是可编址内存的最小单位字节是可编址内存的最小单位变变量量所所需需的的存存储储空空间间可可以以根根据据其其类类型型而而静静态态确定确定一一个个过过程程所所声声明明的的局局部部变变量量，按按这这些些变变量量声声明明时时出出现现的的次次序序，在在局局部部数数据据域域中中依依次次分分配配空间空间局局部部数数据据的的地地址址可可以以用用相相对对于于某某个个位位置置的的地地址来表示址来表示数据对象的存储安排还有一个对齐问题数据对象的存储安排还有一个对齐问题6.1 局部存储分配局部存储分配在在SPARC/Solaris工工作作站站上上下下面面两两个个结结构构的的size分别是分别是24和和16，为什么不一样？，为什么不一样？typedefstruct_atypedefstruct_bcharc1;charc1;longi;charc2;char c2;longi;doublef;doublef;a;b;6.1 局部存储分配局部存储分配在在SPARC/Solaris工工作作站站上上下下面面两两个个结结构构的的size分别是分别是24和和16，为什么不一样？，为什么不一样？typedefstruct_atypedefstruct_bcharc1;0charc1; 0longi;4charc2;1char c2;8longi;4doublef; 16doublef;8a;b;6.1 局部存储分配局部存储分配在在X86/Linux机机器器的的结结果果和和SPARC/Solaris工工作作站不一样，是站不一样，是20和和16。typedefstruct_atypedefstruct_bcharc1;0charc1; 0longi;4charc2;1char c2;8longi;4doublef; 12doublef;8a;b;6.1 局部存储分配局部存储分配6.1.5 程序块程序块本身含有局部变量声明的语句本身含有局部变量声明的语句可以嵌套可以嵌套最接近的嵌套最接近的嵌套作用域规则作用域规则并列程序块不会同时活跃并列程序块不会同时活跃并列程序块的变量可以重叠分配并列程序块的变量可以重叠分配6.1 局部存储分配局部存储分配main()/ beginofB0 /inta=0;intb=0;/ beginofB1 /intb=1;/ beginofB2 /inta=2;/ endofB2 / beginofB3 /intb=3;/ endofB3 / endofB1 / endofB0 /6.1 局部存储分配局部存储分配main()/ beginofB0 /inta=0;intb=0;/ beginofB1 /intb=1;/ beginofB2 /inta=2;/ endofB2 / beginofB3 /intb=3;/ endofB3 / endofB1 / endofB0 /声声明明作作用用域域inta=0;B0 B2intb=0;B0 B1intb=1;B1 B3inta=2;B2intb=3;B36.1 局部存储分配局部存储分配main()/ beginofB0 /inta=0;intb=0;/ beginofB1 /intb=1;/ beginofB2 /inta=2;/ endofB2 / beginofB3 /intb=3;/ endofB3 / endofB1 / endofB0 /声声明明作作用用域域inta=0;B0 B2intb=0;B0 B1intb=1;B1 B3inta=2;B2intb=3;B3a0b0b1a2,b3重叠分配存储单元重叠分配存储单元6.2 全局栈式存储分配全局栈式存储分配介介绍绍程程序序运运行行时时所所需需的的各各个个活活动动记记录录在在存存储储空间的分配策略空间的分配策略6.2 全局栈式存储分配全局栈式存储分配介介绍绍程程序序运运行行时时所所需需的的各各个个活活动动记记录录在在存存储储空间的分配策略空间的分配策略描描述述过过程程的的目目标标代代码码怎怎样样访访问问绑绑定定到到局局部部名名字的存储单元字的存储单元6.2 全局栈式存储分配全局栈式存储分配介介绍绍程程序序运运行行时时所所需需的的各各个个活活动动记记录录在在存存储储空间的分配策略空间的分配策略描描述述过过程程的的目目标标代代码码怎怎样样访访问问绑绑定定到到局局部部名名字的存储单元字的存储单元介绍三种分配策略介绍三种分配策略静态分配策略静态分配策略6.2 全局栈式存储分配全局栈式存储分配介介绍绍程程序序运运行行时时所所需需的的各各个个活活动动记记录录在在存存储储空间的分配策略空间的分配策略描描述述过过程程的的目目标标代代码码怎怎样样访访问问绑绑定定到到局局部部名名字的存储单元字的存储单元介绍三种分配策略介绍三种分配策略静态分配策略静态分配策略栈式分配策略栈式分配策略6.2 全局栈式存储分配全局栈式存储分配介介绍绍程程序序运运行行时时所所需需的的各各个个活活动动记记录录在在存存储储空间的分配策略空间的分配策略描描述述过过程程的的目目标标代代码码怎怎样样访访问问绑绑定定到到局局部部名名字的存储单元字的存储单元介绍三种分配策略介绍三种分配策略静态分配策略静态分配策略栈式分配策略栈式分配策略堆式分配策略堆式分配策略6.2 全局栈式存储分配全局栈式存储分配6.2.1 运行时内存的划分运行时内存的划分代代码码静静态态数数据据堆堆栈栈6.2 全局栈式存储分配全局栈式存储分配静态分配静态分配名名字字在在程程序序被被编编译译时时绑绑定定到到存存储储单单元元，不不需需要运行时的任何支持要运行时的任何支持6.2 全局栈式存储分配全局栈式存储分配静态分配静态分配名名字字在在程程序序被被编编译译时时绑绑定定到到存存储储单单元元，不不需需要运行时的任何支持要运行时的任何支持绑定的生存期是程序的整个运行期间绑定的生存期是程序的整个运行期间6.2 全局栈式存储分配全局栈式存储分配静态分配给语言带来限制静态分配给语言带来限制递归过程不被允许递归过程不被允许6.2 全局栈式存储分配全局栈式存储分配静态分配给语言带来限制静态分配给语言带来限制递归过程不被允许递归过程不被允许数数据据对对象象的的长长度度和和它它在在内内存存中中位位置置的的限限制制，必须是在编译时可以知道的必须是在编译时可以知道的6.2 全局栈式存储分配全局栈式存储分配静态分配给语言带来限制静态分配给语言带来限制递归过程不被允许递归过程不被允许数数据据对对象象的的长长度度和和它它在在内内存存中中位位置置的的限限制制，必须是在编译时可以知道的必须是在编译时可以知道的数据结构不能动态建立数据结构不能动态建立6.2 全局栈式存储分配全局栈式存储分配C语言程序的外部变量和程序中出现的常量语言程序的外部变量和程序中出现的常量都可以静态分配都可以静态分配声明在函数外面声明在函数外面外部变量外部变量 静态分配静态分配静态外部变量静态外部变量 静态分配静态分配声明在函数里面声明在函数里面静态局部变量静态局部变量 也是静态分配也是静态分配自动变量自动变量 不能静态分配不能静态分配6.2 全局栈式存储分配全局栈式存储分配6.2.2 活动树和运行栈活动树和运行栈活动树活动树:用树来描绘控制进入和离开活动的方式用树来描绘控制进入和离开活动的方式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 全局栈式存储分配全局栈式存储分配活动树的特点活动树的特点每个结点代表某过程的一个活动每个结点代表某过程的一个活动根结点代表主程序的活动根结点代表主程序的活动结结点点a是是结结点点b的的父父结结点点，当当且且仅仅当当控控制制流流从从a的活动进入的活动进入b的活动的活动结结点点a处处于于结结点点b的的左左边边，当当且且仅仅当当a的的生生存存期期先于先于b的生存期的生存期6.2 全局栈式存储分配全局栈式存储分配当前活跃着的过程活动可以保存在一个栈中当前活跃着的过程活动可以保存在一个栈中控制栈的内容：控制栈的内容：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 全局栈式存储分配全局栈式存储分配运行栈：运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）6.2 全局栈式存储分配全局栈式存储分配运行栈：运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）ma:arraym6.2 全局栈式存储分配全局栈式存储分配运行栈：运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mi:integerra:arraymr6.2 全局栈式存储分配全局栈式存储分配运行栈：运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mk:integerq(1,9)a:arraymq(1,9)r6.2 全局栈式存储分配全局栈式存储分配运行栈：运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录）mk:integerq(1,9)a:arrayq(1,3)k:integermq(1,9)rp(1,9) q(1,3)q(1,0)p(1,3)6.2 全局栈式存储分配全局栈式存储分配6.2.3 调用序列调用序列过过程程调调用用和和过过程程返返回回都都需需要要执执行行一一些些代代码码来来管理活动记录栈，保存或恢复机器状态等管理活动记录栈，保存或恢复机器状态等6.2 全局栈式存储分配全局栈式存储分配6.2.3 调用序列调用序列过过程程调调用用和和过过程程返返回回都都需需要要执执行行一一些些代代码码来来管理活动记录栈，保存或恢复机器状态等管理活动记录栈，保存或恢复机器状态等过程调用序列过程调用序列过过程程调调用用时时执执行行的的分分配配活活动动记记录录，把把信信息息填填入入它它的的域中的代码域中的代码6.2 全局栈式存储分配全局栈式存储分配6.2.3 调用序列调用序列过过程程调调用用和和过过程程返返回回都都需需要要执执行行一一些些代代码码来来管理活动记录栈，保存或恢复机器状态等管理活动记录栈，保存或恢复机器状态等过程调用序列过程调用序列过过程程调调用用时时执执行行的的分分配配活活动动记记录录，把把信信息息填填入入它它的的域中的代码域中的代码过程返回序列过程返回序列过过程程返返回回时时执执行行的的恢恢复复机机器器状状态态，释释放放活活动动记记录录，使调用过程能够继续执行的代码使调用过程能够继续执行的代码6.2 全局栈式存储分配全局栈式存储分配过过程程调调用用和和过过程程返返回回都都需需要要执执行行一一些些代代码码来来管理活动记录栈，保存或恢复机器状态等管理活动记录栈，保存或恢复机器状态等过程调用序列过程调用序列过过程程调调用用时时执执行行的的分分配配活活动动记记录录，把把信信息息填填入入它它的的域中的代码域中的代码过程返回序列过程返回序列过过程程返返回回时时执执行行的的恢恢复复机机器器状状态态，释释放放活活动动记记录录，使调用过程能够继续执行的代码使调用过程能够继续执行的代码调调用用序序列列和和返返回回序序列列常常常常都都分分成成两两部部分分，分分处于调用过程和被调用过程中处于调用过程和被调用过程中6.2 全局栈式存储分配全局栈式存储分配即即使使是是同同一一种种语语言言，过过程程调调用用序序列列、返返回回序序列列和和活活动动记记录录中中各各域域的的排排放放次次序序，也也会会因因实实现而异现而异设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则返返回回值值临临时时数数据据参参数数控控制制链链访访问问链链机机器器状状态态局局部部数数据据6.2 全局栈式存储分配全局栈式存储分配即即使使是是同同一一种种语语言言，过过程程调调用用序序列列、返返回回序序列列和和活活动动记记录录中中各各域域的的排排放放次次序序，也也会会因因实实现而异现而异设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则以活动记录中间的某个以活动记录中间的某个位置作为基地址位置作为基地址返返回回值值临临时时数数据据参参数数控控制制链链访访问问链链机机器器状状态态局局部部数数据据6.2 全局栈式存储分配全局栈式存储分配即即使使是是同同一一种种语语言言，过过程程调调用用序序列列、返返回回序序列列和和活活动动记记录录中中各各域域的的排排放放次次序序，也也会会因因实实现而异现而异设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则以活动记录中间的某个以活动记录中间的某个位置作为基地址位置作为基地址长度能较早确定的域放在长度能较早确定的域放在活动记录的中间活动记录的中间返返回回值值临临时时数数据据参参数数控控制制链链访访问问链链机机器器状状态态局局部部数数据据6.2 全局栈式存储分配全局栈式存储分配即即使使是是同同一一种种语语言言，过过程程调调用用序序列列、返返回回序序列列和和活活动动记记录录中中各各域域的的排排放放次次序序，也也会会因因实实现而异现而异设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则一般把临时数据域放在一般把临时数据域放在局部数据域的后面局部数据域的后面返返回回值值临临时时数数据据参参数数控控制制链链访访问问链链机机器器状状态态局局部部数数据据6.2 全局栈式存储分配全局栈式存储分配即即使使是是同同一一种种语语言言，过过程程调调用用序序列列、返返回回序序列列和和活活动动记记录录中中各各域域的的排排放放次次序序，也也会会因因实实现而异现而异设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则一般把临时数据域放在一般把临时数据域放在局部数据域的后面局部数据域的后面把参数域和可能有的返回把参数域和可能有的返回值域放在紧靠调用者活动值域放在紧靠调用者活动记录的地方记录的地方返返回回值值临临时时数数据据参参数数控控制制链链访访问问链链机机器器状状态态局局部部数数据据6.2 全局栈式存储分配全局栈式存储分配即即使使是是同同一一种种语语言言，过过程程调调用用序序列列、返返回回序序列列和和活活动动记记录录中中各各域域的的排排放放次次序序，也也会会因因实实现而异现而异设计这些序列和活动记录设计这些序列和活动记录的一些原则的一些原则用同样的代码来执行各个用同样的代码来执行各个活动的保存和恢复活动的保存和恢复返返回回值值临临时时数数据据参参数数控控制制链链访访问问链链机机器器状状态态局局部部数数据据6.2 全局栈式存储分配全局栈式存储分配调用者和被调用者之间的任务划分调用者和被调用者之间的任务划分被调用者的责任被调用者的责任调用者的责任调用者的责任调用者的调用者的活动记录活动记录被被调用者的调用者的活动记录活动记录临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配过程过程p调用过程调用过程q的调用序列的调用序列p计计算算实实参参，依依次次放放入入栈栈顶顶，并并在在栈栈顶顶留留出出放放返回值的空间。返回值的空间。top_sp的值在此过程中被改变的值在此过程中被改变p把把返返回回地地址址和和当当前前base_sp的的值值存存入入q的的活活动动记录中，建立记录中，建立q的访问链，增加的访问链，增加base_sp的值的值q保存寄存器的值和其它机器状态信息保存寄存器的值和其它机器状态信息q根根据据局局部部数数据据域域和和临临时时数数据据域域的的大大小小增增加加top_sp的的值值，初初始始化化它它的的局局部部数数据据，并并开开始始执执行过程体行过程体6.2 全局栈式存储分配全局栈式存储分配调用者和被调用者之间的任务划分调用者和被调用者之间的任务划分被调用者的责任被调用者的责任调用者的责任调用者的责任调用者的调用者的活动记录活动记录被被调用者的调用者的活动记录活动记录临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配过程过程p调用过程调用过程q的返回序列的返回序列q把返回值置入邻近把返回值置入邻近p的活动记录的地方的活动记录的地方q对应调用序列的步骤（对应调用序列的步骤（4），减小），减小top_sp的值的值q恢恢复复寄寄存存器器（包包括括base_sp）和和机机器器状状态态，返回返回pp根根据据参参数数个个数数与与类类型型和和返返回回值值类类型型调调整整top_sp，然后取出返回值然后取出返回值6.2 全局栈式存储分配全局栈式存储分配调用者和被调用者之间的任务划分调用者和被调用者之间的任务划分被调用者的责任被调用者的责任调用者的责任调用者的责任调用者的调用者的活动记录活动记录被被调用者的调用者的活动记录活动记录临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配过程的参数个数可变的情况过程的参数个数可变的情况函数返回值改成用寄存器传递函数返回值改成用寄存器传递编译器产生将这些参数逆序进栈的代码编译器产生将这些参数逆序进栈的代码被调用函数能准确地知道第一个参数的位置被调用函数能准确地知道第一个参数的位置被被调调用用函函数数根根据据第第一一个个参参数数到到栈栈中中取取第第二二、第三个参数等等第三个参数等等6.2 全局栈式存储分配全局栈式存储分配调用者和被调用者之间的任务划分调用者和被调用者之间的任务划分被调用者的责任被调用者的责任调用者的责任调用者的责任调用者的调用者的活动记录活动记录被被调用者的调用者的活动记录活动记录临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配6.2.4栈上可变长数据栈上可变长数据活动记录的长度在编译时不能确定的情况活动记录的长度在编译时不能确定的情况局部数组的大小要等到过程激活时才能确定局部数组的大小要等到过程激活时才能确定在在活活动动记记录录中中为为这这样样的的数数组组分分别别存存放放数数组组指指针的单元针的单元运运行行时时，这这些些指指针针指指向向分分配配在在栈栈顶顶的的存存储储空空间间6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组q的数组的数组q的活动记录的活动记录p的数组的数组p的活动记录的活动记录控制链控制链top_sp base_sp 数组数组A的指针的指针数组数组B的指针的指针数组数组A数组数组B控制链控制链.栈栈6.2 全局栈式存储分配全局栈式存储分配6.2.5悬空引用悬空引用悬空引用：悬空引用：引用某个已被释放的存储单元引用某个已被释放的存储单元6.2 全局栈式存储分配全局栈式存储分配6.2.5悬空引用悬空引用悬空引用：悬空引用：引用某个已被释放的存储单元引用某个已被释放的存储单元main()|int dangle()|int q;|intj=20;q=dangle(); |return&j;|6.3 非局部名字的访问非局部名字的访问本节介绍本节介绍无过程嵌套的静态作用域（无过程嵌套的静态作用域（C语言）语言）有过程嵌套的静态作用域有过程嵌套的静态作用域（Pascal语言）语言）动态作用域动态作用域（Lisp语言）语言）6.3 非局部名字的访问非局部名字的访问6.3.1 无过程嵌套的静态作用域无过程嵌套的静态作用域过过程程体体中中的的非非局局部部引引用用可可以以直直接接使使用用静静态态确确定的地址定的地址6.3 非局部名字的访问非局部名字的访问6.3.1 无过程嵌套的静态作用域无过程嵌套的静态作用域过过程程体体中中的的非非局局部部引引用用可可以以直直接接使使用用静静态态确确定的地址定的地址局局部部变变量量在在栈栈顶顶的的活活动动记记录录中中，可可以以通通过过base_sp指针来访问指针来访问6.3 非局部名字的访问非局部名字的访问6.3.1 无过程嵌套的静态作用域无过程嵌套的静态作用域过过程程体体中中的的非非局局部部引引用用可可以以直直接接使使用用静静态态确确定的地址定的地址局局部部变变量量在在栈栈顶顶的的活活动动记记录录中中，可可以以通通过过base_sp指针来访问指针来访问无须深入栈中取数据，无须访问链无须深入栈中取数据，无须访问链6.3 非局部名字的访问非局部名字的访问6.3.1 无过程嵌套的静态作用域无过程嵌套的静态作用域过过程程体体中中的的非非局局部部引引用用可可以以直直接接使使用用静静态态确确定的地址定的地址局局部部变变量量在在栈栈顶顶的的活活动动记记录录中中，可可以以通通过过base_sp指针来访问指针来访问无须深入栈中取数据，无须访问链无须深入栈中取数据，无须访问链过过程程可可以以作作为为参参数数来来传传递递，也也可可以以作作为为结结果果来返回来返回6.3 非局部名字的访问非局部名字的访问6.3.2 有过程嵌套的静态作用域有过程嵌套的静态作用域sortreadarrayexchangequicksortpartition6.3 非局部名字的访问非局部名字的访问6.3.2 有过程嵌套的静态作用域有过程嵌套的静态作用域过程过程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition36.3 非局部名字的访问非局部名字的访问6.3.2 有过程嵌套的静态作用域有过程嵌套的静态作用域过程过程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition3变量的嵌套深度：它的声明所在过程的嵌套变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度深度作为该名字的嵌套深度6.3 非局部名字的访问非局部名字的访问寻找非局部名字存储单元的访问链寻找非局部名字存储单元的访问链 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 非局部名字的访问非局部名字的访问假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度它引用嵌套深度为为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单元sort1readarray2exchange2quicksort2partition36.3 非局部名字的访问非局部名字的访问假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度它引用嵌套深度为为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单元从栈顶的活动记录开始，追踪访问链从栈顶的活动记录开始，追踪访问链np na次次6.3 非局部名字的访问非局部名字的访问假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度它引用嵌套深度为为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单元从栈顶的活动记录开始，追踪访问链从栈顶的活动记录开始，追踪访问链np na次次到达到达a的声明所在过程的活动记录的声明所在过程的活动记录6.3 非局部名字的访问非局部名字的访问假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度它引用嵌套深度为为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单元从栈顶的活动记录开始，追踪访问链从栈顶的活动记录开始，追踪访问链np na次次到达到达a的声明所在过程的活动记录的声明所在过程的活动记录访问链的追踪用间接操作就可完成访问链的追踪用间接操作就可完成6.3 非局部名字的访问非局部名字的访问访问非局部名字的存储单元访问非局部名字的存储单元 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(1,9)k,v访问链访问链p(1,3)i,j访问链访问链6.3 非局部名字的访问非局部名字的访问过程过程p对变量对变量a访问时，访问时，a的地址由下面的二元的地址由下面的二元组表示：组表示：（np na，a在活动记录中的偏移）在活动记录中的偏移）6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程xnp nx的情况的情况sort1readarray2exchange2quicksort2partition 36.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程xnp nx的情况的情况x肯定就声明在肯定就声明在p中中6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程xnp nx的情况的情况x肯定就声明在肯定就声明在p中中被被调调用用过过程程的的访访问问链链必必须须指指向向调调用用过过程程的的活活动动记记录的访问链录的访问链6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链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(1,9)k,v访问链访问链p(1,3)i,j访问链访问链6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程xnp nx的情况的情况sort1readarray2exchange2quicksort2partition 36.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程xnp nx的情况的情况p和和x的的嵌嵌套套深深度度分分别别为为1，2，nx 1的的外外围围过过程肯定相同程肯定相同6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程xnp nx的情况的情况p和和x的的嵌嵌套套深深度度分分别别为为1，2，nx 1的的外外围围过过程肯定相同程肯定相同追追踪踪访访问问链链np nx +1次次，到到达达了了静静态态包包围围x和和p的且离它们最近的那个过程的最新活动记录的且离它们最近的那个过程的最新活动记录6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链假定嵌套深度为假定嵌套深度为np的过程的过程p调用嵌套深度为调用嵌套深度为nx的过程的过程xnp nx的情况的情况p和和x的的嵌嵌套套深深度度分分别别为为1，2，nx 1的的外外围围过过程肯定相同程肯定相同追追踪踪访访问问链链np nx +1次次，到到达达了了静静态态包包围围x和和p的且离它们最近的那个过程的最新活动记录的且离它们最近的那个过程的最新活动记录所所到到达达的的活活动动记记录录就就是是x的的活活动动记记录录中中的的访访问问链链应该指向的那个活动记录应该指向的那个活动记录6.3 非局部名字的访问非局部名字的访问建立访问链建立访问链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(1,9)k,v访问链访问链p(1,3)i,j访问链访问链6.3 非局部名字的访问非局部名字的访问programparam(input,output);（过程作为参数）过程作为参数）procedureb(functionh(n:integer):integer);beginwriteln(h(2)endb;procedurec;varm:integer;functionf(n:integer):integer;beginf:=m+nendf;beginm:=0;b(f)endc;begincend.6.3 非局部名字的访问非局部名字的访问programparam(input,output);（过程作为参数）过程作为参数）procedureb(functionh(n:integer):integer);beginwriteln(h(2)endb;procedurec;varm:integer;functionf(n:integer):integer;beginf:=m+nendf;beginm:=0;b(f)endc;begincend.过程作为参数传递时，怎样在该过程作为参数传递时，怎样在该过程被激活时建立它的访问链过程被激活时建立它的访问链6.3 非局部名字的访问非局部名字的访问programparam(input,output);（过程作为参数）过程作为参数）procedureb(functionh(n:integer):integer);beginwriteln(h(2)endb;procedurec;varm:integer;functionf(n:integer):integer;beginf:=m+nendf;beginm:=0;b(f)endc;begincend.过程作为参数传递时，怎样在该过程作为参数传递时，怎样在该过程被激活时建立它的访问链过程被激活时建立它的访问链 从从b的访问链难以建立的访问链难以建立f的访问链的访问链6.3 非局部名字的访问非局部名字的访问programparam(input,output);（过程作为参数）过程作为参数）procedureb(functionh(beginwriteln(h(2)end;procedurec;varm:integer;functionf(n:integer)beginf:=m+nendf;beginm:=0;b(f)endc;begincend.访访问问链链访访问问链链paramcmb6.3 非局部名字的访问非局部名字的访问programret(input,output);（过程作为返回值）过程作为返回值）varf:function(integer):integer;functiona:function(integer):integer; varm:integer;functionaddm(n:integer):integer;beginreturnm+nend;beginm:=0;returnaddmend;procedureb(g:function(integer):integer);beginwriteln(g(2)end;beginf:=a;b(f)end.6.3 非局部名字的访问非局部名字的访问programret(input,output);（过程作为返回值）过程作为返回值）varf:function(integer):integer;functiona:function(integer):integer; varm:integer;functionaddm(n:integer):integer;beginreturnm+nend;beginm:=0;returnaddmend;procedureb(g:function(integer):integer);beginwriteln(g(2)end;beginf:=a;b(f)end.retabaddm6.3 非局部名字的访问非局部名字的访问C语语言言的的函函数数声声明明不不能能嵌嵌套套，函函数数不不论论在在什什么情况下激活，要访问的数据分成两种情况么情况下激活，要访问的数据分成两种情况: :非非静静态态局局部部变变量量（包包括括形形式式参参数数），它它们们分分配在活动记录栈顶的那个活动记录中配在活动记录栈顶的那个活动记录中外外部部变变量量（包包括括定定义义在在其其它它源源文文件件中中的的外外部部变变量量）和和静静态态的的局局部部变变量量，它它们们都都分分配配在在静静态数据区态数据区6.3 非局部名字的访问非局部名字的访问6.3.3 动态作用域动态作用域被被调调用用过过程程的的非非局局部部名名字字a和和它它在在调调用用过过程程中中引用的是同样的存储单元引用的是同样的存储单元6.3 非局部名字的访问非局部名字的访问6.3.3 动态作用域动态作用域被被调调用用过过程程的的非非局局部部名名字字a和和它它在在调调用用过过程程中中引用的是同样的存储单元引用的是同样的存储单元新新的的绑绑定定仅仅为为被被调调用用过过程程的的局局部部名名字字建建立立，这这些些名名字字在在被被调调用用过过程程的的活活动动记记录录中中占占用用的的存储单元存储单元6.3 非局部名字的访问非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;beginr:=0.25;show;small;writeln;show;small;writelnend.6.3 非局部名字的访问非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;beginr:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow6.3 非局部名字的访问非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin静态作用域静态作用域r:=0.25;0.250 0.250show;small;writeln;0.250 0.250show;small;writelnend.dynamicshowsmallsmallshowshowshow6.3 非局部名字的访问非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin动动态作用域态作用域r:=0.25;0.250 0.125show;small;writeln;0.250 0.125show;small;writelnend.dynamicshowsmallsmallshowshowshow6.3 非局部名字的访问非局部名字的访问实现动态作用域的方法实现动态作用域的方法深访问深访问用用控控制制链链搜搜索索运运行行栈栈，寻寻找找包包含含该该非非局局部部名名字的第一个活动记录字的第一个活动记录浅访问浅访问为为每每个个名名字字在在静静态态分分配配的的存存储储空空间间中中保保存存它它的的当当前值前值当当过过程程p的的新新活活动动出出现现时时，p的的局局部部名名字字n使使用用在在静静态态数数据据区区分分配配给给n的的存存储储单单元元。n的的先先前前值值可可以以保存在保存在p的活动记录中，当的活动记录中，当p的活动结束时再恢复的活动结束时再恢复6.3 非局部名字的访问非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin(绿色表示已执行部分绿色表示已执行部分)r:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow?r静态区静态区使用值的地方使用值的地方栈区栈区暂存值的地方暂存值的地方dynamicr?6.3 非局部名字的访问非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;beginr:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow0.25rdynamicr?静态区静态区使用值的地方使用值的地方栈区栈区暂存值的地方暂存值的地方6.3 非局部名字的访问非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;beginr:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow0.25rdynamicr?show静态区静态区使用值的地方使用值的地方栈区栈区暂存值的地方暂存值的地方6.3 非局部名字的访问非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;beginr:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow0.25rdynamicr?smallr0.25静态区静态区使用值的地方使用值的地方栈区栈区暂存值的地方暂存值的地方6.3 非局部名字的访问非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;beginr:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow0.125rdynamicr?smallr0.25静态区静态区使用值的地方使用值的地方栈区栈区暂存值的地方暂存值的地方6.3 非局部名字的访问非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;beginr:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow0.25rdynamicr?静态区静态区使用值的地方使用值的地方栈区栈区暂存值的地方暂存值的地方6.4 参参 数数 传传 递递6.4.1值调用值调用实参的右值传给被调用过程实参的右值传给被调用过程值调用可以如下实现值调用可以如下实现把把形形参参当当作作所所在在过过程程的的局局部部名名看看待待，形形参参的的存存储储单元在该过程的活动记录中单元在该过程的活动记录中6.4 参参 数数 传传 递递6.4.1值调用值调用实参的右值传给被调用过程实参的右值传给被调用过程值调用可以如下实现值调用可以如下实现把把形形参参当当作作所所在在过过程程的的局局部部名名看看待待，形形参参的的存存储储单元在该过程的活动记录中单元在该过程的活动记录中调调用用过过程程计计算算实实参参，并并把把其其右右值值放放入入形形参参的的存存储储单元中单元中6.4 参参 数数 传传 递递6.4.2引用调用引用调用实参的左值传给被调用过程实参的左值传给被调用过程引用调用可以如下实现：引用调用可以如下实现：把把形形参参当当作作所所在在过过程程的的局局部部名名看看待待，形形参参的的存存储储单元在该过程的活动记录中单元在该过程的活动记录中调调用用过过程程计计算算实实参参，把把实实参参的的左左值值放放入入形形参参的的存存储单元储单元6.4 参参 数数 传传 递递6.4.2引用调用引用调用实参的左值传给被调用过程实参的左值传给被调用过程引用调用可以如下实现：引用调用可以如下实现：把把形形参参当当作作所所在在过过程程的的局局部部名名看看待待，形形参参的的存存储储单元在该过程的活动记录中单元在该过程的活动记录中调调用用过过程程计计算算实实参参，把把实实参参的的左左值值放放入入形形参参的的存存储单元储单元在在被被调调用用过过程程的的目目标标代代码码中中，任任何何对对形形参参的的引引用用都是通过传给该过程的指针来间接引用实参都是通过传给该过程的指针来间接引用实参6.4 参参 数数 传传 递递6.4.3换名调用换名调用用实参表达式对形参进行正文替换用实参表达式对形参进行正文替换procedureswap(varx,y:integer);vartemp:integer;begintemp:=x;x:=y;y:=tempend6.4 参参 数数 传传 递递6.4.3换名调用换名调用用实参表达式对形参进行正文替换用实参表达式对形参进行正文替换procedureswap(varx,y:integer);vartemp:integer;begin调用调用swap(i,ai)temp:=x;x:=y;y:=tempend6.4 参参 数数 传传 递递6.4.3换名调用换名调用用实参表达式对形参进行正文替换用实参表达式对形参进行正文替换procedureswap(varx,y:integer);vartemp:integer;begin调用调用swap(i,ai)temp:=x;temp:=i;x:=y;i:=ai;y:=tempai:=tempend6.5 堆堆管管理理堆式分配堆式分配堆用来存放生存期不确定的数据堆用来存放生存期不确定的数据C+和和Java允允许许程程序序员员用用new创创建建对对象象，它它们们的的生生存存期期没没有有被被约约束束在在创创建建它它们们的的过过程程活活动动的的生生成成期之内期之内实现内存回收是内存管理器的责任实现内存回收是内存管理器的责任堆空间的回收有两种不同方式堆空间的回收有两种不同方式程序显式释放空间：程序显式释放空间：free（C）或）或delete（C+）垃圾收集器自动收集（垃圾收集器自动收集（Java）6.5 堆堆管管理理6.5.1内存管理器内存管理器内存管理器把握的基本信息是堆中空闲空间内存管理器把握的基本信息是堆中空闲空间分配函数分配函数 回收函数回收函数内存管理器应具有下列性质内存管理器应具有下列性质空间有效性：极小化程序需要的堆空间总量空间有效性：极小化程序需要的堆空间总量程程序序有有效效性性：较较好好地地利利用用内内存存子子系系统统，使使得得程程序序能运行得快一些能运行得快一些低低开开销销：分分配配和和回回收收操操作作所所花花时时间间在在整整个个程程序序执执行时间中的比例尽量小行时间中的比例尽量小6.5 堆堆管管理理6.5.2 计算机内存分层计算机内存分层虚拟内存虚拟内存(磁盘磁盘)物理内存物理内存2级缓存级缓存1级缓存级缓存寄存器寄存器(处理器处理器)典型大小典型大小2千兆字节千兆字节256兆兆 2千兆字节千兆字节128千千 4兆字节兆字节16 64千字节千字节32字字典型访问时间典型访问时间3 15微秒微秒100 150纳秒纳秒40 60纳秒纳秒5 10纳秒纳秒1纳秒纳秒6.5 堆堆管管理理6.5.2 计算机内存分层计算机内存分层现现代代计计算算机机都都设设计计成成程程序序员员不不用用关关心心内内存存子子系系统统的细节就可以写出正确的程序的细节就可以写出正确的程序程程序序的的效效率率不不仅仅取取决决于于被被执执行行的的指指令令数数，还还取取决决于执行每条指令需要多长时间于执行每条指令需要多长时间执行一条指令的时间区别非常可观执行一条指令的时间区别非常可观 差差异异源源于于硬硬件件技技术术的的基基本本局局限限：构构造造不不了了大大容容量量的高速存储器的高速存储器数数据据以以块块（缓缓存存行行、页页）为为单单位位在在相相邻邻层层次次之之间间进行传送进行传送数据密集型程序可从恰当利用内存子系统中获益数据密集型程序可从恰当利用内存子系统中获益6.5 堆堆管管理理6.5.3程序局部性程序局部性大大多多数数程程序序的的大大部部分分时时间间在在执执行行一一小小部部分分代代码，并且仅涉及一小部分数据码，并且仅涉及一小部分数据时间局部性时间局部性程程序序访访问问的的内内存存单单元元在在很很短短的的时时间间内内可可能能再再次次被被程序访问程序访问空间局部性空间局部性毗毗邻邻被被访访问问单单元元的的内内存存单单元元在在很很短短的的时时间间内内可可能能被访问被访问6.5 堆堆管管理理6.5.3程序局部性程序局部性从从代代码码本本身身很很难难看看出出哪哪部部分分代代码码会会被被频频繁繁使使用用,必须动态调整最快缓存的内容必须动态调整最快缓存的内容把把最最近近使使用用的的指指令令保保存存在在缓缓存存是是一一种种较较好好的的最最优优化利用内存分层的策略化利用内存分层的策略改改变变数数据据布布局局或或计计算算次次序序也也可可以以改改进进程程序序数数据据访访问的时间和空间局部性问的时间和空间局部性6.5 堆堆管管理理6.5.4手工回收请求手工回收请求程程序序员员在在程程序序中中显显式式释释放放堆堆块块来来达达到到回回收收堆堆块的目的块的目的内存泄漏：没有释放已经引用不到的堆块内存泄漏：没有释放已经引用不到的堆块只要内存没有用尽，它就不影响程序的正确性只要内存没有用尽，它就不影响程序的正确性 自自动动无无用用单单元元收收集集通通过过回回收收所所有有无无用用单单元元来来摆摆脱内存泄漏脱内存泄漏悬空引用：引用已经被释放的堆块悬空引用：引用已经被释放的堆块 过分热心地释放数据对象而引起过分热心地释放数据对象而引起悬空引用容易导致不会被捕获的错误悬空引用容易导致不会被捕获的错误 本本章章要要点点影响存储分配策略的语言特征影响存储分配策略的语言特征各各种种存存储储分分配配策策略略，主主要要了了解解静静态态分分配配和和动动态栈式分配态栈式分配活动记录中各种数据域的作用和安排活动记录中各种数据域的作用和安排非局部数据访问的实现方法非局部数据访问的实现方法各种参数传递方式及其实现各种参数传递方式及其实现堆管理堆管理例例题题1一个一个C语言程序及其在语言程序及其在X86/Linux操作系统上的编译结操作系统上的编译结果如下。果如下。根据所生成的汇编程序来解释程序中四个变根据所生成的汇编程序来解释程序中四个变量的存储分配、作用域、生存期和置初值方式等方面量的存储分配、作用域、生存期和置初值方式等方面的区别的区别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).value20|.例例题题2main()char*cp1,*cp2;cp1=12345;cp2=abcdefghij;strcpy(cp1,cp2);printf(cp1=%sncp2=%sn,cp1,cp2);在某些系统上的运行结果是：在某些系统上的运行结果是：cp1=abcdefghijcp2=ghij为什么为什么cp2所指的串被修改了？所指的串被修改了？例例题题2因因为为常常量量串串“12345”和和“abcdefghij”连连续续分分配配在在常数区常数区执行前：执行前：123450abcdefghij0 cp1cp2例例题题2因因为为常常量量串串“12345”和和“abcdefghij”连连续续分分配配在在常数区常数区执行前：执行前：123450abcdefghij0 cp1cp2执行后执行后：abcdefghij0fghij0 cp1cp2例例题题2因因为为常常量量串串“12345”和和“abcdefghij”连连续续分分配配在在常数区常数区执行前：执行前：123450abcdefghij0 cp1cp2执行后执行后：abcdefghij0fghij0 cp1cp2现在的编译器大都把程序中的串常量单独存放在只读现在的编译器大都把程序中的串常量单独存放在只读数据段中，因此运行时会报错数据段中，因此运行时会报错例例题题3func(i)longi;longj;j=i-1;func(j);例例题题3func(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(下条指令地址）下条指令地址）. . .参数参数i返址返址控制链控制链变量变量j.ebp esp 栈栈低低高高例例题题3func(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(下条指令地址）下条指令地址）. . .参数参数i返址返址控制链控制链变量变量j.ebp esp 栈栈低低高高调用序列调用序列返回序列返回序列例例题题4下面的程序运行时输出下面的程序运行时输出3个整数。试从运行环个整数。试从运行环境和境和printf的实现来分析，为什么此程序会有的实现来分析，为什么此程序会有3个整数输出？个整数输出？main()printf(“%d,%d,%dn”);例例题题5func(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例例题题5func(i,j,f,e)Sizesofshort,int,long,float,shorti,j;floatf,e;double=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(i,j,f,e)Sizesofshort,int,long,float,shorti,j;floatf,e;double=2,4,4,4,8（在在SPARC/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语语言言编编译译器器是是不不做做实实在在参参数数和和形形式式参参数数的的个个数数和和类类型型是是否否一一致致的的检检查查的，由程序员自己保证它们的一致性的，由程序员自己保证它们的一致性例例题题5当当用用传传统统的的参参数数声声明明方方式式时时，C语语言言编编译译器器是是不不做做实实在在参参数数和和形形式式参参数数的的个个数数和和类类型型是是否否一一致致的的检检查查的，由程序员自己保证它们的一致性的，由程序员自己保证它们的一致性但但是是对对于于形形式式参参数数和和实实在在参参数数是是不不同同的的整整型型，或或者者是是不不同同的的实实型型，编编译译器器则则试试图图保保证证目目标标代代码码运运行行时时能能得得到到正正确确的的结结果果，条条件件是是，当当需需要要把把高高级级别别类类型型数据向低级别类型数据转换时，不出现溢出数据向低级别类型数据转换时，不出现溢出例例题题5当当用用传传统统的的参参数数声声明明方方式式时时，C语语言言编编译译器器是是不不做做实实在在参参数数和和形形式式参参数数的的个个数数和和类类型型是是否否一一致致的的检检查查的，由程序员自己保证它们的一致性的，由程序员自己保证它们的一致性但但是是对对于于形形式式参参数数和和实实在在参参数数是是不不同同的的整整型型，或或者者是是不不同同的的实实型型，编编译译器器则则试试图图保保证证目目标标代代码码运运行行时时能能得得到到正正确确的的结结果果，条条件件是是，当当需需要要把把高高级级别别类类型型数据向低级别类型数据转换时，不出现溢出数据向低级别类型数据转换时，不出现溢出当当整整型型或或实实型型数数据据作作为为实实在在参参数数时时，将将它它们们分分别别提提升到升到long和和double类型的数据再传递到被调用函数类型的数据再传递到被调用函数例例题题5当当用用传传统统的的参参数数声声明明方方式式时时，C语语言言编编译译器器是是不不做做实实在在参参数数和和形形式式参参数数的的个个数数和和类类型型是是否否一一致致的的检检查查的，由程序员自己保证它们的一致性的，由程序员自己保证它们的一致性但但是是对对于于形形式式参参数数和和实实在在参参数数是是不不同同的的整整型型，或或者者是是不不同同的的实实型型，编编译译器器则则试试图图保保证证目目标标代代码码运运行行时时能能得得到到正正确确的的结结果果，条条件件是是，当当需需要要把把高高级级别别类类型型数据向低级别类型数据转换时，不出现溢出数据向低级别类型数据转换时，不出现溢出当当整整型型或或实实型型数数据据作作为为实实在在参参数数时时，将将它它们们分分别别提提升到升到long和和double类型的数据再传递到被调用函数类型的数据再传递到被调用函数被被调调用用函函数数根根据据形形式式参参数数所所声声明明的的类类型型，决决定定是是否否要将实在参数向低级别类型转换要将实在参数向低级别类型转换例例题题5低地址低地址放高位放高位高地址高地址放低位放低位shortlong长整型和短整型长整型和短整型floatdouble双精度型和浮点型双精度型和浮点型例例题题5e，8个字节个字节在在main函函数数中中参参数数压压栈栈时的观点时的观点在在func函函数数中中存存取取形形式式参参数数时的观点时的观点4个字节，起始地址个字节，起始地址544个字节，起始地址个字节，起始地址442个字节，起始地址个字节，起始地址422个字节，起始地址个字节，起始地址36f，8个字节个字节j，4个字节个字节i，4个字节个字节栈栈的的增增长长方向方向参数在栈中的情况参数在栈中的情况例例题题6下下面面程程序序为为什什么么死死循循环环（在在SPARC/SUN工工作作站站上）上）？main()addr();loop();long*p;loop()longi,j; j=0;for(i=0;i10;i+) (*p)-;j+;addr()longk;k=0;p=&k;例例题题6将将long*p改成改成short*p，longk改成改成shortk后，循环体执行一次便停止，为什么？后，循环体执行一次便停止，为什么？main()addr();loop();short*p;loop()longi,j; j=0;for(i=0;i10;i+) (*p)-;j+;addr()shortk;k=0;p=&k;例例题题6将将long*p改成改成short*p，longk改成改成shortk后，循环体执行一次便停止，为什么？后，循环体执行一次便停止，为什么？main()addr();loop();short*p; 活动记录栈是从高向低方向增长活动记录栈是从高向低方向增长loop()longi,j; j=0;for(i=0;i10;i+) (*p)-;j+;addr()shortk;k=0;p=&k;低地址低地址放高位放高位高地址高地址放低位放低位shortklongi例例题题7main() func(); printf(Returnfromfuncn);func() chars4;strcpy(s,12345678);printf(%sn,s);例例题题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);. . .返址返址控制链控制链变量变量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(%dn,fact();returni*fact(i-1);|该程序在该程序在X86/Linux机器上的运行结果如下：机器上的运行结果如下：1201201Segmentationfault(coredumped)例例题题8请解释下面问题：请解释下面问题：第第二二个个fact调调用用：结结果果为为什什么么没没有有受受参参数数过过多多的的影响？影响？第第三三个个fact调调用用：为为什什么么用用浮浮点点数数5.0作作为为参参数数时时结果变成结果变成1?第第四四个个fact调调用用：为为什什么么没没有有提提供供参参数数时时会会出出现现Segmentationfault？例例题题8请解释下面问题：请解释下面问题：第第二二个个fact调调用用：结结果果为为什什么么没没有有受受参参数数过过多多的的影响？影响？解解答答：参参数数表表达达式式逆逆序序计计算算并并进进栈栈，fact能能够够取取到到第一个参数第一个参数例例题题8请解释下面问题：请解释下面问题：第第三三个个fact调调用用：为为什什么么用用浮浮点点数数5.0作作为为参参数数时时结果变成结果变成1?解答：解答：参数参数5.0转换成双精转换成双精度数进栈，占度数进栈，占8个字节个字节它低地址的它低地址的4个字节看成整个字节看成整数时正好是数时正好是0. . .参数参数返址返址控制链控制链局部变量局部变量ebp esp 栈栈低低高高例例题题8请解释下面问题：请解释下面问题：第第四四个个fact调调用用：为为什什么么没没有有提提供供参参数数时时会会出出现现Segmentationfault？解答：由于没有提供参数，解答：由于没有提供参数，fact把老把老ebp（控制链）控制链）（main的活动记录中保存的活动记录中保存的的ebp）当成参数，它一定当成参数，它一定是一个很大的整数，使得活是一个很大的整数，使得活动记录栈溢出动记录栈溢出. . .参数参数返址返址控制链控制链局部变量局部变量ebp esp 栈栈低低高高习习题题第一次：第一次：6.3,6.4,6.5第二次：第二次：6.6,6.9,6.12第三次：第三次：6.16,6.18,6.23