第08章 程序运行时的存储组织及管理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,编译原理基础,1,S.P,O.P,语义分析、生成中间代码,生成目标程序,代码优化,语法分析程序,词法分析程序,错,误,处,理,符,号,表,管,理,编译程序在编译阶段要为源程序中出现的变量、常量等组织好在,运行阶段的存储空间,将这种组织形式通过生成的,目标代码,体现出来,为运行阶段实现存储,奠定基础,2,第八章 程序运行时的存储组织及管理,教学目标,要求明确静态存储分配和动态存储分配的含义,了解栈式动态存储分配和活动记录的含义及组成,了解堆式动态存储分配的分配方式和管理技术,3,8.1,程序运行时的存储组织,8.2,静态存储分配,8.3,栈式动态存储分配,8.4,堆式动态存储分配,教学内容,4,8.1,程序运行时的存储组织,运行时存储空间的划分,代码空间,数据空间,目标代码区,静态数据区,运行栈区,运行堆区,5,存储分配策略,目标代码的长度在编译时就可确定,可放在,静态区,内,;,对于在编译时已知大小的数据对象,(,如,常量,全局变量,静态变量,等等,),也可放在,静态区,内,;,为提高运行效率,应尽可能多地分配,静态数据空间,。,FORTRAN,BASIC,的分配一般可全部放在,静态区,内,.,像,PASCAL,C,这类语言的实现,由于子程序允许,递归,地调用,因此应用一,数据栈,来动态地管理内存分配,.,另外,PASCAL,和,C,还允许,动态地申请,的内存,这种数据的空间可由,堆式分配,实现,.,6,活动记录（,active record,）,执行过程时所需进行的信息管理，是通过,活动记录,实现的，,活动记录,连续存储在块中，其内容见右图。,以过程为单位的动态存储分配方案：,当一过程被调用时，就把其,活动记录,压入运行时存储栈顶，返回时弹出之。,临时变量,内情向量,形式单元,动态链,返回地址,静态链,局部变量,连接,数据区,局部,数据区,SP,TOP,7,8.2,静态存储分配,若在编译阶段就能确定源程序中各个数据实体的存储空间大小，则可以采用较简单的,静态存储管理。,采用静态存储分配的语言必须满足下列条件：,1,）,不允许过程有递归调用。,2,）,不允许有可变大小的数据项，如可变数组或可变字符串。,3,）,不允许用户动态建立数据实体。,满足上述条件的语言有,FORTRAN,、,BASIC,等。,8,8.2,静态存储分配,右下图是一个,FORTRAN,程序模块在采用静态存储分配策略时的典型数据区格局。,隐式参数,（返回地址、寄存器内容等）,形式参数,简单变量,数组,临时变量,1),隐式参数,主要用于和主调模块的通讯，在一般情况下这个参数可以是主调过程的返回地址，或在不能利用寄存器返回函数值时传回函数返回值。这些信息不会在程序中明显地出现，所以称为隐式参数。,2),形式参数,部分存放相应实在参数的地址或值。,3),程序变量部分,将作为简单变量、数组、记录以及编译程序所产生的临时变量的存储空间。,9,静态存储分配,动态存储分配,静态存储分配,在,编译阶段,由,编译程序,实现对存储空间的管理，为源程序中的变量分配存储单元。,在编译时能够确定变量在运行时的数据空间大小,运行时不改变,动态存储分配,在目标程序,运行阶段,由,目标程序,实现对存储空间的组织与管理，为源程序中的变量分配存储单元。,在目标程序运行时进行分配,编译时为运行阶段设计好存储组织形式，即为每个数据项安排好它在数据区中的相对位置,10,8.3,栈式动态存储分配,栈式分配,适用于允许递归调用的程序设计语言,;,引入一运行栈,每调用一次过程,就把该过程的相应调用记录压入栈,过程执行完毕后再将其弹出栈,;,进入时：,在栈顶为其分配一个数据区,退出时,：撤消过程数据区,动作：,1),申请,2),释放,3),嵌套调用,11,下面我们通过一段,C,程序的运行来说明运行栈的变化情况。设有,C,程序如下：,real x;,块,1,int,m1(int,ind,),块,2,int,x;,x=m2(ind+1);,int,m2(int j),块,3,int,f10;,块,4,bool,test1;,main(),块,5,int,x;,x=2;,printf(%dn,m1(x/5);,块,4,数据区,块,3,数据区,块,2,数据区,块,5,数据区,块,1,数据区,块,3,数据区,块,2,数据区,块,5,数据区,块,1,数据区,块,2,数据区,块,5,数据区,块,1,数据区,块,5,数据区,块,1,数据区,块,1,数据区,(a)(b)(c)(d)(e),12,1,、参数区,参数区保存的内容包括：,1),隐式参数,：隐式参数常包含下列几项：,返回地址,：主调程序中调用语句的下一条可执行语句的地址。,指向前一个活动记录起始位置的指针,：该基地址指针存放该模块的主调模块的活动记录的基地址，用于确保控制返回主调过程时，能使运行环境恢复到调用前的格局。,函数返回值：,有的隐式参数区包含此项，有的不包括，还有更好的处理返回值的方法。,2),显式参数,：显式参数区是形式参数的通讯区。,形式参数的传递有传值、传地址、传名等方法。有些语言如,PASCAL,语言即可传值、也可传地址。,C,语言采用的是传值的方式，这种参数传递方法，实在参数的值将赋给形式参数。,当程序运行进入一个程序块时，就要在运行栈中为此程序块添加一个活动记录。活动记录中除了存储局部变量外，还包括一个参数区和一个,display,区。图,8.3,表示了一个典型的活动记录的概貌。,参数区,局部数据,DISPLAY,13,2,、,Display,（嵌套层次显示表）区,display,区用于保存对当前正在执行的模块来说是全局的程序变量区的信息，它由一系列地址指针所组成，每一个指针指向一个程序块的活动记录的开始位置，而这个程序块对于当前正在执行的程序块来说是全局的。,参数区,局部数据,DISPLAY,P,的活动纪录的地址,Q,的最新活动纪录的地址,R,的现行活动纪录地址,2,1,0,例如，令过程,R,的外层为,Q,，,Q,的外层为,P,，则过程,R,运行时,display,表的内容应为：,14,图,8.4,给出了图,8.2(e),的运行栈中各活动记录的内容。,块,4,的活动记录如下：,DISPLAY,区：,指针,d1,和,d2,，,分别指向全局变量区的地址,Abp0,和,Abp3,。,隐式参数区：,有两个参数，第一个是返回地址，因块,4,不是一个独立的函数，是一嵌套的块程序，所以，没有返回地址，同样也没有形参，第,2,个参数,Abp3,表示在运行栈中，前一个活动记录是开始地址为,Abp3,的,m2,活动记录。,局部数据区：,f,和,test,。,abp2,os,无前记录,x,d1,abp0,x,d1,return2,abp1,ind,x,d1,return3,j,d1,d2,abp3,f,test,块,4,活动记录,abp4,m2,活动记录,abp3,m1,活动记录,abp2,main,活动记录,abp1,abp0,15,递归过程的处理,下面程序的运行结果是什么？如果把第,6,行的,(i+1)*fact(),改成,fact()*(i+1),的话，则程序的运行结果是有什么变化？试分析为什么会有这两种不同的结果。,int,fact(),static,int,i=5;,if(i=0)return 1;,else,i-;,return(,(i+1)*fact(),);,/,第,6,行,main(),printf(factor,of 5!=%dn,fact();,16,8.4,堆式动态存储分配,当程序语言允许在运行时为变量,动态申请和释放存储空间,，采用,堆式分配,是最有效的解决方案。,堆式分配的基本思想是,，为正运行的程序划出适当大的空间,(,称为,堆,Heap,),，,每当需要时可从,堆的,空闲区,中分得一块,，,用完之后再退还给堆,。,如,C,语言中的,malloc,和,free,函数。,如,C+,语言中的,new,和,delete,函数。,17,8.4.1,堆分配方式,当运行程序请求一块体积为,N,的空间时，应该如何分配呢？常采用的方法如下：,1,）,先遇到哪个大于,N,的空闲块就从中取出,N,个单元进行分配。,2,）,如果在堆中找不到大于,N,的空闲块，但所有空闲块的总和比,N,大，就需要将空闲块连接在一起，从而形成大于,N,的空闲块。,如果所有空闲块的总和都小于,N,，则需要采用更复杂的办法。如,废品回收技术,，将那些运行程序已经不使用但还没有释放的块、或运行程序目前很少使用的块回收，再重新分配。,18,8.4.2,堆式存储管理技术,u1,u2,u3,u4,u5,u6,u7,u8,u1,u3,u4,u7,u8,(a),程序运行初期：,(b),运行一段时间后：,当有新请求分配内存时，有两种,策略分配,空间：,系统继续从高地址的空闲块中进行分配，而不查看已分配给用户的内存区是否已空闲，直到分配无法进行,(,即剩余的空闲块不能满足分配的请求,),时，系统才去回收所有用户不再使用的空闲块。,用户使用一旦结束，便将所占内存区释放成空闲块。同时，每当新的用户请求分配内存时，系统需要巡视整个内存中所有空闲块，并从中找出一个“合适”的空闲块加以分配。,19,0 10000 20000 30000,(a),内存状态,起始地址,内存大小,使用情况,10000,5000,空闲,20000,3000,空闲,30000,8000,空闲,(b),可利用空间目录,0,5000,20000,0,3000,30000,0,800,#,10000,HEAD 10000 20000 30000,(c),可利用空间链表,图,8.7,堆式存储管理的可利用空间表,20,1,、定长块的管理,将总的可被利用的堆存储区划分成大小适当的一系列块。,这些块通过每块中的,LINK,域连接起来形成单向线性链表，即可利用空间表，如下图所示。,20000,0,30000,0,#,0,10000,HEAD 10000 20000 30000,21,2,、变长块的管理,变长块的管理是常用的堆式存储管理方法,。,系统在运行期间分配给用户的内存块的大小不固定，可以随请求而变。因此，“可利用空间表”中的结点，即空闲块的大小也是随意的。,结点的数据结构如下,TAG,：标记，,0,表示空闲，,1,表示占用。,SIZE,：记录结点大小，指示空闲块的存储量。,LINK,：指向下一个结点。,SPACE,：地址连续的内存空间。,TAG,SIZE,LINK,SPACE,22,变长块内存的分配,假设用户请求一个大小为,n,的存储块，而“可利用空间表”中仅有一块大小为,mn,的空闲块，则分配时只需将大小为,n,的部分分配给申请的用户，同时将剩余的,m-n,部分作为一个结点留在链表中即可。,若可利用空间表中有若干个大于,n,的空闲块时，可采用下列方法分配：,1,、首次满足法,2,、最优满足法,3,、最差满足法,23,8.4.2,堆式存储管理技术,三种分配方式各有所长,最优满足法：,产生内存碎片，保留了大内存块，以备响应后面可能发生的对大存储空间的请求。,最差满足法：,使链表中的结点空间大小趋于均匀，因此，它适用于请求分配的内存大小范围较窄的系统。,首次满足法：,分配随机，适用于事先对系统运行期间可能出现的内存分配和释放情况不能准确把握的场合。,24,8.4.2,堆式存储管理技术,从时间上对三种分配法进行比较,查询“可利用空间表”,首次满足法,最差满足法,最优满足法,分配时,需查询,需查询,回收时,需查询,需查询,25,3,、释放方法,最简单的释放方法是作为一个新的空闲块插入到无序的“可利用空间表”中。,将两个连续的块合并成一个块。需要对“可利用空间表”按块的地址顺序进行组织，同时为了要确定当前释放块的插入位置，还需要对可利用空间表进行搜索。,有的程序设计语言干脆不做释放的工作，直到内存空间用完为止。,26,小结,静态存储分配和动