编译原理第六章运行时存储空间的组织和管理.ppt
- 文档编号:18730311
- 上传时间:2023-10-21
- 格式:PPT
- 页数:110
- 大小:904KB
编译原理第六章运行时存储空间的组织和管理.ppt
《编译原理第六章运行时存储空间的组织和管理.ppt》由会员分享,可在线阅读,更多相关《编译原理第六章运行时存储空间的组织和管理.ppt(110页珍藏版)》请在冰点文库上搜索。
第六章运行时存储空间的组织和管理,术语过程的活动过程的一次执行称为过程的一次活动活动记录过程的活动需要可执行代码和存放所需信息的存储空间,后者称为活动记录本章内容讨论一个活动记录中的数据布局程序执行过程中,所有活动记录的组织方式,第六章运行时存储空间的组织和管理,影响存储分配策略的语言特征过程能否递归当控制从过程的活动返回时,局部变量的值是否要保留过程能否访问非局部变量过程调用的参数传递方式过程能否作为参数被传递过程能否作为结果值传递存储块能否在程序控制下动态地分配存储块是否必须显式地释放,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_atypedefstruct_bcharc1;charc1;longi;charc2;charc2;longi;doublef;doublef;a;b;对齐:
char:
1,long:
4,double:
8,6.1局部存储分配,例在SPARC/Solaris工作站上下面两个结构体的size分别是24和16,为什么不一样?
typedefstruct_atypedefstruct_bcharc1;0charc1;0longi;4charc2;1charc2;8longi;4doublef;16doublef;8a;b;对齐:
char:
1,long:
4,double:
8,6.1局部存储分配,例在X86/Linux机器的结果和SPARC/Solaris工作站不一样,是20和16。
typedefstruct_atypedefstruct_bcharc1;0charc1;0longi;4charc2;1charc2;8longi;4doublef;12doublef;8a;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.2全局栈式存储分配,本节介绍描述过程的目标代码怎样访问绑定到局部名字的存储单元介绍三种分配策略静态分配策略栈式分配策略堆式分配策略,6.2全局栈式存储分配,6.2.1运行时内存的划分,6.2全局栈式存储分配,1、静态分配名字在程序被编译时绑定到存储单元,不需要运行时的任何支持绑定的生存期是程序的整个运行期间,6.2全局栈式存储分配,2、静态分配给语言带来限制递归过程不被允许数据对象的长度和它在内存中位置的限制,必须是在编译时可以知道的数据结构不能动态建立,6.2全局栈式存储分配,例C程序的外部变量、静态局部变量以及程序中出现的常量都可以静态分配声明在函数外面外部变量静态分配静态外部变量静态分配声明在函数里面静态局部变量也是静态分配自动变量不能静态分配,6.2全局栈式存储分配,6.2.2活动树和运行栈1、活动树用树来描绘控制进入和离开活动的方式,6.2全局栈式存储分配,活动树的特点每个结点代表某过程的一个活动根结点代表主程序的活动结点a是结点b的父结点,当且仅当控制流从a的活动进入b的活动结点a处于结点b的左边,当且仅当a的生存期先于b的生存期,6.2全局栈式存储分配,当前活跃着的过程活动可以保存在一个栈中例控制栈的内容:
m,q(1,9),q(1,3),q(2,3),6.2全局栈式存储分配,2、运行栈:
把控制栈中的信息拓广到包括过程活动所需的所有局部信息(即活动记录),6.2全局栈式存储分配,2、运行栈:
把控制栈中的信息拓广到包括过程活动所需的所有局部信息(即活动记录),m,6.2全局栈式存储分配,2、运行栈:
把控制栈中的信息拓广到包括过程活动所需的所有局部信息(即活动记录),6.2全局栈式存储分配,2、运行栈:
把控制栈中的信息拓广到包括过程活动所需的所有局部信息(即活动记录),6.2全局栈式存储分配,2、运行栈:
把控制栈中的信息拓广到包括过程活动所需的所有局部信息(即活动记录),q(1,9),6.2全局栈式存储分配,6.2.3调用序列过程调用序列过程调用时执行的分配活动记录、把信息填入域中的代码过程返回序列过程返回时执行的恢复机器状态,释放活动记录,使调用过程能够继续执行的代码,6.2全局栈式存储分配,即使是同一种语言,过程调用序列、返回序列和活动记录中各域的排放次序,也会因实现而异设计这些序列和活动记录的原则调用者和被调用者交流的数据放在活动记录开始处,并尽可能靠近调用者的活动记录固定长度的项放在活动记录中间。
在编译时不能及时知道大小的项目放在活动记录末端,6.2全局栈式存储分配,1、过程p调用过程q的调用序列,6.2全局栈式存储分配,1、过程p调用过程q的调用序列,
(1)p计算实参,依次放入栈顶,并在栈顶留出放返回值的空间。
top_sp的值在此过程中被改变,6.2全局栈式存储分配,1、过程p调用过程q的调用序列,
(2)p把返回地址和当前base_sp的值存入q的活动记录中,建立q的访问链,增加base_sp的值,6.2全局栈式存储分配,1、过程p调用过程q的调用序列,(3)q保存寄存器的值和其它机器状态信息,6.2全局栈式存储分配,1、过程p调用过程q的调用序列,(4)q根据局部数据域和临时数据域的大小增加top_sp的值,初始化它的局部数据,并开始执行过程体,6.2全局栈式存储分配,调用者p和被调用者q之间的任务划分,6.2全局栈式存储分配,2、过程p调用过程q的返回序列,6.2全局栈式存储分配,2、过程p调用过程q的返回序列,
(1)q把返回值置入邻近p的活动记录存放返回值的地方,6.2全局栈式存储分配,2、过程p调用过程q的返回序列,
(2)q对应调用序列的步骤(4),减小top_sp的值,6.2全局栈式存储分配,2、过程p调用过程q的返回序列,(3)q恢复寄存器(包括base_sp)和机器状态,返回p,6.2全局栈式存储分配,2、过程p调用过程q的返回序列,(4)p根据参数个数与类型和返回值类型调整top_sp,然后取出返回值,6.2全局栈式存储分配,6.2.4栈上可变长数据活动记录的长度在编译时不能确定的情况例:
局部数组的大小要等到过程激活时才能确定备注:
Java语言的实现是将它们分配在堆上,6.2全局栈式存储分配,访问动态分配的数组,
(1)编译时,在活动记录中为这样的数组分别存放数组指针的单元,6.2全局栈式存储分配,访问动态分配的数组,
(2)运行时,这些指针指向分配在栈顶的存储空间,6.2全局栈式存储分配,访问动态分配的数组,(3)运行时,对数组A和B的访问都要通过相应指针来间接访问,6.2全局栈式存储分配,访问动态分配的数组,6.2全局栈式存储分配,6.2.5悬空引用悬空引用:
引用某个已被释放的存储单元,6.2全局栈式存储分配,6.2.5悬空引用悬空引用:
引用某个已被释放的存储单元main()|intdangle()|intq;|intj=20;q=dangle();|return|,*6.3非局部名字的访问,本节介绍无过程嵌套的静态作用域(C语言)有过程嵌套的静态作用域(Pascal语言)动态作用域(Lisp语言),*6.3非局部名字的访问,6.3.1无过程嵌套的静态作用域过程体中的非局部引用可以直接使用静态确定的地址局部变量在栈顶的活动记录中,可以通过base_sp指针来访问无须深入栈中取数据,无须访问链过程可以作为参数来传递,也可以作为结果来返回,*6.3非局部名字的访问,6.3.2有过程嵌套的静态作用域sortreadarrayexchangequicksortpartition,*6.3非局部名字的访问,6.3.2有过程嵌套的静态作用域过程嵌套深度sort1readarray2exchange2quicksort2partition3变量的嵌套深度:
它的声明所在过程的嵌套深度作为该名字的嵌套深度,访问链用来寻找非局部名字的存储单元,*6.3非局部名字的访问,*6.3非局部名字的访问,访问非局部名字的存储单元假定过程p的嵌套深度为np,它引用嵌套深度为na的变量a,nanp。
如何访问a的存储单元sort1readarray2exchange2quicksort2partition3,*6.3非局部名字的访问,访问非局部名字的存储单元假定过程p的嵌套深度为np,它引用嵌套深度为na的变量a,nanp。
如何访问a的存储单元从栈顶的活动记录开始,追踪访问链npna次到达a的声明所在过程的活动记录访问链的追踪用间接操作就可完成sort1readarray2exchange2quicksort2partition3,访问非局部名字的存储单元,sortreadarrayexchangequicksortpartition,*6.3非局部名字的访问,*6.3非局部名字的访问,C语言的函数声明不能嵌套,函数不论在什么情况下激活,要访问的数据分成两种情况非静态局部变量(包括形式参数),它们分配在活动记录栈顶的那个活动记录中外部变量(包括定义在其它源文件之中的外部变量)和静态的局部变量,它们都分配在静态数据区,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,ai)begintemp:
=x;x:
=y;y:
=tempend,6.4参数传递,6.4.3换名调用从概念上说,每次调用时,用实参表达式对形参进行正文替换,然后再执行procedureswap(varx,y:
integer);vartemp:
integer;例如:
调用swap(i,ai)begin替换结果:
temp:
=i;temp:
=x;i:
=ai;x:
=y;ai:
=tempy:
=tempend,6.4参数传递,6.4.3换名调用从概念上说,每次调用时,用实参表达式对形参进行正文替换,然后再执行procedureswap(varx,y:
integer);vartemp:
integer;例如:
调用swap(i,ai)begin替换结果:
temp:
=i;temp:
=x;i:
=ai;x:
=y;ai:
=tempy:
=temp交换两个数据的程序end并非总是正确,栈式存储分配策略在下列情况下不能使用:
活动结束时必须保持局部名字的值被调用者的活动比调用者的活动的生存期长。
堆式存储器的策略:
(堆管理器管理堆空间)把连续存储区域分成块,当活动记录或其他对象需要时就分配。
块的释放可以按任意次序进行,所以经过一段时间后,堆可能包含交错的正在使用的和已经释放的区域,6.5堆管理,6.5堆管理,堆式分配堆用来存放生存期不确定的数据C+和Java允许程序员用new创建对象,它们的生存期没有被约束在创建它们的过程活动的生成期之内实现内存回收是内存管理器的责任堆空间的回收有两种不同方式程序显式释放空间:
free(C)或delete(C+)垃圾收集器自动收集(Java)。
6.5堆管理,6.5.1内存管理器内存管理器把握的基本信息是堆中空闲空间分配函数回收函数内存管理器应具有下列性质空间有效性:
极小化程序需要的堆空间总量程序有效性:
较好地利用内存子系统,使得程序能运行得快一些低开销:
分配和回收操作所花时间在整个程序执行时间中的比例尽量小,6.5堆管理,6.5.2计算机内存分层,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|.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|.,例题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|.,例题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|.,例题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|.,例题2,func(i)longi;longj;j=i-1;func(j);,例题2,func(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(下条指令地址),例题2,func(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(下条指令地址),例题2,func(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(下条指令地址),例题2,func(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(下条指令地址),例题2,func(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(下条指令地址),例题2,func(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(下条指令地址),例题2,func(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(下条指令地址),例题2,func(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(下条指令地址),调用序列之一调用序列之二,例题2,func(i)func:
longi;pushl%ebp老的基地址指针压栈movl%esp,%ebp修改基地址指针longj;subl$4,%esp为j分配空间j=i-1;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编译 原理 第六 运行 存储空间 组织 管理
![提示](https://static.bingdoc.com/images/bang_tan.gif)