第13章运行时存储空间的组织.ppt

第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在运行时的具体存储地址。例：动态数组inta1.m;intb1.m1.n;,4)动态变量编译时不能确定变量i的相对位置offset(i)，也不能确定i的存储格式。即描述符需要到运行时才能确定，因此可在活动记录中为i设置两个指针，一个记录运行时描述符的地址，另一个记录运行时i的地址。例：某些语言中类型可变的变量；某些语言中维数可变的数组。,4.存储分配模式,4.1静态分配可用于静态变量的分配，变量与存储区域的绑定关系在编译时便可建立，并完成存储分配；不允许递归调用，不允许动态数组，不允许动态类型的数据对象。,4.2栈式分配用栈分配活动记录；各程序单元之间的调用遵循“后进先出”模式；活动记录的建立和撤消也满足“后进先出”模式；分配方法：当一个程序单元被激活时,在栈顶分配其活动记录；当程序单元退出时，在栈顶将其活动记录撤销。,例子：某程序中各程序单元的调用顺序为：P运行P调用QQ调用RR退出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;EcallF;FcallG;GcallF;,.,.,.,.,.,1.4CALLP的翻译,(1)Dfree:=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)恢复freefree:=current(2)恢复主调过程的currentcurrent:=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,堆空间,程序单元间通信方式是通过非局部环境和参数传递来实现的。对非局部环境的引用必须考虑变量的作用域，变量的作用域是指可访问该变量的程序范围。,第三节非局部环境,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;,endB;,y:int;,unitC;,endD;,endC;,.,unitD;,.,A,B,C,D,E,F,G,endE;,z:int;,unitF;,endG;,unitG;x,y:int;.,.,unitE;,z:=x+y;,endF;,.,endA;,x:int;,A,B,C,D,E,F,G,2.引用方法,通过“静态链”找到最近的“嵌套外层”中说明的变量。(1)静态连接和静态链静态连接：指向嵌套直接外层的最新活动记录的指针。静态链：各嵌套程序单元的活动记录中，静态连接的序列构成一个静态链。,A,E,F,G,F,例：AcallE;EcallF;FcallG;GcallF;,.,.,.,.,.,假设当前处在栈顶的是单元B的活动记录，单元B中引用了单元A中的变量x。单元A的层次为nA、单元B的层次为nB。要找到变量x的存放地址，即：DA+offset(x)关键是要找到单元A的活动记录DA。,(2)非局部变量x的地址的求法,nB-nA=0：A和B是同一层（A就是B）DA=currentnB-nA=1：A是B的直接外层（第1个外层）DADcurrent+2nB-nA=2：A是B的第2个外层DA=DDcurrent+2+2nB-nA=3：A是B的第3个外层DA=DDDcurrent+222,DA的求法,令nB-nA=d，定义函数f(d)，表示从B的活动记录出发，沿静态链搜索d步，可以到达A的活动记录。f(d)if(d=0)thenreturncurrent;elsereturnDf(d-1)+2;,(3)静态连接的建立（单元X调用单元B时）当前栈顶为X的活动记录，需要建立B的活动记录。,(3)nX-nB=1,(4)nX-nB1,(1)nX-nB=-1,X,B,callB,B,X,callB,B,callB,X,(2)nX-nB=0,B,X,callB,(1)nX-nB=-1,B的静态连接f(0)(2)nX-nB=0,B的静态连接f(1)(3)nX-nB=1,B的静态连接f(2)(4)nX-nB=d,B的静态连接f(d+1)因此，静态连接算法为：Dfree+2=f(d+1),(1)Dfree:=ip+6（保存返回地址）(2)Dfree+1:=current（设置动态链接）(3)Dfree+2:=f(d+1)（设置静态链接）(4)current:=free（建立新的current）(5)free:=free+L（调整free）(6)ip:=P（转移到P）,(4)CALLP的处理,形参和实参形参(FormalParameter)：被调用单元的参数实参(ActualParameter)：调用单元的参数参数传递的类型传值、传值得结果、传地址,第四节参数传递,参数传递实例,proceduremainbegina,b:integer;a:=1;b:=2;print(a,b);swap(a,b);print(a,b);end,procedureswap(x,y)varx,y:intger;beginprint(x,y);x:=x+y;y:=x-y;x:=x-y;print(x,y)end,(1)传值（单向传递）实参的值形参的值运行结果：1,21,22,11,2,(2)传值得结果（双向传递）实参的值形参的值形参的结果值实参的结果值运行结果：1,21,22,12,1,(3)传地址（共用同一数据单元）实参的地址形参的地址运行结果：1,21,22,12,1,注意(3)和(2)的区别，如调用swap(a,a)时的运行结果。,习题,1.对下列程序，试描述每次调用时活动记录栈的状况，直到C中调用B时。重点注意动态连接和静态连接的情况。programA;procedureB;procedureC;callB;endC;cal