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

编译原理和技术中国科学技术大学计算机科学与技术学院陈意云第六章运行时存储空间的组织和管理

术语过程的活动

过程的一次执行称为过程的一次活动活动记录 过程的活动需要可执行代码和存放所需信息的存储空间,后者称为活动记录本章内容讨论一个活动记录中的数据布局程序执行过程中，所有活动记录的组织方式

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

影响存储分配策略的语言特征

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

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

局部存储分配6.1.2名字的作用域和绑定1、名字的作用域一个声明起作用的程序部分称为该声明的作用域即使一个名字在程序中只声明一次，该名字在程序运行时也可能表示不同的数据对象6.1

局部存储分配2、环境和状态环境把名字映射到左值，而状态把左值映射到右值（即名字到值有两步映射）赋值改变状态，但不改变环境

过程调用改变环境如果环境将名字x映射到存储单元s，则说x被绑定到s名字存储单元状态值环境6.1

局部存储分配3、静态概念和动态概念的对应

静

态

概

念

动

态

对

应

过程的定义

过程的活动

6.1

局部存储分配3、静态概念和动态概念的对应

静

态

概

念

动

态

对

应

过程的定义

过程的活动

名字的声明

名字的绑定

6.1

局部存储分配3、静态概念和动态概念的对应

静

态

概

念

动

态

对

应

过程的定义

过程的活动

名字的声明

名字的绑定

声明的作用域

绑定的生存期

6.1

局部存储分配6.1.3活动记录 活动记录的常见布局返回值临时数据参数控制链访问链机器状态局部数据6.1局部存储分分配6.1.4局部数数据的布局局字节是可编编址内存的的最小单位位变量所需的的存储空间间可以根据据其类型而而静态确定定一个过程所所声明的局局部变量，，按这些变变量声明时时出现的次次序，在局局部数据域域中依次分分配空间局部数据的的地址可以以用相对于于活动记录录中某个位位置的地址址来表示数据对象的的存储布局局还有一个个对齐问题题6.1局部存储分分配例 在SPARC/Solaris工作站上下下面两个结结构体的size分别是24和16，为什么不不一样？typedefstruct_a{typedefstruct_b{charc1;charc1;longi;char c2;charc2;longi;doublef;doublef;}a;}b;对齐：char:1,long:4,double:86.1局部存储分分配例 在SPARC/Solaris工作站上下下面两个结结构体的size分别是24和16，为什么不不一样？typedefstruct_a{typedefstruct_b{charc1;0charc1;0longi;4charc2;1charc2;8longi;4doublef;16doublef;8}a;}b;对齐：char:1,long:4,double:86.1局部存储分分配例 在X86/Linux机器的结果果和SPARC/Solaris工作站不一一样，是20和16。typedefstruct_a{typedefstruct_b{charc1;0charc1;0longi;4charc2;1charc2;8longi;4doublef;12doublef;8}a;}b;对齐：char:1,long:4,double:46.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

B2

intb=0;B0

B1

intb=1;B1

B3

inta=2;B2intb=3;B3

a0b0b1a2,b3重叠分配存储单元

6.2全局局栈栈式式存存储储分分配配本节介绍绍介绍程序序运行时时所需的的各个活活动记录录在存储储空间的的分配策策略描述过程程的目标标代码怎怎样访问问绑定到到局部名名字的存存储单元元介绍三种种分配策策略静态分配配策略栈式分配配策略堆式分配配策略6.2全局栈式式存储分分配6.2.1运行时内内存的划划分代码静态数据堆栈6.2全局栈式式存储分分配1、静态分分配名字在程程序被编编译时绑绑定到存存储单元元，不需需要运行行时的任任何支持持绑定的生生存期是是程序的的整个运运行期间间6.2全局栈式式存储分分配2、静态分分配给语语言带来来限制递归过程程不被允允许数据对象象的长度度和它在在内存中中位置的的限制，，必须是是在编译译时可以以知道的的数据结构构不能动动态建立立6.2全局栈式式存储分分配例C程序的外外部变量量、静态态局部变变量以及及程序中中出现的的常量都都可以静静态分配配声明在函函数外面面外部变量量--静态分配配静态外部部变量--静态分配配声明在函函数里面面静态局部部变量--也是静态态分配自动变量量--不能静态态分配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,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的生存期期mq(1,9)rp(1,9)q(1,3)....q(5,9)....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全局栈式式存储分分配2、运行栈栈：把控制栈栈中的信信息拓广广到包括括过程活活动所需需的所有有局部信信息（即即活动记记录）6.2全局栈式式存储分分配2、运行栈栈：把控制栈栈中的信信息拓广广到包括括过程活活动所需需的所有有局部信信息（即即活动记记录）ma:arraym6.2全局栈式式存储分分配2、运行栈栈：把控制栈栈中的信信息拓广广到包括括过程活活动所需需的所有有局部信信息（即即活动记记录）mi:integerra:arraymr6.2全局栈式式存储分分配2、运行栈栈：把控制栈栈中的信信息拓广广到包括括过程活活动所需需的所有有局部信信息（即即活动记记录）mk:integerq(1,9)a:arraymq(1,9)r6.2全局栈式式存储分分配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全局栈式式存储分分配即使是同同一种语语言，过过程调用用序列、、返回序序列和活活动记录录中各域域的排放放次序，，也会因因实现而而异设计这些些序列和和活动记记录的一些原原则以活动记记录中间间的某个个位置作为为基地址址长度能较较早确定定的域放放在活动记录录的中间间返回值临时数据参数控制链访问链机器状态局部数据6.2全局栈式式存储分分配即使是同同一种语语言，过过程调用用序列、、返回序序列和活活动记录录中各域域的排放放次序，，也会因因实现而而异设计这些些序列和和活动记记录的一些原原则一般把临临时数据据域放在在局部数据据域的后后面把参数域域和可能能有的返返回值域放在在紧靠调调用者活活动记录的地地方返回值临时数据参数控制链访问链机器状态局部数据6.2全局栈式式存储分分配即使是同同一种语语言，过过程调用用序列、、返回序序列和活活动记录录中各域域的排放放次序，，也会因因实现而而异设计这些些序列和和活动记记录的一些原原则用同样的的代码来来执行各各个活动的保保存和恢恢复返回值临时数据参数控制链访问链机器状态局部数据6.2全局栈式式存储分分配1、过程p调用过程程q的调用序序列返回值和参数top_sp

base_sp

临时数据局部数据控制链和保存的机器状态

6.2全局栈式式存储分分配1、过程p调用过程程q的调用序序列(1)p计算实实参，，依次次放入入栈顶顶，并并在栈栈顶留留出放放返回回值的的空间间。top_sp的值在在此过过程中中被改改变返回值和参数top_sp

base_sp

临时数据局部数据控制链和保存的机器状态

返回值和参数top_sp

6.2全局栈栈式存存储分分配1、过程程p调用过过程q的调用用序列列(2)p把返回回地址址和当当前base_sp的值存存入q的活动动记录录中，，建立立q的访问问链，，增加加base_sp的值返回值和参数top_sp

base_sp

临时数据局部数据控制链和保存的机器状态

返回值和参数控制链和返回地址base_sp

top_sp

6.2全局栈栈式存存储分分配1、过程程p调用过过程q的调用用序列列(3)q保存存寄存存器的的值和和其它它机器器状态态信息息返回值和参数top_sp

base_sp

临时数据局部数据控制链和保存的机器状态

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

控制链和保存的机器状态top_sp

base_sp

临时数据局部数据控制链和保存的机器状态

6.2全局栈栈式存存储分分配调用者者p和被调调用者者q之间的的任务务划分分被调用者q的责任调用者p的责任调用者p的活动记录被调用者q的活动记录临时数据局部数据返回值和参数返回值和参数

控制链和保存的机器状态top_sp

base_sp

栈增长方向临时数据局部数据控制链和保存的机器状态

6.2全局栈栈式存存储分分配2、过程程p调用过过程q的返回回序列列临时数据局部数据返回值和参数返回值和参数

控制链和保存的机器状态top_sp

base_sp

栈增长方向临时数据局部数据控制链和保存的机器状态

6.2全局栈栈式存存储分分配2、过程程p调用过过程q的返回回序列列临时数据局部数据返回值和参数返回值和参数

控制链和保存的机器状态top_sp

base_sp

栈增长方向临时数据局部数据控制链和保存的机器状态

(1)q把返返回值值置入入邻近近p的的活动动记录录的地地方参数个个数可可变场场合难难以确确定存存放返返回值值的位位置，，因此此通常常用寄寄存器器传递递返回回值6.2全局栈栈式存存储分分配2、过程程p调用过过程q的返回回序列列(2)q对应调调用序序列的的步骤骤(4)，减小小top_sp的值返回值和参数top_sp

base_sp

临时数据局部数据控制链和保存的机器状态

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

base_sp

临时数据局部数据控制链和保存的机器状态

返回值和参数6.2全局栈栈式存存储分分配2、过程程p调用过过程q的返回回序列列返回值和参数top_sp

base_sp

临时数据局部数据控制链和保存的机器状态

(4)p根据参参数个个数与与类型型和返返回值值类型型调整整top_sp，然后取取出返返回值值6.2全局栈栈式存存储分分配3、过过程的的参数数个数数可变变的情情况临时数据局部数据参数参数

控制链和保存的机器状态top_sp

base_sp

栈增长方向临时数据局部数据控制链和保存的机器状态

(1)函函数返返回值值改成成用寄寄存器器传递递6.2全局栈栈式存存储分分配3、过过程的的参数数个数数可变变的情情况临时数据局部数据参数1,…,参数n参数1,…,参数m

控制链和保存的机器状态top_sp

base_sp

栈增长方向临时数据局部数据控制链和保存的机器状态

(2)编编译器器产生生将实实参表表达式式逆序序计算算并将将结果果进栈栈的代代码自上而而下依依次是是参数数1,……,参参数数n6.2全局栈栈式存存储分分配3、过过程的的参数数个数数可变变的情情况临时数据局部数据参数1,…,参数n参数1,…,参数m

控制链和保存的机器状态top_sp

base_sp

栈增长方向临时数据局部数据控制链和保存的机器状态

(3)被被调用用函数数能准准确地地知道道第一一个参参数的的位置置6.2全局栈栈式存存储分分配3、过过程的的参数数个数数可变变的情情况临时数据局部数据参数1,…,参数n参数1,…,参数m

控制链和保存的机器状态top_sp

base_sp

栈增长方向临时数据局部数据控制链和保存的机器状态

(4)被被调用用函数数根据据第一一个参参数到到栈中中取第第二、、第三三个参参数等等等6.2全局栈栈式存存储分分配3、过过程的的参数数个数数可变变的情情况临时数据局部数据参数1,…,参数n参数1,…,参数m

控制链和保存的机器状态top_sp

base_sp

栈增长方向临时数据局部数据控制链和保存的机器状态

C语言言的printf函函数就是是按此此方式式，用C语语言编编写的的下面语语句的的输出出？printf(“%d,%d,%d\n””);6.2全局栈栈式存存储分分配栈上可可变长长数据据活动记记录的的长度度在编编译时时不能能确定定的情例：局部数组的大小要等到过程激活时才能确定备注：

Java语言的实现是将它们分配在堆上6.2全局栈栈式存存储分分配访问动动态分分配的的数组组控制链数组A的指针数组B的指针top_sp

base_sp

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

base_sp

.........栈数组A数组B6.2全局栈栈式存存储分分配访问动动态分分配的的数组组(3)运运行时时，对对数组组A和和B的的访问问都要要通过过相应应指针针来间间接访访问控制链数组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全局栈栈式存存储分分配悬空引引用悬空引引用：：引用某某个已已被释释放的的存储储单元元例：main中引用用p指向的的对象象main(){|intdangle(){intq;|intj=20;q=dangle();|return&j;}|}6.3非局部部名字字的访访问本节介介绍无过程程嵌套套的静静态作作用域域（C语言））有过程程嵌套套的静静态作作用域域（Pascal语言））动态作作用域域（Lisp语言）6.3非局部名字字的访问过程体中的非局部引用可以直接使用静态确定的地址（非局部数据此时就是全局数据）局部变量在栈顶的活动记录中，可以通过base_sp指针来访问无须深入栈中取数据，无须访问链过程可以作为参数来传递，也可以作为结果来返回6.3非局部名字字的访问6.3.2有过程嵌套套的静态作作用域sortreadarrayexchangequicksortpartition6.3非局部名字字的访问6.3.2有过程嵌套套的静态作作用域过程嵌套深度sort1readarray 2exchange2quicksort 2partition 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非非局局部名名字的的访问问6.3非局部部名字字的访访问访问非非局部部名字字的存存储单单元假定过过程p的嵌套套深度度为np，它引用用嵌套套深度度为na的变量量a，nanp，如何何访问问a的存储储单元元sort1readarray2exchange2quicksort2partition3sa,xq(1,3)k,v访问链q(1,9)k,v访问链6.3非局部部名字字的访访问访问非非局部部名字字的存存储单单元假定过过程p的嵌套套深度度为np，它引用用嵌套套深度度为na的变量a，nanp，如何访问a的存储单元从栈顶的活动动记录开始，，追踪访问链链npna次到达a的声明所在过过程的活动记记录访问链的追踪踪用间接操作作就可完成sort1readarray2exchange2quicksort2partition3sa,xq(1,3)k,v访问链q(1,9)k,v访问链访问非局部名名字的存储单单元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非非局部名字的的访问6.3非局部名字的的访问过程p对变量a访问时，a的地址由下面面的二元组表表示：（npna，a在活动记录中中的偏移）6.3非局部名字的的访问建立访问链假定嵌套深度度为np的过程p调用嵌套深度度为nx的过程x(1)np<nx的情况sort1readarray2exchange2quicksort2partition3这时x肯定就声明在在p中6.3非局部名字的的访问建立访问链假定嵌套深度度为np的过程p调用嵌套深度度为nx的过程x(1)np<nx的情况被调用过程的的访问链必须须指向调用过过程的活动记记录的访问链链访问非局部名名字的存储单单元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非非局部名字的的访问6.3非局部名字的的访问建立访问链假定嵌套深度度为np的过程p调用嵌套深度度为nx的过程x(2)npnx的情况sort1readarray2exchange2quicksort2partition3这时p和x的嵌套深度分分别为1，2，…，nx1的外围过程肯肯定相同6.3非局部名字的的访问建立访问链假定嵌套深度度为np的过程p调用嵌套深度度为nx的过程x(2)npnx的情况追踪访问链npnx+1次，到达了静静态包围x和p的且离它们最最近的那个过过程的最新活活动记录所到达的活动动记录就是x的活动记录中中的访问链应应该指向的那那个活动记录录访问非局部名名字的存储单单元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非非局部名字的的访问6.3非局部名字的的访问programparam(input,output);（过程作为参数数）procedureb(functionh(n:integer):integer);beginwriteln(h(2))end{b};procedurec;varm:integer;functionf(n:integer):integer;beginf:=m+nend{f};beginm:=0;b(f)end{c};begincend.函数f作为参数数传递时时，怎样样在f6.3非局部名名字的访访问programparam(input,output);（过程作为为参数））procedureb(functionh(…beginwriteln(h(2))end;procedurec;varm:integer;functionf(n:integer)…beginf:=m+nend{f};beginm:=0;b(f)end{c};begincend.从b的访问链链难以建建立f的访问链链访问链访问链paramcmb

<f>6.3非局部名名字的访访问programparam(input,output);（过程作为为参数））procedureb(functionh(…beginwriteln(h(2))end;procedurec;varm:integer;functionf(n:integer)…beginf:=m+nend{f};beginm:=0;b(f)end{c};begincend.f作为参数数传递时时，它的的起始地地址连同同它的访访问链一一起传递递访问链访问链paramcmb

<f,>6.3非局部名名字的访访问programparam(input,output);（过程作为为参数））procedureb(functionh(…beginwriteln(h(2))end;procedurec;varm:integer;functionf(n:integer)…beginf:=m+nend{f};beginm:=0;b(f)end{c};begincend.b调用f时，用传传递过来来的访问问链来建建立f的访问链链访问链访问链paramcmb

<f,>访问链b6.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.aretbaddm6.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.aretbaddm执行addm时，a的活动记记录已不不存在，，取不到到m的值6.3非局部名名字的访访问C语言的函函数声明明不能嵌嵌套，函函数不论论在什么么情况下下激活，，要访问问的数据据分成两两种情况况非静静态态局局部部变变量量（（包包括括形形式式参参数数）），，它它们们分分配外部变量（包括定义在其它源文件之中的外部变量）和静态的局部变量，它们都分配在静态数据区因此C语言允许函数（的指针）作为返回值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.dynamicshowsmallsmallshowshowshow6.3非局局部programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin静态态作作用用域域show;small;writelnend.dynamicshowsmallsmallshowshowshow6.3非局局部部名名字字programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin动态作用域show;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;begin(绿色表示已执执行部分)r:=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;begin(绿色表示已执执行部分)r:=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;begin(绿色表示已执执行部分)r:=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;begin(绿色表示已执执行部分)r:=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;begin(绿色表示已执执行部分)r:=0.25;show;small;writeln;show;small;writelnend.dynamicshowsmallsmallshowshowshow0.25rdynamicr?静态区使用值的地方栈区暂存值的地方6.4参数数传传递递值调用用实参的的右值值传给给被调调用过过程值调用用可以以如下下实现现把形参参当作作所在在过程程的局局部名名看待待，形形参的的存储储单元元在该该过程程的活活动记记录中中调用过过程计算实实参，，并把把其右右值放放入被调用用过程程形参的的存储储单元元中6.4参数数传传递递引用调调用实参的的左值值传给给被调调用过过程引用调调用可可以如如下实实现：：把形参参当作作所在在过程程的局局部名名看待待，形形参的的存储储单元元在该该过程程的活活动记记录中中调用过过程计算算实参参，把实参参的左左值放放入被被调用用过程程形参参的存存储单单元在被调调用过过程的的目标标代码码中，，任何何对形形参的的引用用都是是通过过传给给该过过程的的指针针来间间接引引用实实参6.4参数数传传递递换名调调用从概念念上说说，每每次调调用时时，用用实参参表达达式对对形参进进行正正文替替换，，然后后再执执行procedureswap(varx,y:integer);vartemp:integer;begintemp:=x;x:=y;y:=tempend6.4参数数传传递递换名调调用从概念念上说说，每每次调调用时时，用用实参参表达达式对对形参进进行正正文替替换，，然后后再执执行procedureswap(varx,y:integer);vartemp:integer;例如：：调用swap(i,a[i])begintemp:=x;x:=y;y:=tempend6.4参数数传传递递换名调调用从概念念上说说，每每次调调用时时，用用实参参表达达式对对形参进进行正正文替替换，，然后后再执执行procedureswap(varx,y:integer);vartemp:integer;例如：：调用swap(i,a[i])begin替换结结果：：temp:=i;temp:=x;i:=a[i];x:=y;a[i]:=tempy:=tempend6.4参数数传传递递换名调调用从概念念上说说，每每次调调用时时，用用实参参表达达式对对形参进进行正正文替替换，，然后后再执执行procedureswap(varx,y:integer);vartemp:integer;例如：：调用swap(i,a[i])begin替换结结果：：temp:=i;temp:=x;i:=a[i];x:=y;a[i]:=tempy:=temp交换两两个数数据的的程序序end并非总总是正正确6.5堆管管理理堆式式分分配配堆用用来来存存放放生生存存期期不不确确定定的的数数据据C++和Java允许许程程序序员员用用new创建建对对象象，，它它们们的的生生存存期期没没有有被被约约束束在在创创建建它它们们的的过过程程活活动动的的生生成成期期之之内内实现现内内存存回回收收是是内内存存管管理理器器的的责责任任堆空空间间的的回回收收有有两两种种不不同同方方式式程序序显显式式释释放放空空间间：：free（C）或或delete（C++）垃圾圾收收集集器器自自动动收收集集（（Java）。。11.3节介介绍绍垃垃圾圾收收集集算算法法，，本本课课程程不不做做介介绍绍6.5堆管管理理6.5.1内存存管管理理器器内存存管管理理器器把把握握的的基基本本信信息息是是堆堆中中空空闲闲空空间间分配配函函数数回收收函函数数内存存管管理理器器应应具具有有下下列列性性质质空间间有有效效性性：：极极小小化化程程序序需需要要的的堆堆空空间间总总量量程序有效性性：较好地地利用内存存子系统，，使得程序序能运行得得快一些低开销：分配和回收收操作所花花时间在整整个程序执执行时间中中的比例尽尽量小6.5堆管理理6.5.2计算机内存存分层虚拟内存(磁盘)物理内存2级缓存1级缓存寄存器(处理器)典型大小>2千兆字节256兆2千兆字节128千4兆字节1664千字节32字典型访问时间315微秒100150纳秒4060纳秒510纳秒1纳秒6.5堆管理理6.5.2计算机内存存分层现代计算机机都设计成成程序员不不用关心内内存子系统统的细节就就可以写出出正确的程程序程序的效率率不仅取决决于被执行行的指令数数，还取决决于执行每每条指令需需要多长时时间执行一条指指令的时间间区别非常常可观差异源于硬硬件技术的的基本局限限：构造不不了大容量量的高速存存储器数据以块（（缓存行、、页）为单单位在相邻邻层次之间间进行传送送数据密集型型程序可从从恰当利用用内存子系系统中获益益6.5堆管理理6.5.3程序局部性性大多数程序序的大部分分时间在执执行一小部部分代码，，并且仅涉涉及一小部部分数据时间局部性性程序访问的的内存单元元在很短的的时间内可可能再次被被程序访问问空间局部性性毗邻被访问问单元的内内存单元在在很短的时时间内可能能被访问6.5堆管理理6.5.3程序局部性性即使知道哪哪些指令会会被频繁执执行，最快快的缓存也也可能没有有大到足以以把它们同同时放在其其中，因此必须须动态调整整最快缓存存的内容把最近使用用的指令保保存在缓存存是一种较较好的最优优化利用内内存分层的的策略改变数据布布局或计算算次序也可可以改进程程序数据访访问的时间间和空间局局部性6.5堆管理理例：一个个结构体大大数组分分拆成若干干个数组structstudent{intnum[10000];intnum;charname[10000][20];charname[20];…… …… …}structstudentst[10000];若是顺序处处理每个结结构体的多多个域，左左边方式的的数据局部部性较好若是先顺序序处理每个个结构的num域，再处理理每个结构构的name域，…，则右边方方式的数据据局部性较较好最好是按左左边方式编编程，由编编译器决定定是否需要要将数据按按右边方式式布局6.5堆管理理6.5.4手工回收请请求程序员在程程序中显式式释放堆块块来达到回回收堆块的的目的内存泄漏：：没有释放放程序已经经引用不到到的堆块只要内存没没有用尽，，它就不影影响程序的的正确性自动无用单单元收集通通过回收所所有无用单单元来摆脱脱内存泄漏漏悬空引用：：引用已经经被释放的的堆块过分热心地地释放数据据对象而引引起悬空引用容容易导致不不会被捕获获的错误本章要要点点影响存储分分配策略的的语言特征征各种存储分分配策略，，主要了解解静态分配配和动态栈栈式分配活动记录中各种数据域的作用和布局非局部数据访问的实现方法各种参数传递方式及其实现堆管理例题题1一个C语言程序及及其在X86/Linux操作系统上上的编译结结果如下。根根据所生成成的汇编程程序来解释释程序中四四个变量的存储分分配、生存存期、作用用域和置初初值方式等等方面的区别staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例题题1.data|.align4.align4|.type cc.2,@object.typeaa,@object|.size cc.2,4.sizeaa,4|cc.2:aa:|.long30.long10|.text.globlbb|.align4.align2|.globlfunc.typebb,@object|func:.sizebb,2| ...bb:|movw$40,-2(%ebp).value20 |...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例题题1.data| .align4.align4|.type cc.2,@object.typeaa,@object|.size cc.2,4.sizeaa,4|cc.2:aa:|.long30.long10|.text.globlbb|.align4.align2|.globlfunc.typebb,@object|func:.sizebb,2| ...bb:|movw$40,-2(%ebp).value20 |...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例题题1.data| .align4.align4|.type cc.2,@object.typeaa,@object|.size cc.2,4.sizeaa,4|cc.2:aa:|.long30.long10|.text.globlbb|.align4.align2|.globlfunc.typebb,@object|func:.sizebb,2|...bb:|movw$40,-2(%ebp).value20|...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例题题1.data|.align4.align4|.typecc.2,@object.typeaa,@object|.sizecc.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|...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例题题1.data|.align4.align4|.typecc.2,@object.typeaa,@object|.sizecc.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|...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例题题1.data|.align4.align4|.typecc.2,@object.typeaa,@object|.sizecc.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|...staticlongaa=10;shortbb=20;func(){staticlongcc=30;shortdd=40;}例题题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%edxi–1}movl%edx,-4(%ebp)i–1jmovl-4(%ebp),%eaxpushl%eax把实参参j的值压压栈callfunc函数调调用addl$4,%esp恢复栈栈顶指指针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%edxi–1}movl%edx,-4(%ebp)i–1jmovl-4(%ebp),%eaxpushl%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%edxi–1}movl%edx,-4(%ebp)i–1jmovl-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%edxi–1}movl%edx,-4(%ebp)i–1jmovl-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%edxi–1}movl%edx,-4(%ebp)i–1jmovl-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%edxi–1}movl%edx,-4(%ebp)i–1jmovl-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%edxi–1}movl%edx,-4(%ebp)i–