编译原理与技术 第6章 运行时存储空间的组织和管理 6学时.

Presentation on theme: "编译原理与技术 第6章 运行时存储空间的组织和管理 6学时."— Presentation transcript:

1 编译原理与技术 第6章 运行时存储空间的组织和管理 6学时

2 过程的活动需要可执行代码和存放所需信息的存储空间， 后者称为活动记录
第6章 运行时存储空间的组织和管理 内容提要 术语 过程的活动 过程的一次执行称为过程的一次活动 活动记录 过程的活动需要可执行代码和存放所需信息的存储空间， 后者称为活动记录 讨论一个活动记录中的数据布局 程序执行过程中，所有活动记录的组织方式

3 当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量 过程调用的参数传递方式 过程能否作为参数被传递
第6章 运行时存储空间的组织和管理 内容提要 影响存储分配策略的语言特征 过程能否递归 当控制从过程的活动返回时，局部变量的值是否要保留 过程能否访问非局部变量 过程调用的参数传递方式 过程能否作为参数被传递 过程能否作为结果值传递 存储块能否在程序控制下动态地分配 存储块是否必须显式地释放

4 第6章 运行时存储空间的组织和管理 6.1 局部存储分配 1学时

5 6.1 局部存储分配 6.1.1 过程 语言概念： 过程定义 过程调用 形式参数 实在参数 活动的生存期

6 一个声明起作用的程序部分称为该声明的作用域 即使一个名字在程序中只声明一次，该名字在程序运行时也 可能表示不同的数据对象
6.1 局部存储分配 6.1.2 名字的作用域和绑定 （1）名字的作用域 一个声明起作用的程序部分称为该声明的作用域 即使一个名字在程序中只声明一次，该名字在程序运行时也 可能表示不同的数据对象 （2）环境和状态 环境把名字映射到左值，而状态把左值映射到右值（即名字 到值有两步映射） 赋值改变状态；过程调用改变环境 如果环境将名字x映射到存储单元s，则说x被绑定到s 名字 存储单元 状态 值 环境

7 （3）静态概念和动态概念的对应 静 态 概 念 动 态 对 应 过程的定义 过程的活动 名字的声明 名字的绑定 声明的作用域 绑定的生存期
6.1 局部存储分配 （3）静态概念和动态概念的对应 静 态 概 念 动 态 对 应 过程的定义 过程的活动 名字的声明 名字的绑定 声明的作用域 绑定的生存期

8 6.1.3 活动记录 活动记录的常见布局 临 时 数 据 局 部 数 据 机 器 状 态 访 问 链 控 制 链 返 回 值 参 数
6.1 局部存储分配 6.1.3 活动记录 活动记录的常见布局 临 时 数 据 参 数 局 部 数 据 机 器 状 态 访 问 链 控 制 链 返 回 值

9 变量所需的存储空间可以根据其类型而静态确定 一个过程所声明的局部变量，按这些变量声明时出现的次序， 在局部数据域中依次分配空间
6.1 局部存储分配 6.1.4 局部数据的布局 字节是可编址内存的最小单位 变量所需的存储空间可以根据其类型而静态确定 一个过程所声明的局部变量，按这些变量声明时出现的次序， 在局部数据域中依次分配空间 局部数据的地址可以用相对于活动记录中某个位置的地址来 表示 数据对象的存储布局还有一个对齐问题

10 例 在SPARC/Solaris工作站上下面两个结构体的size分别是 24和16，为什么不一样？
6.1 局部存储分配 例 在SPARC/Solaris工作站上下面两个结构体的size分别是 24和16，为什么不一样？ typedef struct _a{ typedef struct _b{ char c1; char c1; long i; char c2; char c2; long i; double f; double f; }a; }b; 对齐：char : 1, long : 4, double : 8 4 8 16 1 4 8

11 例 在X86/Linux工作站上下面两个结构体的size分别是20和 16，为什么不一样？
6.1 局部存储分配 例 在X86/Linux工作站上下面两个结构体的size分别是20和 16，为什么不一样？ typedef struct _a{ typedef struct _b{ char c1; char c1; long i; char c2; char c2; long i; double f; double f; }a; }b; 对齐：char : 1, long : 4, double : 4 4 8 12 1 4 8

12 6.1.5 程序块 本身含有局部变量声明的语句 可以嵌套 最接近的嵌套作用域规则 并列程序块不会同时活跃 并列程序块的变量可以重叠分配
6.1 局部存储分配 6.1.5 程序块 本身含有局部变量声明的语句 可以嵌套 最接近的嵌套作用域规则 并列程序块不会同时活跃 并列程序块的变量可以重叠分配

13 例： main() { / begin of B0 / int a = 0; int b = 0;
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 = 2; B2 int b = 3; B3 a0 b0 b1 a2, b3 重叠分配存储单元

14 第6章 运行时存储空间的组织和管理 6.2 全局栈式存储分配 2学时

15 介绍程序运行时所需的各个活动记录在存储空间的分配策略 描述过程的目标代码怎样访问绑定到局部名字的存储单元 介绍三种分配策略
6.2 全局栈式存储分配 本节介绍 介绍程序运行时所需的各个活动记录在存储空间的分配策略 描述过程的目标代码怎样访问绑定到局部名字的存储单元 介绍三种分配策略 静态分配策略 栈式分配策略 堆式分配策略

16 6.2 全局栈式存储分配 6.2.1 运行时内存的划分 代 码 静 态 数 据 堆 栈 低地址 高地址

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

18 例 C程序的外部变量、静态局部变量以及程序中出现的常量 都可以静态分配
6.2 全局栈式存储分配 例 C程序的外部变量、静态局部变量以及程序中出现的常量 都可以静态分配 声明在函数外面 外部变量 -- 静态分配 静态外部变量 -- 静态分配 声明在函数里面 静态局部变量 -- 静态分配 自动变量 -- 不能静态分配

19 6.2 全局栈式存储分配 例题 一个C语言程序及其在X86/Linux操作系统上的编译结果如下 页。根据所生成的汇编程序来解释程序中四个变量的存储分配、 生存期、作用域和置初值方式等方面的区别 static long aa = 10; short bb = 20; func( ) { static long cc = 30; short dd = 40; }

20 6.2 全局栈式存储分配 例题 .data | .text .align 4 | .align 4 .type | .globl func .size aa, 4 | func: aa: | long 10 | movw $40, -2(%ebp) .globl bb | align 2 | .type | .size bb, 2 bb: .value 20 .align 4 .type .size cc.2, 4 cc.2: .long 30 static long aa = 10; short bb = 20; func( ) { static long cc = 30; short dd = 40; }

21 6.2.2 活动树和运行栈 （1）活动树 用树来描绘控制进入和离开活动的方式 m q(1,9) r p(1,9) q(1,3) q(1,0)
6.2 全局栈式存储分配 6.2.2 活动树和运行栈 （1）活动树 用树来描绘控制进入和离开活动的方式 m q(1,9) r p(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.1程序

22 活动树的特点 m q(1,9) r p(1,9) q(1,3) q(5,9) . . . . 6.2 全局栈式存储分配
每个结点代表某过程的一个活动 根结点代表主程序的活动 结点a是结点b的父结点，当且仅当控制流从a的活动进入b的活动 结点a处于结点b的左边，当且仅当a的生存期先于b的生存期 m q(1,9) r p(1,9) q(1,3) q(5,9)

23 当前活跃着的过程活动可以保存在一个栈中——控制栈 例 控制栈的内容：m, q (1, 9), q (1, 3), q (2, 3)
6.2 全局栈式存储分配 当前活跃着的过程活动可以保存在一个栈中——控制栈 例 控制栈的内容：m, q (1, 9), q (1, 3), q (2, 3) m q(1,9) r p(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)

24 （2）运行栈：把控制栈中的信息拓广到包括过程活动所需的 所有局部信息（即活动记录）
6.2 全局栈式存储分配 （2）运行栈：把控制栈中的信息拓广到包括过程活动所需的 所有局部信息（即活动记录） 函数调用关系树 main r 栈 int i r ( ) main

25 （2）运行栈：把控制栈中的信息拓广到包括过程活动所需的 所有局部信息（即活动记录）
6.2 全局栈式存储分配 （2）运行栈：把控制栈中的信息拓广到包括过程活动所需的 所有局部信息（即活动记录） 函数调用关系树 main r q(1,9) int i, j p (1, 9) int p; int m, n p(1,9) int i q (1, 9) int m, n 栈 main

26 （2）运行栈：把控制栈中的信息拓广到包括过程活动所需的 所有局部信息（即活动记录）
6.2 全局栈式存储分配 （2）运行栈：把控制栈中的信息拓广到包括过程活动所需的 所有局部信息（即活动记录） 函数调用关系树 int i, j p (1, 3) int p; int m, n main r q(1,9) int i q (1, 3) int m, n p(1,9) q(1,3) int i q (1, 9) int m, n p(1,3) 栈 main

27 （2）运行栈：把控制栈中的信息拓广到包括过程活动所需的 所有局部信息（即活动记录）
6.2 全局栈式存储分配 （2）运行栈：把控制栈中的信息拓广到包括过程活动所需的 所有局部信息（即活动记录） 函数调用关系树 int i q (1, 0) int m, n main r q(1,9) int i q (1, 3) int m, n p(1,9) q(1,3) int i q (1, 9) int m, n p(1,3) q(1,0) 栈 main

28 过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等
6.2 全局栈式存储分配 6.2.3 调用序列 过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等 过程调用序列 过程调用时执行的分配活动记录，把信息填入它的域中，使被调用过程可以开始执行的代码 过程返回序列 被调用过程返回时执行的恢复机器状态，释放被调用过程活动记录，使调用过程能够继续执行的代码 调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中

29 即使是同一种语言，过程调用序列、返回序列和活动记录中 各域的排放次序，也会因实现而异 设计这些序列和活动记录的一些原则：
6.2 全局栈式存储分配 即使是同一种语言，过程调用序列、返回序列和活动记录中 各域的排放次序，也会因实现而异 设计这些序列和活动记录的一些原则： 以活动记录中间的某个位置作为 基地址 长度能较早确定的域放在活动记 录的中间 一般把临时数据域放在局部数据 域的后面 把参数域和可能有的返回值域放 在紧靠调用者活动记录的地方 用同样的代码来执行各个活动的 保存和恢复 临 时 数 据 参 数 局 部 数 据 机 器 状 态 访 问 链 控 制 链 返 回 值

30 p计算实参，依次放入栈顶，并在栈顶留出放返回值的空间。top_sp的值在此过程中被改变
6.2 全局栈式存储分配 （1）过程p调用过程q的调用序列 p计算实参，依次放入栈顶，并在栈顶留出放返回值的空间。top_sp的值在此过程中被改变 p把返回地址和当前base_sp的值存入q的活动记录中，建立q的访问链，增加base_sp的值 控制链和返回地址 top_sp base_sp top_sp 返回值和参数 top_sp 临时数据局部数据 base_sp 控制链 和保存的机器状态 返回值和参数   

31 q根据局部数据域和临时数据域的大小增加top_sp的值，初始化它的局部数据，并开始执行过程体 控制链 和保存的机器状态 top_sp
6.2 全局栈式存储分配 （1）过程p调用过程q的调用序列 临时数据局部数据 top_sp q保存寄存器的值和其它机器状态信息 q根据局部数据域和临时数据域的大小增加top_sp的值，初始化它的局部数据，并开始执行过程体 控制链 和保存的机器状态 top_sp base_sp top_sp 返回值和参数 top_sp 临时数据局部数据 base_sp 控制链 和保存的机器状态 返回值和参数   

32 调用者p和被调用者q之间的任务划分 top_sp 临时数据局部数据 被调用者q的责任 base_sp 控制链 被调用者q的活动记录
6.2 全局栈式存储分配 调用者p和被调用者q之间的任务划分 临时数据局部数据 top_sp 被调用者q的责任 调用者p的责任 调用者p的 活动记录 被调用者q的活动记录 base_sp 控制链 和保存的机器状态 返回值和参数 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 返回值和参数   

33 q把返回值置入邻近p的活动记录的地方 参数个数可变场合难以确定存放返回值的位置，因此通常用寄存器传递返回值
6.2 全局栈式存储分配 （2）过程p调用过程q的返回序列 临时数据局部数据 top_sp q把返回值置入邻近p的活动记录的地方 参数个数可变场合难以确定存放返回值的位置，因此通常用寄存器传递返回值 q对应调用序列的步骤4，减小top_sp的值 控制链 和保存的机器状态 top_sp base_sp top_sp 返回值和参数 top_sp 临时数据局部数据 base_sp 控制链 和保存的机器状态 返回值和参数   

34 q恢复寄存器(包括base_sp)和机器状态，返回p
6.2 全局栈式存储分配 （2）过程p调用过程q的返回序列 q恢复寄存器(包括base_sp)和机器状态，返回p p根据参数个数与类型和返回值类型调整top_sp，然后取出返回值 控制链 和保存的机器状态 top_sp base_sp top_sp 返回值和参数 top_sp 临时数据局部数据 base_sp 控制链 和保存的机器状态 返回值和参数   

35 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 . . . 参数i 返址 控制链 变量j ebp esp 栈 低 高

36 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 esp ebp . . .

37 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 esp 参数i ebp . . .

38 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 esp 返址 参数i ebp . . .

39 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 esp 控制链 返址 参数i ebp . . .

40 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 esp ebp 控制链 返址 参数i . . .

41 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 esp 变量j ebp 控制链 返址 参数i . . .

42 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 esp 变量j ebp 控制链 返址 参数i 调用序列之一 调用序列之二 . . .

43 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 esp ebp 控制链 返址 参数i . . .

44 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 esp 返址 参数i ebp . . .

45 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 esp 参数i ebp . . .

46 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 esp ebp . . .

47 6.2 全局栈式存储分配 例题 func(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 把实参i的值压栈 call func 函数调用 addl $4,%esp 恢复栈顶指针 L1: leave 即 mov ebp, esp; pop ebp ret 即 pop eip(下条指令地址) 画出某次调用的活动记录 返回序列之一 返回序列之二 esp ebp . . .

48 编译器产生将实参表达式逆序计算并将结果进栈的代码 自上而下依次是参数1, … , 参数n
6.2 全局栈式存储分配 （3）过程的参数个数可变的情况 临时数据局部数据 top_sp 函数返回值改成用寄存器传递 编译器产生将实参表达式逆序计算并将结果进栈的代码 自上而下依次是参数1, … , 参数n 被调用函数能准确地知道第一个参数的位置 被调用函数根据第一个参数到栈中取第二、第三个参数等等 base_sp 控制链 和保存的机器状态 参数1, …, 参数n 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 返回值和参数   

49 C语言的printf函数就是按此方式，用C语言编写的
6.2 全局栈式存储分配 例题 临时数据局部数据 top_sp C语言的printf函数就是按此方式，用C语言编写的 下面语句输出的是什么？ printf("%d, %d, %d\n"); base_sp 控制链 和保存的机器状态 参数1, …, 参数n 栈 增 长 方 向 临时数据局部数据 控制链 和保存的机器状态 返回值和参数   

50 例：局部数组的大小要等到过程激活时才能确定 备注：现代编程语言的通常将它们分配在堆上
6.2 全局栈式存储分配 6.2.4 栈上可变长数据 活动记录的长度在编译时不能确定的情况 例：局部数组的大小要等到过程激活时才能确定 备注：现代编程语言的通常将它们分配在堆上 访问动态分配的数组 控制链 数组A的指针 数组B的指针 top_sp base_sp . . . 编译时，在活动记录中为这样的数组分配存放数组指针的单元 运行时，这些指针指向分配在栈顶的数组存储空间 运行时，对数组A和B的访问都要通过相应指针来间接访问 top_sp 数组A 数组B

51 main( ) { | int  dangle ( ) { int q; | int j = 20;
6.2 全局栈式存储分配 6.2.5 悬空引用 悬空引用：引用某个已被释放的存储单元 例：main中引用p指向的对象 main( ) { | int  dangle ( ) { int q; | int j = 20; q = dangle ( ); | return &j; } | }

52 第6章 运行时存储空间的组织和管理 6.3 非局部名字的访问 1.5学时

53 有过程嵌套的静态作用域（Pascal语言） 动态作用域（Lisp语言）
6.3 非局部名字的访问 本节介绍 无过程嵌套的静态作用域（C语言） 有过程嵌套的静态作用域（Pascal语言） 动态作用域（Lisp语言）

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

55 变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字 的嵌套深度
6.3 非局部名字的访问 6.3.2 有过程嵌套的静态作用域 过程的嵌套深度 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字 的嵌套深度 program sort var a,x procedure readarray var i begin …a… end; procedure exchange (i,j) procedure quicksort (m,n) var k,v function partition (y,z) var i,j begin …a…v… end; begin … end; begin … end. y,z, i,j i m,n, k,v a,x 3 2 1

56 访问链 用来寻找非局部名字的存储单元 e (1, 3) 访问链 s a, x q (1, 3) k, v q (1, 9) p (1, 3)
6.3 非局部名字的访问 访问链 用来寻找非局部名字的存储单元 e (1, 3) 访问链 s a, x q (1, 3) k, v q (1, 9) p (1, 3) i, j s a, x q (1, 3) k, v 访问链 q (1, 9) p (1, 3) i, j s a, x q (1, 3) k, v 访问链 q (1, 9) s a, x q (1, 9) k, v 访问链

57 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 访问非局部名字的存储单元
6.3 非局部名字的访问 访问非局部名字的存储单元 假定过程p的嵌套深度为np，它引用嵌套深度为na的变量a， na  np，如何访问a的存储单元？ 从栈顶的活动记录开始，追踪访问链np  na次 到达a的声明所在过程的活动记录 访问链的追踪用间接操作就可完成 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 s a, x q (1, 3) k, v 访问链 q (1, 9)

58 过程p对变量a访问时，a的地址由下面的二元组表示： （np  na，a在活动记录中的偏移）
6.3 非局部名字的访问 过程p对变量a访问时，a的地址由下面的二元组表示： （np  na，a在活动记录中的偏移） e (1, 3) 访问链 s a, x q (1, 3) k, v q (1, 9) p (1, 3) i, j sort 1 readarray 2 exchange 2 quicksort 2 partition 3 s a, x q (1, 3) k, v 访问链 q (1, 9) p (1, 3) i, j s a, x q (1, 3) k, v 访问链 q (1, 9) s a, x q (1, 9) k, v 访问链

59 假定嵌套深度为np的过程p调用嵌套深度为nx的过程x (1) nx > np 的情况
6.3 非局部名字的访问 建立访问链 假定嵌套深度为np的过程p调用嵌套深度为nx的过程x (1) nx > np 的情况 被调用过程的访问链必须指向调用过程的活动记录的访 问链 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 这时x肯定就声明在p中，且nx=np+1，由过程p建立x的活动记录

60 nx > np 访问链 e (1, 3) i, j i, j p (1, 3) p (1, 3) k, v k, v k, v 访问链
6.3 非局部名字的访问 nx > np e (1, 3) 访问链 s a, x q (1, 3) k, v q (1, 9) p (1, 3) i, j sort 1 readarray 2 exchange 2 quicksort 2 partition 3 s a, x q (1, 3) k, v 访问链 q (1, 9) p (1, 3) i, j s a, x q (1, 3) k, v 访问链 q (1, 9) s a, x q (1, 9) k, v 访问链

61 假定嵌套深度为np的过程p调用嵌套深度为nx的过程x (2) nx ≤ np 的情况
6.3 非局部名字的访问 建立访问链 假定嵌套深度为np的过程p调用嵌套深度为nx的过程x (2) nx ≤ np 的情况 追踪访问链np - nx + 1次，到达了静态包围x和p的且离 它们最近的那个过程的最新活动记录 所到达的活动记录就是x的活动记录中的访问链应该指向 的那个活动记录 sort 1 readarray 2 exchange 2 quicksort 2 partition 3 这时p和x的嵌套深度分别为1，2，…，nx 1的外围过程肯定相同

62 np  nx 访问链 e (1, 3) i, j i, j p (1, 3) p (1, 3) k, v k, v k, v 访问链
6.3 非局部名字的访问 np  nx e (1, 3) 访问链 s a, x q (1, 3) k, v q (1, 9) p (1, 3) i, j sort 1 readarray 2 exchange 2 quicksort 2 partition 3 s a, x q (1, 3) k, v 访问链 q (1, 9) p (1, 3) i, j s a, x q (1, 3) k, v 访问链 q (1, 9) s a, x q (1, 9) k, v 访问链

63 函数f作为参数传递时，怎样在f被激活时建立它的访问链？
6.3 非局部名字的访问 过程作为参数 program param(input, output); procedure b(function h(n: integer): integer); begin writeln(h(2)) end {b}; procedure c; var m: integer; function f(n: integer): integer; begin f := m+n end {f}; begin m := 0; b(f) end {c}; begin c end. 函数f作为参数传递时，怎样在f被激活时建立它的访问链？ 访 问 链 f 访 问 链 <f, > b m 从b的访问链难以建立f的访问链 f作为参数传递时，它的起始地址连同它的访问链一起传递 b调用f时，用传递过来的访问链来建立f的访问链 访 问 链 c param

64 执行addm时，a的活动记录已不存在，取不到m的值 Pascal不允许过程作为返回值
6.3 非局部名字的访问 过程作为返回值 program ret (input, output); var f: function (integer): integer; function a: function (integer): integer; var m: integer; function addm (n: integer): integer; begin return m+n end; begin m:= 0; return addm end; procedure b (g: function (integer): integer); begin writeln (g(2)) end; begin f := a; b(f) end. a ret b addm 执行addm时，a的活动记录已不存在，取不到m的值 Pascal不允许过程作为返回值

65 C语言的函数声明不能嵌套，函数不论在什么情况下激活，要访问的数据分成两种情况
6.3 非局部名字的访问 C语言的函数声明不能嵌套，函数不论在什么情况下激活，要访问的数据分成两种情况 非静态局部变量（包括形式参数），它们分配在活动记录栈顶的那个活动记录中 外部变量（包括定义在其它源文件之中的外部变量）和静态的局部变量，它们都分配在静态数据区 因此C语言允许函数（的指针）作为返回值

66 被调用过程的非局部名字a和它在调用过程中引用的是同样 的存储单元 基于运行时的调用关系 而不是基于静态作用域来确定
6.3 非局部名字的访问 6.3.3 动态作用域 被调用过程的非局部名字a和它在调用过程中引用的是同样 的存储单元 基于运行时的调用关系 而不是基于静态作用域来确定 新的绑定仅为被调用过程的局部名字建立，这些名字在被调 用过程的活动记录中占用存储单元 这一点与静态作用域没有区别

67 program dynamic(input, output); var r: real; procedure show;
6.3 非局部名字的访问 program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; begin r := 0.125; show end; begin r := 0.25; show; small; writeln; show; small; writeln end. dynamic show small 静态作用域 动态作用域

68 用控制链搜索运行栈，寻找包含该非局部名字的第一个活动记录
6.3 非局部名字的访问 实现动态作用域的方法 深访问 用控制链搜索运行栈，寻找包含该非局部名字的第一个活动记录 浅访问 为每个名字在静态分配的存储空间中保存它的当前值 当过程p的新活动出现时，p的局部名字n使用在静态数据区分配给n的存储单元。n的先前值保存在p的活动记录中，当p的活动结束时再恢复

69 program dynamic(input, output); var r: real; procedure show;
6.3 非局部名字的访问 program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; begin r := 0.125; show end; begin (绿色表示已执行部分) r := 0.25; show; small; writeln; show; small; writeln end. dynamic show small ? r 静态区 使用值的地方 栈区 暂存值的地方 dynamic

70 program dynamic(input, output); var r: real; procedure show;
6.3 非局部名字的访问 program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; begin r := 0.125; show end; begin (绿色表示已执行部分) r := 0.25; show; small; writeln; show; small; writeln end. dynamic show small 0.25 r 静态区 使用值的地方 栈区 暂存值的地方 dynamic ?

71 program dynamic(input, output); var r: real; procedure show;
6.3 非局部名字的访问 program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; begin r := 0.125; show end; begin (绿色表示已执行部分) r := 0.25; show; small; writeln; show; small; writeln end. dynamic show small 0.25 r 静态区 使用值的地方 栈区 暂存值的地方 dynamic ? show

72 program dynamic(input, output); var r: real; procedure show;
6.3 非局部名字的访问 program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; begin r := 0.125; show end; begin (绿色表示已执行部分) r := 0.25; show; small; writeln; show; small; writeln end. dynamic show small 0.25 r 静态区 使用值的地方 栈区 暂存值的地方 dynamic ? small

73 program dynamic(input, output); var r: real; procedure show;
6.3 非局部名字的访问 program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; begin r := 0.125; show end; begin (绿色表示已执行部分) r := 0.25; show; small; writeln; show; small; writeln end. dynamic show small 0.125 r 静态区 使用值的地方 栈区 暂存值的地方 dynamic ? small 0.25

74 program dynamic(input, output); var r: real; procedure show;
6.3 非局部名字的访问 program dynamic(input, output); var r: real; procedure show; begin write(r: 5: 3) end; procedure small; begin r := 0.125; show end; begin (绿色表示已执行部分) r := 0.25; show; small; writeln; show; small; writeln end. dynamic show small 0.25 r 静态区 使用值的地方 栈区 暂存值的地方 dynamic ?

75 第6章 运行时存储空间的组织和管理 6.4 参数传递 1学时

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

77 把形参当作所在过程的局部名看待，形参的存储单元在 该过程的活动记录中 调用过程计算实参，把实参的左值放入被调用过程形参 的存储单元
6.4 参数传递 6.4.2 引用调用 实参的左值传给被调用过程 引用调用可以如下实现： 把形参当作所在过程的局部名看待，形参的存储单元在 该过程的活动记录中 调用过程计算实参，把实参的左值放入被调用过程形参 的存储单元 在被调用过程的目标代码中，任何对形参的引用都是通 过传给该过程的指针来间接引用实参

78 从概念上说，每次调用时，用实参表达式对形参进行正文替 换，然后再执行
6.4 参数传递 6.4.3 换名调用 从概念上说，每次调用时，用实参表达式对形参进行正文替 换，然后再执行 例如： procedure swap(var x, y: integer); var temp: integer; begin temp := x; x := y; y := temp end 调用swap(i, a[i]) 替换结果：temp := i; i := a[i]; a[i] := temp 交换两个数据的程序并非总是正确

79 printf("cp1 = %s\ncp2 = %s\n", cp1, cp2); } 在某些系统上的运行结果是：
6.4 参数传递 例题1 main() { char *cp1, *cp2; cp1 = "12345"; cp2 = "abcdefghij"; strcpy(cp1,cp2); printf("cp1 = %s\ncp2 = %s\n", cp1, cp2); } 在某些系统上的运行结果是： cp1 = abcdefghij cp2 = ghij 为什么cp2所指的串被修改了？

80 因为常量串“12345”和“abcdefghij”连续分配在常数区 执行前：
6.4 参数传递 例题1 因为常量串“12345”和“abcdefghij”连续分配在常数区 执行前：   cp1 cp2 执行后： 现代编译器大都把程序中的串常量单独存放在只读数据段中， 因此运行时会报错 1 2 3 4 5 \0 a b c d e f g h i j a b c d e f g h i j \0

81 Address of i,j,f,e = ┄36, ┄42, ┄ 44, ┄ 54（八进制数）
6.4 参数传递 例题2 func(i,j,f,e) short i,j; float f,e; { short i1,j1; float f1,e1; printf(&i,&j,&f,&e); printf(&i1,&j1,&f1,&e1); } main() func(i,j,f,e); Address of i,j,f,e = ┄36, ┄42, ┄ 44, ┄ 54（八进制数） Address of i1,j1,f1,e1 = ┄26, ┄24, ┄20, ┄14 在SPARC/SUN工作站上， Sizes of short, int, long, float, double = 2, 4, 4, 4, 8 为什么4个形式参数i,j,f,e的地址间隔和它们类型的大小不一致

82 当用传统的参数声明方式时，编译器不检查实参和形参的个 数和类型是否一致，由程序员自己负责 但对形参和实参是不同的整型，或不同的实型
6.4 参数传递 例题2 当用传统的参数声明方式时，编译器不检查实参和形参的个 数和类型是否一致，由程序员自己负责 但对形参和实参是不同的整型，或不同的实型 编译器试图保证运行时能得到正确结果 条件是：若需数据类型转换时，不出现溢出 编译器的做法 把整型或实型数据分别提升到long和double类型的数据， 再传递到被调用函数 被调用函数根据形参所声明的类型，决定是否要将传来 的实参向低级别类型转换

83 例题2 双精度型和浮点型 长整型和短整型 低地址 低位 long float short double 高位 高地址 6.4 参数传递 大端
Big-Endian 高位 低位 大端 Big-Endian 小端 Little-Endian 高地址

84 例题2 在main函数中参数压栈时的观点 在func函数中存取形式参数时的观点 i，4个字节 2个字节，起始地址36 j，4个字节
6.4 参数传递 例题2 在main函数中参数压栈时的观点 在func函数中存取形式参数时的观点 起始地址34 i，4个字节 2个字节，起始地址36 起始地址40 j，4个字节 2个字节，起始地址42 起始地址44 4个字节，起始地址44 f，8个字节 栈的增长方向 起始地址54 4个字节，起始地址54 e，8个字节 参数在栈中的情况

85 下面程序为什么死循环（在SPARC/SUN工作站上） ？ main() { addr(); loop(); } long *p;
6.4 参数传递 例题3 下面程序为什么死循环（在SPARC/SUN工作站上） ？ main() { addr(); loop(); } long *p; loop() { long i,j;   j=0; for(i=0; i<10; i++){ (*p)--; j++; } } addr() { long k; k=0; p=&k;} main p loop i j main p addr k=0

86 将long *p改成short *p，long k 改成short k后，循环体执 行一次便停止，为什么？
6.4 参数传递 例题3 将long *p改成short *p，long k 改成short k后，循环体执 行一次便停止，为什么？ main() { addr(); loop(); } short *p; loop() { long i,j;   j=0; for(i=0;i<10;i++){ (*p)--; j++; } } addr() { short k; k=0; p=&k;} short long 高位，低地址 低位，高地址 main p loop i j

87 printf("Return from func\n"); } func() { char s[4];
6.4 参数传递 例题4 main() { func(); printf("Return from func\n"); } func() { char s[4]; strcpy(s," "); printf("%s\n",s); } 在X86/Linux操作系统上的运行结果如下： Return from func Segmentation fault (core dumped) . . . 返址 控制链 变量s ebp esp 栈

88 printf("Return from func\n"); } func() { char s[4];
6.4 参数传递 例题4 main() { func(); printf("Return from func\n"); } func() { char s[4]; strcpy(s," "); printf("%s\n",s); } 在X86/Linux操作系统上的运行结果如下： Segmentation fault (core dumped) . . . 返址 控制链 变量s ebp esp 栈

89 第四次调用为什么会出现Segmentation fault？
6.4 参数传递 例题5 int fact(i) | main() int i; | { { if(i==0) | printf("%d\n", fact(5)); return 1; | printf("%d\n", fact(5,10,15)); else | printf("%d\n", fact(5.0)); return i*fact(i-1); | printf("%d\n", fact()); } | } 该程序在X86/Linux机器上的运行结果如下： Segmentation fault (core dumped) 第二次调用为什么没有受参数过多的影响？ 第三次调用为什么结果变成1? 第四次调用为什么会出现Segmentation fault？

90 第一个问题：第二次调用为什么没有受参数过多的影响？ 参数表达式逆序计算并进栈，fact能够取到第一个参数
6.4 参数传递 例题5 第一个问题：第二次调用为什么没有受参数过多的影响？ 参数表达式逆序计算并进栈，fact能够取到第一个参数 第二个问题：第三次调用为什么结果变成1? 参数5.0转换成双精度数进栈，占8个字节。它低地址的4个 字节看成整数时正好是0 IEEE standard 754存储方式（从高位到低位） float： 1位符号位，8位指数位，然后是23位尾数 double： 1位符号位，11位指数位，然后是52位尾数 5.0： …… 最高位1不写入内存 +1023

91 第三个问题：第四次调用为什么会出现Segmentation fault？
6.4 参数传递 例题5 第三个问题：第四次调用为什么会出现Segmentation fault？ 由于没有提供参数，而main函数又无局部变量，fact把老 ebp（控制链）（main的活动记录中保存的ebp）当成参数， 它一定是一个很大的整数，使得活动记录栈溢出 . . . 控制链 返址 局部变量 ebp esp 栈

92 第6章 运行时存储空间的组织和管理 6.5 堆管理 0.5学时

93 C++和Java允许程序员用new创建对象，它们的生存期 没有被约束在创建它们的过程活动的生成期之内 实现内存回收是内存管理器的责任
6.5 堆管理 堆式分配 堆用来存放生存期不确定的数据 C++和Java允许程序员用new创建对象，它们的生存期 没有被约束在创建它们的过程活动的生成期之内 实现内存回收是内存管理器的责任 堆空间的回收有两种不同方式 程序显式释放空间：free（C）或delete（C++） 垃圾收集器自动收集（Java）。11.3节介绍垃圾收集算 法，本课程不做介绍

94 程序有效性：较好地利用内存子系统，使得程序能运行 得快一些 低开销：分配和回收操作所花时间在整个程序执行时间 中的比例尽量小
6.5 堆管理 6.5.1 内存管理器 内存管理器把握的基本信息是堆中空闲空间 分配函数 回收函数 内存管理器应具有下列性质 空间有效性：极小化程序需要的堆空间总量 程序有效性：较好地利用内存子系统，使得程序能运行 得快一些 低开销：分配和回收操作所花时间在整个程序执行时间 中的比例尽量小

95 6.5.2 计算机内存分层 虚拟内存(磁盘) 物理内存 2级缓存 1级缓存 寄存器(处理器) 典型大小 > 2千兆字节
6.5 堆管理 6.5.2 计算机内存分层 虚拟内存(磁盘) 物理内存 2级缓存 1级缓存 寄存器(处理器) 典型大小 > 2千兆字节 256兆2千兆字节 128千4兆字节 1664千字节 32字 典型访问时间 315微秒 100150纳秒 4060纳秒 510纳秒 1纳秒

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

97 大多数程序的大部分时间在执行一小部分代码，并且仅涉及 一小部分数据 时间局部性 刚被访问的内存单元在很短的时间内可能再次被访问 空间局部性
6.5 堆管理 6.5.3 程序局部性 大多数程序的大部分时间在执行一小部分代码，并且仅涉及 一小部分数据 时间局部性 刚被访问的内存单元在很短的时间内可能再次被访问 空间局部性 毗邻被访问单元的内存单元在很短的时间内可能被访问 即使知道哪些指令会被频繁执行，最快缓存的容量也可能不 足以同时容纳它们，因此必须动态调整最快缓存的内容 把最近使用的指令保存在缓存是一种较好的最优化利用内存 分层的策略 改变数据布局或计算次序也可以改进程序数据访问的时间和 空间局部性

98 struct student { | int num[10000]; int num; | char name[10000][20];
6.5 堆管理 例： 一个结构体大数组 | 分拆成若干个数组 struct student { | int num[10000]; int num; | char name[10000][20]; char name[20]; | … … … … } st[10000]; 若是顺序处理每个结构体的多个域，左边方式的数据局部性 较好 若是先顺序处理每个结构的num域，再处理每个结构的 name域，…，则右边方式的数据局部性较好 最好是按左边方式编程，由编译器决定是否需要将数据按右 边方式布局

99 程序员在程序中显式释放堆块来达到回收堆块的目的 内存泄漏：没有释放程序已经引用不到的堆块 只要内存没有用尽，它就不影响程序的正确性
6.5 堆管理 6.5.4 手工回收请求 程序员在程序中显式释放堆块来达到回收堆块的目的 内存泄漏：没有释放程序已经引用不到的堆块 只要内存没有用尽，它就不影响程序的正确性 自动无用单元收集通过回收所有无用单元来摆脱内存 泄漏 悬空引用：引用已经被释放的堆块 过分热心地释放数据对象而引起 悬空引用容易导致不会被捕获的错误

100 影响存储分配策略的语言特征，名字的作用域、活动的生存 期 各种存储分配策略，主要了解静态分配和动态栈式分配
6 运行时存储空间的组织和管理 本章要点 影响存储分配策略的语言特征，名字的作用域、活动的生存 期 各种存储分配策略，主要了解静态分配和动态栈式分配 活动记录、运行栈中各种数据域的作用、布局、管理 非局部数据访问，访问链的建立与使用 过程调用和返回的动作序列 各种参数传递方式及其实现 堆管理

101 习题 结构体的存储空间分配 6.4 6.5（两版略有差异，但原理一样） 运行控制 6.6 参数传递 6.9 6.12
6 运行时存储空间的组织和管理 习题 结构体的存储空间分配 6.4 6.5（两版略有差异，但原理一样） 运行控制 6.6 参数传递 6.9 6.12

102 6 运行时存储空间的组织和管理 习题 字符串和数组的存储空间分配 6.17 6.18 非局部数据访问 6.20