8hh第6章运行时存储空间组织

,单击此处编辑母版标题样式,#,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,6,章,运,运,行,行时,存,存储,空,空间,组,组织,前面,讨,讨论,了,了对,源,源程,序,序进,行,行,静态,分,分析,的,编译,程,程序,的不,同,同阶,段,段,这些,分,分析,仅,仅取,决,决于,源程,序,序本,身,身,的特,性,性,与,目标,机,机,及,目标,机,机的,操,操作,系,系统,特,特性无关,。,但编,译,译程,序,序的,最,最终,目,目的,是,是把,源,源程,序,序翻,译,译成,能,能在,目标,机,机,上运,行,行的,目标,程,程序,这就,要,要求,编,编译,程,程序,不,不仅,能,能生,成,成目,标,标代,码,码,还要,在,在,生成,目,目标,代,代码之前,进行,目,目标,程,程序,运行,环,环境,的,的设,计,计,和,数据,空,空间,的,的分,配,配,。,例如,目标,程,程序,运行,时,时,源程,序,序中,各,各种,变量,、,、常,量,量,等如,何,何在,存,存储,器,器中,存放,?,如何,对,对它,们,们进,行,行,访问,?,源程,序,序中,各,各种,变,变量,、,、常,量,量的,作用,域,域,和,生存,期,期,如何,确,确定,?,递归,过,过程的数,据,据空,间,间,如何,在,在运,行,行过,程,程中,实,实现,动态,的,的分,配,配,?,这些,问,问题对于,编,编译,程,程序,是,是非常,复,复杂,又,又十,分,分重,要,要的,。,。,分配,目标,程,程序,数据,空,空间,的,的基,本,本策,略,略,:,1.,静态,分,分配,策,策略,若一,个,个程,序,序语,言,言,不允,许,许有,递,递归,过,过程,不允,许,许含,可,可变,体,体积,的,的数据,项,项,或,待定,性,性质,的,的名,字,字,则在,编,编译,时,时能,完全,确,确定,其程,序,序的,每,每个,数,数据,项,项目,的,的存,储,储空,间,间位,置,置,这种,策,策略,叫,叫,静态,分,分配,策,策略,。,例如,FORTRAN,语言,2.,栈式,动,动态,分,分配,策,策略,若程,序,序语,言,言,允许,有,有递,归,归过,程,程,和,可变,数,数组,则程,序,序,数据,空,空间,的,的分,配,配,需采用,动态策略,即在,程,程序,运,运行时进,行,行数据,空,空间,的,的分,配,配,此时,目,目标,程,程序可用,栈,作为,动,动态,的,的数,据,据空,间,间。,程序,运行,时,时,每当,进,进入,一,一个子,程,程序,其所,需,需的,数,数据,空,空间,就,就动,态,态地,分配,于,于栈,顶,顶,一旦该子,程,程序,运行,结,结束,其所,占,占用,的,的空,间,间就,释放,这种,方,方法,叫,叫,栈式,动,动态,分,分配,策,策略,。,3.,堆式,动,动态,分,分配,策,策略,若程,序,序语,言,言允,许,许用,户,户,动态,地,地申请,和,和释,放,放,存储,空,空间,并且申请,和,和释,放,放之,间,间,不一,定,定,遵守,“,先申,请,请后,释,释放,”,的原,则,则,则必,须,须让,运,运行,程,程序,拥,拥有,一,一个,大,大存,储,储区,(,堆,),申请,时,时从,堆,堆中,分,分配,一,一块,释放,时,时退,还,还给,堆,堆,这种,方,方法,叫,叫,堆式,动,动态,分,分配,策,策略,。,6.1,静态存储,分,分配,6.2,简单,的,的栈式存储,分,分配,6.3,嵌套,过,过程,语,语言,的,的栈,式,式实,现,现,6.4,堆式动态,存,存储,分,分配,6.5,参数,传,传递,补,补遗,6.1,静态,存,存储,分,分配,若,编译,时,时,能确定,程,程序,运,运行时所,需,需存,储,储空,间,间的,大,大小,则,编译时,能安排好程序运行时的,全,全部,数,数据,空,空间,并能,确,确定,每,每个,数,数据,项,项的地,址,址,这种,存,存储,分,分配,方,方法,叫,叫做,静态,分,分配,。,FORTRAN,语言,不允,许,许,有,递归,过程,每个,数,数据,名,名所,需,需存,储,储空,间,间的,大,大小,是,是常,量,量,(,即,不允,许,许,含,可变,体,体积,的数,据,据,),且所,有,有数,据,据名,的,的性,质,质是,完,完全,确,确定,的,的,(,不允,许,许,出现,动态,确定,其,其性,质,质的,数,数据,名,名,),。故,FORTRAN,程序,可,可静态分配,存,存储,空,空间,。,。,(1),数组,的,的,上下,界,界,必须,是常,数,数,;,(2),过程,调,调用,不允,许,许递,归,归,;,(3),不允,许,许,采用,动态,数据,结,结构,即程,序,序运,行,行过,程,程中,不,不允,许,许申,请,请和,释,释放,存,存储,空,空间,。,。,适于,静态存储,分,分配,的语,言,言需,满,满足,的,的条,件,件,:,满足,条,条件的语言,有,有,FORTRAN,BASIC,等。,这些语,言,言的编,译,译程序,可完全,确,确定,程序中,数据项,所,所在地,址,址,(,通常为,相,相应于,各,各数据,区,区起始,地,地址的,位,位移量,),。,由于过,程,程调用,不,不允许,递,递归,因此数,据,据项的,存,存储地,址,址与过,程,程相联,系,系。,过程调,用,用所使,用,用的局部数,据,据区,直接安,排,排在,过程的,目,目标代,码,码后,并把各,数,数据项,的,的,存储地,址,址,填入相,关,关的目标代,码,码,以便在,过,过程运,行,行时,访问,这个局,部,部数据,区,区。,采用静,态,态存储,分,分配时,不存在,对,对存储,区,区的再,利,利用问,题,题,目标程,序,序执行,时,时不必,进,进行,运行时,存,存储空,间,间管理,因此,过程进,入,入和退,出,出很简,单,单。,FORTRAN,语言的,静,静态存,储,储管理,特,特点使,FORTRAN,程序中,各,各程序,段,段可独,立,立地进,行,行编译,。,在编译,过,过程中,给程序,中,中,变量,或,数组,分配存,储,储单元,的,的一般,方,方法为,:,为每个,变量,(,或,数组,),确定一,个,个,有序整,数,数对,并把,这一对,整,整数,填入符,号,号表相,应,应登记,项,项的信,息,息栏中,。,。,其中,第一个,整,整数,指示数,据,据区的,编号,第二个,整,整数,指明该,变,变量,(,或数组,),所对应,的,的,存储起,始,始单元,相应于,其,其所在,数,数据区,起,起点的,位移,。,各数据,区,区的起,始,始地址,在,在编译,时,时暂不,确,确定,待各程,序,序段全,部,部编译完后,再由,连接装,配,配程序,最终确,定,定,并将各,程,程序段,的,的目标,代,代码组,装,装成一,个,个完整,的,的目标,程,程序。,FORTRAN,程序段,的,的,局部数,据,据区,可由图,6-1,所示的,项,项目组,成,成,:,临时变量,数组,简单变量,形式单元,寄存器保护区,隐参数,返回地址,图,6-1,一个,FORTRAN,程序段的,局部数据区,隐参数,指过程,调,调用时,的,的连接,信,信息,如返回,地,地址、,寄,寄存器,保,保护区,等,等,;,形式单,元,元,用来存,放,放过程,调,调用时,与,与形参,对,对应的,实,实参地,址,址或值,。,。,首先考,虑,虑一种,简,简单程,序,序语言,:,没有分,程,程序结,构,构,过程定,义,义,不允许,嵌,嵌套,但,允许,过程的,递归调,用,用,允许,过程,含可变,数,数组,。,C,语言除,了,了不允,许,许含可,变,变数组,外,外,就是这,样,样一种,语,语言。,6.2,简单的,栈,栈式存,储,储分配,C,语言的,程,程序结,构,构,如下,:,全局数,据,据说明,main(),main,中的数,据,据说明,void R(),R,中的数,据,据说明,void Q( ),Q,中的数,据,据说明,计算,n!,的,C,程序的,执,执行过,程,程可用,栈,实现,:,# include,“,“stdio.h,”,”,long factorial(int n), if (n1) return(n*,factorial,(n-1);,else return(1);,main (), int,num,;,doscanf(“%d”,if(num=0 & num=0);,6.2.1,栈式存,储,储分配,与,与活动,记,记录,使用栈,式,式存储,分,分配法,意,意味着,程,程序运,行,行时,每当进,入,入一个,过,过程,(,或函数,),就有一,个,个相应,的,的活动,记,记录累,筑,筑于栈,顶,顶,此记录,含,含有连,接,接数据,、,、形式,单,单元、,局,局部变,量,量、局,部,部数组,的,的内情,向,向量和,临,临时工,作,作单元,等,等。,在,执行可,执,执行语,句,句之前,把局部数,组,组所需空,间,间累筑于,栈,栈顶,从而形,成,成过程,工,工作时,的,的完整,数,数据区,。,。,注意,:,每个过,程,程的,活动记,录,录的体,积,积,在编译,时,时可以,静,静态地,确,确定。,由于允,许,许含有,可变数,组,组,故,数组的,大,大小,在,运行时,才能知,道,道。,由于可,变,变数组,的,的大小不,能,能预先,获,获知,为了扩,充,充方便,把,数组区,累筑于,活,活动记,录,录之上,的,的当前,栈,栈顶。,当一个,过,过程执,行,行完毕,返,返回时,它在栈,顶,顶的数,据,据区,(,包括,活动记,录,录,和,数组区,),随即不,复,复存在,。,。,由于,C,语言不含可,变,变数组,故,其,活动记,录,录本身包,含,含了局,部,部数组,的,的空间,。,图,6-2,和图,6-3,分别给,出,出了,C,语言,和,含可变,数,数组的,某,某简单,语,语言,程序运,行,行时的,数,数据空,间,间结构,即显示,了,了主程,序,序调用,了,了过程,Q,Q,调用了,过,过程,R,R,投入运,行,行后,的存储,结,结构。,SP,TOP,R,的活动记录,Q,的活动记录,main,的活动记录,全局数据区,图,6-2,C,语言程序,的存储组织,SP,总是指,向,向执行,过,过程活,动,动记录,的,的起点,TOP,始终指,向,向栈顶单元,。,。,当,进入,一个过,程,程时,SP,指向为,此,此过程,创,创建的,活,活动记,录,录的起,点,点,TOP,指向为,此,此过程,创,创建的,活,活动记,录,录的顶,端,端。,当,进入,一个过,程,程时,SP,指向为,此,此过程,创,创建的,活,活动记,录,录的起,点,点,TOP,指向为,此,此过程,创,创建的,活,活动记,录,录的顶,端,端,;,若含有,可变数,组,组,则分配数组区后,TOP,又改为,指,指向数,组,组区的,顶,顶端。,图,6-3,含可变,数,数组的,程,程序,的存储,组,组织,R,的数组区,R,的活动记录,Q,的数组区,Q,的活动记录,TOP,SP,main,的,数组区,main,的,活动记录,主程序全局数据区,C,的活动,记,记录含,以,以下几,个,个区段,:,连接数据,(,两项,):,老,SP,值,和,返回地址,其中,老,SP,为前一活,动,动记录的,起,起始地址,;,参数个数,;,形式单元,(,存放实参,的,的值或地,址,址,);,过程的,局部变量,(,简单变量,),、,数组的内,情,情向量,和,临时工作,单,单元,。,1,TOP,临时工作单元,内情向量,简单变量,形式单元,参数个数,返回地址,老,SP,SP,2,0,图,6-4,C,过程的活,动,动记录,C,语言,不允许函数,嵌,嵌套,即不允许,一,一个过程,的,的定义出,现,现在另一过程的定义之,内,内。因此,C,语言的非局部变,量,量仅能出现,在,在源程序,头,头,非局部变,量,量可采用,静态存储,并在编译时,确,确定它们,的,的地址。,C,语言中,过程的,每个局部,变,变量或形,参,参在活动记,录,录中的位置是确,定,定的,。因此,变量和形,参,参,运行时,在栈上的,绝对地址,:,绝对地址,=,活动记录,基,基址,(SP)+,相对地址,对于当前,正,正在执行,的,的过程,其任一,局部变量或形参,A,的引用均,可,可表示为,变,变址访问,XSP,其中,X,代表,A,相对于活,动,动记录基,址,址的,偏移量,这个偏移,量,量在编译,时,时可完全,确,确定下来,。,。,过程的,局部数组,的,的内情向,量,量,的相对地,址,址在编译,时,时同样可,完,完全确定,下,下来。当,数,数据空间,在,在过程中,获,获得分配,后,后,对数组元,素,素的引用,易,易于用变,址,址方式访问。,6.2.2,过程的执,行,行,1.,过程调用,过程调用,的,的四元式,序,序列为,:,parT,1,parT,2,parT,n,callP,n,由于此时,TOP,指向被调,过,过程,P,之前的栈,顶,顶,而,P,的,形式单元,与,活动记录,起,起点,之间的距,离,离是确定,的,的,(,等于,3),因而由,调用过程,给,被调过程,P,的,活动记录,(,正在形成,),的,形式单元传递实参值或实参地址,即每个,parT,i,(i=1,n),可直接翻,译,译成如下,指,指令,:,(i+3)TOP=T,i,/,传参数值,或,(i+3)TOP=addrT,i,/,参数地址,四元式,callP,n,翻译成,:,1TOP=SP,/,保护现行,SP,3TOP=n,/,传递参数,个,个数,JSRP,/,转向,P,过程,参数个数,n,TOP+3,SP,T,2,T,1,现行,SP,值,P,的活动记录,调用过程,TOP,4,3,2,1,0,图,6-5,调用过程,P,之前先构,造,造,P,的活动记,录,录的部分,内,内容,2.,过程进入,转入过程,P,后,首先要做,的,的是定义,新活动记,录,录的,SP,保护,返回地址,和定义,新活动记,录,录的,TOP,值,即执行下,述,述指令,:,SP,= TOP+1,/,定义新,SP,1SP,=,返,回,回,地,地,址,址,/,保,护,护,返,返,回,回,地,地,址,址,TOP,=TOP+,L,/,定,义,义,新,新,TOP,其,中,中,L,是,过,过,程,程,P,的,活,活,动,动,记,记,录,录,所,所,需,需,的,的,单,单,元,元,数,数,该,数,数,在,在,编,编,译,译,时,时,可,可,静,静,态,态,计,计,算,算,出,出,。,。,对,含,可,可,变,变,数,数,组,组,的,情,情,况,况,紧,接,接,上,上,述,述,指,指,令,令,之,之,后,后,是,是,对,对,数,数,组,组,进,进,行,行,存,存,储,储,分,分,配,配,的,的,指,指,令,令,。,。,对,数,数,组,组,进,进,行,行,存,存,储,储,分,分,配,配,的,的,指,指,令,令,是,在,在,翻,译,译,数,数,组,组,说,说,明,明,时,产,产,生,生,的,的,对,每,个,个,数,数,组,组,说,说,明,明,相,应,应,的,的,目,目,标,标,指,指,令,令,组,组,将,将,做,做,以,以,下,下,工,工,作,作,:,(1),计,算,算,各,各,维,维,的,的,上,上,下,下,限,限,;,(2),调,用,用,数,组,组,空,空,间,间,分,分,配,配,子,子,程,程,序,序,。,数,组,组,空,空,间,间,分,分,配,配,子,子,程,程,序,序计,算,算,并,并,填,填,好,好,内,内,情,情,向,向,量,量,的,的,所,所,有,有,信,信,息,息,然,后,后,在,在,TOP,所,指,指,位,位,置,置,之,之,上,上,留,出,出,数,数,组,组,所,所,需,需,空,空,间,间,并,将,将,TOP,调,整,整,为,为,指,指,向,向,数,数,组,组,区,区,顶,顶,端,端,。,。,P,的数组区,返回地址,P,的活动记录,(,长度为,L),1,调用过程,SP,TOP,0,此,后,后,在,执,执,行,行,语,语,句,句,过,过,程,程,中,中,凡,引,用,用,形,参,参,、,、,局,局,部,部,变,变,量,量,或,或,数,数,组,组,元,元,素,素,都,都,以,以,SP,为,基,基,址,址,进,进,行,行,相,相,对,对,访,访,问,问,。,。,进,入,入,过,过,程,程,P,后,所,所,做,做,工,工,作,作,如,如,下,下,图,图,:,3.,过,程,程,返,返,回,回,C,语,言,言,及,及,其,其,它,它,一,一,些,些,语,语,言,言,含,含,return(E),形,式,式,的,的,返,返,回,回,语,语,句,句,。,。,假,定,定,E,值,已,计,计,算,算,出,出,来,来,并,并,存,存,放,放,在,在,某,某,临,临,时,时,单,单,元,元,T,中,则,此,此,时,时,可,可,将,将,T,值,传,传,送,送,到,到,某,某,个,个,特,特,定,定,寄,寄,存,存,器,器,中,中,(,调,用,用,过,过,程,程,将,将,从,从,这,这,个,个,特,特,定,定,寄,寄,存,存,器,器,中,中,获,获,得,得,被,被,调,调,过,过,程,程,P,的,结,结,果,果,),。,剩,下,下,的,的,工,工,作,作,是,是,恢,复,复,SP,和,TOP,并,按,按,返,回,回,地,地,址,址,实,行,行,无,无,条,条,件,件,转,移,移,即,执,执,行,行,下,下,述,述,指,指,令,令,序,序,列,列,:,TOP,=SP,1,/,恢,复,复,调,调,用,用,过,过,程,程,的,的,TOP,值,SP,=0SP,/,恢,复,复,调,调,用,用,过,过,程,程,的,的,SP,值,X,=2TOP,/,将,返,回,回,地,地,址,址,送,X,UJ,0X,/,无,条,条,件,件,转,转,移,移,到,到,调,调,用,用,过,过,程,程,一,个,个,过,过,程,程,也,也,可,可,通,通,过,过,它,它,的,的,end,语,句,句,(C,语,言,言,为,为,),自,动,动,返,返,回,回,。,。,若,若,此,此,过,过,程,程,是,是,一,一,个,个,函,数,数,则,按,按,上,上,述,述,办,办,法,法,传,传,递,递,结,结,果,果,值,值,否,则,则,仅,仅,直,直,接,接,执,执,行,行,上,上,述,述,返,返,回,回,指,指,令,令,序,序,列,列,。,。,SP,TOP,返,回,回,地,地,址,址,老,SP,P,空,间,间,调,用,用,过,过,程,程,空,空,间,间,图,6-7,过,程,程,P,的,返,返,回,回,示,示,意,意,图,图,6.3,嵌,套,套,过,过,程,程,语,语,言,言,的,的,栈,栈,式,式,实,实,现,现,在简单程序,语,语言实现中,允许过程的,递,递归调用,且过程中,可含可变数,组,组,。现在再加,上,上一种功能,-,允许过程的,嵌,嵌套性,如,PASCAL,。,由于,PASCAL,含有文件和,动,动态变量,故它的存储,分,分配不能简,单,单地用栈式,方,方法实现。,考虑,PASCAL,的一个子集,即去掉,文件和动态,变,变量,这两种数据,类,类型,则可用下述,方,方法实现存,储,储分配,:,6.3.1,嵌套层次显,示,示表和活动,记,记录,假定主程序,的,的层数为,0,。若过程,Q,是在层数为,i,的过程,P,内定义的,且,P,是包围,Q,的最小过程,则,Q,的层数为,i+1,。,编译程序处,理,理过程说明,时,时,过程的层数,作为过程名,的,的一个重要,属,属性登记在,符,符号表中。,由于过程定,义,义是嵌套的,因而一个过,程,程可以,引用,包围它的任,一,一外层过程,所,所定义的变,量,量或数组,即,运行时,过程,Q,可引用它的,任,任一外层过,程,程,P,的最新活动,记,记录中的某,些,些数据。,因此,过程,Q,运行时必须,知,知道它的所,有,有外层的最,新,新活动记录,的,的地址。,由于允许递,归,归和可变数,组,组的存在,过程的活动,记,记录位置往,往,往是变迁的,因而必须设,法,法跟踪每个,外,外层过程的,最,最新活动记,录,录的位置。,一种常用的,跟,跟踪每个外,层,层过程最新,活,活动记录位,置,置的有效办,法,法,:,每,进入,一个过程后,在建立它的,活,活动记录区,的,的同时,建立一张嵌套层次显,示,示表,DISPLAY,。,假定现在进,入,入的过程层,数,数为,i,则它的,DISPLAY,表含有,i+1,个单元,。,DISPLAY,表本身是一,个,个栈,自顶而下依,次,次存放着现,行,行层、直接,外,外层,第,0,层的最新活,动,动记录的,起始地址,。,表,6.1,DISPLAY,表,假设过程,R,的外层为,Q, Q,的外层为主,程,程序,P,则,R,运行时的,DISPLAY,表的内容如,表,表,6.1,所示。,2,R,的现行活动记录的,起始地址,(SP,的现行值,),1,Q,的最新活动记录的,起始地址,0,P,的活动记录的,起始地址,由于过程的,层,层数可静态,确,确定,因此每个过,程,程的,DISPLAY,表的体积,在编译时即,可,可知道。为,了,了便于组织,存,存储区,把,DISPLAY,表,作为活动记,录,录的一部分,置于形式单元的,上,上端,。,由于每个过,程,程的,形式单元数,在编译时已,知,知,因此,DISPLAY,表的,相对地址,d,在编译时已,确,确知。,被调过程为,了,了建立自己,的,的,DISPLAY,必须知道它,的,的直接外层,过,过程的,DISPLAY,。,这意味着必,须,须把,直接,外,外层,的,的,DISPLAY,地址,(,称为,全,全局,DSPLAY,地址,),作为,连,连接,数,数据,之,之一,传,传给,被,被调,过,过程,。,。于,是,是,连接,数,数据,包含,老,SP,值、,返,返回,地,地址,和,全局,DISPLAY,地址,这三,项,项内,容,容。,d,k,第,k,层,SP,2,第,1,层过,程,程,SP,1,主程,序,序,SP,连接,数,数据,临时,变,变量,内情,向,向量,简单,变,变量,d,DISPLAY,表,形式,单,单元,3,参数,个,个数,2,全局,DISPLAY,地址,1,返回,地,地址,0,老,SP,TOP,SP,整个,活,活动,记,记录,的,的结,构,构如,下,下表,:,