运行时存储空间的组织课件

,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第13章,运,运行,时,时存储空,间,间的组织,第一节,程,程序的存,储,储空间,1.代,码,码空间和,数,数据空间,1.1,程,程序投入,运,运行的必,要,要条件,程序要投,入,入运行，,必,必须在内,存,存中分配,一,一定的存,储,储空间，,并,并将程序,装,装入其中,，,，包括：,可运行的,代,代码（代,码,码空间）,代码运行,的,的环境（,数,数据空间,）,）,1.2,代,代码空间,（,（C）,内容：线,性,性存放着,目,目标指令,序,序列。当,前,前执行的,指,指令位置,由,由指令指,针,针ip指,示,示。,1.3,数,数据空间,（,（D）,内容：变,量,量、常数,、,、控制信,息,息、描述,符,符等。,静态分配,：,：在运行,前,前就可确,定,定数据空,间,间的大小,在编,译,译时刻就,能,能进行的,存,存储分配,。,。,动态分配,：,：运行时,才,才能进行,的,的存储分,配,配。,2.活,动,动记录,程序由程,序,序单元（,函,函数、子,程,程序）组,成,成，因此,程,程序的数,据,据空间由,相,相应程序,单,单元的数,据,据空间组,成,成。,一个程序,单,单元的数,据,据空间叫,做,做该程序,单,单元的活,动,动记录。,一个程序,单,单元在执,行,行过程中,所,所需要的,数,数据信息,、,、管理信,息,息都是通,过,过它的活,动,动记录来,存,存放的。,一个程序,单,单元的每,一,一次激活,，,，都应在,内,内存中建,立,立相应的,活,活动记录,。,。,2.1,活,活动记录,的,的内容,(1),返,返回地址,(2),动,动态连接,(3),静,静态连接,(4),现,现场保护,(5),参,参数区,(6),变量区,变量区,参数区,现场保护,静态连接,动态连接,返回地址,2.2,活,活动记录,的,的特点,除了变量,存,存储区外,，,，其余部,分,分存储长,度,度编译时,可,可以确定,，,，所以变,量,量 i,的,的地址可,用,用下式表,示,示：,D+offset(i),其中，D是活动,记,记录的首,地,地址；offset(i),是,是变量i 在活,动,动记录中,的,的位移。,2.3,变,变量的类,型,型,1)静,态,态变量,编译时可,以,以确定活,动,动记录的,首,首地址D,和,和变量的,相,相对位置offset(i)。不,管,管在程序,单,单元的哪,一,一次激活,中,中，变量,的,的存储位,置,置均为：D+offset(i)。,2)半,静,静态变量,编译时可,确,确定变量i的相对,位,位置offset(i)，,单,单元激活,时,时可确定,活,活动记录,的,的首地址D。则每,一,一次激活,，,，变量对,应,应一个不,同,同的存储,位,位置：D+offset(i)。,3)半,动,动态变量,编译时不,能,能确定变,量,量 i,的,的相对位,置,置offset(i)，但,能,能确定i 的存,储,储格式。,可在活动,记,记录中为i 建,立,立一个描,述,述符，用,于,于记录i 在内,存,存中的存,储,储格式，,并,并在描述,符,符中建立,一,一个指针,域,域，用于,记,记录 i,在,在运行,时,时的具体,存,存储地址,。,。,例：动态,数,数组 int a1.m;int b1.m1.n;,4)动,态,态变量,编译时不,能,能确定变,量,量 i,的,的相对位,置,置offset(i)，也,不,不能确定i 的,存,存储格式,。,。,即描述符,需,需要到运,行,行时才能,确,确定，因,此,此可在活,动,动记录中,为,为 i,设,设置两个,指,指针，一,个,个记录运,行,行时描述,符,符的地址,，,，另一个,记,记录运行,时,时 i,的,的地址。,例：某,些,些语言中,类,类型可变,的,的变量；,某些语言,中,中维数可,变,变的数组,。,。,4.存,储,储分配模,式,式,4.1,静,静态分配,可用于静,态,态变量的,分,分配，变,量,量与存储,区,区域的绑,定,定关系在,编,编译时便,可,可建立，,并,并完成存,储,储分配；,不允许递,归,归调用，,不,不允许动,态,态数组，,不,不允许动,态,态类型的,数,数据对象,。,。,4.2,栈,栈式分配,用栈分配,活,活动记录,；,；,各程序单,元,元之间的,调,调用遵循,“,“后进先,出,出”模式,；,；,活动记录,的,的建立和,撤,撤消也满,足,足“后进,先,先出”模,式,式；,分配方法,：,：当一个,程,程序单元,被,被激活时,在栈,顶,顶分配其,活,活动记录,；,；当程序,单,单元退出,时,时，在栈,顶,顶将其活,动,动记录撤,销,销。,例子：,某程序中,各,各程序单,元,元的调用,顺,顺序为：,P运行,P调用Q,Q调用R,R退出,Q退出,P退出,P的活动,记,记录,Q的活动,记,记录,R的活动,记,记录,.,.,.,4.3,堆,堆分配,由于动态,变,变量的首,地,地址、长,度,度、类型,等,等在编译,时,时无法确,定,定，在执,行,行过程中,也,也可能改,变,变，所以,不,不可能在,栈,栈上为这,样,样的对象,分,分配存储,区,区。对于,这,这些变量,，,，必须分,配,配在堆上,。,。,例如：C,中,中通过malloc分配的,变,变量；某,些,些语言中,的,的动态变,量,量等。,4.4,存,存储空间,的,的组织,代码,静态数据,栈,堆,第二节,栈,栈式分配,1.半,静,静态变量,的,的栈式分,配,配,1.1,特,特点,变量及活,动,动记录的,长,长度都可,静,静态确定,；,；,一个程序,单,单元可能,被,被多次激,活,活，活动,记,记录是在,程,程序单元,激,激活时动,态,态建立，,并,并与代码,段,段建立联,系,系的。,1.2,处,处理方法,(1),设,设置当前,栈,栈指针current，表,示,示当前活,动,动记录的,开,开始位置,（,（活动记,录,录首地址D）；,(2),指,指针free表示,数,数据存储,器,器下一个,可,可用单元,；,；,(3),变,变量绑定,于,于它在活,动,动记录中,的,的常数位,移,移 i，,变,变量通过current变,址,址访问；,(4)A调用B,时,时，在A,活,活动记录,的,的栈顶之,上,上建立B,的,的当前实,例,例的活动,记,记录；,(5),从,从B返回,时,时，释放,其,其活动记,录,录。,1.3,动,动态连接,和,和动态链,动态连接,：,：A调用B时，B,的,的活动记,录,录中保存,的,的A的活,动,动记录地,址,址。,动态链：,由,由动态连,接,接组成的,一,一个调用,链,链。,A,E,F,G,F,例：AcallE;E call F;FcallG;G call F;,.,.,.,.,.,1.4CALLP的,翻,翻译,(1)D free:=ip+5（,保,保存返回,地,地址）,(2)Dfree+1:=current（,保,保存current）,(3)current:=free,（,（建立新,的,的current,）,）,(4)free:=free+L,（,（调整free,）,）,(5)ip:=P（,转,转移到P,）,）,例子：过,程,程A调用,过,过程P,返回地址,动态连接,返回地址,动态连接,A的活动,记,记录,P的活动,记,记录,current,free,free,current,current,current,1.5RETURN语句,的,的翻译,(1),恢,恢复free,free:=current,(2),恢,恢复主调,过,过程的current,current:=Dcurrent+1,(3),返,返回,ip:=Dfree,返回地址,动态连接,返回地址,动态连接,A的活动,记,记录,P的活动,记,记录,free,current,过程P退,出,出，返回,过,过程A,current,free,2.半,动,动态变量,的,的栈式分,配,配,在活动记录,中,中为变量i建立描述,符,符；,在活动记录,的,的最后分配,变,变量 i,；,；,用描述中的,指,指针域指向,变,变量 i,的,的存储位置,。,。,变量区,变量 i,的,的存储区,参数区,现场保护,静态连接,动态连接,返回地址,current,free,(1)编,译,译时创建描,述,述符，并产,生,生在运行时,动,动态修改描,述,述符和创建,变,变量存储空,间,间的指令。,(2)一,个,个单元激活,后,后（进入该,单,单元），遇,到,到变量 i,的,的说明时,，,，调用上述,指,指令（填描,述,述符，分配,存,存储空间）,，,，并调整free:=free+L,。,。,3.动态,变,变量的存储,分,分配,在活动记录,中,中为变量i 分配两,个,个指针,在堆上分配,动,动态变量的,描,描述符和存,储,储空间,用活动记录,中,中的两个指,针,针指向上述,两,两个位置,变量区,返回地址,current,free,变量 i 的描述符,变量 i 的存储区,堆空间,程序单元间,通,通信方式是,通,通过非局部,环,环境和参数,传,传递来实现,的,的。,对非局部环,境,境的引用必,须,须考虑变量,的,的作用域，,变,变量的作用,域,域是指可访,问,问该变量的,程,程序范围。,第三节 非,局,局部环境,1.动态,作,作用域规则,这是一种最,近,近活动规则,，,，对非局部,变,变量，引用,的,的应是最近,的,的,“调用外层,”,”,中说明的变,量,量。,例：A-C-F的调用,序,序列，F的,直,直接调用外,层,层为C、C,的,的直接调用,外,外层为A。,2.引用,方,方法,通过,“动态链”,找到最近的,“调用外层,”,”,中说明的变,量,量。,一、动态作,用,用域规则,1.静态,作,作用域规则,这是一种最,近,近嵌套规则,，,，对非局部,变,变量，引用,的,的应是最近,的,的,“嵌套外层,”,”,中说明的变,量,量。例：,嵌,嵌套的层次,若A是B的,直,直接外层，,则,则B的层次=A的层次+1。,A(0)、B(1)、C(2)、D(3)、E(1)、F(2)、G(2),二、静态作,用,用域规则,unitA;,y:int;,unitB;,end B;,y:int;,unitC;,end D;,end C;,.,unitD;,.,A,B,C,D,E,F,G,end E;,z:int;,unitF;,end G;,unitG;,x,y:int;,.,.,unitE;,z:=x+y;,end F;,.,end A;,x:int;,A,B,C,D,E,F,G,2.引用,方,方法,通过,“静态链”,找到最近的,“嵌套外层,”,”,中说明的变,量,量。,(1)静,态,态连接和静,态,态链,静态连接：,指,指向,嵌套直接外,层,层,的,最新,活动记录的,指,指针。,静态链：各,嵌,嵌套程序单,元,元的活动记,录,录中，静态,连,连接的序列,构,构成一个静,态,态链。,A,E,F,G,F,例：A call E;E call F;F call G;G call F;,.,.,.,.,.,假设当前处,在,在栈顶的是,单,单元B的活,动,动记录，单,元,元B中引用,了,了单元A中,的,的变量x。,单,单元A的层,次,次为nA、,单,单元B的层,次,次为nB。,要,要找到变量x的存放地,址,址，即：,DA+offset(x),关键是要找,到,到单元A的,活,活动记录DA。,(2)非,局,局部变量x,的,的地址的求,法,法,nB-nA=0：A和B,是,是同一层（A就是B）,DA=current,nB-nA=1：A是B,的,的直接外层,（,（第1个外,层,层）,DA Dcurrent+2,nB-nA=2：A是B,的,的第2个外,层,层,DA=DDcurrent+2+2,nB-nA=3：A是B,的,的第3个外,层,层,DA=DDDcurrent+2 2 2,DA的求法,令nB-nA=d，定义,函,函数f(d)，表示从B的活动记,录,录出发，