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

《第6章 运行时存储空间的组织和管理编译原理中国科.pptx》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

编译原理和技术 第六章运行时存储空间的组织和管理术语过程的活动过程的一次执行称为过程的一次活动活动记录过程的活动需要可执行代码和存放所需信息的存储空间,后者称为活动记录本章内容讨论一个活动记录中的数据布局程序执行过程中，所有活动记录的组织方式 第六章运行时存储空间的组织和管理影响存储分配策略的语言特征过程能否递归当控制从过程的活动返回时，局部变量的值是否要保留过程能否访问非局部变量过程调用的参数传递方式过程能否作为参数被传递过程能否作为结果值传递存储块能否在程序控制下动态地分配存储块是否必须显式地释放 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;charc2;charc2;longi;doublef;doublef;}a;}b;对齐：char:1,long:4,double:8 6.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:8 6.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:4 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;B3a0b0b1a2,b3重叠分配存储单元 6.2全局栈式存储分配本节介绍介绍程序运行时所需的各个活动记录在存储空间的分配策略描述过程的目标代码怎样访问绑定到局部名字的存储单元介绍三种分配策略静态分配策略栈式分配策略堆式分配策略 6.2全局栈式存储分配6.2.1运行时内存的划分代码静态数据堆栈 6.2全局栈式存储分配1、静态分配名字在程序被编译时绑定到存储单元，不需要运行时的任何支持绑定的生存期是程序的整个运行期间 6.2全局栈式存储分配2、静态分配给语言带来限制递归过程不被允许数据对象的长度和它在内存中位置的限制，必须是在编译时可以知道的数据结构不能动态建立 6.2全局栈式存储分配例C程序的外部变量、静态局部变量以及程序中出现的常量都可以静态分配声明在函数外面外部变量--静态分配静态外部变量--静态分配声明在函数里面静态局部变量--也是静态分配自动变量--不能静态分配 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全局栈式存储分配活动树的特点每个结点代表某过程的一个活动根结点代表主程序的活动结点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:arraym 6.2全局栈式存储分配2、运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）mi:integerra:arraymr 6.2全局栈式存储分配2、运行栈：把控制栈中的信息拓广到包括过程活动所需的所有局部信息（即活动记录）mk:integerq(1,9)a:arraymq(1,9)r 6.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.3调用序列过程调用和过程返回都需要执行一些代码来管理活动记录栈，保存或恢复机器状态等过程调用序列过程调用时执行的分配活动记录，把信息填入它的域中，使被调用过程可以开始执行的代码过程返回序列被调用过程返回时执行的恢复机器状态，释放被调用过程活动记录，使调用过程能够继续执行的代码调用序列和返回序列常常都分成两部分，分处于调用过程和被调用过程中 6.2全局栈式存储分配即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异设计这些序列和活动记录的一些原则以活动记录中间的某个位置作为基地址长度能较早确定的域放在活动记录的中间返回值临时数据参数控制链访问链机器状态局部数据 6.2全局栈式存储分配即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异设计这些序列和活动记录的一些原则一般把临时数据域放在局部数据域的后面把参数域和可能有的返回值域放在紧靠调用者活动记录的地方返回值临时数据参数控制链访问链机器状态局部数据 6.2全局栈式存储分配即使是同一种语言，过程调用序列、返回序列和活动记录中各域的排放次序，也会因实现而异设计这些序列和活动记录的一些原则用同样的代码来执行各个活动的保存和恢复返回值临时数据参数控制链访问链机器状态局部数据 6.2全局栈式存储分配1、过程p调用过程q的调用序列返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态 6.2全局栈式存储分配1、过程p调用过程q的调用序列(1)p计算实参，依次放入栈顶，并在栈顶留出放返回值的空间。top_sp的值在此过程中被改变返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态返回值和参数top_sp 6.2全局栈式存储分配1、过程p调用过程q的调用序列(2)p把返回地址和当前base_sp的值存入q的活动记录中，建立q的访问链，增加base_sp的值返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态返回值和参数控制链和返回地址base_sptop_sp 6.2全局栈式存储分配1、过程p调用过程q的调用序列(3)q保存寄存器的值和其它机器状态信息返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态返回值和参数控制链和保存的机器状态 6.2全局栈式存储分配1、过程p调用过程q的调用序列(4)q根据局部数据域和临时数据域的大小增加top_sp的值，初始化它的局部数据，并开始执行过程体临时数据局部数据返回值和参数返回值和参数控制链和保存的机器状态top_spbase_sp临时数据局部数据控制链和保存的机器状态 6.2全局栈式存储分配调用者p和被调用者q之间的任务划分被调用者q的责任调用者p的责任调用者p的活动记录被调用者q的活动记录临时数据局部数据返回值和参数返回值和参数控制链和保存的机器状态top_spbase_sp栈增长方向临时数据局部数据控制链和保存的机器状态 6.2全局栈式存储分配2、过程p调用过程q的返回序列临时数据局部数据返回值和参数返回值和参数控制链和保存的机器状态top_spbase_sp栈增长方向临时数据局部数据控制链和保存的机器状态 6.2全局栈式存储分配2、过程p调用过程q的返回序列临时数据局部数据返回值和参数返回值和参数控制链和保存的机器状态top_spbase_sp栈增长方向临时数据局部数据控制链和保存的机器状态(1)q把返回值置入邻近p的活动记录的地方参数个数可变场合难以确定存放返回值的位置，因此通常用寄存器传递返回值 6.2全局栈式存储分配2、过程p调用过程q的返回序列(2)q对应调用序列的步骤(4)，减小top_sp的值返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态返回值和参数控制链和保存的机器状态 6.2全局栈式存储分配2、过程p调用过程q的返回序列(3)q恢复寄存器(包括base_sp)和机器状态，返回p返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态返回值和参数 6.2全局栈式存储分配2、过程p调用过程q的返回序列返回值和参数top_spbase_sp临时数据局部数据控制链和保存的机器状态(4)p根据参数个数与类型和返回值类型调整top_sp，然后取出返回值 6.2全局栈式存储分配3、过程的参数个数可变的情况临时数据局部数据参数参数控制链和保存的机器状态top_spbase_sp栈增长方向临时数据局部数据控制链和保存的机器状态(1)函数返回值改成用寄存器传递 6.2全局栈式存储分配3、过程的参数个数可变的情况临时数据局部数据参数1,…,参数n参数1,…,参数m控制链和保存的机器状态top_spbase_sp栈增长方向临时数据局部数据控制链和保存的机器状态(2)编译器产生将实参表达式逆序计算并将结果进栈的代码自上而下依次是参数1,…,参数n 6.2全局栈式存储分配3、过程的参数个数可变的情况临时数据局部数据参数1,…,参数n参数1,…,参数m控制链和保存的机器状态top_spbase_sp栈增长方向临时数据局部数据控制链和保存的机器状态(3)被调用函数能准确地知道第一个参数的位置 6.2全局栈式存储分配3、过程的参数个数可变的情况临时数据局部数据参数1,…,参数n参数1,…,参数m控制链和保存的机器状态top_spbase_sp栈增长方向临时数据局部数据控制链和保存的机器状态(4)被调用函数根据第一个参数到栈中取第二、第三个参数等等 6.2全局栈式存储分配3、过程的参数个数可变的情况临时数据局部数据参数1,…,参数n参数1,…,参数m控制链和保存的机器状态top_spbase_sp栈增长方向临时数据局部数据控制链和保存的机器状态C语言的printf函数就是按此方式，用C语言编写的下面语句的输出？printf(“%d,%d,%d ”); 6.2全局栈式存储分配6.2.4栈上可变长数据活动记录的长度在编译时不能确定的情况例：局部数组的大小要等到过程激活时才能确定备注：Java语言的实现是将它们分配在堆上 6.2全局栈式存储分配访问动态分配的数组控制链数组A的指针数组B的指针top_spbase_sp.........栈(1)编译时，在活动记录中为这样的数组分配存放数组指针的单元 6.2全局栈式存储分配访问动态分配的数组(2)运行时，这些指针指向分配在栈顶的数组存储空间控制链数组A的指针数组B的指针top_spbase_sp.........栈数组A数组B 6.2全局栈式存储分配访问动态分配的数组(3)运行时，对数组A和B的访问都要通过相应指针来间接访问控制链数组A的指针数组B的指针top_spbase_sp.........栈数组A数组B 6.2全局栈式存储分配访问动态分配的数组q的数组q的活动记录p的数组p的活动记录控制链top_spbase_sp数组A的指针数组B的指针数组A数组B控制链.........栈 6.2全局栈式存储分配6.2.5悬空引用悬空引用：引用某个已被释放的存储单元 6.2全局栈式存储分配6.2.5悬空引用悬空引用：引用某个已被释放的存储单元例：main中引用p指向的对象main(){|intdangle(){intq;|intj=20;q=dangle();|return&j;}|} 6.3非局部名字的访问本节介绍无过程嵌套的静态作用域（C语言）有过程嵌套的静态作用域（Pascal语言）动态作用域（Lisp语言） 6.3非局部名字的访问6.3.1无过程嵌套的静态作用域过程体中的非局部引用可以直接使用静态确定的地址（非局部数据此时就是全局数据）局部变量在栈顶的活动记录中，可以通过base_sp指针来访问无须深入栈中取数据，无须访问链过程可以作为参数来传递，也可以作为结果来返回 6.3非局部名字的访问6.3.2有过程嵌套的静态作用域sortreadarrayexchangequicksortpartition 6.3非局部名字的访问6.3.2有过程嵌套的静态作用域过程嵌套深度sort1readarray2exchange2quicksort2partition3变量的嵌套深度：它的声明所在过程的嵌套深度作为该名字的嵌套深度 访问链用来寻找非局部名字的存储单元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，nanp，如何访问a的存储单元sort1readarray2exchange2quicksort2partition3sa,xq(1,3)k,v访问链q(1,9)k,v访问链 6.3非局部名字的访问访问非局部名字的存储单元假定过程p的嵌套深度为np，它引用嵌套深度为na的变量a，nanp，如何访问a的存储单元从栈顶的活动记录开始，追踪访问链npna次到达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的地址由下面的二元组表示：（npna，a在活动记录中的偏移） 6.3非局部名字的访问建立访问链假定嵌套深度为np的过程p调用嵌套深度为nx的过程x(1)np 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 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访问链b 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.aretbaddm 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.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.dynamicshowsmallsmallshowshowshow 6.3非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin静态作用域r:=0.25;0.2500.250show;small;writeln;0.2500.250show;small;writelnend.dynamicshowsmallsmallshowshowshow 6.3非局部名字的访问programdynamic(input,output);varr:real;procedureshow;beginwrite(r:5:3)end;proceduresmall;varr:real;beginr:=0.125;showend;begin动态作用域r:=0.25;0.2500.125show;small;writeln;0.2500.125show;small;writelnend.dynamicshowsmallsmallshowshowshow 6.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.1值调用实参的右值传给被调用过程值调用可以如下实现把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中调用过程计算实参，并把其右值放入被调用过程形参的存储单元中 6.4参数传递6.4.2引用调用实参的左值传给被调用过程引用调用可以如下实现：把形参当作所在过程的局部名看待，形参的存储单元在该过程的活动记录中调用过程计算实参，把实参的左值放入被调用过程形参的存储单元在被调用过程的目标代码中，任何对形参的引用都是通过传给该过程的指针来间接引用实参 6.4参数传递6.4.3换名调用从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行procedureswap(varx,y:integer);vartemp:integer;begintemp:=x;x:=y;y:=tempend 6.4参数传递6.4.3换名调用从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行procedureswap(varx,y:integer);vartemp:integer;例如：调用swap(i,a[i])begintemp:=x;x:=y;y:=tempend 6.4参数传递6.4.3换名调用从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行procedureswap(varx,y:integer);vartemp:integer;例如：调用swap(i,a[i])begin替换结果：temp:=i;temp:=x;i:=a[i];x:=y;a[i]:=tempy:=tempend 6.4参数传递6.4.3换名调用从概念上说，每次调用时，用实参表达式对形参进行正文替换，然后再执行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兆字节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堆管理例：一个结构体大数组分拆成若干个数组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|.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;} 例题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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）...参数i返址控制链变量j...ebpesp栈低高 例题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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）......ebpesp 例题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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）......ebpesp参数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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）......ebpesp参数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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）......ebpesp参数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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）......ebpesp参数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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）...参数i返址控制链变量j...ebpesp栈低高 例题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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）...参数i返址控制链变量j...ebpesp栈低高调用序列之一调用序列之二 例题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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）...参数i返址控制链变量j...ebpesp栈低高返回序列之一返回序列之二 例题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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）返回序列之一返回序列之二......ebpesp参数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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）返回序列之一返回序列之二......ebpesp参数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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）返回序列之一返回序列之二......ebpesp参数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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）返回序列之一返回序列之二......ebpesp 例题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–1jmovl-4(%ebp),%eaxpushl%eax把实参j的值压栈callfunc函数调用addl$4,%esp恢复栈顶指针L1:leave即movebp,esp;popebpret即popeip(下条指令地址）返回序列之一返回序列之二......ebpesp 例题3下面的程序运行时输出3个整数。试从运行环境和printf的实现来分析，为什么此程序会有3个整数输出？main(){printf(“%d,%d,%d ”);} 例题4main(){char*cp1,*cp2;cp1="12345";cp2="abcdefghij";strcpy(cp1,cp2);printf("cp1=%s cp2=%s ",cp1,cp2);}在某些系统上的运行结果是：cp1=abcdefghijcp2=ghij为什么cp2所指的串被修改了？ 例题4因为常量串“12345”和“abcdefghij”连续分配在常数区执行前：12345abcdefghijcp1cp2 例题4因为常量串“12345”和“abcdefghij”连续分配在常数区执行前：12345abcdefghijcp1cp2执行后：abcdefghijfghijcp1cp2 例题4因为常量串“12345”和“abcdefghij”连续分配在常数区执行前：12345abcdefghijcp1cp2执行后：abcdefghijfghijcp1cp2现在的编译器大都把程序中的串常量单独存放在只读数据段中，因此运行时会报错 例题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个形式参数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当用传统的参数声明方式时，编译器不检查实参和形参的个数和类型是否一致，由程序员自己负责但对形参和实参是不同的整型，或不同的实型－编译器试图保证运行时能得到正确结果－条件是：若需数据类型转换时，不出现溢出编译器的做法－把整型或实型数据分别提升到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;i<10;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;i<10;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;i<10;i++){(*p)--;j++;}}addr(){shortk;k=0;p=&k;}低地址放高位高地址放低位shortklongi 例题7main(){func();printf("Returnfromfunc ");}func(){chars[4];strcpy(s,"12345678");printf("%s ",s);}在X86/Linux操作系统上的运行结果如下：12345678ReturnfromfuncSegmentationfault(coredumped) 例题7main(){func();printf("Returnfromfunc ");}func(){chars[4];strcpy(s,"12345678");printf("%s ",s);}......返址控制链变量sebpesp栈低高 例题7main(){func();printf("Returnfromfunc ");}func(){chars[4];strcpy(s,"123456789");printf("%s ",s);}123456789Segmentationfault(coredumped)......返址控制链变量sebpesp栈低高 例题8intfact(i)|main()inti;|{{|printf("%d ",fact(5));if(i==0)|printf("%d ",fact(5,10,15));return1;|printf("%d ",fact(5.0));else|printf("%d ",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...参数返址控制链局部变量ebpesp栈低高 例题8请解释下面问题：第四个fact调用：为什么没有提供参数时会出现Segmentationfault？解答：由于没有提供参数，而main函数又无局部变量，fact把老ebp（控制链）（main的活动记录中保存的ebp）当成参数，它一定是一个很大的整数，使得活动记录栈溢出...控制链返址控制链局部变量ebpesp栈低高