编译原理第六章运行时存储空间的组织和管理

1、第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 术语术语过程的过程的活动活动过程的一次执行称为过程的一次活动过程的一次执行称为过程的一次活动 活动记录活动记录过程的活动需要可执行代码和存放所需信息的存储空间过程的活动需要可执行代码和存放所需信息的存储空间, ,后者称为活动记录后者称为活动记录本章内容本章内容 讨论一个活动记录中的数据布局讨论一个活动记录中的数据布局 程序执行过程中，所有活动记录的组织方式程序执行过程中，所有活动记录的组织方式 第六章第六章 运行时存储空间的组织和管理运行时存储空间的组织和管理 影响存储分配策略的语言特征影响存储分配策略的语言特征 过程能否递归

2、过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量过程能否访问非局部变量 过程调用的参数传递方式过程调用的参数传递方式 过程能否作为参数被传递过程能否作为参数被传递 过程能否作为结果值传递过程能否作为结果值传递 存储块能否在程序控制下动态地分配存储块能否在程序控制下动态地分配存储块是否必须显式地释放存储块是否必须显式地释放6.1 局部存储分配局部存储分配6.1.1 过程过程语言概念：语言概念：过程定义、过程定义、过程过程调用、形式参数、实在参调用、形式参数、实在参数、数、活动的活动的生存期生存期6.1 局部存储

3、分配局部存储分配6.1.2 名字的作用域和绑定名字的作用域和绑定1、名字的作用域、名字的作用域 一个声明起作用的程序部分称为该声明的一个声明起作用的程序部分称为该声明的作作用域用域6.1 局部存储分配局部存储分配2、环境和状态、环境和状态 环境把名字映射到左值，而状态把左值映射环境把名字映射到左值，而状态把左值映射到右值（即到右值（即名字到值有两步映射名字到值有两步映射） 赋值改变状态，但不改变环境赋值改变状态，但不改变环境 过程调用改变环境过程调用改变环境 如果环境将名字如果环境将名字x映射到存储单元映射到存储单元s，则说则说x被被绑定绑定到到s名字名字存储单元存储单元状态状态值值环境环境6

4、.1 局部存储分配局部存储分配3、静态概念和动态概念的对应、静态概念和动态概念的对应静静 态态 概概 念念 动动 态态 对对 应应 过程的定义过程的定义 过程的活动过程的活动 6.1 局部存储分配局部存储分配3、静态概念和动态概念的对应、静态概念和动态概念的对应静静 态态 概概 念念 动动 态态 对对 应应 过程的定义过程的定义 过程的活动过程的活动 名字的声明名字的声明 名字的绑定名字的绑定 6.1 局部存储分配局部存储分配3、静态概念和动态概念的对应、静态概念和动态概念的对应静静 态态 概概 念念 动动 态态 对对 应应 过程的定义过程的定义 过程的活动过程的活动 名字的声明名字的声明 名

5、字的绑定名字的绑定 声明的作用域声明的作用域 绑定的生存期绑定的生存期 6.1 局部存储分配局部存储分配6.1.3 活动记录活动记录活动记录的常见布局活动记录的常见布局返返 回回 值值临临 时时 数数 据据参参 数数控控 制制 链链访访 问问 链链机机 器器 状状 态态局局 部部 数数 据据6.1 局部存储分配局部存储分配6.1.4 局部数据的布局局部数据的布局 字节是可编址内存的最小单位字节是可编址内存的最小单位 一个过程所声明的局部变量，按这些变量声明时出一个过程所声明的局部变量，按这些变量声明时出现的次序，在局部数据域中依次分配空间现的次序，在局部数据域中依次分配空间 局部数据的地址可以

6、用相对于某个位置的地址来表局部数据的地址可以用相对于某个位置的地址来表示示 数据对象的存储布局还有一个数据对象的存储布局还有一个对齐问题对齐问题6.1 局部存储分配局部存储分配 例例 在在SPARC/Solaris工作站上下面两个结构体的工作站上下面两个结构体的size分别是分别是24和和16，为什么不一样？，为什么不一样？typedef struct _atypedef struct _bchar c1; char c1;long i; char c2;char c2; long i;double f; double f;a; b;对齐：对齐：char : 1, long : 4, doub

7、le : 86.1 局部存储分配局部存储分配 例例 在在SPARC/Solaris工作站上下面两个结构体的工作站上下面两个结构体的size分别是分别是24和和16，为什么不一样？，为什么不一样？typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2; 1char c2;8 long i; 4double f;16 double f; 8a; b;对齐：对齐：char : 1, long : 4, double : 86.1 局部存储分配局部存储分配 例例 在在X86/Linux机器的结果和机器的结果和SPARC

8、/Solaris工作工作站不一样，是站不一样，是20和和16。typedef struct _atypedef struct _bchar c1;0 char c1;0long i;4 char c2; 1char c2;8 long i; 4double f;12 double f; 8a; b;对齐：对齐：char : 1, long : 4, double : 46.1 局部存储分配局部存储分配6.1.5 程序块程序块 本身含有局部变量声明的语句本身含有局部变量声明的语句 可以嵌套可以嵌套 最接近的嵌套最接近的嵌套作用域规则作用域规则 并列程序块不会同时活跃并列程序块不会同时活跃 并列程

9、序块的变量可以重叠分配并列程序块的变量可以重叠分配6.1 局部存储分配局部存储分配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 /声声 明明 作作 用用 域域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a =

10、 2;B2int b = 3; B3 a0b0b1a2, b3重叠分配存储单元重叠分配存储单元 6.2 全局栈式存储分配全局栈式存储分配本节介绍本节介绍 描述过程的目标代码怎样访问绑定到局部名字的存描述过程的目标代码怎样访问绑定到局部名字的存储单元储单元 介绍三种分配策略介绍三种分配策略 静态分配策略静态分配策略 栈式分配策略栈式分配策略 堆式分配策略堆式分配策略6.2 全局栈式存储分配全局栈式存储分配6.2.1 运行时内存的划分运行时内存的划分代代 码码静静 态态 数数 据据堆堆栈栈6.2 全局栈式存储分配全局栈式存储分配1、静态分配、静态分配 名字在程序被编译时绑定到存储单元，不需名字在程

11、序被编译时绑定到存储单元，不需要运行时的任何支持要运行时的任何支持 绑定的生存期是程序的整个运行期间绑定的生存期是程序的整个运行期间6.2 全局栈式存储分配全局栈式存储分配2、静态分配给语言带来限制、静态分配给语言带来限制 递归过程不被允许递归过程不被允许 数据对象的长度和它在内存中位置的限制，数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的必须是在编译时可以知道的 数据结构不能动态建立数据结构不能动态建立6.2 全局栈式存储分配全局栈式存储分配 例例 C程序的外部变量、静态局部变量以及程程序的外部变量、静态局部变量以及程序中出现的常量都可以静态分配序中出现的常量都可以静态分配

12、声明在函数外面声明在函数外面外部变量外部变量 静态分配静态分配静态外部变量静态外部变量 静态分配静态分配 声明在函数里面声明在函数里面静态局部变量静态局部变量 也是静态分配也是静态分配自动变量自动变量 不能静态分配不能静态分配6.2 全局栈式存储分配全局栈式存储分配6.2.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,3)q(5,9)q(5,5)p(5,9)q(7,9)q(7,7)q(9,9)p(7,9)6.2 全局

13、栈式存储分配全局栈式存储分配 活动树的特点活动树的特点每个结点代表某过程的一个活动每个结点代表某过程的一个活动根结点代表主程序的活动根结点代表主程序的活动结点结点a是结点是结点b的父结点，当且仅当控制流从的父结点，当且仅当控制流从a的的活动进入活动进入b的活动的活动结点结点a处于结点处于结点b的左边，当且仅当的左边，当且仅当a的生存期先的生存期先于于b的生存期的生存期6.2 全局栈式存储分配全局栈式存储分配 当前活跃着的过程活动可以保存在一个栈中当前活跃着的过程活动可以保存在一个栈中 例例 控制栈的内容：控制栈的内容：m, q (1, 9), q (1, 3), q (2, 3) mq(1,9

14、)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、运行栈：、运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录） ma : arraym6

15、.2 全局栈式存储分配全局栈式存储分配2、运行栈：、运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录） mint ira : arraymr6.2 全局栈式存储分配全局栈式存储分配2、运行栈：、运行栈：把控制栈中的信息拓广到包括过程把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录） mq(1,9)rmint iq (1, 9)a : arrayint m, n6.2 全局栈式存储分配全局栈式存储分配2、运行栈：、运行栈：把控制栈中的信息拓广到包括过程把控

16、制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）活动所需的所有局部信息（即活动记录） mq(1,9)rp(1,9) q(1,3)q(1,0)p(1,3)q (1, 9)mint ia : arrayint m, nint m, nint iq (1, 3)6.2 全局栈式存储分配全局栈式存储分配6.2.3 调用序列调用序列 过程调用序列过程调用序列过程调用时执行的分配活动记录、把信息填入域中的代码过程调用时执行的分配活动记录、把信息填入域中的代码 过程返回序列过程返回序列过程返回时执行的恢复机器状态，释放活动记录，使调用过过程返回时执行的恢复机器状态，释放活动记录，使调用过程能够

17、继续执行的代码程能够继续执行的代码6.2 全局栈式存储分配全局栈式存储分配 即使是同一种语言，过程调用序列、返回序列和活即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异动记录中各域的排放次序，也会因实现而异 设计这些序列和活动记录的原则设计这些序列和活动记录的原则调用者和被调用者交流的数据放在调用者和被调用者交流的数据放在活动记录开始处，并尽可能靠近调用活动记录开始处，并尽可能靠近调用者的活动记录者的活动记录固定长度的项放在活动记录中间。固定长度的项放在活动记录中间。在编译时不能及时知道大小的项目在编译时不能及时知道大小的项目放在活动记录末端放在活动记录末端返

18、返 回回 值值临临 时时 数数 据据参参 数数控控 制制 链链访访 问问 链链机机 器器 状状 态态局局 部部 数数 据据6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列(1) p计算实参，依计算实参，依次放入栈顶，并在次放入栈顶，并在栈顶留出放返回值栈顶留出放返回值的空间。的空间。top_sp的的值在此过程中被改值在此过程

19、中被改变变返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 返回值和参数返回值和参数6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列(2) p把返回地址和把返回地址和当前当前base_sp的值的值存入存入q的活动记录的活动记录中，建立中，建立q的访问的访问链，增加链，增加base_sp的值的值返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 返回值和参数返回值和参数控制链和返回地址控

20、制链和返回地址6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列(3) q保存寄存器的保存寄存器的值和其它机器状态值和其它机器状态信息信息返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 返回值和参数返回值和参数控制链控制链 和保存的机器状态和保存的机器状态6.2 全局栈式存储分配全局栈式存储分配1、过程、过程p调用过程调用过程q的调用序列的调用序列(4) q根据局部数据根据局部数据域和临时数据域的域和临时数据域的大小增加大小增加top_sp的的值，初始化它的局值，初

21、始化它的局部数据，并开始执部数据，并开始执行过程体行过程体临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链 和保存的机器状态和保存的机器状态top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配调用者调用者p和被调用者和被调用者q之间的任务划分之间的任务划分被调用者被调用者q的责任的责任调用者调用者p的责任的责任调用者调用者p的的活动记录活动记录被被调用者调用者q的活动记录的活动记录临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回

22、值和参数 控制链控制链 和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列临时数据局部数据临时数据局部数据返回值和参数返回值和参数返回值和参数返回值和参数 控制链控制链 和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过

23、程调用过程q的返回序列的返回序列临时数据局部数据临时数据局部数据返回值返回值和参数和参数返回值和参数返回值和参数 控制链控制链 和保存的机器状态和保存的机器状态top_sp base_sp 栈栈增增长长方方向向临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 (1) q把返回值置入邻把返回值置入邻近近p的活动记录存放的活动记录存放返回值的地方返回值的地方 6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列(2) q对应调用序列对应调用序列的步骤的步骤(4)，减小，减小top_sp的值的值返回值和参数返回值和参数top_s

24、p base_sp 临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 返回值和参数返回值和参数控制链控制链 和保存的机器状态和保存的机器状态6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返回序列(3) q恢复寄存器恢复寄存器(包包括括base_sp)和机器和机器状态，返回状态，返回p返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 返回值和参数返回值和参数6.2 全局栈式存储分配全局栈式存储分配2、过程、过程p调用过程调用过程q的返回序列的返

25、回序列返回值和参数返回值和参数top_sp base_sp 临时数据局部数据临时数据局部数据控制链控制链 和保存的机器状态和保存的机器状态 (4) p根据参数个数根据参数个数与类型和返回值类与类型和返回值类型调整型调整top_sp，然然后取出返回值后取出返回值6.2 全局栈式存储分配全局栈式存储分配6.2.4 栈上可变长数据栈上可变长数据活动记录的长度在编译时不能确定的情况活动记录的长度在编译时不能确定的情况 例：局部数组的大小要等到过程激活时才能例：局部数组的大小要等到过程激活时才能确定确定备注：备注： Java语言的实现是将它们分配在堆上语言的实现是将它们分配在堆上6.2 全局栈式存储分配

26、全局栈式存储分配访问动态分配的数组访问动态分配的数组控制链控制链数组数组A的指针的指针数组数组B的指针的指针top_sp base_sp . . . . . . .栈栈(1) 编译时，在活编译时，在活动记录中为这样动记录中为这样的数组分别存放的数组分别存放数组指针的单元数组指针的单元6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组(2) 运行时，运行时，这些指针指向这些指针指向分配在栈顶的分配在栈顶的存储空间存储空间控制链控制链数组数组A的指针的指针数组数组B的指针的指针top_sp base_sp . . . . . . .栈栈数组数组A数组数组B6.2 全局栈式

27、存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组(3) 运行时，运行时，对数组对数组A和和B的访问都要通的访问都要通过相应指针来过相应指针来间接访问间接访问控制链控制链数组数组A的指针的指针数组数组B的指针的指针top_sp base_sp . . . . . . .栈栈数组数组A数组数组B6.2 全局栈式存储分配全局栈式存储分配访问动态分配的数组访问动态分配的数组q的数组的数组q的活动记录的活动记录p的数组的数组p的活动记录的活动记录控制链控制链top_sp base_sp 数组数组A的指针的指针数组数组B的指针的指针数组数组A数组数组B控制链控制链. . . . . . .栈栈

28、6.2 全局栈式存储分配全局栈式存储分配6.2.5 悬空引用悬空引用悬空引用：悬空引用：引用某个已被释放的存储单元引用某个已被释放的存储单元6.2 全局栈式存储分配全局栈式存储分配6.2.5 悬空引用悬空引用悬空引用：悬空引用：引用某个已被释放的存储单元引用某个已被释放的存储单元main()|int dangle ( ) |int q;|int j = 20; q = dangle ( ); |return &j;|*6.3 非局部名字的访问非局部名字的访问本节介绍本节介绍 无过程嵌套的静态作用域（无过程嵌套的静态作用域（C语言）语言） 有过程嵌套的静态作用域有过程嵌套的静态作用域（Pasca

29、l语言）语言） 动态作用域动态作用域（Lisp语言）语言）* 6.3 非局部名字的访问非局部名字的访问6.3.1 无过程嵌套的静态作用域无过程嵌套的静态作用域 过程体中的非局部引用可以直接使用静态确过程体中的非局部引用可以直接使用静态确定的地址定的地址 局部变量在栈顶的活动记录中，可以通过局部变量在栈顶的活动记录中，可以通过base_sp指针来访问指针来访问 无须深入栈中取数据，无须访问链无须深入栈中取数据，无须访问链 过程可以作为参数来传递，也可以作为结果过程可以作为参数来传递，也可以作为结果来返回来返回*6.3 非局部名字的访问非局部名字的访问6.3.2 有过程嵌套的静态作用域有过程嵌套的

30、静态作用域sortreadarrayexchangequicksortpartition*6.3 非局部名字的访问非局部名字的访问6.3.2 有过程嵌套的静态作用域有过程嵌套的静态作用域 过程过程嵌套深度嵌套深度sort1readarray2exchange2quicksort2partition3 变量的嵌套深度：它的声明所在过程的嵌套变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度深度作为该名字的嵌套深度 访问链访问链用来寻找非局部用来寻找非局部名字的存储单元名字的存储单元sa, xq (1, 9)k, v访问链访问链sa, xq (1, 3)k, v访问链访问链q (1,

31、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 非局部名字的访问非局部名字的访问 访问非局部名字的存储单元访问非局部名字的存储单元 假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度为它引用嵌套深度为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单元sort1readarra

32、y2exchange2quicksort2partition3*6.3 非局部名字的访问非局部名字的访问 访问非局部名字的存储单元访问非局部名字的存储单元 假定过程假定过程p的嵌套深度为的嵌套深度为np，它引用嵌套深度为它引用嵌套深度为na的变量的变量a，na np。如何访问如何访问a的存储单元的存储单元 从栈顶的活动记录开始，追踪访问链从栈顶的活动记录开始，追踪访问链np na次次到达到达a的声明所在过程的活动记录的声明所在过程的活动记录 访问链的追踪用间接操作就可完成访问链的追踪用间接操作就可完成sort1readarray2exchange2quicksort2partition3 访问

33、非局部名字的存储单元访问非局部名字的存储单元 sort readarray exchange quicksort partitionsa, 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 非局部名字的访问非局部名

34、字的访问 C语言的函数声明不能嵌套，函数不论在什语言的函数声明不能嵌套，函数不论在什么情况下激活，要访问的数据分成两种情况么情况下激活，要访问的数据分成两种情况非静态局部变量（包括形式参数），它们分配在非静态局部变量（包括形式参数），它们分配在活动记录栈顶的那个活动记录中活动记录栈顶的那个活动记录中外部变量（包括定义在其它源文件之中的外部变外部变量（包括定义在其它源文件之中的外部变量）和静态的局部变量，它们都分配在静态数据量）和静态的局部变量，它们都分配在静态数据区区6.4 参参 数数 传传 递递6.4.1 值调用值调用 实参的右值传给被调用过程实参的右值传给被调用过程 值调用可以如下实现值调

35、用可以如下实现 把形参当作所在过程的局部名看待，形参的存储把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中单元在该过程的活动记录中调用过程计算实参，并把其右值放入形参的存储调用过程计算实参，并把其右值放入形参的存储单元中单元中6.4 参参 数数 传传 递递6.4.2 引用调用引用调用 实参的左值传给被调用过程实参的左值传给被调用过程 引用调用可以如下实现：引用调用可以如下实现： 把形参当作所在过程的局部名看待，形参的存储把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中单元在该过程的活动记录中调用过程计算实参，调用过程计算实参，把实参的左值放入形参的存把实参的

36、左值放入形参的存储单元储单元 在被调用过程的目标代码中，任何对形参的引用在被调用过程的目标代码中，任何对形参的引用都是通过传给该过程的指针来间接引用实参都是通过传给该过程的指针来间接引用实参6.4 参参 数数 传传 递递6.4.3 换名调用换名调用从概念上说，每次调用时，用实参表达式对从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行形参进行正文替换，然后再执行procedure swap(var x, y: integer);var temp: integer; begin temp := x; x := y; y := temp end6.4 参参 数数 传传 递递6.4.

37、3 换名调用换名调用从概念上说，每次调用时，用实参表达式对从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行形参进行正文替换，然后再执行procedure swap(var x, y: integer);var temp: integer;例如：例如：调用调用swap(i, ai) begin temp := x; x := y; y := temp end6.4 参参 数数 传传 递递6.4.3 换名调用换名调用从概念上说，每次调用时，用实参表达式对从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行形参进行正文替换，然后再执行procedure swap(va

38、r x, y: integer);var temp: integer;例如：例如：调用调用swap(i, ai) begin 替换结果：替换结果： temp := i; temp := x; i := ai; x := y; ai := temp y := temp end6.4 参参 数数 传传 递递6.4.3 换名调用换名调用从概念上说，每次调用时，用实参表达式对从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行形参进行正文替换，然后再执行procedure swap(var x, y: integer);var temp: integer;例如：例如：调用调用swap(i

39、, ai) begin 替换结果：替换结果： temp := i; temp := x; i := ai; x := y; ai := temp y := temp 交换两个数据的程序交换两个数据的程序 end并非总是正确并非总是正确 栈式存储分配策略在下列情况下不能使用：栈式存储分配策略在下列情况下不能使用： 活动结束时必须保持局部名字的值活动结束时必须保持局部名字的值 被调用者的活动比调用者的活动的生存期长。被调用者的活动比调用者的活动的生存期长。 堆式存储器的策略：（堆管理器管理堆空间）堆式存储器的策略：（堆管理器管理堆空间） 把连续存储区域分成块，当活动记录或其他对象把连续存储区域分成

40、块，当活动记录或其他对象需要时就分配。需要时就分配。 块的释放可以按任意次序进行，所以经过一段时块的释放可以按任意次序进行，所以经过一段时间后，堆可能包含交错的正在使用的和已经释放间后，堆可能包含交错的正在使用的和已经释放的区域的区域6.5 堆堆 管管 理理6.5 堆堆 管管 理理堆式分配堆式分配 堆用来存放生存期不确定的数据堆用来存放生存期不确定的数据 C+和和Java允许程序员用允许程序员用new创建对象，它们的生存期没创建对象，它们的生存期没有被约束在创建它们的过程活动的生成期之内有被约束在创建它们的过程活动的生成期之内 实现内存回收是内存管理器的责任实现内存回收是内存管理器的责任 堆空

41、间的回收有两种不同方式堆空间的回收有两种不同方式 程序显式释放空间：程序显式释放空间：free（C）或）或delete（C+） 垃圾收集器自动收集（垃圾收集器自动收集（Java）。）。6.5 堆堆 管管 理理6.5.1 内存管理器内存管理器 内存管理器把握的基本信息是堆中空闲空间内存管理器把握的基本信息是堆中空闲空间 分配函数分配函数 回收函数回收函数 内存管理器应具有下列性质内存管理器应具有下列性质 空间有效性：极小化程序需要的堆空间总量空间有效性：极小化程序需要的堆空间总量 程序有效性：较好地利用内存子系统，使得程序能运行程序有效性：较好地利用内存子系统，使得程序能运行得快一些得快一些 低

42、开销低开销：分配和回收操作所花时间在整个程序执行时间分配和回收操作所花时间在整个程序执行时间中的比例尽量小中的比例尽量小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 计算机内存分层计算机内存分层 现代计算机都设计成程序

43、员不用关心内存子系统的细节现代计算机都设计成程序员不用关心内存子系统的细节就可以写出正确的程序就可以写出正确的程序 程序的效率不仅取决于被执行的指令数，还取决于执行程序的效率不仅取决于被执行的指令数，还取决于执行每条指令需要多长时间每条指令需要多长时间 执行一条指令的时间区别非常可观执行一条指令的时间区别非常可观 差异源于硬件技术的基本局限：构造不了大容量的高速差异源于硬件技术的基本局限：构造不了大容量的高速存储器存储器 数据以块（缓存行、页）为单位在相邻层次之间进行传数据以块（缓存行、页）为单位在相邻层次之间进行传送送 数据密集型程序可从恰当利用内存子系统中获益数据密集型程序可从恰当利用内存

44、子系统中获益6.5 堆堆 管管 理理6.5.3 程序局部性程序局部性 大多数程序的大部分时间在执行一小部分代码，并大多数程序的大部分时间在执行一小部分代码，并且仅涉及一小部分数据且仅涉及一小部分数据 时间局部性时间局部性 程序访问的内存单元在很短的时间内可能再次被程序访程序访问的内存单元在很短的时间内可能再次被程序访问问 空间局部性空间局部性 毗邻被访问单元的内存单元在很短的时间内可能被访问毗邻被访问单元的内存单元在很短的时间内可能被访问6.5 堆堆 管管 理理6.5.3 程序局部性程序局部性 从代码本身很难看出哪部分代码会被频繁使用从代码本身很难看出哪部分代码会被频繁使用,必必须动态调整最快

45、缓存的内容须动态调整最快缓存的内容 把最近使用的指令保存在缓存是一种较好的最优把最近使用的指令保存在缓存是一种较好的最优化利用内存分层的策略化利用内存分层的策略 改变数据布局或计算次序也可以改进程序数据访改变数据布局或计算次序也可以改进程序数据访问的时间和空间局部性问的时间和空间局部性6.5 堆堆 管管 理理6.5.4 手工回收请求手工回收请求 程序员在程序中显式释放堆块来达到回收堆块的目程序员在程序中显式释放堆块来达到回收堆块的目的的 内存泄漏：没有释放已经引用不到的堆块内存泄漏：没有释放已经引用不到的堆块 只要内存没有用尽，它就不影响程序的正确性只要内存没有用尽，它就不影响程序的正确性 自

46、动无用单元收集通过回收所有无用单元来摆脱内存自动无用单元收集通过回收所有无用单元来摆脱内存泄漏泄漏 悬空引用：引用已经被释放的堆块悬空引用：引用已经被释放的堆块 过分热心地释放数据对象而引起过分热心地释放数据对象而引起 悬空引用容易导致不会被捕获的错误悬空引用容易导致不会被捕获的错误 本本 章章 要要 点点 影响存储分配策略的语言特征影响存储分配策略的语言特征 各种存储分配策略，主要了解静态分配和动各种存储分配策略，主要了解静态分配和动态栈式分配态栈式分配 活动记录中各种数据域的作用和布局活动记录中各种数据域的作用和布局 非局部数据访问的实现方法非局部数据访问的实现方法 各种参数传递方式及其实

47、现各种参数传递方式及其实现 堆管理堆管理例例 题题 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

48、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|. . .例例 题题 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.

49、globl bb|.align 4.align 2| .globl func .type bb,object| func:.size bb,2|. . .bb:|movw $40,-2(%ebp).value 20|. . .例例 题题 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

50、bb,2|. . .bb:|movw $40,-2(%ebp).value 20|. . .例例 题题 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|. . .例例 题题 2func(i)long i;

51、long j;j= i -1;func(j);例例 题题 2func(i)func: long i; pushl %ebp 老的基地址指针压栈老的基地址指针压栈 movl %esp,%ebp修改修改基地址指针基地址指针 long j; subl $4,%esp 为为j分配空间分配空间 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把实参把实参j的值压栈的值压栈 call func 函数调用函数调用 addl

52、$4,%esp 恢复栈顶指针恢复栈顶指针L1: leave 即即 mov ebp, esp; pop ebp ret 即即 pop eip(下条指令地址）下条指令地址）. . .参数参数i返址返址控制链控制链变量变量j. . .ebp esp 栈栈低低高高例例 题题 2func(i)func: long i; pushl %ebp 老的基地址指针压栈老的基地址指针压栈 movl %esp,%ebp修改修改基地址指针基地址指针 long j; subl $4,%esp 为为j分配空间分配空间 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl

53、 %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把实参把实参j的值压栈的值压栈 call func 函数调用函数调用 addl $4,%esp 恢复栈顶指针恢复栈顶指针L1: leave 即即 mov ebp, esp; pop ebp ret 即即 pop eip(下条指令地址）下条指令地址）. . . . .ebp esp 例例 题题 2func(i)func: long i; pushl %ebp 老的基地址指针压栈老的基地址指针压栈 movl %esp,%ebp修改修改基地址指针基地址指针 long j;

54、 subl $4,%esp 为为j分配空间分配空间 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把实参把实参j的值压栈的值压栈 call func 函数调用函数调用 addl $4,%esp 恢复栈顶指针恢复栈顶指针L1: leave 即即 mov ebp, esp; pop ebp ret 即即 pop eip(下条指令地址）下条指令地址）. . . . .ebp esp 参数参数i例例 题题 2func

55、(i)func: long i; pushl %ebp 老的基地址指针压栈老的基地址指针压栈 movl %esp,%ebp修改修改基地址指针基地址指针 long j; subl $4,%esp 为为j分配空间分配空间 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把实参把实参j的值压栈的值压栈 call func 函数调用函数调用 addl $4,%esp 恢复栈顶指针恢复栈顶指针L1: leave 即即 m

56、ov ebp, esp; pop ebp ret 即即 pop eip(下条指令地址）下条指令地址）. . . . .ebp esp 参数参数i返址返址例例 题题 2func(i)func: long i; pushl %ebp 老的基地址指针压栈老的基地址指针压栈 movl %esp,%ebp修改修改基地址指针基地址指针 long j; subl $4,%esp 为为j分配空间分配空间 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%ea

57、x pushl %eax 把实参把实参j的值压栈的值压栈 call func 函数调用函数调用 addl $4,%esp 恢复栈顶指针恢复栈顶指针L1: leave 即即 mov ebp, esp; pop ebp ret 即即 pop eip(下条指令地址）下条指令地址）. . . . .ebp esp 参数参数i返址返址控制链控制链例例 题题 2func(i)func: long i; pushl %ebp 老的基地址指针压栈老的基地址指针压栈 movl %esp,%ebp修改修改基地址指针基地址指针 long j; subl $4,%esp 为为j分配空间分配空间 j= i -1; mo

58、vl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把实参把实参j的值压栈的值压栈 call func 函数调用函数调用 addl $4,%esp 恢复栈顶指针恢复栈顶指针L1: leave 即即 mov ebp, esp; pop ebp ret 即即 pop eip(下条指令地址）下条指令地址）. . . . .ebp esp 参数参数i返址返址控制链控制链例例 题题 2func(i)func: long i; pushl %ebp

59、 老的基地址指针压栈老的基地址指针压栈 movl %esp,%ebp修改修改基地址指针基地址指针 long j; subl $4,%esp 为为j分配空间分配空间 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %eax 把实参把实参j的值压栈的值压栈 call func 函数调用函数调用 addl $4,%esp 恢复栈顶指针恢复栈顶指针L1: leave 即即 mov ebp, esp; pop ebp ret 即即

60、 pop eip(下条指令地址）下条指令地址）. . .参数参数i返址返址控制链控制链变量变量j. . .ebp esp 栈栈低低高高例例 题题 2func(i)func: long i; pushl %ebp 老的基地址指针压栈老的基地址指针压栈 movl %esp,%ebp修改修改基地址指针基地址指针 long j; subl $4,%esp 为为j分配空间分配空间 j= i -1; movl 8(%ebp),%edx 取取i到到寄存器寄存器 func(j); decl %edx i 1 movl %edx,-4(%ebp) i 1 j movl -4(%ebp),%eax pushl %